MATH 417 Lecture 3

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

Fixed Point Algorithm

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

If $x\in \left[a,b\right]$ , then $g(x)\in \left[a,b\right]$ (for all $x\in \left[a,b\right]$ )
$\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}}$

$g(x)\in \left[{\frac {1}{\sqrt {3}}},{\sqrt {\frac {\mathrm {e} }{3}}}\right]\subset \left[0,1\right]$
$\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 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 \to p} as 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 \to \infty} .

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

quod erat demonstrandum

Note: We can choose any precision we want. The closer we get to 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} , the faster Newton's method converges. However, we have to choose the right starting value 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_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 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_{-1}} , generally start out with 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 \left( p_{-1}, p_0 \right) = \left( a,b \right)} .

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+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 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} at 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} With the slope of the line between 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} 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 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.

start with 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_L} 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 p_R} (assumed to be on either side of the root).
use secant method to generate a candidate point 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} .
If 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(p_L) \cdot f(p_n) < 0} , then 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_L} 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 p_n} are on either side of the root, so we accept 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_R := p_n} as our new right endpoint.
Otherwise, if 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(p_L) \cdot f(p_n) > 0} , then they are both on the same side of the root, but 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} is a better left approximation than 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_L} , so we accept 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_L := p_n} as our new left endpoint.

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