Engineering I

ROOT FINDING TECHNIQUES: Bisection Method

Consider a function f ( x ) which has the following graph:

Suppose that we want to locate the root which lies between +1 and +2. We start by defining xLeft = +1 and xRight = +2.

This is our initial bracket. We can check the validity of this bracket by making sure that

f( xRight ) * f ( xLeft ) < 0 .

Note however that the bracket [ -2 , +2] , which includes 3 roots and it is therefore inappropriate, would have been erroneously validated by the above test.

The bisection method improves the bracket by computing

xMid = ( xLeft + xRight ) / 2

and then selecting a new bracket either as [xLeft, xMid] or as [xMid, xRight]. Of course at each step the method also checks xMid to see if it satisfies the criteria for a good enough approximation to the root. If the criteria ( either closeness of x or smallness of f(x) ) are satisfied then the procedure terminates.

How do we decide about the new bracket? We must calculate the product

f( xLeft ) * f ( xMid )

If the above product is zero then the root is exactly xMid. If the product is negative, then the new bracket must be [xLeft.,.xMid] , otherwise the next bracket must be [xMid.,.xRight]. The rule is that the function must have values of opposite sign at the two ends of the appropriate bracket.

As an example of the method consider the following table which illustrates the steps needed to find the positive root of

x² – 2 = 0

We start with the initial bracket [1, 2 ] . Note that our initial error in estimating the root is therefore less than 0.5 (half of the bracket length). Try to explain why.

xLeft	xRight	f(xLeft)	f(xRight)	xMid	f(xMid)	remarks
1	2	-1	2	1.5	0.25	xMid must replace xRight error < 0.5
1	1.5	-1	0.25	1.25	-0.4375	xMid must replace xLeft Note that from here on the only newly calculated numbers at each row are xMid and f(xMid). error < 0.25
1.25	1.5	-0.4375	0.25	1.375	-0.1094	xMid must replace xLeft error < 0.125
1.375	1.5	-0.1094	0.25	1.4375	0.0664	xMid must replace xRight error < 0.0625
1.375	1.4375	-0.1094	0.0664	1.4063	STOP	error < 0.03125

Note that the actual root of the equation is the square root of two, which is 1.414213562. If we round this value to 4 decimal places we have 1.4142. What is the error between this “exact” value and our approximation?

There are two error estimates we may calculate:

Absolute error: | 1.4063 – 1.4142 | = 0.0079 which is indeed less than 0.03125 as predicted by the table.

Relative error: | ( 1.4063 – 1.4142 ) / 1.4142 | = 0.0056 or as we usually say 0.56 per cent.