11.2: Newton's Method

For a general function $f(x)$ it may be difficult to find a solution to $f(a) = 0$. However, if $f(x) = b + mx$ is a linear function, then we may solve for $0 = f(a) = b + ma$ as $a := \frac{-b}{m}$.

Newton's method is a way to solve for $f(a) = 0$ by approximating $f(x)$ by a linear function.

Newton's method: the theory

If $f(x)$ is differentiable, then for any point $c$ we may approximate $f(x)$ by the tangent line to the graph of $f$ at $\langle c, f(c) \rangle$. That is,

$$f(x) \approx f(c) + f'(c) (x - c)$$

So, if the tangent line is a good approximation to $f$ between $c$ and a zero of $f$, then we may find an approximate zero by solving for $0 = f(a) \approx f(c) + f'(c) (a - c)$ giving $a = c - \frac{f(c)}{f'(c)}$. (The attribution of this method to Raphson is incorrect.)

Newton's method: the algorithm

Given: A differentiable function $f(x)$.

Goal: Find a solution (or an approximate solution) to $f(a) = 0$.

Process: Step 0: Guess an approximate zero $x_0$ and set $d := x_0$.

Step 1: Compute $f(d)$. If $f(d)$ is close enough to zero for you, then set $a = d$ and quit.

Step 2: Compute $f'(d)$. If $f'(d) = 0$, then this method fails. Go back to step 0.

Step 3: Approximate $f(x) \approx f(d) + f'(d) (x - d)$. Set the approximation equal to zero and solve for $x$ finding $x := d - \frac{f(d)}{f'(d)}$. If this is the $n^\text{th}$ iteration of this process, call this number $x_n$. Reset $d := x_n$ and return to step 1.

(More on Newton's method.)

Example

Find a solution to $0 = f(x) = x^6 - 5 x^2 + x + 1$.

A solution

We compute $f'(x) = 6x^5 - 10x + 1$.

$i$	$x_i$	$f(x_i)$	$f'(x_i)$
$0$	$-1$	$-4$	$-5$
$1$	$-0.20000$	$0.60007$	$2.99808$
$2$	$-0.40015$	$-0.19664$	$4.93994$
$3$	$-0.36034$	$-0.00739$	$4.56698$
$4$	$-0.35873$	$-0.00001$	$4.55161$
$5$	$-0.35872$	$\approx 2 \times 10^{-10}$	$4.55158$

(Graphs)

Difficulties with the method

• If $f'(x_0) = 0$, then the method fails completely.

• If there is a point $c$ for which $f'(c) = 0$ but $f(c) \approx 0$, then by choosing $x_0 \approx c$, even if the process converges, then it may take many steps.

• If there are many solutions to $f(x) = 0$, then this process may produce a solution far away from the initial guess, and not necessarily the nearest zero.

(Demonstration)

Another Example

Use Newton's method to approximate $\sqrt[3]{7}$.

Let $f(x) = x^3 - 7$. (So that $f'(x) = 3 x^2$.) We wish to find $a$ with $f(a) = 0$.

Start with $x_0 = 2$. Then $x_1 = 2 - \frac{1}{12} = \frac{23}{12}$. We compute $(\frac{23}{12})^3 - 7 \approx 0.04$. The next approximation is $x_2 = \frac{18215}{9522} \approx 1.912938458$ while $(\frac{18215}{9522})^3 - 7 \approx 0.00008$.

A final example

Find a solution to $e^x = 2x + 1$.

Solution

Here $f(x) = e^x - 2x - 1$ so that $f'(x) = e^x - 2$. If we start with $x_0 = 1$, then

$x_1 \approx 1.39221$, $x_2 \approx 1.27396$, $x_3 \approx 1.25678$, $x_4 \approx 1.25643$, $x_5 \approx 1.25643$.

(Note: There is another zero: $f(0) = 0$!)