MATH 417 Lecture 3

« previous | Tuesday, January 21, 2014 | next »

Fixed Point Algorithm

To solve for $f(x)=0$ for $x\in \left[a,b\right]$, we first write $x=g(x)$ and evaluate $p_{n+1}=g(p_{n})$ for $n=1,2,\ldots$, where $p_{0}$ is an initial guess.

Conditions

1. If $x\in \left[a,b\right]$, then $g(x)\in \left[a,b\right]$ (for all $x\in \left[a,b\right]$)
2. $\max {\left|g'(x)\right|}\leq k<1$ for $x\in \left[a,b\right]$.

If both conditions are met, then $\left|p_{n}-p\right|\leq k^{n}\,\max {\left(p_{0}-a,b-p_{0}\right)}$

Example 1

${\begin{aligned}x^{3}-2x-5&=0\\-2x&=5-x^{3}\\x&=-5/2+1/2*x^{3}\end{aligned}}$ Doesn't satisfy first condition: $g\in \left[{\frac {3}{2}},11\right]$ Or the second condition: $g'(x)\geq 6$ (the distance between $p$ and $p_{n}$ is always 6 times larger than $p_{n-1}$)

${\begin{aligned}x^{3}&=2x+5\\x&={\sqrt[{3}]{2x+5}}\end{aligned}}$ First condition holds: $g\in \left[{\sqrt[{3}]{9}},{\sqrt[{3}]{11}}\right]$ Satisfies second condition: $g'(x)\leq {\frac {2}{3}}\,\left(2x+5\right)^{-{\frac {2}{3}}}={\frac {2}{3^{\frac {7}{3}}}}$ For $p_{0}={\frac {5}{2}}$ (midpoint), then we can get 3 digits of precision in 4 steps.

${\begin{aligned}x(x^{2}-2)&=5\\x^{2}-2&={\frac {5}{x}}\\x&={\sqrt {2+{\frac {5}{x}}}}\end{aligned}}$ Nasty, but it works...

Example 2

$f(x)=\mathrm {e} ^{x}-3x^{2}$

$f(0)=1$ and $f(1)=\mathrm {e} -3<0$

So find a root on $x\in \left[0,1\right]$

$x={\frac {1}{\sqrt {3}}}\,\mathrm {e} ^{\frac {x}{2}}$

1. $g(x)\in \left[{\frac {1}{\sqrt {3}}},{\sqrt {\frac {\mathrm {e} }{3}}}\right]\subset \left[0,1\right]$
2. $\left|g'(x)\right|={\frac {1}{2{\sqrt {3}}}}\,\mathrm {e} ^{\frac {x}{2}}\leq {\frac {1}{2}}\,{\sqrt {\frac {\mathrm {e} }{3}}}$

Section 2.3: Newton's Method

One of the best methods used to date

Can we do better than bisection or fixed point?

Only works if $f(x)$ is continuous, monotone, and concave up/down...

Given $p_{0}$ on one side of $p$ and $f(p_{n})$, Compute $f_{t}(x)$, the line tangent to $f$ at $x$:

${\begin{aligned}y&=f(p_{n})+f'(p_{n})\,(x-p_{n})\\x&=p_{n}-{\frac {f(p_{n})}{f'(p_{n})}}\end{aligned}}$

Use the second equation to find where $f_{t}(x)$ intersects the $x$-axis and use that number as the next value in the iteration: $p_{n+1}=p_{n}-{\frac {f(p_{n})}{f'(p_{n})}}$.

However, if $f'(p_{n})\approx 0$, then our estimate will not get us very close to the root.

Convergence

Theorem. Assume $f\in C^{2}\left[a,b\right]$, $f(x)=0$ for some $x\in \left[a,b\right]$, and $f'(x)\neq 0$ for all $x\in \left[a,b\right]$. Then there exists a $\delta >0$ such that if $p_{0}\in \left(p-\delta ,p+\delta \right)$, then $p_{n}\to p$ as $n\to \infty$.

Proof. Newton's method is a fixed point method with $g(x)=x-{\frac {f(x)}{f'(x)}}$. Hence $g'(x)={\frac {f(x)\,f''(x)}{(f'(x))^{2}}}$. When $x=p$, we get $g'(p)={\frac {f(p)\,f''(p)}{(f'(p))^{2}}}=0$ because $f(p)=0$. We have $g'(x)$ continuous and equal to 0 at a point, therefore, there exists a $\delta >0$ such that for any $\epsilon >0$, there exists a $\delta >0$ (depending only on $\epsilon$) such that $\left|g'(x)-g'(p)\right|=\left|g'(x)\right|<\epsilon$ when $x\in \left(p-\delta ,p+\delta \right)$

quod erat demonstrandum

Note: We can choose any precision we want. The closer we get to $p$, the faster Newton's method converges. However, we have to choose the right starting value $p_{0}$

Variations/Improvements on Newton's Method

Secant Method

Instead of using a tangent line, we use a secant line between two consecutive approximations.

This requires only one function evaluation at each step.

(need $p_{-1}$, generally start out with $\left(p_{-1},p_{0}\right)=\left(a,b\right)$.

$p_{n+1}=p_{n}-f(p_{n})\,{\frac {p_{n}-p_{n-1}}{f(p_{n})-f(p_{n-1})}}$

Observe that the fractional part of the second term approximates the derivative of $f$ at $p_{n}$ With the slope of the line between $p_{n}$ and $p_{n+1}$. Hence the name secant method.

False Position Method

Uses same approximation as a Secant method, but tests the new point before accepting it to ensure that the root is always surrounded between endpoints.

1. start with $p_{L}$ and $p_{R}$ (assumed to be on either side of the root).
2. use secant method to generate a candidate point $p_{n}$.
3. If $f(p_{L})\cdot f(p_{n})<0$, then $p_{L}$ and $p_{n}$ are on either side of the root, so we accept $p_{R}:=p_{n}$ as our new right endpoint.
4. Otherwise, if $f(p_{L})\cdot f(p_{n})>0$, then they are both on the same side of the root, but $p_{n}$ is a better left approximation than $p_{L}$, so we accept $p_{L}:=p_{n}$ as our new left endpoint.

Always converges for concave-up or concave-down function.