Root finding methods

• Bisection method.
  
  • Example:
    
• Newton's method.
  
  • Formula
    
  • Example
    
• Iteration method
  
  • Example 1
    
  • Example 2
    
  • Increasing the efficiency by a transformation of the equation
    
    • Procedure
      
    • Example1
      
    • Example2
      
    • Exercise
      

Bisection method.

• f(m) = 0 ; then m is the root r.
• f(m).f(a) < 0 ; then the root r is in [a,m]
• f(m).f(b) < 0 ; then the root r is in [m,b]

Example:

 
        t3  + 4 t2  - 1 = 0

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.

Formula

 
        y - f(ro) = f'(ro) (x - ro)

        for y = 0 we have

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

Example

 
        t3  + 4 t2  - 1 = 0

 
                    to3 + 4 to2 - 1
        t1 = to - ------------------ = 0.4736842
                    3 to2  + 8 to

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 t_o the root r.

Iteration method

Start with an approximation x₀ of the root.
Calculate x₀, x₁, ..., x_n, ... such that

 
   x1=f(x0);

   x2=f(x1);

   x3=f(x2);

  ...

 
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

 
|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)

 
    xn = f(xn-1)

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

=>    L = f(L)

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

Then

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

Example 1

Starting with x₀ = 2 we calculate x₁,x₂,...

 
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

Example 2

 
   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

Increasing the efficiency by a transformation of the equation

x_o = 0.5 is a first approximation of the root.

The f(x) from the previous theorem is here x + x³ + 4 x² - 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)

 
  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 x_o of the root.
2. We write x = x + r.g(x)
3. We choose an r-value such that 1 + r g'(x_o) is about zero. Let r_o = the chosen value.
4. We apply iteration on x = x + r_o.g(x) starting with x = x_o

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. r_o=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 x_o = 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 . r_o = -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
   

Exercise

 

     

The specified angle is t radians.
The area of the triangle OAB is  sin(t)cos(t).
The area of the circular sector OAB is t.
The area of the circular segment to the right of the chord AB is

    t - sin(t)cos(t) = t - (1/2)sin(2t)

 
     t - (1/2)sin(2t) = pi/4

<=>  t - (1/2)sin(2t) - pi/4 = 0

We calculate t with the efficient iteration method.
We choose to = 1 radian as a first approximation of t.

    t = t + r( t - (1/2)sin(2t) - pi/4)

We take r = ro and ro is approximately the root of

    1 + r (1 - cos(2to) = 0

<=>  ro = 1/(cos(2)-1)

Choose ro = -0.7

We apply the iteration to the equation

t = t - 0.7( t - (1/2)sin(2t) - pi/4)

We find t = 1.1549407

The distance between the center points is 2.cos(t) = 0.807945