MATH566 Lesson 17: Numerical differentiation

Overview

• Approximate derivative by derivative of approximation

• Finite difference formulas from Taylor series

Calculus review

• $f:ℝ\to ℝ$ differentiable up to order $k$, $f\in C^{\left(k\right)}\left(ℝ\right)$

• The derivative of $f$ is the function $f^{\text{'}}\in C^{(k-1)}\left(ℝ\right)$

  ${\displaystyle f^{\text{'}}\left(x\right)=\frac{df}{dx}={lim}_{h\to 0}\frac{f(x+h)-f\left(x\right)}{h}}$

• The differentiation operator $D=\frac{d}{dx}$ is linear

  ${\displaystyle D(\alpha f+\beta g)=\alpha D\left(f\right)+\beta D\left(g\right)}$

• Geometric interpretation of derivatives:

  • first derivative: slope of tangent

  • second derivative: related to curvature

    ${\displaystyle \kappa =\frac{\left|f^{\text{'}\text{'}}\left(x\right)\right|}{\sqrt{1+{\left(f^{\text{'}}\left(x\right)\right)}^2}}}$

Derivative approximation

• Consider $f:ℝ\to ℝ$, $f\in C^{\left(k\right)}\left(ℝ\right)$, $f\left(x\right)$ difficult to compute

• Approximation $g:ℝ\to ℝ$, $f\in C^{\left(k\right)}\left(ℝ\right)$, $g\left(x\right)$ simpler to compute

  ${\displaystyle g\cong f}$

  Examples: interpolation, least squares

• Basic idea: approximation of derivative = derivative of approximation

  ${\displaystyle f^{\text{'}}\left(x\right)\cong g^{\text{'}}\left(x\right)}$

• Example: consider data $𝒟=\{(x_0,f_0),(x_1,f_1)\}$. Interpolant is

  ${\displaystyle g\left(t\right)=p_1\left(t\right)=\sum _{i=0}^1{f}_i{\ell }_i\left(t\right),{\ell }_0\left(t\right)=\frac{t-x_1}{x_0-x_1},{\ell }_1\left(t\right)=\frac{t-x_0}{x_1-x_0}}$ ${\displaystyle f^{\text{'}}\left(t\right)\cong p_1^{\text{'}}\left(t\right)=\sum _{i=0}^1{f}_i{\ell }_i^{\text{'}}\left(t\right)=\frac{f_0}{x_0-x_1}+\frac{f_1}{x_1-x_0}=\frac{f_1-f_0}{x_1-x_0}}$

Derivatives from Newton form of interpolating polynomial

• For data $𝒟=\{(x_0,f_0),\dots ,(x_n,f_n)\}$ differentiation of the Lagrange form

  ${\displaystyle p_n\left(t\right)=\sum _{i=0}^n{f}_i{\ell }_i\left(t\right)}$

  leads to $n+1$ derivatives of $n^{\mathrm{th}}$ degree polynomials

  ${\displaystyle p_n^{\text{'}}\left(t\right)=\sum _{i=0}^n{f}_i{\ell }_i^{\text{'}}\left(t\right)}$

• The Newton form

  ${\displaystyle p\left(t\right)=\left[f_0\right]+[f_1,f_0](t-x_0)+\cdots +[f_n,\dots ,f_0](t-x_0)\cdot \dots \cdot (t-x_{n-1})}$

  requires less effort, $n+1$ derivative of polynomials of degree $0,1,\dots ,n$

Uniform grid formulas - Finite differences

• Often $x_k=x_0+kh$,$h=(x_n-x_0)/n$, i.e., $f$ sampled at equidistant points

• Sample point positions with respect to evaluation point:

  • Left sample points $ℒ=\{(x_{n-k},f_{n-k}),(x_{n-k+1},f_{n-k+1}),\dots ,(x_n,f_n)\}$

  • Centered sample points $𝒞=\{(x_{n-k},f_{n-k}),\dots ,(x_n,f_n),\dots ,(x_{n+k},f_{n+k})\}$

  • Right sample points $ℛ=\{(x_n,f_n),(x_{n+1},f_{n+1})\dots ,(x_{n+k},f_{n+k})\}$

Derivative approximation from Taylor series

• Consider $f:ℝ\to ℝ$, $f\in {ℂ}^{\left(N\right)}\left(ℝ\right)$, hard to compute, known at sample points $x_j=x_n+jh$, $j\in \{0,\pm 1,\pm 2,\dots \}$, $f_j\equiv f\left(x_j\right)$

• An alternative approach to obtaining approximations of $f_n^{\left(k\right)}\equiv f^{\left(k\right)}\left(x_n\right)$ from the sample points is through linear combinations of Taylor series

  ${\displaystyle f\left(x_{n+j}\right)=f_n+\frac{1}{1!}{f}_n^{\text{'}}\cdot (jh)+\frac{1}{2!}{f}_n^{{}^{\text{'}\text{'}}}\cdot {(jh)}^2+\frac{1}{3!}{f}_n^{{}^{\text{'}\text{'}\text{'}}}\cdot {(jh)}^3+\cdots }$

• Example:

  ${\displaystyle \begin{array}{l}{f}_{n+1}=f\left(x_{n+1}\right)=f_n+f_n^{\text{'}}\cdot h+\frac{1}{2}{f}_n^{{}^{\text{'}\text{'}}}\cdot h^2+\frac{1}{6}{f}_n^{\text{'}\text{'}\text{'}}{h}^3+\cdots \\ f_{n-1}=f\left(x_{n-1}\right)=f_n-f_n^{\text{'}}\cdot h+\frac{1}{2}{f}_n^{{}^{\text{'}\text{'}}}\cdot h^2-\frac{1}{6}{f}_n^{\text{'}\text{'}\text{'}}{h}^3+\cdots \end{array}}$

  Eliminate $f_n^{\text{'}\text{'}}$ from above and obtain

  ${\displaystyle f_n^{\text{'}}=\frac{f_{n+1}-f_{n-1}}{2h}+\frac{1}{3}{f}_n^{\text{'}\text{'}\text{'}}{h}^2+\cdots =\frac{f_{n+1}-f_{n-1}}{2h}+𝒪\left(h^2\right)}$

Finite difference analysis

• Taylor series expansions are used to obtain the order of accuracy of a formula (do not confuse with order of convergence of a sequence)

• From previous example

  ${\displaystyle f_n^{\text{'}}=\frac{f_{n+1}-f_{n-1}}{2h}+\frac{1}{3}{f}_n^{\text{'}\text{'}\text{'}}{h}^2+\cdots =\frac{f_{n+1}-f_{n-1}}{2h}+𝒪\left(h^2\right)}$

  hence the approximation $f_n^{\text{'}}\cong (f_{n+1}-f_{n-1})/(2h)$ is of second order (of accuracy)

• Example: determine order of accuracy of $f_n^{\text{'}}\cong (-3f_n+4f_{n+1}-f_{n+2})/\left(2h\right)$

  ${\displaystyle \begin{array}{l}-3f_n=-3f_n\\ 4f_{n+1}=4f_n+4f_n^{\text{'}}\cdot h+2f_n^{{}^{\text{'}\text{'}}}\cdot h^2+\frac{2}{3}{f}_n^{\text{'}\text{'}\text{'}}{h}^3+\cdots \\ -f_{n+2}=-f_n-f_n^{\text{'}}\cdot \left(2h\right)-\frac{1}{2}{f}_n^{{}^{\text{'}\text{'}}}\cdot {\left(2h\right)}^2-\frac{1}{6}{f}_n^{\text{'}\text{'}\text{'}}{\left(2h\right)}^3-\cdots \end{array}\Rightarrow }$ ${\displaystyle (-3f_n+4f_{n+1}-f_{n+2})/\left(2h\right)=f_n^{\text{'}}-\frac{2}{3}{f}_n^{\text{'}\text{'}\text{'}}{h}^2=f_n^{\text{'}}+𝒪\left(h^2\right),\mathrm{second}\mathrm{order}.}$

Finite difference formula types

• Position of evaluation of derivative point w.r.t. sample points

  • left: evaluate $f_n^{\left(k\right)}$ using sample points $f_{n+j},j⩽0$

    ${\displaystyle f_n^{\text{'}}=\frac{f_n-f_{n-1}}{h}+𝒪\left(h\right)}$

  • right: evaluate $f_n^{\left(k\right)}$ using sample points $f_{n+j},j⩾0$

    ${\displaystyle f_n^{\text{'}}=\frac{f_{n+1}-f_n}{h}+𝒪\left(h\right)}$

  • centered: evaluate $f_n^{\left(k\right)}$ using sample points $f_{n+j},-m⩽j⩽m$

    ${\displaystyle f_n^{\text{'}}=\frac{f_{n+1}-f_{n-1}}{2h}+𝒪\left(h^2\right)}$

    (note higher order accurach of centered formulas)