MATH 417 Lecture 7

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

Review

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

Finite and Divided Differences

Definition of finite difference:

$\begin{array}{rl}{\mathrm{\Delta }}_{h}g(x_0)& =g(x_0+h)-g(x_0)\\ {\mathrm{\Delta }}_h^{n+1}f(x_0)& ={\mathrm{\Delta }}_h^{n}f(x_0+h)-{\mathrm{\Delta }}_h^{n}f(x_0)\\ {\mathrm{\Delta }}_h^{0}f(x_0)& =f(x_0)\end{array}$

If points are equidistant, then

$\begin{array}{rl}f[x_0,x_1]& =\frac{f(x_0+h)-f(x_0)}{h}=\frac{{\mathrm{\Delta }}_{h}f(x_0)}{h}\\ f[x_0,x_1+h,x_2+2h,\dots ,x_n]& =\frac{(-1{)}^n}{n!h^n}\sum _{k=0}^{n}f(x_0+kh)(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})\end{array}$

Interpolating Polynomials

Lagrange Polynomials

$p(x)=\sum f(x_j)L_{n,j}(x)$, where $L_{n,j}=\prod _{i=0}^n\frac{x-x_i}{x_j-x_i}$

Basis for space of polynomials $P_n$ is

$\{\frac{(x-x_1)\dots (x-x_n)}{(x_0-x_1)\dots (x_0-x_n)},\frac{(x-x_0)(x-x_2)\dots (x-x_n)}{(x_1-x_0)(x_1-x_2)\dots (x_1-x_n)},\dots ,\frac{(x-x_0)(x-x_1)\dots (x-x_{n-1})}{(x_n-x_0)(x_n-x_1)\dots (x_n-x_{n-1}}\}$

There are $n+1$ independent functions in $P_n$.

Newton Polynomials

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

Basis for space of polynomials $P_n$ is

$\{1,x-x_0,(x-x_0)(x-x_1),(x-x_0)(x-x_1)(x-x_2),\dots \}$

Hermite Polynomials

Interpolate function and derivative:

Find $H_{2n+1}(x)$ such that $H_{2n+1}(x_j)=f(x_j)$ and $H_{2^{\prime }n+1}(x_j)=f^{\prime }(x_j)$ for $j=0,1,\dots ,n$.

$H_{2n+1}=\sum _{j=0}^{n}f(x_j)H_{n,j}(x)+\sum _{j=0}^n{f}^{\prime }(x_j){\hat{H}}_{n,j}(x)$

Find ${\hat{H}}_{n,j}(x)$

Restrictions:

• ${\hat{H}}_{n,j}(x_i)=0$ for all $i$
• ${\hat{H}}_{n^{\prime },j}(x_i)=0$ if $i\ne j$
• $\frac{\mathrm{d}{\hat{H}}_{n,j}}{\mathrm{d}x}(x_j)=1$

${\hat{H}}_{n,j}(x)=\alpha (x-x_j)(L_{n,j}(x){)}^2$, where $\alpha$ is some constant

Take derivative to find $\alpha$:

${\hat{H}}_{n^{\prime },j}(x)=\alpha L_{n,j}^2(x_j)+\cancel{\alpha (x_j-x_j)2L_{n,j}(x_j)L_{n^{\prime },j}(x_j)}$

Therefore $\alpha =1$.

${\hat{H}}_{n,j}(x)=(x-x_j){(L_{n,j}(x))}^2$

Find $H_{n,j}$

Restrictions:

• $H_{n,j}(x_i)=0$ for $i\ne j$
• $H_{n,j}(x_j)=1$
• $H{\text{'}}_{n,j}(x_i)=0$ for all $i$.

$H_{n,j}(x)={(L_{n,j}(x))}^2(1+a(x-x_j))$, where $a$ is some constant.

Differentiating this function reveals $a=2L_{n^{\prime },j}(x_j)$. Therefore

$H_{n,j}(x){(L_{n,j}(x))}^2(1-2L_{n^{\prime },j}(x_j)(x-x_j))$

Example

Use Newton's and Hermite's method to compute $H_{2n+1}$ for $n=2$ ($H_5$)

Newton

$x$	0	1	2
$f$	4	1	7
$f^{\prime }$	5	0	1

Starting point is

x f(x)
0  4
      5
0  4

1  1
      0
1  1

2  7
      1
2  7

Completed table is

x f(x)
0  4
       5
0  4      -8
      -3       11
1  1       3       -19/4
       0      3/2         -3/4
1  1       6       -25/4
       6      -11
2  7      -5
       1 
2  7

$\begin{array}{rl}{H}_5(x)& \to 0,0,1,1,2,2\\ & =4+5x-8x^2+11x^2(x-1)-\frac{19}{4}{x}^2(x-1{)}^2-\frac{3}{4}{x}^2(x-1{)}^2(x-2)& =7+(x-2)-5(x-2{)}^2-11(x-2{)}^2(x-1)-\frac{25}{4}(x-2{)}^2(x-1{)}^2-\frac{3}{4}(x-2{)}^2(x-1{)}^{2}x\end{array}$

Hermite

First we need the lagrange polynomials:

$\begin{array}{rl}{L}_{2,0}(x)& =\frac{(x-1)(x-2)}{(0-1)(0-2)}=\frac{1}{2}(x-1)(x-2)\\ L_{2,1}(x)& =\frac{(x-0)(x-2)}{(1-0)(1-2)}=-x(x-2)\\ L_{2,2}(x)& =\frac{(x-0)(x-1)}{(2-0)(2-1)}=\frac{1}{2}x(x-1)\end{array}$

Therefore, plugging these into the $\hat{H}$-part of our formula for $H_{2n+1}$ gives

$H_5(x)=5x{\left(\frac{(x-1)(x-2)}{2}\right)}^2+0+1(x-2){\left(\frac{x(x-1)}{2}\right)}^2+\dots$

Now we need to find the derivatives of our lagrange polynomials above:

$\begin{array}{rl}{L}_{2^{\prime },0}(x)& =x-\frac{3}{2}\\ L_{2^{\prime },1}(x)& =-2x+2\\ L_{2^{\prime },2}(x)& =x-\frac{1}{2}\end{array}$

Evaluated at our points, we get

$\begin{array}{rl}{L}_{2^{\prime },0}(0)& =-\frac{3}{2}\\ L_{2^{\prime },1}(1)& =0\\ L_{2^{\prime },2}(2)& =\frac{3}{2}\end{array}$

Plugging these values into the $H$-part of our formula for $H_{2n+1}$ gives

$H_5(x)=4\cdot \frac{(x-1{)}^2(x-2{)}^2}{4}(1-2(-\frac{3}{2})x)+1\cdot x^2(x-2{)}^2+7\cdot \frac{x^2(x-1{)}^2}{4}(1-2\cdot \frac{3}{2}(x-2))+5x{\left(\frac{(x-1)(x-2)}{2}\right)}^2+0+1(x-2){\left(\frac{x(x-1)}{2}\right)}^2$

Quiz

Nothing from section 3.5

Most likely something to do with interpolating polynomials (if no method is specified, use Newton)