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

$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

• $p_{2}(x)=4-3x+{\frac {9}{2}}x(x-1)$
• $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:

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

$x$	0	1	2
$f(x)$	2	1	2
$f'(x)$	-1	1

Goal: Find $p_{4}$ such that $p_{4}(x_{i})=f(x_{i})$ and $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 $n$-th derivative of $f$ at a point, we repeat that point $n+1$ times in the table. Conversely, if we want to repeat a point $k$ times in the table, we need the values of the $k+1$-th derivative at that point

Therefore $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