MATH 417 Lecture 4

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

Error Estimation

Ideally, we have $er{r}_n=|p_n-p|\to 0$ as $n\to \mathrm{\infty }$. However

With bisection, we have $\frac{er{r}_{n+1}}{er{r}_n}\to \frac{1}{2}$

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

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

Definition

If $\underset{n\to \mathrm{\infty }}{\lim }\frac{|p_{n+1}-p|}{{|p_n-p|}^{\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=|p_n-p|=\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^{\prime }(x)}$, so

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

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

If we compute $g^{″}(x)=\frac{\text{blah}}{{(3x^2-22)}^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^{\prime }(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{|p_{n+1}-p|}{{|p_n-p|}^2}=\frac{1}{2}|g^{″}({\xi }_n)|$

Analysis of Newton's Method

So far we have assumed that $f^{\prime }(p)\ne 0$

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

If $f^{\prime }(p)=0$, then $p_{n+1}=p_n-\frac{f(p_n)}{f^{\prime }(p_n)}$ converges to $p=p-\frac{f(p)}{f^{\prime }(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.