bisection_method.c File Reference

In mathematics, the Bisection Method is a root-finding method that applies to any continuous function for which one knows two values with opposite signs. More...

#include <assert.h>
#include <math.h>
#include <stdio.h>

Include dependency graph for bisection_method.c:

Macros
#define	EPSILON   0.0001
	for assert
#define	NMAX   50

Functions
double	sign (double a, double b)
	Function to check if two input values have the same sign (the property of being positive or negative)
double	func (double x)
	Continuous function for which we want to find the root.
double	bisection (double x_left, double x_right, double tolerance)
	Root-finding method for a continuous function given two values with opposite signs.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

In mathematics, the Bisection Method is a root-finding method that applies to any continuous function for which one knows two values with opposite signs.

The method consists of repeatedly bisecting the interval defined by the two values and then selecting the subinterval in which the function changes sign, and therefore must contain a root. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods.

Author

Aybars Nazlica

Macro Definition Documentation

EPSILON

#define EPSILON   0.0001

for assert

for fabs for IO operations

Function Documentation

bisection()

double bisection	(	double	x_left,
		double	x_right,
		double	tolerance
	)

Root-finding method for a continuous function given two values with opposite signs.

Parameters

x_left	Lower endpoint value of the interval
x_right	Upper endpoint value of the interval
tolerance	Error threshold

Returns

root of the function if bisection method succeed within the maximum number of iterations

-1 if bisection method fails

{
    int n = 1;      // step counter
    double middle;  // midpoint
 
    while (n <= NMAX)
    {
        middle = (x_left + x_right) / 2;  // bisect the interval
        double error = middle - x_left;
 
        if (fabs(func(middle)) < EPSILON || error < tolerance)
        {
            return middle;
        }
 
        if (sign(func(middle), func(x_left)) > 0.0)
        {
            x_left = middle;  // new lower endpoint
        }
        else
        {
            x_right = middle;  // new upper endpoint
        }
 
        n++;  // increase step counter
    }
    return -1;  // method failed (maximum number of steps exceeded)
}

Here is the call graph for this function:

func()

double func

(

double

x

)

Continuous function for which we want to find the root.

Parameters

x	Real input variable

Returns

The evaluation result of the function using the input value

{
    return x * x * x + 2.0 * x - 10.0;  // f(x) = x**3 + 2x - 10
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

{
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

sign()

double sign	(	double	a,
		double	b
	)

Function to check if two input values have the same sign (the property of being positive or negative)

Parameters

a	Input value
b	Input value

Returns

1.0 if the input values have the same sign,

-1.0 if the input values have different signs

{
    return (a > 0 && b > 0) + (a < 0 && b < 0) - (a > 0 && b < 0) -
           (a < 0 && b > 0);
}

test()

static void test ( void  )

static

Self-test implementations.

Returns

void

{
    /* Compares root value that is found by the bisection method within a given
     * floating point error*/
    assert(fabs(bisection(1.0, 2.0, 0.0001) - 1.847473) <
           EPSILON);  // the algorithm works as expected
    assert(fabs(bisection(100.0, 250.0, 0.0001) - 249.999928) <
           EPSILON);  // the algorithm works as expected
 
    printf("All tests have successfully passed!\n");
}

Here is the call graph for this function: