MATH 417 Lecture 7

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

Review

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

Finite and Divided Differences

Definition of finite difference:

${\begin{aligned}\Delta _{h}\,g(x_{0})&=g(x_{0}+h)-g(x_{0})\\\Delta _{h}^{n+1}f(x_{0})&=\Delta _{h}^{n}\,f(x_{0}+h)-\Delta _{h}^{n}\,f(x_{0})\\\Delta _{h}^{0}f(x_{0})&=f(x_{0})\end{aligned}}$

If points are equidistant, then

${\begin{aligned}f[x_{0},x_{1}]&={\frac {f(x_{0}+h)-f(x_{0})}{h}}={\frac {\Delta _{h}\,f(x_{0})}{h}}\\f[x_{0},x_{1}+h,x_{2}+2h,\ldots ,x_{n}]&={\frac {(-1)^{n}}{n!\,h^{n}}}\,\sum _{k=0}^{n}f(x_{0}+kh)\,(-1)^{k}\,{\binom {n}{k}}\end{aligned}}$

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

$\left\{{\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})}},\ldots ,{\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}}}\right\}$

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},\ldots ,x_{n}](x-x_{0})\dots (x-x_{n-1})$

Basis for space of polynomials $P_{n}$ is

$\left\{1,x-x_{0},(x-x_{0})(x-x_{1}),(x-x_{0})(x-x_{1})(x-x_{2}),\ldots \right\}$

Hermite Polynomials

Interpolate function and derivative:

Find $H_{2n+1}(x)$ such that $H_{2n+1}(x_{j})=f(x_{j})$ and $H_{2n+1}'(x_{j})=f'(x_{j})$ for $j=0,1,\ldots ,n$.

$H_{2n+1}=\sum _{j=0}^{n}f(x_{j})\,H_{n,j}(x)+\sum _{j=0}^{n}f'(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,j}'(x_{i})=0$ if $i\neq 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,j}'(x)=\alpha L_{n,j}^{2}(x_{j})+{\cancel {\alpha \,(x_{j}-x_{j})2L_{n,j}(x_{j})\,L_{n,j}'(x_{j})}}$

Therefore $\alpha =1$.

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

Find $H_{n,j}$

Restrictions:

• $H_{n,j}(x_{i})=0$ for $i\neq j$
• $H_{n,j}(x_{j})=1$
• $H'_{n,j}(x_{i})=0$ for all $i$.

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

Differentiating this function reveals $a=2\,L_{n,j}'(x_{j})$. Therefore

$H_{n,j}(x)\left(L_{n,j}(x)\right)^{2}\,\left(1-2\,L_{n,j}'(x_{j})\,(x-x_{j})\right)$

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'$	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{aligned}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{aligned}}$

Hermite

First we need the lagrange polynomials:

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

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{aligned}L_{2,0}'(x)&=x-{\frac {3}{2}}\\L_{2,1}'(x)&=-2x+2\\L_{2,2}'(x)&=x-{\frac {1}{2}}\end{aligned}}$

Evaluated at our points, 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 \begin{align} L_{2,0}'(0) &= -\frac{3}{2} \\ L_{2,1}'(1) &= 0 \\ L_{2,2}'(2) &= \frac{3}{2} \end{align}}

Plugging these values into 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 H} -part of our formula for $H_{2n+1}$ 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 H_5(x) = 4 \cdot \frac{(x-1)^2(x-2)^2}{4} \left( 1-2 \left( -\frac{3}{2} \right) x \right) + 1 \cdot x^2(x-2)^2 + 7 \cdot \frac{x^2(x-1)^2}{4} \left( 1 - 2 \cdot \frac{3}{2} (x-2) \right) + 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)