Numerical Analysis

Nonlinear Equations

Methods for finding roots of equations f(x) = 0. Default function: f(x)=x3−x−2f(x) = x^3 - x - 2

Bisection Method

Theory

The bisection method finds a root by repeatedly halving an interval [a,b][a, b] where f(a)f(a) and f(b)f(b) have opposite signs.

c=a+b2c = \frac{a + b}{2}

If f(a)f(a) · f(c)f(c) < 0, then root is in [a,c][a, c]; otherwise in [c,b][c, b].

Convergence rate: O(1/2n)O(1/2^n) — linear convergence

Interactive Visualizer

Custom function (press Enter or Apply)
f(x) =
Initial a
Initial b
Tolerance ε

Implementation

INPUT: f, a, b, TOL, max_iter
OUTPUT: approximate root c

for n = 1, 2, ..., max_iter:
    c = (a + b) / 2
    if f(b) * f(c) > 0:
        b = c
    else:
        a = c
    if |b - a| < TOL:
        RETURN c

RETURN "Method failed"