Root finding methods

We describe a few methods to find the roots of an equation. We usually apply one of these methods when each algebraic method has left us in the lurch.

Bisection method.

When f(x) is continuous in the environment of a single root r, then f(x) changes sign through r. There is a small interval [a,b] including r such that f(a).f(b) < 0. Taking the midpoint m of [a,b], there are three possibilities. Now we can restart the procedure with the smaller interval [a,m] or [m,b]. The interval becomes smaller and smaller, so we can find an approximation of the root r.

Example:

The equation 
 
        t3  + 4 t2  - 1 = 0
has a positive root r in [0,1]. f(0)<0 and f(1)>0.
Since f(0.5) = 0.125 the root is in [0, 0.5].
Since f(0.25) = -0.73 the root is in [0.25, 0.5].
Since f(0.375) = -0.38 the root is in [0.375, 0.5].
Since f(0.4375) = -0.15 the root is in [0.4375, 0.5].
Since f(0.46875) = -0.018 the root is in [0.46875, 0.5].
Since f(0.484375) = 0.05 the root is in [0.46875, 0.484375].
... and so we approach the root 0.472834 It is superfluous to say that it is easy to computerize this method. Then we have the root in less than a second.

Newton's method.

Say f(x) is differentiable in the environment of a root r and ro is a first approximation of the root r. Now point P(ro,f(ro)) is on the curve of the function. The slope of the tangent line in P is f'(ro). This tangent line intersects the x-axis in a point with a x-value r1. The value r1 is a better approximation of the root than ro. From r1 you can find a better approximation r2. ...

Formula

The equation of the tangent line in point P is 
 
        y - f(ro) = f'(ro) (x - ro)

        for y = 0 we have

                    f(ro)
        r1 = ro - --------
                    f'(ro)

Example

Take again the equation 
 
        t3  + 4 t2  - 1 = 0
Take to = 0.5 as a first approximation. Then 
 
                    to3 + 4 to2 - 1
        t1 = to - ------------------ = 0.4736842
                    3 to2  + 8 to
Taking t1 as a new approximation we find t2= 0.472834787153
Taking t2 as a new approximation we find t3= 0.472833908996
Taking t3 as a new approximation we find t4= 0.472833908996

You see that this method is a very powerful method to approximate the root.

Again it is superfluous to say that it is easy to computerize this method. Then we have the root in less than a second.

This method requires that the first approximation is sufficiently close to the root r.

Iteration method

Suppose that you can bring an equation g(x)=0 in the form x = f(x). We'll show that you can solve this equation , on certain conditions, using iteration.

Start with an approximation x0 of the root.
Calculate x0,x1,...,xn,... such that x1=f(x0);x2=f(x1);x3=f(x2); ...

Theorem:
If the sequence x0,x1,...,xn, ... belongs to an interval I, where |f'(x)| < k < 1 , then the sequence has a limit L and L is the only root of x=f(x) in the interval I.

Proof:
Appealing on Lagrange's theorem we can write: 

 
x2 - x1 = f(x1) - f(x0) = (x1 - x0).f'(c1) with  c1 between x0 and x1
x3 - x2 = f(x2) - f(x1) = (x2 - x1).f'(c2) with  c1 between x1 and x2
    ...
xn+1-xn = f(xn) - f(xn-1)=(xn - xn-1).f'(cn) with cn between xn and xn-1
Since |f'(x)| < k < 1 
 
|x2 - x1 |   <  k.|x1 - x0|
|x3 - x2 |   <  k.|x2 - x1|
    ...
|xn+1-xn|  <  k.|xn - xn-1|

Multiplying each side

|xn+1-xn|  < kn . |x1 - x0|           (1)

Now

|xn+p-xn| = |xn+p - xn+p-1 + xn+p-1 - xn+p-2 + ...

               + xn+1-xn |

=> |xn+p-xn| =< |xn+p - xn+p-1| + |xn+p-1 - xn+p-2| + ...

               + |xn+1-xn |

 and using (1)

=> |xn+p-xn| < |x1 - x0|.(kn+p-1 + kn+p-2+...+kn)

=> |xn+p-xn| < |x1 - x0|. (kn - kn+p)/(1-k)


=> |xn+p-xn| < |x1 - x0|. kn/(1-k)
Since k<1 is kn/(1-k) smaller than each strictly positive number e if n is sufficiently large and p = 1,2,3, ...

Therefore we conclude with the Criterion of Cauchy that the sequence {xn} converges. Say the limit is L.

 
    xn = f(xn-1)

=> lim xn = lim f(xn-1)

=>    L = f(L)
Thus, L is a root of the equation x = f(x).

If M is a second root of x = f(x) in interval I, then 

 
   M - L = f(M) - f(L) = (M - L).f'(c) with  c in I

Then

     f'(c) = 1  and this gives a contradiction.

Example of the iteration method

We'll solve x = 2 + sin(x)/2.
Here f(x) =2 + sin(x)/2 and f'(x) = cos(x)/2 and the condition |f'(x)| < k < 1 is satisfied for all x.

Starting with x0 = 2 we calculate x1,x2,... 

 
2.45464871341284
2.31708861973148
2.36710557531865
2.34967477062353
2.35585092904743
2.35367483693284
2.35444309931047
2.35417205822186
2.35426770472895
2.35423395542163
2.35424586438903
2.35424166217094
2.35424314497835
2.35424262175115
2.35424280637852
2.35424274123042
2.35424276421875
2.35424275610703
2.35424275896935
2.35424275795934
The root is 2.35424275822278

Another example of the iteration method

We'll solve x.tanh(x)=1.
 
   x = coth(x)

   f(x) = coth(x)

   |f'(x)| = | -1/sinh2(x)| < 1/x2

   |f'(x)| < 1 for x > 1

Starting with x0 = 1   we calculate x1,x2,...

1.31303528549933
1.15601401811395
1.21990402611162
1.19100666638769
1.20352756742564
1.19799585895445
1.20041926080065
1.19935362719156
1.19982145104824
1.19961592438525
1.19970618895035
1.19966654047733
1.19968395490739
1.19967630592522
1.19967966556677
The root is 1.1996786402

Tranformation of an equation

If we try to solve the equation t3 + 4 t2 - 1 = 0 with the iteration method, we can write t = t + t3 + 4 t2 - 1 .

to = 0.5 is a first approximation of the root. But the condition |f'(x)| < k < 1 is not satisfied in the environment of the root.

Therefore, we transform the equation in 

 
    t = t + r.(t3  + 4 t2  - 1)
We can choose the value of r without changing the root. From the theorem above, we know that the convergence is very fast if k has a value near 0. 

 
Here f'(t) = 1 + r.(3t2 + 8t)

Since the root is near 0.5, we choose r = -0.21.

Now f'(t) is near 0 in the environment of the root.

We solve t = t - 0.21(t3  + 4 t2  - 1) starting with t = 0.5

0.47375
0.472892306269531
0.472837688600127
0.472834153854809
0.472833924859327
0.472833910023068
0.472833909061846
0.47283390899957
0.472833908995535
0.472833908995274
0.472833908995257
0.472833908995256

Program for iteration method

You don't need a big program to find the roots of an equation.

Here is the extremely simple Perl program used to calculate the root of x.tanh(x) = 1. 

 
#!/usr/bin/perl

$x = 1;

for $i (1..40) {
  $x = (exp($x)+exp(-$x))/(exp($x)-exp(-$x)) ;
  print $x,"\n";
}
Of course, you can do the same thing in Basic or Pascal or C.

Topics and Problems

MATH-abundance home page - tutorial

MATH-tutorial Index

The tutorial address is http://home.planetinternet.be/~ping1339

Copying Conditions

Send all suggestions and remarks to Johan.Claeys@ping.be