:: Newton Raphson Method (N-R Method) ::

m a t h p a g e: : t h e o r y & p r a c t i c e

main menu

equations and simultaneous equations with solution

» EQUATIONS

» SIMULTANEOUS EQUATIONS

» SOLUTIONS

» Differntial Equations

ALGEBRARIC SIMULTANEOUS EQUATIONS -> Newton Raphson Method (N-R Method)

Systems of two simultaneous linear equations in two unknowns

System of three simultaneous linear equations in three unknowns

Nonlinear systems of equations

Newton's Method for Nonlinear Systems

Newton Raphson Method (N-R Method)

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

Cons: a) Need 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 such that

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

(2)	$\begin{displaymath} 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) \end{displaymath}$

where $\xi(x)$ lies between

and $\overline x.$ Since

, with

, gives

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

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

$\begin{displaymath} 0\approx f(\overline x)+(p-\overline x)f'(\overline x) \end{displaymath}$

is a good approximates. Solving for

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

N-R method begins with an estimate

and generates a sequence $\{p_n\}$

$\fbox{$p_n=p_{n-1}-\displaystyle \frac{f(p_{n-1})}{f'(p_{n-1})}n\ge 1\quad p_0\equiv$\ initial guess}$

See Figure 16 for the algorithm.

**Figure 16:** Newton Raphson Algorithm
$\includegraphics[totalheight=4.1in]{newt1.eps}$

Algorithm inputs initial guess , tolerance TOL, maximum iterations

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

Error Analysis by error (for simplicity we assume no round-off errors)

Assume is simple zero and continuous. Then

	$\displaystyle e_{n+1}$	$\textstyle =$	$\displaystyle p_{n+1}-p=p_n-\frac{f(p_n)}{f'(p_n)}-p$
(3)		$\textstyle =$	$\displaystyle e_n -\frac{f(p_n)}{f'(p_n)}=\frac{e_nf'(p_n)-f(p_n)} {f'(p_n)}$

By Taylor's:

$\begin{displaymath} 0=f(p)=f(p_n-e_n)=f(p_n)-e_n f'(p_n)+\frac12 e^2_n f'' (\xi_n) \end{displaymath}$

where $\xi_n$ is between

and

. Rearranging:

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

(5)	$\begin{displaymath} 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 \end{displaymath}$

$% latex2html id marker 10298 $\therefore$$ Quadratic Convergence.

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

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 $\displaystyle \frac12 \vert f''(p)\vert\bigg/\vert f'(p)\vert$ , and $\delta c(\delta)$ converges to .

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

Suppose start N-R Method with 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)$

$\begin{displaymath} \frac12 \vert f''(\xi_0)\vert \bigg/\vert f'(p_0)\vert\le c(\delta) \end{displaymath}$

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$

$% latex2html id marker 10342 $\therefore p_1$$ lies within $\delta$ distance to . 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$ $% latex2html id marker 10350 $\displaystyle \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 and $f'(p)\ne 0\Rightarrow \exists$ a neighborhood of and constant such that if Newton method started in that neighborhood, successive guesses become closer to and satisfy

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

$\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: . $\Box$

Example Efficient Method of computing square root of number:

let and $x=\sqrt{R}$ then

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$