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, 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 \det{A_n} = (-1) \prod_{0 \le i < j \le n} (x_i - x_j) \ne 0}

To find 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 L_n} , We construct a polynomial 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 P_{n,k}} that is 0 at all points 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_i} except when 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 = k} , in which case 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 P_{n,k}(x_k) = 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 P_{n,k}(x) = \prod_{i \ne k} \frac{x-x_i}{x_k-x_i}}

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 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

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 L_n(x) = \sum_{k=0}^n f(x_k) \, P_{n,k}(x)}

quod erat demonstrandum

Example

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	3
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(x)}	4	1	7	28

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 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 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(x) \in C^{\left( n+1 \right)}\left[ a,b \right]} 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 a \le x_0 < x_1 < \dots < x_n \le b} .

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(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 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(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 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(x) = 0} and 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(x_k) = 0} . Hence there are 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} 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