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:
Consider the equation x = f(x).
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.

Example 1

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

Example 2

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

Increasing the efficiency by a transformation of the equation

We try to solve the equation x3 + 4 x2 - 1 = 0 with the iteration method.
We can rewrite this equation as x = x + (x3 + 4 x2 - 1) .

xo = 0.5 is a first approximation of the root.

The f(x) from the previous theorem is here x + x3 + 4 x2 - 1 .
But the condition |f'(x)| < k < 1 is not satisfied in the environment of the root.

Therefore, we transform the equation to 

 
    x = x + r.(x3  + 4 x2  - 1)
Now, we can choose the value of r without changing the root. The f(x) from the theorem is now x + r.(x3 + 4 x2 - 1).
From the proof of the theorem above, we know that the convergence is very fast if f '(x) has a value near 0 in the environment of the root. 
 
  f'(x) = 1 + r.(3x2 + 8t)

  Since the root is near 0.5, we choose r such that

  f'(0.5) = 1 + r.(3 (0.5)2 + 8.(0.5)) = 0

  r = -0.21052631579 but we choose   r = -0.21.

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

  We apply iteration to  x = x - 0.21(x3  + 4 x2  - 1) starting with x = 0.5

0.47375
0.472892306269531
0.472837688600127
0.472834153854809
0.472833924859327
0.472833910023068
0.472833909061846
0.47283390899957
0.472833908995535

Procedure

  1. We want a root of the function g(x)=0 and we know a first approximation xo of the root.
  2. We write x = x + r.g(x)
  3. We choose an r-value such that 1 + r g'(xo) is about zero. Let ro = the chosen value.
  4. We apply iteration on x = x + ro.g(x) starting with x = xo

Example1

  1. We want the roots of x ln(x) - ln(0.7) = 0.
    Using a plot we see that there are two roots and we can choose the approximations 0.28 and 0.46.
    We will first apply the method to 0.28
  2. We write x = x + r(x ln(x) - ln(0.7))
  3. We choose an r-value such that 1+r(1+ln(0.28))=0. ro=3.66 is a good approximation.
  4. We apply iteration to x = x + 3.66 (x ln(x) - ln(0.7))
    In a few steps we find very good results. 
     
0.28000000000
0.280895070246
0.280901147167
0.280901224144
0.280901225114
  5. Calculate the second root as an exercise starting with 0.46.

Example2

  1. We want the roots of x - sin(x) - 0.5 = 0. Using a plot we see that xo = 1.5 is a good approximation.
  2. We write x = x + r(x - sin(x) - 0.5)
  3. We choose an r-value such that 1 + r(1-cos(1.5))= 0 . ro = -1.077
  4. We apply iteration to x = x - 1.077 (x - sin(x) - 0.5)
    and we find very good results using only three steps. 
     
1.49730210057
1.49730039266
1.4973003891


Topics and Problems

MATH-abundance home page - tutorial

MATH-tutorial Index

The tutorial address is http://home.scarlet.be/math/

Copying Conditions

Send all suggestions, remarks and reports on errors to Johan.Claeys@ping.be     The subject of the mail must contain the flemish word 'wiskunde' because other mails are filtered to Trash