Newton's Method

newton's method is one of the greatest examples of applied differentiation. The method is best illustrated by way of example.

problem. Without a calculator, compute 5.{\sqrt{5}.}

The first step is to express the quantity 5{\sqrt{5}} as an equation:

x2=5 x^2 = 5

Next, we'll want to abstract the equation as a function:

f(x)=x2−5 f(x) = x^2 - 5

Now the question is, what values of x{x} satisfy the following:

f(x)=x2−5=0 f(x) = x^2 - 5 = 0

Plotting the function f(x)=x2−5{f(x) = x^2 - 5} is pretty easy, so let's take a look at that:

Newton's Method

The idea now is to try and estimate 5.{\sqrt{5}.} 5{\sqrt{5}} is close to 4,{\sqrt{4},} which is 2.{2.} So our initial guess, call it x0,{x_0,} will be 2:{2:}

x0=2 x_0 = 2

The next step is to pretend that f(x){f(x)} is linear. We mark where f(2){f(2)} is, and draw a tangent line there. Where the tangent line intersects the {\text{x-axis}} is where our new guess will be:

A tangent line

Notice that by doing this, we've gotten closer to where f(x){f(x)} actually cross the {\text{x-axis}.} This is the key idea behind newton's method. We keep guessing, over and over again, until we eventually reach the desired result.

The equation of the tangent line is:

y−y0=m(x−x0) y - y_0 = m(x-x_0)

In our diagram above, the tangent line is the blue line. Where it crosses the {\text{x-axis}} is a point we'll call x1.{x_1.} We want to find the value of x1.{x_1.} Easy: It's when y=0.{y = 0.}

0−y0=m(x1−x0)−y0m=x1−x0 \begin{aligned} 0 - y_0 &= m(x_1 - x_0) \\[1em] -\dfrac{y_0}{m} &= x_1 - x_0 \end{aligned}

Now we can derive a formula for x1:{x_1:}

−y0m=x1−x0x0−y0m=x1 \begin{aligned} -\dfrac{y_0}{m} &= x_1 - x_0 \\[1em] x_0 - \dfrac{y_0}{m} &= x_1 \end{aligned}

We have our formula for x1:{x_1:}

x1=x0−y0m x_1 = x_0 - \dfrac{y_0}{m}

Now, we know that y0{y_0} is just the function f(x){f(x)} evaluated at x0.{x_0.} We also know that m{m} is the slope of f(x){f(x)} at x0.{x_0.} Thus, the formula, expanded, is:

x1=x0−f(x0)f′(x0) x_1 = x_0 - \dfrac{f(x_0)}{f'(x_0)}

The formula above is what allows us to calculate any root. This formula is so important that we state it a little more formally:

newton's wethod. Let f(x){f(x)} be a function. If f(x){f(x)} is differentiable, then for any point xn{x_n} on f(x),{f(x),} we may approximate f(x){f(x)} by the tangent line to the graph of f(x){f(x)} at the point (xn,f(xn)).{(x_n, f(x_n)).} That is,

f(x)≈f(xn)+f′(xn)(x−xn) f(x) \approx f(x_n) + f'(x_n)(x - x_n)

Hence, if the tangent line is a good approximation to f{f} between xn{x_n} and a zero of f(x),{f(x),} then we may find an approximate zero by solving for:

0=f(xn+1)≈f(xn)+f′(xn)(xn+1−xn) 0 = f(x_{n+1}) \approx f(x_n) + f'(x_n)(x_{n+1} - x_n)

giving:

xn+1=xn−f(xn)f′(xn) x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}

Let's apply the formula. We start with x0=2,{x_0 = 2,} and f(x)=x2−5.{f(x) = x^2-5.} Then, we have f′(x)=2x.{f'(x) = 2x.} Thus:

x1=x0−x02−52x0=x0−(x0)(x0)−52x0=x0−(x0)(x0)−52x0=x0−12x0+52x0=12x0+52x0 \begin{aligned} x_1 &= x_0 - \dfrac{x_0^2 - 5}{2x_0} \\[1em] &= x_0 - \dfrac{(x_0)(x_0) - 5}{2x_0} \\[1em] &= x_0 - \dfrac{\cancel{(x_0)}(x_0) - 5}{2\cancel{x_0}} \\[1em] &= x_0 - \dfrac{1}{2}x_0 + \dfrac{5}{2x_0} \\[1em] &= \dfrac{1}{2}x_0 + \dfrac{5}{2x_0} \end{aligned}

Plugging in x0=2:{x_0 = 2:}

x1=12x0+52x0=12(2)+52(2)=1+54=44+54=94 \begin{aligned} x_1 &= \dfrac{1}{2}x_0 + \dfrac{5}{2x_0} \\[1em] &= \dfrac{1}{2}(2) + \dfrac{5}{2(2)} \\[1em] &= 1 + \dfrac{5}{4} \\[1em] &= \dfrac{4}{4} + \dfrac{5}{4} \\[1em] &= \dfrac{9}{4} \end{aligned}

Then we can solve for x2{x_2} by plugging in x1=94:{x_1 = \dfrac{9}{4}:}

x2=12x0+52x0=12⋅94+52(94)=12⋅94+52⋅49=98+2018=98+109=(9)(9)+(10)(8)(9)(8)=81+8072=16172 \begin{aligned} x_2 &= \dfrac{1}{2}x_0 + \dfrac{5}{2x_0} \\[1em] &= \dfrac{1}{2} \cdot \dfrac{9}{4} + \dfrac{5}{2 \left(\dfrac{9}{4}\right)} \\[3em] &= \dfrac{1}{2} \cdot \dfrac{9}{4} + \dfrac{5}{2} \cdot \dfrac{4}{9} \\[1em] &= \dfrac{9}{8} + \dfrac{20}{18} \\[1em] &= \dfrac{9}{8} + \dfrac{10}{9} \\[1em] &= \dfrac{(9)(9) + (10)(8)}{(9)(8)} \\[1em] &= \dfrac{81 + 80}{72} \\[1em] &= \dfrac{161}{72} \\[1em] \end{aligned}

Then we can solve for x2{x_2} by plugging in x1=16172:{x_1 = \dfrac{161}{72}:}

x2=12x0+52x0=12⋅16172+52(16172)=12⋅16172+52⋅72161=161144+360322 \begin{aligned} x_2 &= \dfrac{1}{2}x_0 + \dfrac{5}{2x_0} \\[1em] &= \dfrac{1}{2} \cdot \dfrac{161}{72} + \dfrac{5}{2 \left(\dfrac{161}{72}\right)} \\[3em] &= \dfrac{1}{2} \cdot \dfrac{161}{72} + \dfrac{5}{2} \cdot \dfrac{72}{161} \\[1em] &= \dfrac{161}{144} + \dfrac{360}{322} \end{aligned}

On a calculator, 5≈2.2360679775.{\sqrt{5} \approx 2.2360679775.} Comparing our approximations:

n{n}xn{x_n}En=∣5−xn∣{E_n =\lvert \sqrt{5} - x_n \rvert}
0{0}2{2}0.2360679775≈2.4×10−1{0.2360679775 \approx 2.4 \times 10^{-1}}
1{1}94{\dfrac{9}{4}}0.0139320225≈1.4×10−2{0.0139320225 \approx 1.4 \times 10^{-2}}
2{2}16172{\dfrac{161}{72}}0.00004313361≈4.3×10−5{0.00004313361 \approx 4.3 \times 10^{-5}}
3{3}161144+360322{\dfrac{161}{144} + \dfrac{360}{322}}≈4.16×10−10{\approx 4.16 \times 10^{-10}}

Looking at the table, once we're at the second iteration, we're already at such a good approximation of 5{\sqrt{5}} that we don't need to go any further. In fact, most calculators won't even go to the third iteration.

Again, newton's method works by repeatedly bringing the tangent line's intersection with the x{x}-axis closer and closer to the target what we want:

A closer look at Newton's method

As illustrated in the diagram above, notice how close x2{x_2} is to the target, the x{x} value marked with the brown vertical line. The distance En=∣x−xn∣{E_n = \lvert x - x_n \rvert } is the error margin. The distance En+1{E_{n+1}} is roughly (En)2.{(E_{n})^2.} This in turn means that, roughly speaking, the error margin is squared at each iteration of applying the

newton's method (i.e., the number of digits of accuracy doubles at each iteration):

En{E_n}Error
E0{E_0}≈10−1{\approx 10^{-1}}
E1{E_1}≈10−2{\approx 10^{-2}}
E2{E_2}≈10−4{\approx 10^{-4}}
E3{E_3}≈10−8{\approx 10^{-8}}
E4{E_4}≈10−16{\approx 10^{-16}}

There are, however, a few constraints to newton's method. The constraints are as follows:

  1. ∣f′∣{\lvert f' \rvert } must not be small.
  2. ∣f′′∣{\lvert f'' \rvert } must not be too big.
  3. x0,{x_0,} the initial guess, starts nearby x,{x,} the target.