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)




  • 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 $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

    (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 $x$ and $\overline x.$ Since $f(p)=0$, with $x=p$, 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 $p$:

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

    N-R method begins with an estimate $p_0$ 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 $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

      $\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 $p_n$ and $p$. 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 $e_n$ 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 $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 $\displaystyle \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)$

    \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 $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$      % 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 $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

    \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: $f'(x)>0$. $\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$