MATH 417 Lecture 6

« previous | Thursday, January 30, 2014 | next »

Last Time

Find $p(x)$ of degree $p\leq n$ such that $p(x_{i})=f(x_{i})$ given samples $x_{0},x_{1},\ldots ,x_{n}$ of $f$.

1. There is a unique $p(x)$
2. $p(x)=\sum _{k=1}^{n}f(x)\,\prod _{i=1;i\neq k}^{n}{\frac {x-x_{i}}{x_{k}-x_{i}}}$
3. $f(x)-p(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\,\prod _{k=0}^{n}(x-x_{k})$

Iterative Process for Lagrange Interpolating Polynomial

Given $x_{0},x_{1},\ldots ,x_{n-1},x_{n}$,

1. $L_{0}(x)$ interpolates $f(x)$ at $x_{0},x_{1},\ldots ,x_{n-1}$: $L_{0}(x_{i})=f(x_{i})$ for $0\leq i\leq n-1$
2. $L_{1}(x)$ interpolates $f(x)$ at $x_{1},\ldots ,x_{n-1},x_{n}$: $L_{1}(x_{i})=f(x_{i})$ for $1\leq i\leq n-1$

Can we find $p(x)=(\Box )\,L_{0}(x)+(\Box )\,L_{1}(x)$? Paul Neville did.

Conditions: $p(x_{0})=f(x_{0})$ and $p(x_{n})=f(x_{n})$ Hence

${\begin{aligned}p_{n}(x)&=\left({\frac {x-x_{n}}{x_{0}-x_{n}}}\right)\,L_{0}(x)+\left({\frac {x-x_{0}}{x_{n}-x_{0}}}\right)\,L_{1}(x)\\&={\frac {(x-x_{0})\,L_{1}(x)-(x-x_{n})L_{0}(x)}{x_{n}-x_{0}}}\end{aligned}}$

1. At iteration $i=0$, our interpolations of each point are the constants $x_{i}$
2. At iteration $i=1$, our interpolations of each consecutive pair of points are linear
3. At iteration $i=2$, our interpolations of each consecutive triple of points are quadratic
4. etc.
5. until we combine all points into $p_{n}(x)$

However, this method is unstable (especially when points are close together, and ${\frac {x-x_{i}}{x_{k}-x_{i}}}$ in the product has much roundoff error)

Newton's Formula for $p(x)$

Given $x_{0},x_{1}$, we can find

1. $f(x)\approx f(x_{0})=p_{0}(x)$.
2. $f(x)\approx p_{1}(x)=f(x_{0})+{\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}\,\left(x-x_{0}\right)$

Observe that $p_{1}(x)\to f(x_{0})+{\frac {f'(x_{0})}{1!}}\,(x-x_{0})$ as $x\to x_{0}$

$f(x)=p_{n-1}(x)+f[x_{0},x_{1},\ldots ,x_{n}]\,\prod _{k=0}^{n-1}\left(x-x_{k}\right)$

Where $f[x_{0},x_{1},\ldots ,x_{n}]$ is the coefficient of $x^{n}$ in $p_{n}(x)$.

We know from above that

1. $f[x_{0}]=f(x_{0})$
2. $f[x_{0},x_{1}]={\begin{cases}{\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}&x_{1}\neq x_{0}\\{\frac {f'(x_{0})}{1!}}&x_{1}=x_{0}\end{cases}}$

We can extract

$f[x_{0},x_{1},x_{2}]={\begin{cases}{\frac {f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}}}&x_{2}\neq x_{0}\\{\frac {f''(x_{0})}{2!}}&x_{0}=x_{1}=x_{2}\end{cases}}$

In general, when the points coincide, we take the Taylor series.

Applying this to Neville's iterative method, we find

• $L_{1}(x)=f[x_{1},x_{2},\ldots ,x_{n}]\,x^{n-1}+\Theta (x^{n-2})$
• $L_{0}(x)=f[x_{0},x_{1},\ldots ,x_{n-1}]\,x^{n-1}+\Theta (x^{n-2})$
• $p_{n}(x)=x^{n}\,{\frac {f[x_{1},\ldots ,x_{n}]-f[x_{0},\ldots ,x_{n-1}}{x_{n}-x_{0}}}+\Theta (x^{n-1})$

In General,

$f[x_{0},\ldots ,x_{n}]={\begin{cases}{\frac {f[x_{1},\ldots ,x_{n}]-f[x_{0},\ldots ,x_{n-1}]}{x_{n}-x_{0}}}&x_{n}\neq x_{0}\\{\frac {f^{(n)}(x_{0})}{n!}}&x_{0}=x_{1}=\dots =x_{n}\end{cases}}$

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 p_n(x) = f(x_0) + f[x_0, x_1] \, (x - x_0) + f[x_0, x_1, x_2] \, (x - x_0) \, (x-x_1) + \dots + f[x_0, x_1, \ldots, x_n] \, (x-x_0) \, \dots \, (x-x_{n-1}) }

Example

x f(x) f[.,.] f[.,.,.] f[.,.,.,.] f[.,.,.,.,.] f[.,.,.,.,.,.]
0  4
         -3
1  1             9/2
          6              -17/6
2  7              -4                  11/12
         -2                5/6                     -3/20
3  5            -3/2                    1/6
         -5                3/2
4  0               3
          1
5  1

Therefore

• 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) = 4 - 3x + \frac{9}{2} x(x-1)}
• 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_5(x) = 4 - 3x + \frac{9}{2} x(x-1) - \frac{17}{6} x(x-1)(x-2) + \frac{11}{12} x(x-1)(x-2)(x-3) - \frac{3}{20} x(x-1)(x-2)(x-3)(x-4)}

We could have interpolated the polynomial in reverse:

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_5(x) = 1 + 1(x-5) + 3(x-5)(x-4) + \frac{3}{2} (x-5)(x-4)(x-3) + \frac{1}{6} (x-5)(x-4)(x-3)(x-2) - \frac{3}{20} (x-5)(x-4)(x-3)(x-2)(x-1)}

Since 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_5(x)} is unique, forwards and backwards methods (and Lagrange's) must give the same result.

Example 2

This cannot be interpolated by Lagrange's method

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	1	2
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)}	2	1	2
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)}	-1	1

Goal: 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_4} such that 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_4(x_i) = f(x_i)} 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 p_4'(x_i) = f'(x_i)} .

x f(x) f[.,.] f[.,.,.] f[.,.,.,.] f[.,.,.,.,.]
0  2
         -1
0  2              0
         -1                 2
1  1              2                   -3/2
          1                -1
1  1              0
          1
2  2

Note: If we are given the 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 n} -th derivative 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} at a point, we repeat that point 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 n+1} times in the table. Conversely, if we want to repeat a point 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} times in the table, we need the values of the 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+1} -th derivative at that point

Therefore 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_4(x) = 2 - x + 0x^2 + 2x^2(x-1) - \frac{3}{2} x^2(x-1)^2} .

Homework

3.3: 10, 11, 12, 13, 14, 15