MATH 417 Lecture 4

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

Error Estimation

Ideally, we have $err_{n}=\left|p_{n}-p\right|\to 0$ as $n\to \infty$. However

With bisection, we have ${\frac {err_{n+1}}{err_{n}}}\to {\frac {1}{2}}$

With fixed point iteration, we have $\left|p_{n+1}-p\right|=\left|g(p_{n})-g(p)\right|=\left|g'(\xi )\right|\,\left|p_{n}-p\right|$, so $\left|{\frac {p_{n+1}-p}{p_{n}-p}}\right|=\left|g'(\xi )\right|\to g'(p)$

In both cases, the error ratio is greater than 0. It would be very nice if it converges to 0.

Definition

If $\lim _{n\to \infty }{\frac {\left|p_{n+1}-p\right|}{\left|p_{n}-p\right|^{\alpha }}}=\lambda >0$, then the convergence order of $p_{n}\to p$ is $\alpha$.

• ${\frac {1}{2^{n}}}$ is 1^st-order
• ${\frac {1}{2^{2^{n}}}}$ is 2^nd-order
• ${\frac {1}{2^{2^{2^{n}}}}}$ is 3^nd-order

For example, the following is an order-2 sequence:

$e_{n}=\left|p_{n}-p\right|={\frac {1}{2^{2^{n}}}}$

If $e_{0}=1$, then $e_{1}={\frac {1}{4}}$, $e_{2}={\frac {1}{16}}$, $e_{5}={\frac {1}{2^{32}}}$, $e_{10}={\frac {1}{2^{1024}}}$

Hence $\alpha =2$ and by the definition above, $\lambda =1$.

Newton's method is one such order-2 sequence.

Analysis of Quiz Problem

$f(x)=x^{3}-22x-14$o

Using Newton's method, $g(x)=x-{\frac {f(x)}{f'(x)}}$, so

$p_{n+1}=p_{n}-{\frac {p_{n}^{3}-22p_{n}-14}{3p_{n}^{2}-22}}$

To analyze, we find $g'(x)={\frac {\mbox{blah}}{\left(3x^{2}-22\right)^{2}}}$, but more importantly, $g'(p)=0$!

If we compute $g''(x)={\frac {\mbox{blah}}{\left(3x^{2}-22\right)^{3}}}$, we find $g''(x)$ is bounded above by some $M$ and bounded below by $0$ because the function is concave-up.

Taylor series expansion of $g(x)$ centered at p:

$g(x)=g(p)+{\cancel {(x-p)\,g'(p)}}+(x-p)^{2}\,{\frac {g''(\xi _{n})}{2!}}$

If we take $x=p_{n}$, we find $\xi _{n}$ is between $p_{n}$ and $p$

Solving for $p_{n+1}-p$ yields

$p_{n+1}-p=0+(p_{n}-p)^{2}\,{\frac {g''(\xi _{n})}{2}}$

Hence ${\frac {\left|p_{n+1}-p\right|}{\left|p_{n}-p\right|^{2}}}={\frac {1}{2}}\left|g''(\xi _{n})\right|$

Analysis of Newton's Method

So far we have assumed that $f'(p)\neq 0$

If $f$ is smooth, then Newton's method is 2^nd order convergent (if it works)

If $f'(p)=0$, then $p_{n+1}=p_{n}-{\frac {f(p_{n})}{f'(p_{n})}}$ converges to $p=p-{\frac {f(p)}{f'(p)}}$, which seems impossible because we would be dividing by zero, but in practice we never reach this point computationally.

In this case, Newton's method becomes a 1^st-order convergent method.