2.1 Bisection Method PDF

Preview

Summary

Dr. TJ 331 notes...

Description

Maths 331

TJ

§ 2.1: The Bisection Method (Bracketing Methods for Locating a Root) Definition: A number p is called a root or a zero of f (x) if f ( p)  0 . For example the roots or (zeros) of f ( x)  x 2  5 x  6  0 are p  3 and p  2 . To find the root or zeros of a given function in a given interval, we have Intermediate value Theorem Let f be a continuous function on the interval [ a, b] and it is such that f (a) f (b)  0 (i.e. f (a) and f ( b) have opposite signs). Let t be any number between f (a) and f ( b) . Then there exists a number c  (a, b) such that f (c)  t . This result provides a simple and effective way of finding the approximate location of the zeros of f. If f (a) f (b)  0 then there exist a number r [a, b] with f (r )  0 , i.e. f has a root in the interval [a, b] .

Any interval known to contain one or more roots of f ( x)  0 is referred to as a bracketing interval. Example 1: Show that the equation x 3  x  1  0 has at least one root in [1, 2] . Solution:

f ( x)  x 3  x  1 is continuous on [1, 2] because it is polynomial. f (1)  ……………………………………………………………………………………………………… f (2)  ……………………………………………………………………………………………………….. since f (1) f ( 2)  0 , there exist r  [1, 2] such that …………………………………. We now describe a method known as bisection method. It is one of the Bracketing methods to find a zero of a nonlinear equation. In this method the length of the bracketing interval is reduce in a systematic way. The bisection method will work when f (a) f (b)  0 and there is more than one root in the interval [a, b] . It calls for repeated halving of the subinterval [a, b] and at each step locating the half-containing r. In computer science this process is known as a binary search procedure.

21.09.19

Academic Year 2019-2020

1

Maths 331

TJ

The algorithm of Bisection Method as follows: 1)

Set a 0  a , b0  b .

2)

a  b0 . Compute the mid-point r0  0 2

If f ( r0 )  0 then stop. We have the solution. If f ( a0 ) f ( r0 )  0 then r  ( a0 , r01 ) set a1  a0 , b1  r0 . Go to step 2. If f (r0 ) f (b0 )  0 then r  (r0 , b0 ) set a1  r0 , b1  b0 . Go to step 2.

3) 4) 5)

Now repeat this process to [ a1 , b1 ] . Continue until we get convergence (i.e. get solution).

ab )  0 so take new 2 a b ]. interval as [ a, 2

a b ) f (b)  0 so take new 2 ab , b] . interval as [ 2

Here f (

Here f (a ) f (

After one step of the algorithm, we have found either a zero or a new bracketing interval that is precisely half the length of the original one. The process continues until the length of the bracketing interval is less than a prescribed tolerance. Next we illustrate how the bisection method can be applied. Example 2: Use bisection Method to find positive root of f ( x)  x 3  x  1 on [-1,2].

f ( 1)  1 1 1  1

1)

f ( 2 )  8  02  1  7  f ( 1) f ( 2 )  0. Hence, there exists a zeros r  [ 1,2] such that r0 

2)

 1 2  0 .5 2

with f( 0.5)  (0.5) 3  0.5  1  1.375 3)

Since f ( 0.5) f ( 2)  0  The root lies on [0.5,2] such that r1 

with

f (1.25)  (1.25) 3 1.25  1  0.297 Since f (1.25) f ( 2)  0  The root lies on [1.25, 2].

4)

0.5  2  1.250 2

After 20 steps of Bisection method you will get r  1. 325 and

f (r )  f (1.325)  1.325 3  1.325  1  0.001

21.09.19

Academic Year 2019-2020

2

Maths 331

TJ

When to stop the iteration? We can select a tolerance   0 and generate the sequences of the root approximation r0 , r1 , ..., rn until one of the following conditions satisfies: a)

rn 1  rn   ,

b)

rn 1  rn

c) f ( rn )  

  , rn 1  0 ,

rn1

Unfortunately, there are some difficulties with these stopping criteria. For example rn 1  rn converge to zero while the sequence itself diverges. When using computer to generate the approximation, and to avoid infinite loop, it is better to set an upper bound on the number of iterations. To investigate the accuracy within which the bisection method determines a root of a given function, we have the following theorem. Convergence Analysis Theorem: Suppose that f  C[a, b] and f (a) f (b)  0 . The bisection method generates a sequence {rn } approximating a zero r of f with

r  rn 

ba 2 n 1

,

n  0,1, 2,

and therefore the sequence {rn } converges to the zero x  r , that is lim rn  r . n  If an error tolerance has been prescribed in advance, it is possible to determine the number of steps required in the bisection method. Suppose, for example, we want the error be

r  rn  

where

a b rn  n n 2

Then, it is necessary to solve the following inequality for n :

b a 2 n 1



Example 3: How many iterations (steps) of bisection method are needed to approximate the root of f ( x)  x 3  x  1 on [-1, 2] with an error of less than or equal 0.0001. b a 2  (1)    0.0001 Using 1 1 2 n 2 n 3  0.0001 n 1 2  ……………………………………………………………………………………………………………………. ……………………………………………………………………………………………………………………. ……………………………………………………………………………………………………………………. …………………………………………………………………………………………………………………….

It is important to keep in mind that the error analysis gives only a bound for the number of iterations. In many cases, this bound is much larger than the actual number required.

21.09.19

Academic Year 2019-2020

3

Maths 331

TJ

Advantages of Bisection Method:  Method always converges.  We always have a bound for the root.  The number of iteration required to obtain a specified accuracy in the solution is predetermined. Disadvantages of Bisection Method:

  

It converges very slowly. Good intermediate solutions are discarded. We need two initial guesses if the interval is not given. This is not easy if we have no idea about the root.

Matlab Code for the Bisection Method >> f=@(x) x^3+4*x^2-10;

% defining f

function p = bisection(f,a,b) % Input your function in the command window % Give initial guesses for the interval. % call the function of the bisection method using the command bisection(f,a,b) if f(a)*f(b)>0 disp('Wrong choice for the initial interval') else p = (a + b)/2; err = abs(f(p)); while err > 1e-7 if f(a)*f(p)> bisection(f,1,2) ans = 1.3652

Exercises: (Do all your calculations to 4 decimal places) Q1. Use the bisection method to find r4 for f ( x)  x  cos x on [0, 1]. Q2.

Show that

f ( x)  x 3  4 x 2  10  0 has a root in the interval[1, 2] . How many iterations

are needed to get an accuracy less than or equal 10  5 . Q3.

Find approximation to 3 using the bisection algorithm in the interval [1, 2](apply 4 iterations).

Q4.

Use bisection method to determine the point of intersection of the curves given by y  x 3  2 x  1 and y  x 2 in the interval [-1, 1].

Q5.

Use Bisection method to approximate the zeros of f ( x )  x 3  x  3  0 in the interval [0, 4].

perform the iteration till the error between two consecutive approximation is 0.00001 Q6. Solve all the above questions using the given Matlab subroutine.

21.09.19

Academic Year 2019-2020

4...