Week 3 - Numerical Differentiation#

Numerical Differentiation#

Estimate derivatives at $x_0$ using function values at nearby points.

$f'(x_0),\quad f''(x_0),\quad \ldots$

Function values may come from:

Tabulated data
An explicit but difficult function
A black-box model or simulation

When to use#

Numerical differentiation	Analytical differentiation
Complicated expression, black box or data only	Derivative is easily found

Notation#

For equally spaced points:

$x_i=x_0+ih$

$f_i=f(x_i)$

where $h$ is the step size.

Deriving Difference Formulas#

Interpolating polynomials	Taylor series
Fit a polynomial or spline near $x_0$ , then differentiate	Expand about $x_0$ and rearrange
Also works for uneven spacing, but formulas change	Directly shows the truncation-error order

Interpolating Polynomials#

Approximate the function with an interpolating polynomial $p(x)$ :

$f'(x_0)\approx p'(x_0)$

Linear interpolation gives a forward difference
Quadratic interpolation gives a central difference

Taylor Series#

Expand to the right and left of $x_0$ :

$f(x_0\pm h) = f_0 \pm hf'_0 +\frac{h^2}{2}f''_0 \pm\frac{h^3}{6}f'''_0 +\frac{h^4}{24}f^{(4)}_0 +\cdots$

Numerical differentiation is unstable because it amplifies small errors.

For noisy data:

Fit an approximating, not interpolating, curve
Differentiate the fitted curve

Finite Difference Formulas#

First Derivative#

Method	Formula	Error
Forward	$\displaystyle f'(x_0)=\frac{f_1-f_0}{h}+O(h)$	$O(h)$
Backward	$\displaystyle f'(x_0)=\frac{f_0-f_{-1}}{h}+O(h)$	$O(h)$
Central	$\displaystyle f'(x_0)=\frac{f_1-f_{-1}}{2h}+O(h^2)$	$O(h^2)$
3-point forward	$\displaystyle f'(x_0)=\frac{-f_2+4f_1-3f_0}{2h}+O(h^2)$	$O(h^2)$
5-point central	$\displaystyle f'(x_0)=\frac{-f_2+8f_1-8f_{-1}+f_{-2}}{12h}+O(h^4)$	$O(h^4)$

Second Derivative#

Method	Formula	Error
Forward	$\displaystyle f''(x_0)=\frac{f_2-2f_1+f_0}{h^2}+O(h)$	$O(h)$
Central	$\displaystyle f''(x_0)=\frac{f_1-2f_0+f_{-1}}{h^2}+O(h^2)$	$O(h^2)$
4-point forward	$\displaystyle f''(x_0)=\frac{-f_3+4f_2-5f_1+2f_0}{h^2}+O(h^2)$	$O(h^2)$
5-point central	$\displaystyle f''(x_0)=\frac{-f_2+16f_1-30f_0+16f_{-1}-f_{-2}}{12h^2}+O(h^4)$	$O(h^4)$

Higher Derivatives#

Third Derivative#

Method	Formula	Error
Forward	$\displaystyle f'''(x_0)=\frac{f_3-3f_2+3f_1-f_0}{h^3}+O(h)$	$O(h)$
Central	$\displaystyle f'''(x_0)=\frac{f_2-2f_1+2f_{-1}-f_{-2}}{2h^3}+O(h^2)$	$O(h^2)$

Fourth Derivative#

Method	Formula	Error
Forward	$\displaystyle f^{(4)}(x_0)=\frac{f_4-4f_3+6f_2-4f_1+f_0}{h^4}+O(h)$	$O(h)$
Central	$\displaystyle f^{(4)}(x_0)=\frac{f_2-4f_1+6f_0-4f_{-1}+f_{-2}}{h^4}+O(h^2)$	$O(h^2)$

Accuracy and Error#

Derivative of

$\ln x$ at

$x_0=2$

Given:

$f(x)=\ln x$

The true derivative is:

$f'(2)=\frac{1}{2}=0.5$

For $h=1$ :

$f'_{\text{forward}}(2) = \frac{\ln 3-\ln 2}{1} = 0.405465$

$f'_{\text{central}}(2) = \frac{\ln 3-\ln 1}{2} = 0.549306$

$h$	Forward estimate	Forward error	Central estimate	Central error
$1$	$0.405465$	$0.094535$	$0.549306$	$0.049306$
$0.1$	$0.487902$	$0.012098$	$0.500417$	$4.1729\times10^{-4}$
$0.01$	$0.498754$	$1.245\times10^{-3}$	$0.500004$	$4.1667\times10^{-6}$
$0.001$	$0.499875$	$1.2496\times10^{-4}$	$0.500000$	$4.1666\times10^{-8}$

For this example:

Forward difference approaches from below
Central difference approaches from above

Order of Accuracy#

A formula with error $O(h^p)$ is accurate to order $p$ .

Accuracy	Halving $h$ approximately changes error by
First order	$\frac{1}{2}$
Second order	$\frac{1}{4}$
Fourth order	$\frac{1}{16}$

Equivalently:

$O(h)$ error decreases by about $10$ when $h$ decreases by $10$
$O(h^2)$ error decreases by about $100$ when $h$ decreases by $10$

One-sided vs Central#

One-sided differences	Central differences
Use points on only one side of $x_0$	Use points on both sides of $x_0$
Required near boundaries	Usually provide higher-order estimates
Sometimes required in PDE methods	Behave better near the interval midpoint

Truncation and Round-off Error#

Reducing $h$ causes a trade-off:

Truncation error	Round-off error
Decreases with $h$	Increases as values are divided by smaller $h$

For the forward first derivative:

$\left| f'(x_0) - \frac{\bar f_1-\bar f_0}{h} \right| \le \frac{M_2h}{2} + \frac{2\delta}{h}$

where:

$M_2 = \max_{x_0\le x\le x_0+h} |f''(x)|$

$|f_1-\bar f_1|+|f_0-\bar f_0| \le 2\delta$

$f_i$ is the true value
$\bar f_i$ is the computed value
$\delta$ is the round-off error

Optimal Step Size#

The best $h$ balances truncation and round-off error.

For values accurate to machine precision $\epsilon$ :

Estimate	Suggested $h_{\mathrm{opt}}$
First derivative, central difference	$\sqrt[3]{\epsilon}$
Second derivative	$\sqrt[4]{\epsilon}$

Workshop: Supersonic flap lift sensitivity

Estimate the sensitivity of lift $L$ to angle of attack $\alpha$ :

$L'(\alpha)=\frac{dL}{d\alpha}$

Treat the flap as a black box and use the simulation data to estimate the sensitivity for:

$\alpha<30^\circ$

$\alpha\ (^\circ)$	Lift $(\mathrm N)$	Drag $(\mathrm N)$
$1.06$	$122.2$	$52.4$
$1.62$	$185.8$	$55.9$
$2.71$	$311.4$	$67.0$
$4.29$	$497.1$	$93.2$
$6.30$	$743.1$	$144.4$
$8.66$	$1053.9$	$233.1$
$11.2$	$1434.3$	$372.6$
$14.0$	$1884.5$	$575.8$
$16.9$	$2395.5$	$851.0$
$19.7$	$2945.8$	$1197.4$
$22.3$	$3503.8$	$1601.1$
$24.6$	$4034.4$	$2035.3$
$26.7$	$4505.3$	$2462.4$
$28.2$	$4883.5$	$2836.2$
$29.3$	$5150.7$	$3116.3$
$29.9$	$5286.7$	$3265.1$

The $\alpha$ values are unevenly spaced, so the standard equally spaced formulas are not identical.

Key ideas

Use analytical differentiation when it is easy
Finite differences estimate derivatives from nearby function values
Central differences usually have higher-order accuracy
One-sided differences are useful near boundaries
Standard formulas assume equally spaced points
Numerical differentiation amplifies noise
Smaller $h$ reduces truncation error but increases round-off error
Choose $h$ by balancing both sources of error

Contributors: Keys

Comments

Powered by GitHub issues