MATH 417 Lecture 9

« previous | Tuesday, February 11, 2014 | next »

Section 4.1

Given the values $f(x_{0}),\ldots ,f(x_{n})$, we want to approximate $f^{(k)}(x_{j})$ by a numerical rule.

1. $f(x)\approx P_{n}(x)$, where $P_{n}(x)$ is the Lagrange polynomial
2. $f^{(k)}(x_{j})=\left.{\frac {\mathrm {d} ^{k}}{\mathrm {d} x^{k}}}\left(P_{n}(x)\right)\right|_{x=x_{j}}$

We are interested in the absolute error of (2).

We know the error of (1) is

$\left|f(x)-P_{n}(x)\right|=\left|{\frac {f^{(n+1)}(\xi (x))}{(n+1)!}}\right|\,\left|\prod _{k=0}^{n}(x-x_{k})\right|$

If all points are equidistant (at a distance $h$), then the error is $O(h^{n+1})$

By taking $k$ derivatives, we expect the error of (2) to be at most ${\frac {O(h^{n+1})}{h^{k}}}=O(h^{n+1-k})$.

Taylor Series

Given 3 points $f(x_{0}-h)$, $f(x_{0})$, and $f(x_{0}+h)$, what is the second derivative at the midpoint ($f''(x_{0})$). We expect it to be $O(h)$.

The Taylor Series expansions of $f(x_{0}+h)$ and $f(x_{0}-h)$ are

${\begin{aligned}f(x_{0}+h)&=f(x_{0})+h\,f'(x_{0})+{\frac {h^{2}}{2}}\,f''(x_{0})+{\frac {h^{3}}{3!}}\,f'''(x_{0})+{\frac {h^{4}}{4!}}\,f^{(4)}(\xi )\\f(x_{0}-h)&=f(x_{0})-h\,f'(x_{0})+{\frac {h^{2}}{2}}\,f''(x_{0})-{\frac {h^{3}}{3!}}\,f'''(x_{0})+{\frac {h^{4}}{4!}}\,f^{(4)}(\zeta )\end{aligned}}$

Where $\xi \in \left(x_{0},x_{0}+h\right)$, and $\zeta \in \left(x_{0}-h,x_{0}\right)$.

Adding both equations gives

${\begin{aligned}f(x_{0}+h)+f(x_{0}-h)&=2f(x_{0})+h^{2}\,f''(x_{0})+2\,{\frac {h^{4}}{4!}}\,f^{(4)}+\dots +2\,{\frac {h^{2n}}{(2n)!}}\,f^{(2n)}(x_{0})\\&=2f(x_{0})+h^{2}\,f''(x_{0})+\,{\frac {h^{4}}{4!}}\,\left(f^{(4)}(\xi )+f^{(4)}(\zeta )\right)\end{aligned}}$

Observe that we have

${\frac {f(x_{0}+h)-2f(x_{0})+f(x_{0}-h)}{h^{2}}}=f''(x_{0})+{\frac {h^{2}}{12}}\,{\frac {f^{(4)}(\xi )+f^{(4)}(\zeta )}{2}}$

Hence our error is

${\frac {h^{2}}{12}}\,f^{(4)}(\eta )$

for some $\eta \in \left(x_{0}-h,x_{0}+h\right)$ (this is true by the mean value theorem: the average value of a function between two points is also a value of the function between the two points)

Richardson Extrapolation

From Taylor series expansion of $f(x_{0}+h)$ centered at $x_{0}$, we get

$E(h)={\frac {f(x_{0}+h)-f(x_{0})}{h}}-f'(x_{0})={\frac {h}{2!}}\,f''(x_{0})+{\frac {h^{2}}{3!}}\,f^{(3)}(x_{0})+\dots +{\frac {h^{n-1}}{n!}}\,f^{(n)}(x_{0})+\dots$.

$E(2h)={\frac {f(x_{0}+2h)-f(x_{0})}{2h}}-f'(x_{0})=h\,f''(x_{0})+{\frac {(2h)^{2}}{3!}}\,f^{(3)}(x_{0})+\dots +{\frac {(2h)^{n-1}}{n!}}\,f^{(n)}(x_{0})+\dots$.

Taking $2E(h)-E(2h)$ gives

${\begin{aligned}2\left({\frac {f(x_{0}+h)-f(x_{0})}{h}}-f'(x_{0})\right)-{\frac {f(x_{0}+2h)-f(x_{0})}{2h}}+f'(x_{0})&=\left(2\,{\frac {h^{2}}{3!}}-{\frac {(2h)^{2}}{3!}}\right)f'''(x_{0})+\dots +\left(2\,{\frac {h^{n-1}}{n!}}-{\frac {(2h)^{n-1}}{n!}}\right)\,f^{(n)}(x_{0})+\dots \\{\frac {-f(x_{0}+2h)+4f(x_{0}+h)-3f(x_{0})}{2h}}-f'(x_{0})&=-{\frac {1}{3}}\,h^{2}\,f'''(x_{0})-{\frac {6h^{3}}{4!}}\,f^{(4)}(x_{0})-{\frac {14h^{4}}{5!}}f^{(5)}-\dots \end{aligned}}$

Let's call that last equation ${\tilde {E}}(h)$. Now we can recursively do $4{\tilde {E}}(h)-{\tilde {E}}(2h)=O(h^{3})$:

${\frac {f(x_{0}+4h)-12f(x_{0}+2h)+32f(x_{0}+h)-23f(x_{0})}{12h}}-f'(x_{0})=O(h^{3})$

Richardson Extrapolation on Taylor Series Rule

Suppose we want $f''(x_{0})-{\mbox{rule}}=O(h^{4})$. Then we need 5 points.

To find the rule, we take ${\frac {4E(h)-E(2h)}{4}}$, where

$E(h)={\frac {f(x_{0}+h)-2f(x_{0})+f(x_{0}+h)}{h^{2}}}-f''(x_{0})=2\,{\frac {h^{2}}{4!}}\,f^{(4)}(x_{0})+2\,{\frac {h^{4}}{6!}}\,f^{(6)}(x_{0})+\dots +2\,{\frac {h^{2n-2}}{(2n)!}}\,f^{(2n)}(x_{0})+\dots$

After some algebra, we get

${\frac {-f(x_{0}+2h)+16f(x_{0}+h)-30f(x_{0})+16f(x_{0}-h)-f(x_{0}-2h)}{12h^{2}}}-f''(x_{0})=O(h^{4})$

Example: Undetermined Coefficients

Given points $x_{0}-3h$, $x_{0}$, and $x_{0}+5h$, find an approximation of $f'(x_{0})$ of order $O(h^{2})$ using the values $f(x_{0}-3h)$, $f(x_{0})$, and $f(x_{0}+5h)$.

There are three ways to find this (unique) answer:

1. find $P_{2}(x)$, differentiate, and plug in $x_{0}$.
2. Taylor series/undetermined coefficients:
   • $f(x_{0}-3h)=f(x_{0})-3h\,f'(x_{0})+{\frac {9h^{2}}{2}}\,f''(x_{0})-{\frac {27h^{3}}{3!}}\,f'''(x_{0})+O(h^{4})$
   • Failed to parse (syntax error): {\displaystyle f(x_0+5h) = f(x_0) + 5h \, f'(x_0) + \frac{25h^2}{2} \, f''(x_0) + \frac{125h^3}{3!} \' f'''(x_0) + O(h^4)}
   • Take $A\,f(x_{0}-3h)+B\,f(x_{0}+5h)=(A+B)\,f(x_{0})=h(5B-3A)\,f'(x_{0})+{\frac {h^{2}}{2}}\,(25B+9A)\,f''(x_{0})+{\frac {h^{3}}{6}}\,(126B+27A)\,f'''(x_{0})+(A+B)\,O(h^{4})$
   • We want the coefficient of $f'(x)$ to be 1 and the coefficient of $f'''(x_{0})$ to be 0, so $A=-{\frac {25}{120h}}$ and $B={\frac {3}{40h}}$.
   • Plugging this back in gives ${\frac {-25f(x_{0}-3h)}{120h}}+{\frac {3f(x_{0}+5h)}{40h}}-\left(-{\frac {25}{120h}}+{\frac {30}{40h}}\right)\,f(x_{0})=f'(x_{0})+O(h^{2})$
   • Simplified, our rule is ${\frac {9f(x_{0}+5h)+16f(x_{0})-25f(x_{0}-3h)}{120h}}-f'(x_{0})=O(h^{2})$