Bisection

viewed 5998 times and licensed 163 times

Calculates the zeros of a function using the bisection method.

Controller: CodeCogs

Contents

Interface
Bisection
Page Comments

Interface

C++

Bisection

doublebisection(	double	(`f`)(double)[function pointer]*
	double	`x0` `= -1E+7`
	double	`x1` `= 1E+7`
	double	`eps` `= 1E-10`	)

The simplest root-finding algorithm is the bisection method: we start with two points a and b which bracket a root, and at every iteration we pick either the subinterval $\inline [a, c]$ or $\inline [c, b]$ , where $\inline c = (a + b) / 2$ is the midpoint between a and b. The algorithm always selects a subinterval which contains a root. It is guaranteed to converge to a root, however its progress is rather slow (the rate of convergence is linear).

To give you a better idea on the way this method works, the following graph shows different iterations in the approximation process. Here is the associated list of pairs chosen at consecutive steps

$(a_0, b_0) \quad (a_1, b_0) \quad (a_1, b_1) \quad (a_2, b_1)$

(2)

MISSING IMAGE!

1/bisection-378.png cannot be found in /users/1/bisection-378.png. Please contact the submission author.

This algorithm finds the roots of the user-defined function f starting with an initial interval [x0, x1] and iterating until the accuracy eps is achieved.

References:

Jean-Pierre Moreau's Home Page, http://perso.wanadoo.fr/jean-pierre.moreau/
F.R. Ruckdeschel, "BASIC Scientific Subroutines", Vol. II, BYTE/McGRAWW-HILL, 1981
Wikipedia, http://en.wikipedia.org/wiki/Root-finding_algorithm

Example 1

#include <codecogs/maths/rootfinding/bisection.h>
 
#include <iostream>
#include <iomanip>
 
// user-defined function
double f(double x) {
    return (x - 2) * (x + 1) * (x + 10);
}
 
int main() 
{
    double x = Maths::RootFinding::bisection(f, -2, 0);
 
    std::cout << "The calculated zero is X = " << std::setprecision(12) << x <<  std::endl;
    std::cout << "The associated ordinate value is Y = " << f(x) << std::endl;
    return 0;
}

Output:

The calculated zero is X = -1
The associated ordinate value is Y = 0

Parameters

f	the user-defined function
x0	Default value = -1E+7
x1	Default value = 1E+7
eps	Default value = 1E-10

Authors

Lucian Bentea (August 2005)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.