## Bisection Method

The bisection method is one of the simplest to understand and program and one of the slowest. Given a continuous real-valued function of a real-variable,*f(x)*, in which one wants to approximate the location of at least one root the bisection method proceeds after finding two values such that the function evaluated at the two values has opposite signs, i.e. if

*a*and

*b*are two numbers such that

*f(a)·f(b) < 0*then a zero of

*f(x)*exists on the interval

*(min(a,b), max(a,b))*.

The fact that a zero of

*f(x)*exists is a consequence of the intermediate value theorem of elementary analysis or from topology using the lemma that the continuous image of a connected set is connected as well as the lemma that a subset of

*R*,(with the usual topology) with more than two points is connected if and only if it is an interval. Note that this technique cannot be applied to functions such as

*f(x) = x²*.

The bisection method proceeds by evaluating the function at the midpoint of the of the interval, then the endpoint of the interval where evaluation of the function has the same sign as the function evaluated at the midpoint is replaced with the midpoint, thus halving the interval. The iterative process is continued until the halted. In the implementation given below the process is either terminated by the user, or when there is no machine representable number between the two endpoints, or when the function evaluates to zero at the new midpoint.

There are several comments which should be made in locating a zero of a continuous real-valued function of a real-variable

*f(x)*:

- If α is any non-zero real number, then
*f(x)*and*α f(x)*have the same roots. I.e. you can scale the function*f(x)*without modifying the location of the roots.

- For the bisection method, the only properties of
*f(x)*that are used are: Is it positive? Is it negative? Is it zero? I.e. One could simply return +1, -1, or 0 when asked to evaluate*f(x)*.

- The observation above then leads to the following: The bisection method is generally considered to be one of the slowest methods for finding the roots of a continuous function
*f(x)*. The term slowest refers to fact that there are more calls to the function*f(x)*than in the other methods. But suppose that the function*f(x)*is the sum of two functions*g(x)*and*h(x)*where*g(x)*is easy to evaluate (fast in machine time) and*h(x)*is difficult (slow in machine time). Further assume that it is known that for all*x*,*m ≤ h(x) ≤ M*where*m < 0*,*0 < M*and the magnitudes of*m*and*M*are small. Then when evaluating*f(x)*for use in the bisection method, if*g(x) > -m*then*f(x)*must be positive and*h(x)*need not be evaluated, similarly if*g(x) < -M*then*f(x)*must be negative and again*h(x)*need not be evaluated. So there are examples where the slowest method may be faster. (Different units of speed.)

- When the bisection method terminates, the final interval is guaranteed to contain a zero of the function. But the final interval could also contain more than one zero of the function, in fact it could contain an uncountably infinite number of zeros. Consider the function
*f(x) = (x + 1)*for*x < -1*,*f(x) = 0*for*-1 ≤ x ≤ 1*and*f(x) = (x - 1)*for*x > 1*and start the bisection method at*x = -2, f(-2) = -1*and*x = 2, f(2) = 1*.

### Function List

- int Bisection_Method( double (*f)(double), double *a, double *fa,

double *b, double *fb, void *data[],

int (*verify_setup)(double, double, double, double, void**, int*),

int (*terminate)(double, double, double, double, void**,int*),

int *msg)

Locate at least one root of*f(x)*in the interval ( min(**a,*b*), max(**a, *b*) ) where *fa = f(*a), *fb = f(*b) and**fa · *fb < 0*. The procedure terminates when the user supplied routine*terminate()*returns a*1*in which case the Bisection_Method returns a*2*. Bisection_Method returns a*1*if the user supplied routine*verify_setup()*returns a*0*which signifies that the initial setup has an error. If the user supplied routine*verify_setup()*returns a*1*or non-zero then the iteration process is started. Bisection_Method can also terminate with different return values, see the table below.

An example of a user supplied*terminate()*routine and a user supplied*verify_setup()*is given below in the routines Bisection_Method_Terminate and Bisection_Method_Verify_Setup respectively. Also included below is a routine to setup the array*data*called Bisection_Method_Setup.

The return values for the Bisection_Method are:**Return Values****Description***0*At least one of the pointer arguments is NULL. *1*The user supplied *verify_setup()*function returned a*0*. The user specified error code should be stored at**msg*.2 The user supplied *terminate()*function returned a*1*. The user specified termination code should be stored at**msg*.*3*There is no machine representable number between the two endpoints. 4 The function evaluates to zero at the midpoint.

The arguments to the Bisection_Method are:**Argument****Description***f*A real-valued function of a real-variable, i.e. a function with an argument of type *double*which returns a*double*.a A pointer to one end of the interval for which the function at the endpoints has opposite signs. When Bisection_Method is invoked, *a is the initial value of an endpoint, on return *a is the final value of the endpoint. *fa*A pointer to the value of *f*evaluated at**a*, i.e.**fa = f(*a)*. When Bisection_Method is invoked, *fa is the user supplied value of*f(*a)*where**a*is the initial value at that endpoint, on return *fa is the final value of*f(*a)*where**a*is the final value at that endpoint.b A pointer to the other end of the interval for which the function at the endpoints has opposite signs. When Bisection_Method is invoked, *b is the initial value of an endpoint, on return *b is the final value of the endpoint. *fb*A pointer to the value of *f*evaluated at**b*, i.e.**fb = f(*b)*. When Bisection_Method is invoked, *fb is the user supplied value of*f(*b)*where**b*is the initial value at that endpoint, on return *fb is the final value of*f(*b)*where**b*is the final value at that endpoint.data An array of pointers of the type *void**. The array*data*is not used by Bisection_Method directly but only passed to the user supplied*verify_setup()*and*terminate()*routines. This allows the user to pass additional information to the*terminate()*routine so it can determine whether or not to terminate the iteration. The user supplied*verify_setup()*routine generally only checks that*data*has no obvious flaws.*verify_setup()*A user supplied routine to verify that the input data to Bisection_Method and to the user supplied *terminate()*routine met the requirements that both routines function correctly. For a description of the arguments to*verify_setup()*, see the Bisection_Method_Verify_Setup routine below which is an example of a user supplied*verify_setup()*routine. If*verify_setup()*detects an error, it can store an error code at *msg thus allowing the user to determine the reason for the error.*terminate()*A user supplied routine to terminate or continue iterating. For a description of the arguments to *terminate()*, see the Bisection_Method_Terminate routine below which is an example of a user supplied*terminate()*routine. If*terminate()*returns*1*halt, it can store a halt code at *msg thus allowing the user to determine the reason for the halting.msg A pointer to an integer. This address is passed to the user supplied routines so that they can return error codes or halt codes.

- int Bisection_Method_Terminate( double a, double fa, double b, double fb, void *data[], int *halt_code)

*Bisection_Method_Terminate()*is an example of a user supplied*terminate()*routine. This function returns a*0*if the process is to continue and a*1*if the iterating process is to halt. The arguments*a, fa, b, fb*of*Bisection_Method_Terminate()*correspond to the dereferenced arguments*a, fa, b, fb*of the routine*Bisection_Method()*, while*data*is the same and*halt_code*corresponds to argument*msg*of*Bisection_Method()*.

The return values for the Bisection_Method_Terminate are:**Return Values****Description**0 Continue iterating. 1 Terminate iterating.

For this routine the data array consists of four pointers:**Data Array Index****Description**0 A (double *) pointer to the relative tolerance. 1 A (double *) pointer to the absolute tolerance. 2 A (double *) pointer to the lower bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to determine convergence. 3 A (double *) pointer to the upper bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to determine convergence.

If a*1*is returned (halt the iteration) then**halt_code*is set to the following values:**Halt Code****Meaning**0 The process converges using the relative tolerance test, i.e. *|b - a| / min(|a|,|b|) ≤ relative_tolerance*,

where both*a*and*b*must have the same sign.1 The process converges using the absolute tolerance test, i.e. *|b - a| ≤ absolute_tolerance*.2 The function vanishes at one or both of the endpoints.

- int Bisection_Method_Verify_Setup( double a, double fa, double b, double fb, void *data[], int *err)

*Bisection_Method_Verify_Setup()*is an example of a user supplied*verify_setup()*routine. This function returns a*0*if an error was detected and a*1*if no error was detected, i.e. start the iteration process. The arguments*a, fa, b, fb*of*Bisection_Method_Verify_Setup()*correspond to the dereferenced arguments*a, fa, b, fb*of the routine*Bisection_Method()*, while*data*is the same and*err*corresponds to argument*msg*of*Bisection_Method()*.

For this routine the data array consists of four pointers:**Index****Description**0 A (double *) pointer to the relative tolerance. 1 A (double *) pointer to the absolute tolerance. 2 A (double *) pointer to the lower bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to determine whether to halt the iteration or not. 3 A (double *) pointer to the upper bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to whether to halt the iteration or not.

If a*0*is returned (an error was detected) then**err*is set to the following values:**Number****Meaning**1 The endpoints agree i.e. *a = b*.2 The function evaluated at the endpoints has the same sign. In case the function vanishes at an endpoint, the *terminate()*procedure will terminate the iteration.3 The address of the *data*array is*0*.4 The address of an element of the *data*array is*0*.5 The relative tolerance is non-positive. 6 The absolute tolerance is non-positive. 7 The lower bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test is not negative. 8 The upper bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test is not positive.

- int Bisection_Method_Setup( double *rel_tolerance, double *abs_tolerance, double *test_region_lower_bound, double *test_region_upper_bound, void *data[])

*Bisection_Method_Setup()*is an example of a program to populate the array*data*for use in both*Bisection_Method_Verify_Setup()*and*Bisection_Method_Terminate()*routines after being passed to*Bisection_Method()*. In particular,*data[0] = (void *)rel_tolerance*,*data[1] = (void *)abs_tolerance*,*data[2] = (void *)test_region_lower_bound*, and*data[3] = (void *)test_region_upper_bound*,

where *rel_tolerance is the relative tolerance, *abs_tolerance is the absolute tolerance, *test_region_lower_bound is the lower bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to determine whether to halt the iteration or not, and *test_region_upper_bound is the lower bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to determine whether to halt the iteration or not. The array*data*must be dimensioned at least 4 in the calling routine.

The function,*Bisection_Method_Setup()*, returns a*0*if at least one of the arguments is NULL, otherwise the function returns a*1*.

*C* Source Code

- The file, bisection_method.c, contains the version of Bisection_Method( ) written in
*C*.

- The file, bisection_method_terminate.c, contains the version of Bisection_Method_Terminate( ) written in
*C*.

- The file, bisection_method_verify_setup.c, contains the version of Bisection_Method_Verify_Setup( ) written in
*C*.

- The file, bisection_method_setup.c, contains the version of Bisection_Method_Setup( ) written in
*C*.