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 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 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 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+1)} -differentiable. Let's compute that derivative:

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 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 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 g^{(n+1)}(t)} has a zero at some 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 \xi \in \left[ a,b \right]} . To solve for it, we set 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 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