Question

Difference between bisection section, newton raphson and regula falsi method

Answer 1

Explanation:

Given a function

f x  0

, continuous on a closed interval

a,b

, such that

f af b  0 , then, the function

f x  0

has at least a root or zero in the interval

a,b

. The method calls for a repeated halving of subintervals of

a,b

containing the root. The root always converges, though very slow in converging [5].

Algorithm of Bisection Method for Root- Finding:

Inputs: (i)

f x – the given function,

(ii)

0 0 a ,b – the two numbers, such that

f af b  0 .

Output: An approximation of the root of

f x  0

in

  0 0 a ,b

, for

k  0,1,2,...

do until satisfied.

 Compute

2

k k

k

a b

C





 Test if

Ck

is the desired root. If so, stop.

 If

Ck

is not the desired root, test if

f Ck

f ak

  0

. If so, set

bk1  Ck

and

ak1  Ck

Otherwise, set

Ck  bk1  bk

End

Stopping Criteria for Bisection Method

The following are the stopping criteria as suggested by [1]: Let



be the error tolerance, that is we would like to

obtain the root with an error of at most of



. Then, accept

Ck

x 

as a root of

f x  0

. If any of the

following criteria is satisfied:

(i)

( ) Ck

f 

(ie the functional value is less than or equal to the tolerance).

(ii)

 

 

k

k k

C

C 1 C

(ie the relative change is less than or equal to the tolerance).

(iii)

 



k

b a

2

( )

(ie the length of the interval after k iterations is less than or equal to tolerance).

(iv) The number of iterations k is greater than or equal to a predetermined number, say N.

Theorem 1: The number of iterations, N needed in the Bisection method to obtain an accuracy of



is given by:

N

2

10

10 10

log

log (  )  log ( )



bo ao

Proof: Let the interval length after N iteration be

N

bo ao

2



. So to obtain an accuracy of

 



N

o o b a

2

.That is

  



2 ( ) o o

N

b a

( )

2

o o

N

b  a

 

 

log 2 log( )

10 bo ao

N



 



log 2 log( )

10 bo ao

N



  



log 2

log ( )

10

10

o o b a

N





 



log 2

log ( ) log ( )

10

10 10   

 

bo ao N as required.

Note: Since the number of iterations, N needed to achieve a certain accuracy depends upon the initial length of

the interval containing the root, it is desirable to choose the initial interval

  0 0 a ,b

as small as possible.

We solve

f x  x  cos x  0

at [0,1] using Bisection method with the aid of the software, Mathematica