next up previous
Next: Stopping Criterion Up: Solutions of Equations Previous: Approximate Numerical Methods

Newton-Raphson Method

The method can be derived in a variety of different ways. Here we use a graphical approcah. We start with an initial guess for the root $r$. Call this initial estimate $x_{0}$. Next we construct the tangent to the curve at $(x_{0}, F(x_{0}))$. Then, we calculate where this tangent crosses the $x$-axis. This provides the next estimate, $x_{1}$, for the root $r$. This is illustrated in Figure 1.3.

Figure 1.3: The tangent at $(x_{0}, F(x_{0}))$ cuts the $x$-axis at $x_{1}$. The tangent at $(x_{1}, F(x_{1}))$ cuts the $x$-axis at $x_{2}$.
\includegraphics [scale=0.7]{numfig3.ps}

The equation of the tangent at $x_{0}$ is

\begin{displaymath}
y - y_{0} = m(x - x_{0}),
\end{displaymath}

where

\begin{displaymath}
y_{0} = F(x_{0}) \hbox{ and } m = F^{\prime}(x_{0}).
\end{displaymath}

Hence,
\begin{displaymath}
y - F(x_{0}) = F^{\prime}(x_{0}) (x - x_{0}).
\end{displaymath} (1.9)

The tangent intersects the $x$-axis at $y=0$ and this value of $x$ gives us our next estimate of the root. Thus,
\begin{displaymath}
x = x_{1} = x_{0} - {F(x_{0})\over F^{\prime}(x_{0})}.
\end{displaymath} (1.10)

Using (1.10) we obtain $x_{1}$. By replacing $x_{0}$ by $x_{1}$ in (1.10) generates $x_{2}$, which could be a better estimate for the root than $x_{1}$. Repeating this process generates a sequence of iterates

\begin{displaymath}
x_{0},\hbox{ }x_{1},\hbox{ }x_{2}, \cdots , x_{n}, \cdots
\end{displaymath}

which possibly converges to the root $r$. Thus,

\begin{displaymath}
x_{n} \rightarrow r \hbox{ as }n \rightarrow \infty.
\end{displaymath}

Knowing $x_{n}$ we can generate $x_{n+1}$ using (1.10) or specifically
\begin{displaymath}
x_{n+1} = x_{n} - {F(x_{n})\over F^{\prime}(x_{n})}
\end{displaymath} (1.11)

This is the Newton-Raphson method for obtaining a root of the function $F$. This is the most widely used practical technique for solving algebraic equations. It has fast convergence and this will be discussed later.

Example 1. .5Consider

\begin{displaymath}
F(x) = x e^{x}-1.
\end{displaymath}

Then using the product rule for differentiating a product

\begin{displaymath}
u^{\prime}v + u v^{\prime},
\end{displaymath}

with $u = x$ and $v=e^{x}$, the derivative of $F$ is

\begin{displaymath}
F^{\prime} = e^{x} + x e^{x} - 0 = (x + 1) e^{x}.
\end{displaymath}

This is positive if $x$ is positive. Now since

\begin{displaymath}
F(0) = - 1, \qquad F(1) = e^{1} - 1 > 0,
\end{displaymath}

there is only one root in the interval $[0,1]$. Then the Newton-Raphson formula is

\begin{displaymath}
x_{n+1} = x_{n} - {(x_{n} e^{x_{n}} - 1)\over (x_{n} + 1)e^{x_{n}}}.
\end{displaymath}

Take as our intial guess $x_{0} = 1$. Probably a better guess would be to take the midpoint of the interval, i.e. $x_{0} = 0.5$. However, if the method converges, the initial guess is not too crucial. The results of the iteration are presented in the table.

Table 1.4: The Newton-Raphson method applied to $F(x) = xe^{x} -1$.
$x_{n}$ $F(x_{n})$ $F^{\prime}(x_{n})$ $x_{n+1}$
1 1.71828 5.43656 0.68394
0.68394 0.35534 3.33701 0.57745
0.57445 0.02872 2.810211 0.56723
0.56723 $ 2.396\times 10^{-4}$ 2.763615 0.567143296
0.567143296 $1.7\times 10^{-8}$ 2.763223 0.567143289

When do we stop the iteration procedure?

Subsections
next up previous
Next: Stopping Criterion Up: Solutions of Equations Previous: Approximate Numerical Methods
Prof. Alan Hood
2000-02-01