MATH 417 Lecture 5

« previous | Tuesday, January 28, 2014 | next »

Best Floating Point Adding Algorithm

1. sort collection of numbers
2. arrange in "baskets" of size $2^{n}$ for $n\in \mathbb {Z}$. (e.g. 1/32, 1/16, 1/8, 1/4, 1/2, 1, 2, 4, 8, 16, 32)
3. starting with smallest basket, remove 2 numbers and insert their sum into the next basket
4. repeat (3) until only one number remains in the largest basket

Roundoff error will be minimized.

Polynomial Interpolation

Given $f(x)$ for $x\in \left[0,1\right]$, we want to approximate with a simpler function $p(x)$.

Stuff to show:

1. there exists only one polynomial
2. find it
3. find the error

Existence

Theorem. Given $f(x)\in C\left[0,1\right]$ and $\epsilon >0$, there exists a polynomial $p(x)$ of degree $N(\epsilon )$ such that $\left|f(x)-p(x)\right|<\epsilon$ for all $x\in \left[0,1\right]$.

Proof. [Omitted in the book, so we will not cover it here]

quod erat demonstrandum

The good news: every function can be approximated by a polynomial. Weierstrass proved the existence of such polynomials, but Bernstein actually found one.

Lagrange Interpolating Polynomial

For $n\geq 0$, given $n+1$ measurements $f(x_{0}),f(x_{1}),\ldots ,f(x_{n})$, where $x_{0}<x_{1}<\dots <x_{n}$, We want to find $L_{n}$ such that $L_{n}(x_{k})=f(x_{k})$ for $k=0,1,\ldots ,n$, and $\deg {L_{n}}\leq n$.

Theorem 1. There exists a unique $p(x)=L_{n}(x)$ which satisfies the conditions above:

$p(x)=a_{n}\,x^{n}+a_{n-1}\,x^{n-1}+\dots +a_{1}\,x+a_{0}$

Proof. We take our initial conditions $p(x_{i})=f(x_{i})$ and construct a matrix equation $A\,{\vec {x}}={\vec {b}}$:

${\begin{bmatrix}x_{0}^{n}&x_{0}^{n-1}&\dots &x_{0}&1\\x_{1}^{n}&x_{1}^{n-1}&\dots &x_{1}&1\\\vdots &\vdots &\ddots &\vdots &\vdots \\x_{n-1}^{n}&x_{n-1}^{n-1}&\dots &x_{n-1}&1\\x_{n}^{n}&x_{n}^{n-1}&\dots &x_{n}&1\end{bmatrix}}\,{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{1}\\a_{0}\end{bmatrix}}={\begin{bmatrix}f(x_{0})\\f(x_{1})\\\vdots \\f(x_{n-1})\\f(x_{n})\end{bmatrix}}$

There is only one unique solution if and only if $\det {A}\neq 0$.

Basis.

1. Given one point $x_{0}$, the determinant is just $1\neq 0$.
2. Given two points $x_{0},x_{1}$, the determinant is $-(x_{1}-x_{0})\neq 0$ since points are distinct.
3. Given three points $x_{0},x_{1},x_{2}$, the determinant is $-(x_{2}-x_{0})\,(x_{2}-x_{1})\,(x_{1}-x_{0})\neq 0$

Induction. In general, $\det {A_{n}}=(-1)\prod _{0\leq i<j\leq n}(x_{i}-x_{j})\neq 0$

To find $L_{n}$, We construct a polynomial $P_{n,k}$ that is 0 at all points $x_{i}$ except when $i=k$, in which case $P_{n,k}(x_{k})=1$.

$P_{n,k}(x)=\prod _{i\neq k}{\frac {x-x_{i}}{x_{k}-x_{i}}}$

Therefore $L_{n}=f(x_{0})\,P_{n,0}(x)+f(x_{1})\,P_{n,1}(x)+\dots +f(x_{n})\,P_{n,n}(x)$, or in short

$L_{n}(x)=\sum _{k=0}^{n}f(x_{k})\,P_{n,k}(x)$

quod erat demonstrandum

Example

$x$	0	1	2	3
$f(x)$	4	1	7	28

$L_{3}(x)=4\,{\frac {(x-1)(x-2)(x-3)}{(0-1)(0-2)(0-3)}}+1\,{\frac {(x-0)(x-2)(x-3)}{(1-0)(1-2)(1-3)}}+7\,{\frac {(x-0)(x-1)(x-3)}{(2-0)(2-1)(2-3)}}+28\,{\frac {(x-0)(x-1)(x-2)}{(3-0)(3-1)(3-2)}}$.

Error Estimation

Theorem. Let $f(x)\in C^{\left(n+1\right)}\left[a,b\right]$ for $a\leq x_{0}<x_{1}<\dots <x_{n}\leq b$.

$f(x)-L_{n}(x)=(x-x_{0})\,(x-x_{1})\dots (x-x_{n})\,{\frac {f^{\left(n-1\right)}(\xi )}{\left(n+1\right)!}}\,\!$

Proof. Let $g(t)=f(t)-L_{n}(t)-(f(x)-L_{n}(x))\,{\frac {(t-x_{0})(t-x_{1})\dots (t-x_{n})}{(x-x_{0})(x-x_{1})\dots (x-x_{n})}}$. This function is special because $g(x)=0$ and $g(x_{k})=0$. Hence there are $n+2$ roots, and it is $(n+1)$-differentiable. Let's compute that derivative:

$g^{(n+1)}(t)=f^{(n+1)}(t)-{\frac {f(x)-L_{n}(x)}{(x-x_{0})(x-x_{1})\dots (x-x_{n})}}\,(n+1)!$

We know $g^{(n+1)}(t)$ has a zero at some $\xi \in \left[a,b\right]$. To solve for it, we set $0=f^{(n+1)}(\xi )-{\frac {f(x)-L_{n}(x)}{(x-x_{0})(x-x_{1})\ldots (x-x_{n})}}\,(n+1)!$. Therefore our desired equation follows

quod erat demonstrandum