Bisection method

The bisection method finds a root by repeatedly halving an interval whose endpoint function values have opposite signs and keeping a half that still brackets a root.

Intermediate value theorem: A theorem stating that a continuous function takes every value between its values at two points. Continuity and opposite endpoint signs guarantee a root somewhere in the interval.
Brent's method: A root-finding algorithm combining bisection, secant steps, and inverse quadratic interpolation. It retains bisection's reliability while often converging much faster.
Root of a function: An input value at which a function evaluates to zero. The method's target is a root enclosed by the initial interval.
Fixed-point iteration: An iterative method that seeks a solution of x = g(x) by repeatedly evaluating g. It can solve equations through reformulation, but does not inherently maintain a sign-changing interval.
Root bracketing: A root-finding strategy that confines a root to an interval using function values at its endpoints. Bisection is a bracketing method that preserves the sign change at every step.
Regula falsi: A bracketing root-finding method that replaces interval halving with a secant-line intersection. It preserves a sign-changing bracket but may shrink one endpoint very slowly.
Sign function: A function that records whether a real number is negative, zero, or positive. Bisection uses endpoint signs to decide which half preserves the bracket.
False position: Another name for the regula falsi method, which uses a secant intersection while retaining a root bracket. Its endpoint updates differ from bisection's equal-halves rule despite sharing the bracketing principle.
Bisection error bound: The bound showing that after n bisections, the interval width is its initial width divided by 2ⁿ. The shrinking interval directly gives a rigorous bound on the root approximation error.
Secant method: An iterative root-finding method that estimates derivatives using successive function values. It often converges faster, but unlike bisection it does not guarantee a retained root bracket.

Linked from 20 pages