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 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 h} ), then the error 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 O(h^{n+1})}

By taking 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 k} derivatives, we expect the error of (2) to be at most 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{O(h^{n+1})}{h^k} = O(h^{n+1-k})} .

Taylor Series

Given 3 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 f(x_0-h)} , $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+h)} , what is the second derivative at the midpoint (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)} ). We expect it to be 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)} .

The Taylor Series expansions 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 + h)} 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 - h)} are

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} 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{align} }

Where $\xi \in \left(x_{0},x_{0}+h\right)$, 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 \zeta \in \left( x_0-h,x_0 \right)} .

Adding both equations 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} 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{align}}

Observe that we have

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+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

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{h^2}{12} \, f^{(4)}(\eta)}

for some 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 \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 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+h)} centered at 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} , 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 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} .

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(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 $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 (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 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 $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)}