MATH 417 Lecture 3

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

Fixed Point Algorithm

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

Conditions

1. If $x\in [a,b]$, then $g(x)\in [a,b]$ (for all $x\in [a,b]$)
2. $\max |g^{\prime }(x)|\le k<1$ for $x\in [a,b]$.

If both conditions are met, then $|p_n-p|\le k^n\max (p_0-a,b-p_0)$

Example 1

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

$\begin{array}{rl}{x}^3& =2x+5\\ x& =\sqrt[3]{2x+5}\end{array}$ First condition holds: $g\in [\sqrt[3]{9},\sqrt[3]{11}]$ Satisfies second condition: $g^{\prime }(x)\le \frac{2}{3}{(2x+5)}^{-\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{array}{rl}x(x^2-2)& =5\\ x^2-2& =\frac{5}{x}\\ x& =\sqrt{2+\frac{5}{x}}\end{array}$ 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 [0,1]$

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

1. $g(x)\in [\frac{1}{\sqrt{3}},\sqrt{\frac{\mathrm{e}}{3}}]\subset [0,1]$
2. $|g^{\prime }(x)|=\frac{1}{2\sqrt{3}}{\mathrm{e}}^{\frac{x}{2}}\le \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{array}{rl}y& =f(p_n)+f^{\prime }(p_n)(x-p_n)\\ x& =p_n-\frac{f(p_n)}{f^{\prime }(p_n)}\end{array}$

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^{\prime }(p_n)}$.

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

Convergence

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

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

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 $(p_{-1},p_0)=(a,b)$.

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