The Bisection Method is a simple and robust root-finding algorithm that works by repeatedly bisecting an interval and selecting a subinterval where a root must lie. It is based on the Intermediate Value Theorem from calculus, which states that if a continuous function has values of opposite signs at the endpoints of an interval, then it must have at least one root within that interval.
The Bisection Method, also known as the Binary Search Method for root-finding, is one of the oldest and most straightforward numerical methods. Its origins can be traced back to ancient mathematics, but it was first formally described by Bolzano in his 1817 paper on the Intermediate Value Theorem. Despite its simplicity, the method remains valuable today due to its reliability and guaranteed convergence for continuous functions.
Click Start to begin visualization
def bisection_method(f, a, b, tolerance=1e-6, max_iterations=100):
"""
Find root of f(x) = 0 in interval [a,b] using bisection method.
Args:
f: Function to find root of
a, b: Interval endpoints
tolerance: Acceptable error
max_iterations: Maximum number of iterations
Returns:
Approximate root of f(x)
"""
if f(a) * f(b) >= 0:
raise ValueError("Function must have opposite signs at endpoints")
iteration = 0
while (b - a) > tolerance and iteration < max_iterations:
c = (a + b) / 2 # Midpoint
fc = f(c)
if abs(fc) < tolerance:
return c
if f(a) * fc < 0:
b = c
else:
a = c
iteration += 1
return (a + b) / 2
# Example usage
if __name__ == "__main__":
# Example function: x³ - x - 2
def f(x): return x**3 - x - 2
# Find root in interval [1, 2]
root = bisection_method(f, 1, 2)
print(f"Root found at x = {root:.6f}")
print(f"f({root:.6f}) = {f(root):.6f}")
#include <iostream>
#include <cmath>
#include <stdexcept>
class BisectionMethod {
private:
double tolerance;
int maxIterations;
public:
BisectionMethod(double tol = 1e-6, int maxIter = 100)
: tolerance(tol), maxIterations(maxIter) {}
template<typename F>
double findRoot(F f, double a, double b) {
if (f(a) * f(b) >= 0) {
throw std::invalid_argument(
"Function must have opposite signs at endpoints"
);
}
int iteration = 0;
while ((b - a) > tolerance && iteration < maxIterations) {
double c = (a + b) / 2;
double fc = f(c);
if (std::abs(fc) < tolerance)
return c;
if (f(a) * fc < 0)
b = c;
else
a = c;
iteration++;
}
return (a + b) / 2;
}
};
int main() {
// Example function: x³ - x - 2
auto f = [](double x) { return x*x*x - x - 2; };
BisectionMethod solver;
try {
double root = solver.findRoot(f, 1.0, 2.0);
std::cout << "Root found at x = " << root << std::endl;
std::cout << "f(" << root << ") = " << f(root) << std::endl;
}
catch (const std::exception& e) {
std::cerr << "Error: " << e.what() << std::endl;
}
return 0;
}
public class BisectionMethod {
private readonly double tolerance;
private readonly int maxIterations;
public BisectionMethod(double tolerance = 1e-6, int maxIterations = 100) {
this.tolerance = tolerance;
this.maxIterations = maxIterations;
}
public double FindRoot(Func<double, double> f, double a, double b) {
if (f(a) * f(b) >= 0) {
throw new ArgumentException(
"Function must have opposite signs at endpoints"
);
}
int iteration = 0;
while ((b - a) > tolerance && iteration < maxIterations) {
double c = (a + b) / 2;
double fc = f(c);
if (Math.Abs(fc) < tolerance)
return c;
if (f(a) * fc < 0)
b = c;
else
a = c;
iteration++;
}
return (a + b) / 2;
}
public static void Main() {
// Example function: x³ - x - 2
double f(double x) => x * x * x - x - 2;
var solver = new BisectionMethod();
try {
double root = solver.FindRoot(f, 1.0, 2.0);
Console.WriteLine($"Root found at x = {root:F6}");
Console.WriteLine($"f({root:F6}) = {f(root):F6}");
}
catch (Exception e) {
Console.WriteLine($"Error: {e.Message}");
}
}
}
The time complexity is O(log((b-a)/ε)), where:
The space complexity is O(1), which includes: