Difference between revisions of "Numerical Differentiation"

From Sutherland_wiki
Jump to: navigation, search
(Update taylor series approach to generating derivative stencils)
m (fix a mistake in the text on deriving the stencils from Taylor series.)
 
(5 intermediate revisions by the same user not shown)
Line 43: Line 43:
  
 
If we subtract the Taylor series expansion at <math>x_{i-1}</math>
 
If we subtract the Taylor series expansion at <math>x_{i-1}</math>
−
from the one at <math>x_{i-1}</math>, we find
+
from the one at <math>x_{i+1}</math>, we find
 
:<math>
 
:<math>
 
f(x_{i+1})-f(x_{i-1}) = 2f^{\prime}(x_i)h + \tfrac{1}{3} f^{\prime\prime\prime}(x_i) h^3 + \cdots
 
f(x_{i+1})-f(x_{i-1}) = 2f^{\prime}(x_i)h + \tfrac{1}{3} f^{\prime\prime\prime}(x_i) h^3 + \cdots
Line 74: Line 74:
 
|
 
|
 
{| border=1 cellpadding=5 cellspacing=0 style="text-align:center"
 
{| border=1 cellpadding=5 cellspacing=0 style="text-align:center"
−
! Formula for <math> \left. \frac{\mathrm{d\phi}}{\mathrm{d}x} \right|_{i}</math>
+
! Formula for <math> \left. \frac{\mathrm{d} f}{\mathrm{d}x} \right|_{i}</math>
 
! Order
 
! Order
 
|-
 
|-
 
|<math>
 
|<math>
−
   \frac{\phi_{i+1}-\phi_{i}}{h}</math>
+
   \frac{f(x_{i+1})-f(x_{i})}{h}</math>
 
||<math>\mathcal{O}\left( h \right) </math>
 
||<math>\mathcal{O}\left( h \right) </math>
 
|-
 
|-
 
|<math>
 
|<math>
−
   \frac{\phi_{i}-\phi_{i-1}}{h}</math>
+
   \frac{f(x_{i})-f(x_{i-1})}{h}</math>
 
||<math>\mathcal{O}\left( h \right) </math>
 
||<math>\mathcal{O}\left( h \right) </math>
 
|-
 
|-
 
|<math>
 
|<math>
−
   \frac{\phi_{i+1}-\phi_{i-1}}{2 h}</math>
+
   \frac{f(x_{i+1})-f(x_{i-1})}{2 h}</math>
 
| <math>\mathcal{O}\left(h^2 \right) </math>
 
| <math>\mathcal{O}\left(h^2 \right) </math>
 
|-
 
|-
 
|<math>
 
|<math>
−
   \frac{\phi_{i-2} - 8 \phi_{i-1} + 8 \phi_{i+1} - \phi_{i+1}}{12 h}
+
   \frac{f(x_{i-2}) - 8 f(x_{i-1}) + 8 f(x_{i+1}) - f(x_{i+2})}{12 h}
 
</math>
 
</math>
 
||<math>\mathcal{O}\left( h^4 \right) </math>
 
||<math>\mathcal{O}\left( h^4 \right) </math>
Line 120: Line 120:
  
 
Lagrange polynomials, which are commonly used for [[Interpolation#Lagrange_Polynomial_Interpolation|interpolation]], can also be used for differentiation.  The formula is  
 
Lagrange polynomials, which are commonly used for [[Interpolation#Lagrange_Polynomial_Interpolation|interpolation]], can also be used for differentiation.  The formula is  
−
<center><math>f^{\prime}(x) = \sum_{k=0}^n y_k L_{k}^{\prime}(x),</math></center>
+
:<math>f^{\prime}(x) = \sum_{k=0}^n y_k L_{k}^{\prime}(x),</math>
 
where <math>L_{k}^{\prime}(x)</math> is given as
 
where <math>L_{k}^{\prime}(x)</math> is given as
−
<center><math>L_{k}^{\prime}(x) = \left[ \sum_{{j=0}\atop{j\ne k}}^{n} \left( \prod_{ {i=0}\atop{i \ne j,k} }^n (x-x_i) \right) \right] \left[ \prod_{{i=0}\atop{i\ne k}}^{n} (x_k-x_i) \right]^{-1}. </math></center>
+
:<math>L_{k}^{\prime}(x) = \left[ \sum_{{j=0}\atop{j\ne k}}^{n} \left( \prod_{ {i=0}\atop{i \ne j,k} }^n (x-x_i) \right) \right] \left[ \prod_{{i=0}\atop{i\ne k}}^{n} (x_k-x_i) \right]^{-1}. </math>
 
Here <math>n</math> is the order of the polynomial and we require <math>n_p=n+1</math> points to form the Lagrange polynomial.
 
Here <math>n</math> is the order of the polynomial and we require <math>n_p=n+1</math> points to form the Lagrange polynomial.
 +
 +
Here are the results for <var>n = 2, 3, 4</var>
 +
 +
:{| border=1 cellpadding=10 cellspacing=1
 +
!
 +
! <var>n</var>=2
 +
! <var>n=3</var>
 +
! <var>n=4</var>
 +
|-
 +
| <math>L_{0}^{\prime}(x)</math>
 +
| <math>\frac{1}{x_{0}-x_{1}}</math>
 +
| <math>\frac{2x-x_{1}-x_{2}}{(x_{0}-x_{1})(x_{0}-x_{2})}</math>
 +
| <math>\frac{3x^{2}-2x\left(x_{1}+x_{2}+x_{3}\right)+x_{1}\left(x_{2}+x_{3}\right)+x_{2}x_{3}}{\left(x_{0}-x_{1}\right)\left(x_{0}-x_{2}\right)\left(x_{0}-x_{3}\right)}</math>
 +
|-
 +
| <math>L_{1}^{\prime}(x)</math>
 +
| <math>\frac{1}{x_{1}-x_{0}}</math>
 +
| <math>\frac{2x-x_{0}-x_{2}}{(x_{1}-x_{0})(x_{1}-x_{2})}</math>
 +
| <math>-\frac{3x^{2}-2x(x_{0}+x_{2}+x_{3})+x_{0}\left(x_{2}+x_{3}\right)+x_{2}x_{3}}{\left(x_{0}-x_{1}\right)\left(x_{1}-x_{2}\right)\left(x_{1}-x_{3}\right)}</math>
 +
|-
 +
| <math>L_{2}^{\prime}(x)</math>
 +
|
 +
| <math>\frac{2x-x_{0}-x_{1}}{(x_{2}-x_{0})(x_{2}-x_{1})}</math>
 +
| <math>\frac{3x^{2}-2x(x_{0}+x_{1}+x_{3})+x_{0}\left(x_{1}+x_{3}\right)+x_{1}x_{3}}{\left(x_{0}-x_{2}\right)\left(x_{1}-x_{2}\right)\left(x_{2}-x_{3}\right)}</math>
 +
|-
 +
| <math>L_{3}^{\prime}(x)</math>
 +
|
 +
|
 +
|<math>-\frac{3x^{2}-2x(x_{0}+x_{1}+x_{2})+x_{0}\left(x_{1}+x_{2}\right)+x_{1}x_{2}}{\left(x_{0}-x_{3}\right)\left(x_{1}-x_{3}\right)\left(x_{2}-x_{3}\right)}</math>
 +
|}

Latest revision as of 15:56, 26 August 2010

Introduction

Often we need to approximate the derivative of a function when we cannot obtain it analytically. Here we discuss several ways to do this numerically.


Taylor Series

Let's consider the situation where we have samples of a function f(x) at discrete points \begin{array}{cccc}x_1 & x_2 & \cdots & x_n\end{array} seperated by spacing h as depicted in the following figure:

Uniform grid 1D.png

Consider a Taylor series expansions about some arbitrary point x_i. Since x_{i+1}-x_i = x_i-x_{i-1} = h we can write these as follows:

Approximation location Taylor Series Expansion about x_i
x_{i+1} f(x_{i+1}) = f(x_i) + f^\prime(x_i) h + \tfrac{1}{2}f^{\prime\prime}(x_i) h^2 + \tfrac{1}{6}f^{\prime\prime\prime}(x_i) h^3 + \tfrac{1}{24}f^{(4)}(x_i) h^4 + \cdots
x_{i-1} f(x_{i-1}) = f(x_i) - f^\prime(x_i)h + \tfrac{1}{2}f^{\prime\prime}(x_i)h^2 - \tfrac{1}{6}f^{\prime\prime\prime}(x_i)h^3 + \tfrac{1}{24}f^{(4)}(x_i)h^4 - \cdots

If we subtract the Taylor series expansion at x_{i-1} from the one at x_{i+1}, we find

f(x_{i+1})-f(x_{i-1}) = 2f^{\prime}(x_i)h + \tfrac{1}{3} f^{\prime\prime\prime}(x_i) h^3 + \cdots

Now we solve this for f^\prime(x_i) to find

f^{\prime}(x_i) = \frac{f(x_{i+1})-f(x_{i-1})}{2h} - \tfrac{1}{6} f^{\prime\prime\prime}(x_i)h^2 - \cdots

Now if h is small, then the second term (with the h^2 in it) is small and we can approximate the derivative as

f^\prime(x_i) = \frac{f(x_{i+1})-f(x_{i-1})}{2h}

We call this a second order approximation to f^\prime(x) because when we truncated the series approximation to f^\prime(x_i) the largest term there was of the order of h^2.

Note that we now have a way to approximate the derivative of a function if we have the function's values at two locations.

On a uniform mesh, we can use this technique to generate a variety of approximations to derivatives, as summarized in the following table:

Formula for \left. \frac{\mathrm{d} f}{\mathrm{d}x} \right|_{i} Order
\frac{f(x_{i+1})-f(x_{i})}{h} \mathcal{O}\left( h \right)
\frac{f(x_{i})-f(x_{i-1})}{h} \mathcal{O}\left( h \right)
\frac{f(x_{i+1})-f(x_{i-1})}{2 h} \mathcal{O}\left(h^2 \right)
\frac{f(x_{i-2}) - 8 f(x_{i-1}) + 8 f(x_{i+1}) - f(x_{i+2})}{12 h} \mathcal{O}\left( h^4 \right)
Error in approximation of \frac{df}{dx} as a function of the size of the interval h. Click here to download the matlab file that produced this plot.

As can be seen in the figure above, higher order approximations result in significantly lower error for a given spacing h. Note that for h<10^{-3} the fourth-order approximation is contaminated by roundoff error. The same would happen for the other derivative approximations, but at smaller h.


Lagrange Polynomials

Lagrange polynomials, which are commonly used for interpolation, can also be used for differentiation. The formula is

f^{\prime}(x) = \sum_{k=0}^n y_k L_{k}^{\prime}(x),

where L_{k}^{\prime}(x) is given as

L_{k}^{\prime}(x) = \left[ \sum_{{j=0}\atop{j\ne k}}^{n} \left( \prod_{ {i=0}\atop{i \ne j,k} }^n (x-x_i) \right) \right] \left[ \prod_{{i=0}\atop{i\ne k}}^{n} (x_k-x_i) \right]^{-1}.

Here n is the order of the polynomial and we require n_p=n+1 points to form the Lagrange polynomial.

Here are the results for n = 2, 3, 4

n=2 n=3 n=4
L_{0}^{\prime}(x) \frac{1}{x_{0}-x_{1}} \frac{2x-x_{1}-x_{2}}{(x_{0}-x_{1})(x_{0}-x_{2})} \frac{3x^{2}-2x\left(x_{1}+x_{2}+x_{3}\right)+x_{1}\left(x_{2}+x_{3}\right)+x_{2}x_{3}}{\left(x_{0}-x_{1}\right)\left(x_{0}-x_{2}\right)\left(x_{0}-x_{3}\right)}
L_{1}^{\prime}(x) \frac{1}{x_{1}-x_{0}} \frac{2x-x_{0}-x_{2}}{(x_{1}-x_{0})(x_{1}-x_{2})} -\frac{3x^{2}-2x(x_{0}+x_{2}+x_{3})+x_{0}\left(x_{2}+x_{3}\right)+x_{2}x_{3}}{\left(x_{0}-x_{1}\right)\left(x_{1}-x_{2}\right)\left(x_{1}-x_{3}\right)}
L_{2}^{\prime}(x) \frac{2x-x_{0}-x_{1}}{(x_{2}-x_{0})(x_{2}-x_{1})} \frac{3x^{2}-2x(x_{0}+x_{1}+x_{3})+x_{0}\left(x_{1}+x_{3}\right)+x_{1}x_{3}}{\left(x_{0}-x_{2}\right)\left(x_{1}-x_{2}\right)\left(x_{2}-x_{3}\right)}
L_{3}^{\prime}(x) -\frac{3x^{2}-2x(x_{0}+x_{1}+x_{2})+x_{0}\left(x_{1}+x_{2}\right)+x_{1}x_{2}}{\left(x_{0}-x_{3}\right)\left(x_{1}-x_{3}\right)\left(x_{2}-x_{3}\right)}
Retrieved from "https://sutherland.che.utah.edu/wiki/index.php?title=Numerical_Differentiation&oldid=443"