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

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 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 i \ne j}
• 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_{n,j}(x_j) = 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 H'_{n,j}(x_i) = 0} for all 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 i} .

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_{n,j}(x) = \left( L_{n,j}(x) \right)^2 \, (1 + a(x-x_j))} , where 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 a} is some constant.

Differentiating this function reveals $a=2\,L_{n,j}'(x_{j})$. 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 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 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_{2n+1}} for 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 = 2} ($H_{5}$)

Newton

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}	4	1	7
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'}	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

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} 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{align}}

Hermite

First we need the lagrange polynomials:

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}(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{align}}

Therefore, plugging these 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 \hat{H}} -part of our formula for 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_{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) = 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:

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

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 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_{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)