MATH 417 Lecture 9

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

Section 4.1

Given the values Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 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{14 h^4}{5!} f^{(5)} - \dots \end{align}}

Let's call that last equation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{E}(h)} . Now we can recursively do Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4\tilde{E}(h) - \tilde{E}(2h) = O(h^3)} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f''(x_0) - \mbox{rule} = O(h^4)} . Then we need 5 points.

To find the rule, we take Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{4E(h) - E(2h)}{4}} , where

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{-f(x_0+2h) + 16 f(x_0+h) - 30 f(x_0) + 16 f(x_0-h) - f(x_0-2h)}{12h^2} - f''(x_0) = O(h^4)}

Example: Undetermined Coefficients

Given points Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0-3h} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0+5h} , find an approximation of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f'(x_0)} of order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(h^2)} using the values Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_0-3h)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_0)} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_0+5h)} .

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

1. find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_2(x)} , differentiate, and plug in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0} .
2. Taylor series/undetermined coefficients:
   • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f'(x)} to be 1 and the coefficient of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f'''(x_0)} to be 0, so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = -\frac{25}{120h}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B = \frac{3}{40h}} .
   • Plugging this back in gives Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{-25 f(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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{9f(x_0+5h) + 16f(x_0) - 25f(x_0-3h)}{120h} - f'(x_0) = O(h^2)}