The Newton-Raphson Method

The Newton-Raphson method (often shorted to Newton's method) is an algorithm for approximating the roots of a real-valued function.

The method is quite simple, relying upon successive tangent line approximations. Let $d$ be a zero of the function $f$, and assume that $f$ is differentiable on an open interval containing $d$. Pick a value $c_0$ that is believed to be close to $d$, compute the tangent line approximation at $c_0$, and compute the root of this tangent line. Call the root $c_1$. $c_1$ is our new approximation for $d$. Again, we determine the tangent line approximation for $c_1$, and compute the root of this tangent line, calling it $c_2$. We stop when $c_{i+1} - c_i < \epsilon$, where $\epsilon$ is a small value representing how close we would like our approximation to be to $d$.

There are two conditions to watch out for. First, if $f(c_i) = 0$, we have found a zero, and are done. Second, if the tangent line approximation for $c_i$ is horizontal (e.g., 0 slope), we are done; Newton's method is unable to determine the root. In such a case, we might try a different starting guess for $c_0$, and see if we have better luck.

Also, note that the tangent line approximation to $f$ at $c_i$ is given by

$$y = f(c_i) + f'(c_i)(x - c_i)$$

Since we are interested in the root of this line, we set $y = 0$, and solve for $x$, giving

$$\frac{-f(c_i)}{f'(c_i)} + c_i = x$$

Call this formula $r(c)$. Our steps for finding the root of $f$ are thus

1. If $f(c_i)$, STOP. $c_i$ is the root. Otherwise, GOTO STEP 2.
2. if $f'(c_i) = 0$, STOP. Start over, trying a different value for $c_0$.
3. $c_{i+1} = r(c_i)$. If $|c_{i+1} - c_i| < \epsilon$, STOP. $c_{i+1}$ is a good approximation to the root, $d$, of $f$.
4. $c_i = c_{i+1}$. GOTO STEP 1.

Example

Find the root of the polynomial $f(x) = x^3 - 2x - 5$ in the interval $[0, 3]$.

First since $f$ is negative at $0$ and positive at $3$, we know by the Intermediate Value Theorem that a zero exists in this interval. The derivative of $f$ is $3x^2 - 2$, and the root of the tangent line approximation of $f$ at $x$ is given by $$r(x) = \frac{-f(x)}{f'(x)} + x$$

If we choose $x=1$ as our initial guess, we have that

$c$	$f(c)$	$f'(c)$	$n(c)$
1	-6	1	7
7	324	145	4.7655
4.7655	93.693	66.130	3.3487
3.3487	25.854	31.641	2.5316
2.5316	6.1618	17.227	2.1739
2.1739	0.92571	12.178	2.0979
2.0979	0.037445	11.204	2.0946
2.0946	5.4155e-04	11.162	2.0946

Thus, $2.0926$ is a zero to $f$.