4.

2 ITERATIVE METHODS

We have so for discussed root finding methods, which require the interval in
which the root lies. We now describe methods which require one or more
starting values of 𝑥. The first is the iteration method, which requires one
starting value of 𝑥.

To describe this method for finding the roots of the equation f ( x)  0 ….(1)

We rewrite this equation in the form x   ( x) ……………(2)

There are many ways of doing this.

For example, the equation x 3  x 2  1  0 can be expressed as either of the form

   
1 1 1
x  1  x  2
, x  1  x3 2
, x  1  x2 3
.......

Let x0 be an approximate value of the desired root  . Substituting it for x on

the right side of (2), we obtain the first approximation
x1   ( x0 )

The successive approximations are then given by

x2   ( x1 ), x3   ( x2 ), ...... xn   ( xn 1 ),

A number of questions now arise;

(i) Does the sequence of approximations

x0 , x1 , x2 .......xn always converge to some number



(ii) If it does, will  be a root of the equation

(iii) How should we choose  in order that the sequence xo , x ,..., x 1 n

converges
to the root?
The answer to the first question is negative. As an example, we consider the
equation
x  10 x  1
If we take x  0, x  2, x  101, x  10101  1, etc and as n increases, xn increases
0 1 2 3

without limit. Hence, the sequence x0 , x1 , x2 ,..., xn does not always converge
and, in Theorem below, we state the conditions which are sufficient for the
convergence of the sequence.
The second question is easy to answer, for consider the
equation xn 1   ( xn ) ………..(3)
Which gives the relation between the approximations at the nth and (n+1)th
stages. As n increases, the left side tends to the root  , and if  is continuous
the right side tends to  ( ) . Hence, in the limit, we have  ( ) which shows that
is a root of the equation x   ( x)
The answer to the third question is contained in the following theorem:

Theorem

Let x   be a root of f(x) =0 and let I be an interval containing the point

x  . Let  ( x) and  ( x)
1
be continuous in I, where  ( x) is defined by
the equation x   ( x) . Which is equivalent to f(x) = 0. Then if  1 ( x )  1 for all

x in I, the sequence of approximations x0 , x1 , x2 ,..., xn

Defined by (3) converges to the root  , provided that the initial approximation
x0 is chosen in I.

Proof
Since x0 is a root of the equation x   ( x) , we have
   ( ) …………………… (4)
From (3)
x1   ( x0 ) ………………....(5)
Subtraction gives
  x1   ( )   ( x0 )

By using the mean value theorem, the right-hand side can be written as
(  x0 ) 1 (0 ), x0  0  
Hence we obtain
   x1  (  x0 )  1 (0 ), x0  0   …………………(6)

Similarly we obtain
  x2  (  x0 ) 1 (1 ), x1  1  
…………………………………………………(7)
  x3  (  x2 ) 1 (2 ), x2  2   …………………………..(8)
…………………………………..
  xn1  (  xn ) 1 (n ), xn  n   …………………… ………(9)
If we let
 1 (i )  k  1 for all i ……………………………………(10)
Then equation (6) to (10) give
  x1    x0 ,   x2    x1
Which show that each successive approximation remain in I provided that the

initial approximation is chosen in I. now multiply equation (6) to (10) and

simplifying, we obtain

  xn1  (  x0 ) 1 (0 ), 1 (1 )1 (2 )...... 1 (n ) ……………..(11)

As n tends to infinity the right hand side of (11) tends to zero, and it follows that

the sequence of approximations x0, x1, …… converges to the root  .

Problems:

1. Find the real root of the equation f ( x)  x 3  x 2  1 by iterative method on

the interval [0, 1] with an accuracy of 10 4

Solution: To find this root, we rewrite the given equation in the form
1
x --------------------------------------(1)
x 1
1 1
Thus  ( x)  ,  1 ( x)  3
x 1 2  x  1 2

1
and max [0,1]  1 ( x)   k  0.17678  0.2
2 8
 1 k
Using xn  xn 1 
k
1  0.2
xn  xn 1   0.0001  0.0004
0.2
Hence the absolute value of the difference does not exceed 0.0004, the required

accuracy will be achieved and then the iteration can be terminated.

Starting with x0 = 0.75, we obtain the following table

N xn xn  1 xn 1  1
xn  1
0 0.75 1.3228756 0.7559289
1 0.7559289 1.3251146 0.7546517
2 0.7546517 1.3246326 0.5749263

At this stage we find that xn1  xn  0.7549263  0.7546517  0.0002746

Which is less than 0.0004. The iteration is therefore terminated and the root to
the required accuracy is 0.7549.

Example: Find the root of the equation 2x = cosx +3 correct to 3 decimal

places.

Solution: we rewrite the equation in the form

1
x  cos x  3
2
1
so that  ( x)   cos x  3
2
sin x
and  1 ( x )  1
2

Hence the iteration method can be applied to the equation (1) and we start

with x0 
2
The successive iterations are
 x1  1.5,
x2  1.535,
x3  1.518
x4  1.526
x5  1.522
x6  1.524
x7  1.523
x8  1.524

Hence we take the solution as 1.524 correct to three decimal places.

Exercises:

1. Using iteration method, find the approximate roots of the following

equations x 4  x  13  0 correct to four decimal places
2. Show that a real root of the equation log x  x  3  0 lies between 0.1 and
0.23 by using iteration method, by taking 5 approximations.
3. Find the real root of the equation
log x  cos x  0 correct to three decimal places root near to 1 by iteration

method
4. By iteration method find the real root of the equation
x 4  x 3  2 x 2  6 x  4  0 in (2, 3) carryout 5 steps

The Newton- Raphson Method

Introduction

In numerical analysis, Newton's method (also known as the Newton–

Raphson method), named after Isaac Newton and Joseph Raphson, is a method
for finding successively better approximations to the roots of a real -valued
function.
 It is a powerful technique for solving algebraic, transcendental equations
numerically. It is based on the simple idea of linear approximation.
Geometrically, it is described as tangent method or also a chord method in
which we approximate the curve near a root by a straight line. This method is
also called Newton’s Method
Consider the equation f(x) = 0.
Let x be an approximation to the root of f(x) = 0.
0
If x = x + h be the exact root then f(x )= 0
1 0 1

Now
f(x ) = 0  f(x +h) = 0
1 0
h2
f(x ) + h f ' (x )+ f '' ( x )+........ = 0 by Taylor's theorem
0 0 2! 0
n e g lectin g h 2 an d h ig h e r p o w e rs o f h w e g e t
f(x )
f(x ) + h f ' (x ) = 0  h = - 0
0 0 '
f (x )
0
f(x )
T hus x = x - 0 is c lo se to th e ro o t o f f(x ) = 0
1 0 f ' (x )
0
S ta rtin g w ith x still c lo s er v alu e o f th e ro o t o f f(x ) = 0
1
is g iv en b y
f(x )
x =x - 1 c o n tin u in g th is p ro ce s s
2 1 f ' (x )
1
w e g e t v alu es w h ich a re c lo s e r an d c lo s e r to th e a ctu a l ro o t.
an d th e s e step s a re c a lle d ite ratio n s .

T h u s (n + 1 ) th iteratio n is
f(x n )
x = xn - , n = 0 ,1 ,2 ,3 ,......... ---- (1 )
n+1 f ' (x n )
eq u atio n (1 ) is c a lled N ew to n 's ite ra tio n fo rm u la .

Newton-Raphson method for multiple roots

Definition: If we can write f(x) = 0 as f (x) = (x - x*)mg(x) = 0 , where g(x)

is bounded and g(x*) = 0, then x* is called a multiple root of multiplicity m.
If x* is a multiple root of multiplicity m of equation f(x) = 0, then we have from
definition of multiple root:
f (x*) = f (x*) = ... = f  m-1 (x*) = 0 and f  m  (x*)  0
If ξ is a root of f(x) = 0 with multiplicity m, then the iteration formula
corresponding to eqn.(1) is
x n+1  x n - m f(x n )
f (x n )
If the multiplicity is not known in advance then
f  xn  f  xn 
x n+1 =x n -
2
 f   x n   -f  xn  f   x n 

Example 1 : Find the root of x3  5 x  3  0 by Newton – Raphson

method.

Solution : The given equation is f ( x)  x 3  5 x  3  0 .

Here f (1) = - 1 < 0 and f (2) = 1 > 0 so root lies between 1 and 2
Let x0 = 1.5 and f '( x)  3 x 2  5

Using Newton’s formula

x n+1=x n - f(x n )
f'(x n )
= x n - x n -5x2 n +3
3

3x n -5
= 2x n -3 ,
3
n = 0,1,2,3.....
3x 2n -5

Which gives x1 = 2.1429, x2 = 1.9007 x3 = 1.8385 x4 = 1.834

x5 = 1.8342

Thus x = 1.834 is the root correct to three decimal places.

Example 2: Use Newton - Raphson method to find the real root of
3x = cosx + 1

Solution : The given equation is f ( x)  3x  cos x 1  0

f(0) = -2 < 0 and f(1) = 1.4597 > 0

clearly root lies between 0 and 1. We take x0 = 0.6

Also f (x) =3 + sinx

By Newton’s formula

x n+1 = x n - f(x n )
f'(x n )
= x n - 3x n -cosx n -1
3 + sinx n
x sinx n +cos x n +1
= n , n = 0,1,2,3.....
3 + sinx n

For n = 0, x1 = 0.6071, x2 = 0.6071 since x1 = x2

So 0.6071 is the root correct to four decimal places.

Example 2: Find a double root of the equation

f  x  = x 3 -x 2 -x+1=0 choosing x0 = 0.8.
Solution:
f   x  = 3x 2  2x-1
f   x  = 6x-2
 f  x0 
x1 = x 0 - 2  1.012
f   x0 
f  x 
x = x - 2  1  1.0001
2 1 f   x 
 1
 x =1.0001

Exercises :
1. Use Newton - Raphson method to solve the following equations correct
to three decimal places.
(i) x  log x  2 (ii) cos x  x e x
(iii) x 4  x 13  0 (iv) e x sin x  1
2. Find a double root of the equation

f  x  = 27x 5 +27x 4 +36x 3 +28x 2 +9x+1=0 with x 0  1