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}$.

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

$$y - y_{0} = m(x - x_{0}),$$

where

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

Hence,

$$y - F(x_{0}) = F^{\prime}(x_{0}) (x - x_{0}).$$ (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,

$$x = x_{1} = x_{0} - {F(x_{0})\over F^{\prime}(x_{0})}.$$ (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

$$x_{0},\hbox{ }x_{1},\hbox{ }x_{2}, \cdots , x_{n}, \cdots$$

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

$$x_{n} \rightarrow r \hbox{ as }n \rightarrow \infty.$$

Knowing $x_{n}$ we can generate $x_{n+1}$ using (1.10) or specifically

$$x_{n+1} = x_{n} - {F(x_{n})\over F^{\prime}(x_{n})}$$ (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

$$F(x) = x e^{x}-1.$$

Then using the product rule for differentiating a product

$$u^{\prime}v + u v^{\prime},$$

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

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

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

$$F(0) = - 1, \qquad F(1) = e^{1} - 1 > 0,$$

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

$$x_{n+1} = x_{n} - {(x_{n} e^{x_{n}} - 1)\over (x_{n} + 1)e^{x_{n}}}.$$

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?