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=\left(-1\right)^{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 \left[a,b\right]$
2. Iterate: $p_{n+1}=g(p_{n})$ for $n=0,1,2,\ldots$

if $p_{n}$ converges to $p^{*}$ as $n\to \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 $\infty$.

Theorem 2.3

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

1. If $g(x)\in \left[a,b\right]$ for any $x\in \left[a,b\right]$, then there exists a $p$ such that $g(p)=p$.
2. If there exists a $k<1$ such that $\left|g'(x)\right|\leq k$ for all $x\in \left[a,b\right]$, 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)\neq 0$, then by Rolle's theorem, $f(x)=0$ for some $x\in [a,b]$.
2. Assume that $p\neq q$ are both fixed points. Then $\left|p-q\right|=\left|g(p)-g(q)\right|=\left|g'(\zeta )\,(p-q)\right|=\left|g'(\zeta )\right|\,\left|p-q\right|<\left|p-q\right|$. Contradiction.

quod erat demonstrandum

Example

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

• $f(1)<0$
• $f(2)>0$
• $f'(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 $\left[a,b\right]$.

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 $\left[a,b\right]$. More importantly, $\left|g'(x)\right|={\frac {\sqrt {5}}{{\sqrt {2}}\,\left(x+4\right)^{\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\left[a,b\right]$; $\left|g'(x)\right|\leq k<1$ for all $x\in \left[a,b\right]$; $p_{0}$ is any number in $\left[a,b\right]$; and $p_{n+1}=g(p_{n})$, then

1. $\left|p_{n}-p\right|\leq k^{n}\cdot \max {\left(p_{0}-a,b-p_{0}\right)}$ for $n=0,1,\ldots$
2. $\left|p_{n}-p\right|\leq {\frac {k^{n}}{1-k}}\left|p_{1}-p_{0}\right|$

Proof.

$\left|p_{n}-p\right|=\left|g\left(p_{n-1}\right)-g\left(p\right)\right|=\left|g'\left(\zeta \right)\right|\,\left|p_{n-1}-p\right|\leq k\,\left|p_{n-1}-p\right|$

After $k$ interations, we have $\left|p_{n}-p\right|\leq k^{n}\left|p_{0}-p\right|\leq k^{n}\,\max {\left(p_{0}-a,b-p_{0}\right)}$. This proves (1).

Now if we have $m>n$, then ${\begin{aligned}\left|p_{m}-p_{n}\right|&=\left|p_{m}-p_{m-1}+p_{m-1}-p_{m-2}+p_{m-2}-\ldots -p_{n+1}+p_{n+1}-p_{n}\right|\\&\leq \left|p_{m}-p_{m-1}\right|+\left|p_{m-1}-p_{m-2}\right|+\dots +\left|p_{n+1}-p_{n}\right|\end{aligned}}$

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

$\left|p_{j+1}-p_{j}\right|=\left|g(p_{j})-g(p_{j-1}\right|=\left|g'(\zeta )\right|\,\left|p_{j}-p_{j-1}\right|\leq k\left|p_{j}-p_{j-1}\right|\leq \dots \leq k^{j}\left|p_{1}-p_{0}\right|$

Thus the distance above can be better estimated as

${\begin{aligned}\left|p_{m}-p_{n}\right|&=k^{m-1}\left|p_{1}-p_{0}\right|+k^{m-2}\left|p_{1}-p_{0}\right|+\dots +k^{n}\left|p_{1}-p_{0}\right|\\&=k^{n}\left|p_{1}-p_{0}\right|\left(1+k+k^{2}+\dots +k^{n}+\dots \right)\\&={\frac {k^{n}}{1-k}}\left|p_{1}-p_{0}\right|\end{aligned}}$

This proves (2).

quod erat demonstrandum

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

Goal

$\left|p_{n}-p\right|\leq {\mbox{estimate}}$