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{\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 [0,1]$, 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[0,1]$ and $ϵ>0$, there exists a polynomial $p(x)$ of degree $N(ϵ)$ such that $|f(x)-p(x)|<ϵ$ for all $x\in [0,1]$.

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\ge 0$, given $n+1$ measurements $f(x_0),f(x_1),\dots ,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,\dots ,n$, and $\mathrm{deg}{L}_n\le 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\overrightarrow{x}=\overrightarrow{b}$:

$\left[\begin{array}{ccccc}{x}_0^n& x_0^{n-1}& \dots & x_0& 1\\ x_1^n& x_1^{n-1}& \dots & x_1& 1\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 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{array}\right]\left[\begin{array}{c}{a}_n\\ a_{n-1}\\ ⋮\\ a_1\\ a_0\end{array}\right]=\left[\begin{array}{c}f(x_0)\\ f(x_1)\\ ⋮\\ f(x_{n-1})\\ f(x_n)\end{array}\right]$

There is only one unique solution if and only if $\det A\ne 0$.

Basis.

1. Given one point $x_0$, the determinant is just $1\ne 0$.
2. Given two points $x_0,x_1$, the determinant is $-(x_1-x_0)\ne 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)\ne 0$

Induction. In general, $\det A_n=(-1)\prod _{0\le i<j\le n}(x_i-x_j)\ne 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\ne 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^{(n+1)}[a,b]$ for $a\le x_0<x_1<\dots <x_n\le b$.

$f(x)-L_n(x)=(x-x_0)(x-x_1)\dots (x-x_n)\frac{f^{(n-1)}(\xi )}{(n+1)!}$

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 [a,b]$. To solve for it, we set $0=f^{(n+1)}(\xi )-\frac{f(x)-L_n(x)}{(x-x_0)(x-x_1)\dots (x-x_n)}(n+1)!$. Therefore our desired equation follows

quod erat demonstrandum