MATH 417 Lecture 9

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

Section 4.1

Given the values $f(x_0),\dots ,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)={\frac{{\mathrm{d}}^k}{\mathrm{d}{x}^k}(P_n(x))|}_{x=x_j}$

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

We know the error of (1) is

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

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{array}{rl}f(x_0+h)& =f(x_0)+h{f}^{\prime }(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}^{\prime }(x_0)+\frac{h^2}{2}{f}^{″}(x_0)-\frac{h^3}{3!}{f}^{‴}(x_0)+\frac{h^4}{4!}{f}^{(4)}(\zeta )\end{array}$

Where $\xi \in (x_0,x_0+h)$, and $\zeta \in (x_0-h,x_0)$.

Adding both equations gives

$\begin{array}{rl}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!}(f^{(4)}(\xi )+f^{(4)}(\zeta ))\end{array}$

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 (x_0-h,x_0+h)$ (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^{\prime }(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^{\prime }(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{array}{rl}2(\frac{f(x_0+h)-f(x_0)}{h}-f^{\prime }(x_0))-\frac{f(x_0+2h)-f(x_0)}{2h}+f^{\prime }(x_0)& =(2\frac{h^2}{3!}-\frac{(2h{)}^2}{3!})f^{‴}(x_0)+\dots +(2\frac{h^{n-1}}{n!}-\frac{(2h{)}^{n-1}}{n!})f^{(n)}(x_0)+\dots \\ \frac{-f(x_0+2h)+4f(x_0+h)-3f(x_0)}{2h}-f^{\prime }(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{array}$

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^{\prime }(x_0)=O(h^3)$

Richardson Extrapolation on Taylor Series Rule

Suppose we want $f^{″}(x_0)-\text{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^{\prime }(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}^{\prime }(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 $Af(x_0-3h)+Bf(x_0+5h)=(A+B)f(x_0)=h(5B-3A)f^{\prime }(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^{\prime }(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}-(-\frac{25}{120h}+\frac{30}{40h})f(x_0)=f^{\prime }(x_0)+O(h^2)$
   • Simplified, our rule is $\frac{9f(x_0+5h)+16f(x_0)-25f(x_0-3h)}{120h}-f^{\prime }(x_0)=O(h^2)$