MATH 417 Lecture 6

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

Last Time

Find $p(x)$ of degree $p\le n$ such that $p(x_i)=f(x_i)$ given samples $x_0,x_1,\dots ,x_n$ of $f$.

1. There is a unique $p(x)$
2. $p(x)=\sum _{k=1}^{n}f(x)\prod _{i=1;i\ne 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,\dots ,x_{n-1},x_n$,

1. $L_0(x)$ interpolates $f(x)$ at $x_0,x_1,\dots ,x_{n-1}$: $L_0(x_i)=f(x_i)$ for $0\le i\le n-1$
2. $L_1(x)$ interpolates $f(x)$ at $x_1,\dots ,x_{n-1},x_n$: $L_1(x_i)=f(x_i)$ for $1\le i\le n-1$

Can we find $p(x)=(◻)L_0(x)+(◻)L_1(x)$? Paul Neville did.

Conditions: $p(x_0)=f(x_0)$ and $p(x_n)=f(x_n)$ Hence

$\begin{array}{rl}{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{array}$

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

Observe that $p_1(x)\to f(x_0)+\frac{f^{\prime }(x_0)}{1!}(x-x_0)$ as $x\to x_0$

$f(x)=p_{n-1}(x)+f[x_0,x_1,\dots ,x_n]\prod _{k=0}^{n-1}(x-x_k)$

Where $f[x_0,x_1,\dots ,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{array}{ll}\frac{f(x_1)-f(x_0)}{x_1-x_0}& x_1\ne x_0\\ \frac{f^{\prime }(x_0)}{1!}& x_1=x_0\end{array}$

We can extract

$f[x_0,x_1,x_2]=\{\begin{array}{ll}\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}& x_2\ne x_0\\ \frac{f^{″}(x_0)}{2!}& x_0=x_1=x_2\end{array}$

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,\dots ,x_n]x^{n-1}+\mathrm{\Theta }(x^{n-2})$
• $L_0(x)=f[x_0,x_1,\dots ,x_{n-1}]x^{n-1}+\mathrm{\Theta }(x^{n-2})$
• $p_n(x)=x^n\frac{f[x_1,\dots ,x_n]-f[x_0,\dots ,x_{n-1}}{x_n-x_0}+\mathrm{\Theta }(x^{n-1})$

In General,

$f[x_0,\dots ,x_n]=\{\begin{array}{ll}\frac{f[x_1,\dots ,x_n]-f[x_0,\dots ,x_{n-1}]}{x_n-x_0}& x_n\ne x_0\\ \frac{f^{(n)}(x_0)}{n!}& x_0=x_1=\dots =x_n\end{array}$

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,\dots ,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^{\prime }(x)$	-1	1

Goal: Find $p_4$ such that $p_4(x_i)=f(x_i)$ and ${p_4}^{\prime }(x_i)=f^{\prime }(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