MATH 417 Lecture 2

« previous | Thursday, January 16, 2014 | next »

Floating Points

64 bits

0	1	0	0	0	0	0	0	0	0	1	1	1	0	1	1	1	0	0	1	0	0	0	1	0	...	0
$s$ (sign)	$c$ (exponent; 11 bits)											$f$ (fractional part; 52 bits)

$x={(-1)}^s{2}^{c-1023}(1+f)$

Bisection Algorithm

Binary search for a zero point between $a$ and $b$ by checking sign of midpoints.

Section 2.2: Fixed Point Iteration

Banach 1923

Given equation $f(x)=0$, rewrite as a function $x=g(x)$

For example $x^2-x-2=0$ is rewritten as $x=x^2-2$.

1. Take $p_0\in [a,b]$
2. Iterate: $p_{n+1}=g(p_n)$ for $n=0,1,2,\dots$

if $p_n$ converges to $p^{*}$ as $n\to \mathrm{\infty }$, then $p^{*}$ is a fixed point such that $f(p^{*})=0$.

This is only useful if you know an interval where a fixed point must exist.

e.g. choosing $p_0=5$ causes the iteration to diverge to $\mathrm{\infty }$.

Theorem 2.3

Given $x=g(x)$, where $x\in [a,b]$ and $g$ is continuous on $[a,b]$,

1. If $g(x)\in [a,b]$ for any $x\in [a,b]$, then there exists a $p$ such that $g(p)=p$.
2. If there exists a $k<1$ such that $|g^{\prime }(x)|\le k$ for all $x\in [a,b]$, then $p$ is unique.

Proof.

1. Rolle's Theorem with $f(x)=x-g(x)$.
   1. If $g(a)=a$ or $g(b)=b$, we're done.
   2. Otherwise, $(g(a)-a)(g(b)-b)\ne 0$, then by Rolle's theorem, $f(x)=0$ for some $x\in [a,b]$.
2. Assume that $p\ne q$ are both fixed points. Then $|p-q|=|g(p)-g(q)|=|g^{\prime }(\zeta )(p-q)|=|g^{\prime }(\zeta )||p-q|<|p-q|$. Contradiction.

quod erat demonstrandum

Example

$f(x)=x^3+4x^2-10=0$. Find zero $x^{*}\in [1,2]$:

• $f(1)<0$
• $f(2)>0$
• $f^{\prime }(x)=3x^2+8x>0$ for $x\in [1,2]$

Find a $g(x)$...

"Stupid change": $x=x-x^3-4x^2+10$ ($p_4\approx 10^8$). This is because $g(x)=x^3-4x^2+x+10$ is not within $[a,b]$.

Another try: $x=\sqrt{\frac{10-x^3}{4}}$. May work, but prof. doesn't like it.

Yet another try: $x=\sqrt{\frac{10}{x+4}}$. Observe this function is within $[a,b]$. More importantly, $|g^{\prime }(x)|=\frac{\sqrt{5}}{\sqrt{2}{(x+4)}^{\frac{3}{2}}}<1$ for $x=1$. In fact, $k=\frac{1}{5\sqrt{2}}$. Therefore, $p_{n+1}=\frac{\sqrt{10}}{\sqrt{p_n+4}}$ will converge:

Theorem. If $g\in C[a,b]$; $|g^{\prime }(x)|\le k<1$ for all $x\in [a,b]$; $p_0$ is any number in $[a,b]$; and $p_{n+1}=g(p_n)$, then

1. $|p_n-p|\le k^n\cdot \max (p_0-a,b-p_0)$ for $n=0,1,\dots$
2. $|p_n-p|\le \frac{k^n}{1-k}|p_1-p_0|$

Proof.

$|p_n-p|=|g\left(p_{n-1}\right)-g\left(p\right)|=\left|g^{\prime }\left(\zeta \right)\right||p_{n-1}-p|\le k|p_{n-1}-p|$

After $k$ interations, we have $|p_n-p|\le k^n|p_0-p|\le k^n\max (p_0-a,b-p_0)$. This proves (1).

Now if we have $m>n$, then $\begin{array}{rl}|p_m-p_n|& =|p_m-p_{m-1}+p_{m-1}-p_{m-2}+p_{m-2}-\dots -p_{n+1}+p_{n+1}-p_n|\\ & \le |p_m-p_{m-1}|+|p_{m-1}-p_{m-2}|+\dots +|p_{n+1}-p_n|\end{array}$

For any consecutive $p_{j+1}$ and $p_j$, we get

$|p_{j+1}-p_j|=|g(p_j)-g(p_{j-1}|=|g^{\prime }(\zeta )||p_j-p_{j-1}|\le k|p_j-p_{j-1}|\le \dots \le k^j|p_1-p_0|$

Thus the distance above can be better estimated as

$\begin{array}{rl}|p_m-p_n|& =k^{m-1}|p_1-p_0|+k^{m-2}|p_1-p_0|+\dots +k^n|p_1-p_0|\\ & =k^n|p_1-p_0|(1+k+k^2+\dots +k^n+\dots )\\ & =\frac{k^n}{1-k}|p_1-p_0|\end{array}$

This proves (2).

quod erat demonstrandum

In many cases (for good guesses), the second estimate will be better than the first

Goal

$|p_n-p|\le \text{estimate}$