(Method of halving the interval (Bisection Method:

Method of halving the interval (Bisection Method):
Suppose a continuous function f defined on the interval [x_0 ,x_1] is given with f(x_0) and f(x_1) of opposite sign (i.e. f(x_0)?f(x_1)<0). Then by intermediate value theorem ((If f?C[x_0, x_1] and k is any number between f(x_0) and f(x_1), then there exists x_2?(x_0, x_1) for which f(x_2)=k)) there exists a point x_2?(x_0, x_1) such that f(x_2) =0 (there is at least root of f(x)=0 ) . We now bisect this interval x_2 = (x_0+x_1)/2 , and then three possibilities arises( and then we consider the interval [ x_0 , x_2 ] or [ x_2 , x_1 ] at whose end- point take apposite sign )
<0 there is a root between x_0 , x_2 ? x_3=(x_0+ x_2)/2 If f(x_0)? f(x_2) = >0 there is a root between x_1 , x_2? x_3=(x_1+ x_2)/2
=0 x_2 is exact root ((Stop)).
We stop iteration if the interval width is as small as desired i.e. |x_i-x_(i-1) |?? for any i.
Example1 :-
Use six iteration to locate the root of equation 2^x-5x+2 by using bisection method
Solution :
f(0)=3 f(1)=-1

f(0)=3 f(0.5)=0.914 f(1)=-1

f(0.5)=0.914 f(0.75)=-0.068 f(1)=-1

f(0.5)=0.914 f(0.625)=0.417 f(0.75)=-0.068

f(0.625)=0.417 f(0.6875)=0.1729 f(0.75)=-0.068

f(0.6875)=0.1729 f(0.71875)=0.052 f(0.75)=-0.068

f(0.71875)=0.052 f(0.734375)=-0.008 f(0.75)=-0.068

? The root is 0.734375
Example 2:
Find an approximate root of f(x)=x2-2 in the interval [1,2] by using Bisection method if its possible with error ???10?^(-4)
Solution: It is possible to use bisection method because f is continuous on [1,2] and f(a)=f(1)=-1; f(b)=f(2)=2 i.e. f(a)?f(b)=-2<0.
x1= , |a-x_1|=0.5>?. Find x2:
f(x1)=0.25 ? f(x1)?f(a)<0 ? there is a root between x1 and a ? x2=
|x_2-x_1 |=0.25>?. Find x3:
f(x2)=-0.437 ? f(x2)?f(x1)<0 ? there is a root between x1 and x2 ? x3=

Stop iteration if |x_i-x_(i-1) |?? for any i=1, 2, ….

Example 3:
Find an approximate root of f(x)=xlog(x)-1=0 in the interval [1,2] by using Bisection method with error ???10?^(-3)
Solution: f(x0)=f(1)=-1; f(x1)=f(2)=0.3863 i.e. f(x0)?f(x1)=-0.3863<0.
, f(x2)=-0.3918 ? , f(x3)=- 0.02061 ? , f(x4)=+ 0.1786 ? , f(x_5)=0.07791

x6=1.78125 x7=1.765625 x8=1.7578125 x9=1.76171875
x10=1.763671875 x11=1.762953125
So the root is x11=1.762953125 with error ??0.001



H.W:
Use six iteration to locate the root of equation x^3-x^2-3x-3=0 by using bisection method

Theorem:
Let f?C[a,b] and suppose f(a)?f(b)<0. The bisection procedure generates a sequence {Pn} approximating P with the property
Proof: For each we have bn-an= and P?(an,bn). Since Pn= for all , it follows that
Example 3:
Determine approximately how many iterations are necessary to solve f(x) with error ?? over [a,b].
Solution: We must find an integer n that will satisfy ?? ? ? ) ? .
If f(x)=x3+4x-10=0, and [1,2].
? n=17(number of iterations).