# How to find a derivative? How to find a derivative? Gordon Li The Problem

is trivial to compute for smooth continuous functions Real data is always discrete (and noisy!) The Problem Q: Given some empirical data can we find a method to approximate ?

A: Not really numerical differentiation is non-trivial! Why is Numerical Differentiation needed? We may want to find rates of change for the unknown function Needed to numerically solve many nonlinear differential equations

Used to compute Taylor polynomial approximations for Because my supervisor told me to do it Forward/Backward Difference Method We approximate using the gradient of the secant between each pair of adjacent points.

Forward: Backward: Forward/Backward Difference Method We can estimate the error using Taylors Theorem:

The error is and the time complexity is . Attempt #1 +() Rounding Error

We assume that creates a rounding error of the form: The total error is . Floating-point Representation Both types of error are fundamentally due to the floating-point representation of real numbers by computers.

Floating-point Representation Numerical differentiation is ill-conditioned, so floating-point error gets compounded with each use cannot be chosen too small, otherwise it will get rounded to zero and produce is probably inconsistent (changes for different )

It is still the best system we have Central Difference Method We can improve on the forward/backward difference method by using triplets instead of pairs. The idea is that all the even terms will cancel in the Taylor expansion.

Central Difference Method We can estimate the error using Taylors Theorem: The error is and the time complexity is . Attempt #2

() Richardson Extrapolation The idea is to compute for 2 different values of , and combine the results in some appropriate manner, as guided by our knowledge of the error behaviour.

The error is and the time complexity is . Attempt #3 ( ) ( )

Polynomial Interpolation We can look at the data globally instead of locally to try and minimise the noise by fitting a polynomial of degree . Polynomial Interpolation

We can approximate by differentiating the polynomial The error is and the time complexity is . Attempt #4 ()

Why is Numerical Differentiation difficult? We can show that numerical differentiation is fundamentally difficult using Fourier analysis. Write in terms of the inverse Fourier Transform of :

differentiation is equivalent to multiplication in the frequency domain. Why is Numerical Differentiation difficult? Noise is caused by high frequency Fourier components These high frequency components get amplified by the multiplication in the frequency domain, hence creating large errors

The same logic can be used to show that integration is equivalent to division in the frequency domain, hence minimising the error and making numerical integration a trivial task Spectral Methods The idea is to use Fourier analysis to filter out the noise, but lose some accuracy in the process.

1. Compute the discrete Fourier transform (DFT) of using the FFT algorithm 2. Filter out the high frequency components (but not too much) 3. Perform the multiplication in the frequency domain 4. Compute the inverse DFT using the FFT algorithm. The error depends on the filter and the time complexity is .

Attempt #5 Summary Method

Error Forward/Backward Difference Central Difference Richardson Extrapolation Polynomial Interpolation FFT

Depends on how you filter Time Complexity