2. Newton's Method for Solving Equations
by M. Bourne
Computers use iterative methods to solve equations. The process involves making a guess at the true solution and then applying a formula to get a better guess and so on until we arrive at an acceptable approximation for the solution.
If we wish to find x so that `f(x) = 0` (a common type of problem), then we guess some initial value x0 which is close to the desired solution and then we get a better approximation using Newton's Method:
[This is just based on the point-slope form of a straight line].
Find the root of
2x2 − x − 2 = 0
between `1` and `2`.
The graph is as follows:
Try x0 = 1.5
` = 1.5-(f(1.5))/(f’(1.5))`
Now f(1.5) = 2(1.5)2 − 1.5 − 2 = 1
f '(x) = 4x − 1 and f '(1.5) = 6 − 1 = 5
So `1.3` is a better approximation.
Continuing the process,
` = 1.3- (f(1.3))/(f’(1.3))`
` = 1.3-0.08/4.2`
We can continue for as many steps as necessary to give the required accuracy.
Check: Using some Computer Algebra Systems, (eg Mathcad) we also need to give an initial guess (say, x = 2) and the result is:
root(2x2 − x − 2, x) = 1.2807764064044
The software just keeps applying the algorithm until the decimal digits don't change any more. It then returns the answer.
This example has another root, which is negative.
You can explore this example further in Newton's Method Interactive Graph.
Non-polynomial Functions with Multiple Roots
When using a computer to find roots of more complicated functions it's best to understand what is going on and give the computer a guess close to your desired answer.
Solve 1− t2 + 2t = 0
[Certain math software is not able to find the solution directly for us. We need to know how to properly use the tool to get the solution, either with graphs or setting up Newton's Method. This could involve giving an initial estimate for the root.]
Let y = 1− t2 + 2t
The graph of `y(t)`:
There appear to be 2 roots, one near t = −1 and the other near t = 3. However, if we look more carefully in the region near t = 3 (by zooming in), we see that there is more than one root there.
By simple substitution, we can see that one of the roots is exactly t = 3:
1 − (3)2 + 23 = 0
Now for the root near t = 3.4.
We will use Newton's Method to approximate the root. We need to differentiate y = 1− t2 + 2t. Since we have t as an exponent in our expression, we need to use logarithms when differentiating. [See how to differentiate logarithms in Derivative of the Logarithmic Function].
Let's differentiate 2t by itself first.
Let h = 2t.
Take natural log of both sides:
`ln\ h=t\ ln\ 2`
`1/h (dh)/dt=ln\ 2`
`(dh)/(dt)=h\ ln\ 2=2^t\ ln\ 2`
`(dy)/(dt)=f'(t)=-2t+2^t\ ln\ 2`
So for Newton's Method in this example, we would have:
`(f(t))/(f'(t))=(1-t^2+2^t)/(-2t+2^t ln\ 2)`
Initial guess: t0 = 3.4
`t_1=3.4-(f(t))/(f'(t)) -` ` (1-3.4^2+2^3.4)/(-2(3.4)+2^3.4 ln\ 2) ` `= 3.407615918`
We can write this more conveniently (for later steps) showing the substitution as:
`t_1=3.4-[(1-t^2+2^t)/(-2t+2^t ln\ 2)]_(t=3.4)` `=3.407615918`
Now, doing another step of Newton's Method:
`t_2` `=3.407615918-` `[(1-t^2+2^t)/(-2t+2^t ln\ 2)]_(t=3.407615918)` `=3.407450596`
And doing another step:
`t_3` `=3.407450596-` `[(1-t^2+2^t)/(-2t+2^t ln\ 2)]_(t=3.407450596)` `=3.407450522`
`t_4` `=3.407450522-` `[(1-t^2+2^t)/(-2t+2^t ln\ 2)]_(t=3.407450522)` `=3.407450505`
We can conclude that correct to 7 decimal places, t = 3.4074505.Using Graphs Instead
Using a computer algebra system, we can zoom into the root and we can see (from where the graph cuts the y-axis) that t is indeed close to `3.40745`.
Now for the negative case. Let t0 = −1 be our initial guess.
`t_1` `=-1-[(1-t^2+2^t)/(-2t+2^t ln\ 2)]_(t=-1)` `=-1.213076633`
`t_2` `=-1.213076633-` `[(1-t^2+2^t)/(-2t+2^t ln\ 2)]_(t=-1.213076633)` `=-1.198322474`
`t_3` `=-1.198322474-` `[(1-t^2+2^t)/(-2t+2^t ln\ 2)]_(t=-1.198322474)` `=-1.198250199`
We could continue until we obtained the required accuracy.
Comparing this to the zoomed in graph, we can see that the solution is t = −1.198250197, correct to 9 decimal places.
So the solutions for 1− t2 + 2t = 0 are
t = −1.19825,
t = 3, or
t = 3.40745,
correct to 5 decimal places.
Solve 3x3 − 9x2 + 5x + 2 = 0 using Newton's Method.
We'll learn in the Curve Drawing section that a cubic curve can have either:
- One real root;
- Two real roots (one of them repeated); or
- Three distinct roots
The best thing to do is to sketch the curve, but let's assume that's too hard for now. We can determine where at least one of the roots occurs by substituting values of `x` until we see a change in the sign for `y` (which would indicate the curve must have passed through the `x`-axis in that interval).
Starting at `x=0`, we find that `y=2`, which is positive.
Next, try `x=1`, and we get `y=1`, which is still positive. (Of course, the curve could have dipped below the `x`-axis between `0` and `1`, but without a sketch, we don't know.)
Try `x=2` and we get `y=0`. This is a lucky guess, and gives us one of the roots.
Trying more positive values (`x=3,4,5...`) gives us larger and larger values for `y` (which are `17,70,177,...`), so we are clearly moving away from the root.
We continue to stumble around in the dark, and assume maybe there is a root near `x=1`. Let's try the algorithm with `x_0=1` and see what happens.
We'll need the derivative:
`dy/dx = 9x^2-18x+5`
` = 1-(f(1))/(f’(1))`
` = 1-1/(-4)`
` = 1.25`
` = 1.25-(f(1.25))/(f’(1.25))`
` = 1.26363636363`
Continuing on we get:
x3 = 1.26376260461638
x4 = 1.26376261582597
x5 = 1.26376261582597
x6 = 1.26376261582597
Since there is no more change to our value, we can assume we've found the second root, at `x=1.26376261582597`.
You can use the interactive graph applet to find the third root.
Solve x2 = 0 using Newton's Method.
Of course, we can easily solve this one by inspection.
But I've included it because it illustrates a case when Newton's Method is not very efficient.
Newton's Method works well when the slope of the line is reasonably steep, but in cases where it's quite flat near the root (similar to Example 2 above), it does not converge very quickly.
(You can investigate this example in the interactive graph applet.)
In fact, even after 12 steps of the method, we are still not very close to the root.
Let's start at `x=-4`.
`dy/dx = 2x`
` = -4-(f(-4))/(f’(-4))`
` = -4-16/(-8)`
` = -2`
` = -2-(f(-2))/(f’(-2))`
` = -2-4/(-4)`
` = -1`
Continuing on we get:
x3 = -0.5
x4 = -0.25
x5 = -0.125
x6 = -0.0625
x7 = -0.03125
x8 = -0.015625
x9 = -0.0078125
x10 = -0.00390625
x11 = -0.001953125
x12 = -0.0009765625
Generally, however, Newton's Method is a simple and neat way to find roots of equations. It is commonly used (in conjunction with other efficiency algorithms) by computers and calculators.