Newton Raphson Method (N-R Method)

Pros: Faster than 2-point methods: the bisection and regula-falsi method are linear, secant method (see 5.5) is superlinear. N-R Method has quadratic convergence.

Cons: a) Need $f'(x)$ or a good approximation to it (in general an approximations will produce less than quadratic speed of convergence).

b) Not guaranteed to always converge.

Problem Statement': Find $x=p$ such that $f(x)=0$

Suppose $f\in C^2[a,b]$. Let $\overline x\in [a,b]$ an approximation to $p$ such that $f'(\overline x)\ne 0$ and $\vert\overline x-p\vert$ is``small.'' Then

$$f(x)=f(\overline x)+(x-\overline x) f'(\overline x)+ \frac{(x-\overline x)^2}{2}f''(\xi(x))+ O(\vert x- \overline x \vert^3)$$ (2)

where $\xi(x)$ lies between $x$ and $\overline x.$ Since $f(p)=0$, with $x=p$, (2) gives

$$0=f(\overline x)+(p-\overline x)f'(x)+ \frac{(p-\overline x)^2}{2}f''(\xi(p)).$$

If $\vert p-\overline x\vert$ is small, $\vert p-\overline x\vert^2$ smaller, and

$$0\approx f(\overline x)+(p-\overline x)f'(\overline x)$$

is a good approximates. Solving for $p$:

$$p\approx \overline x-\frac{f(\overline x)}{f'(\overline x)}$$

N-R method begins with an estimate $p_0$ and generates a sequence $\{p_n\}$

See Figure 16 for the algorithm.

Figure 16: Newton Raphson Algorithm

Algorithm inputs initial guess $p_0$, tolerance TOL, maximum iterations

Step 1: Set $i=1$
Step 2: While $i\le N_0$ do Steps 3 - 6
Step 3: Set $p=p_0-f(p_0)/f'(p_0)$ % to compute $p_i$
Step 4: If $\vert p-p_0\vert<$ TOL then
OUTPUT $p$
STOP
Step 5: Set $i=i+1$
Step 6: Set $p_0=p$    % update $p_0$
Step 7: Output (`Method failed after $N_0$ iterates')
STOP

Error Analysis by error $e_n=p_n-p$     (for simplicity we assume no round-off errors)

Assume $p$ is simple zero and $f''$ continuous. Then

$$e_{n+1} = p_{n+1}-p=p_n-\frac{f(p_n)}{f'(p_n)}-p$$

$$= e_n -\frac{f(p_n)}{f'(p_n)}=\frac{e_nf'(p_n)-f(p_n)} {f'(p_n)}$$ (3)

By Taylor's:

$$0=f(p)=f(p_n-e_n)=f(p_n)-e_n f'(p_n)+\frac12 e^2_n f'' (\xi_n)$$

where $\xi_n$ is between $p_n$ and $p$. Rearranging:

$$% latex2html id marker 1097e_nf'(p_n)-f(p_n)=\frac12f''(\... ...^2_n\quad \mbox {substitute into }(\ref{new2}) \mbox {to get }$$ (4)

$$e_{n+1}=\frac12\frac{f''(\xi_n)}{f'(p_n)}e^2_n\approx\frac12 \frac {f''(p)}{f'(p)} e^2_n = Ce^2_n$$ (5)

$\therefore$ Quadratic Convergence.

Haven't established convergence. Just the rate. By (4), proof is as follows: if $e_n$ small and if $$\frac12 \displaystyle \frac{f''(\xi_n)}{f'(p_n)}$$ is not too large $\Rightarrow e_{n+1}$ will be smaller than $e_n$.

Define $c(\delta)=\frac12\displaystyle \max_{\vert x-p\vert\le\delta} \vert f''(x)\vert\bigg/ \min_{\vert x-p\vert\le \delta}\vert f'(x)\vert,\quad \delta >0$

Select $\delta$ small enough so that denominator is positive, and then if necessary, decrease $\delta$ so that $\delta c(\delta)<1$. This is possible because as $\delta\rightarrow 0$, then $c(\delta)$ converges to $$\frac12 \vert f''(p)\vert\bigg/\vert f'(p)\vert$$, and $\delta c(\delta)$ converges to $0$.

Having fixed $\delta$, set $\rho=\delta c(\delta)$.

Suppose start N-R Method with $p_0$ satisfying $\vert p_0-p\vert\le \delta$. Then $\vert e_0\vert\le \delta$ and $\vert\xi_0-p\vert\le \delta\Rightarrow$ by definition of $c(\delta)$

$$\frac12 \vert f''(\xi_0)\vert \bigg/\vert f'(p_0)\vert\le c(\delta)$$

By (4) $\vert p_1-p\vert=\vert e_1\vert\le e^2_0 c(\delta)=\vert e_0\vert\vert e_0\vert... ...)\le \vert e_0\vert\delta c(\delta)=\vert e_0\vert\rho<\vert e_0\vert\le \delta$

$\therefore p_1$ lies within $\delta$ distance to $p$. Repeating,

$$\begin{eqnarray*} \vert e_1\vert\le \rho\vert e_0\vert\\ \vert e_2\vert\le \r... ...3\vert e_0\vert\\ :\\ \vert e_n\vert\le \rho^n\vert e_0\vert \end{eqnarray*}$$

Since $0\le\rho<1$      $$\lim_{n\to\infty}\rho^n=0\therefore \lim_{n\to\infty}e_n =0$$

Theorem: (Newton) Let $f\in C^2[a,b]$. If $p\in [a,b]$ is simple zero (such that $f(p)=0$ and $f'(p)\ne 0\Rightarrow \exists$ a neighborhood of $p$ and constant $C$ such that if Newton method started in that neighborhood, successive guesses become closer to $p$ and satisfy

$$\vert p_{n+1}-p\vert\le C(p_n-p)^2\quad n\ge 0$$

$\Box$

In some situations Newton Method is guaranteed to converge from any arbitrary starting point:

Theorem 2: If $f\in C^2(R)$, is increasing, convex, and $f(p)=0\Rightarrow p$ is unique and Newton will converge to it from any starting point. $\Box$

Exercise Prove Theorem 2. Hints: Convex means $f''(x)>0\, \forall x$. Increasing means: $f'(x)>0$. You may also use (5). $\Box$

Example Efficient Method of computing square root of number:

let $R>0$     and $x=\sqrt{R}$     then $x^2-R=0$

then Newton Raphson formula yields $x_{n+1}=\displaystyle \frac12 \left(x_n+\frac{R}{x_n}\right)$ (credited to Heron, Greek Engineer circa 100 B.C. - 100 A.D).

$\Box$