Root finding

Find a value $x$ satisfying $f(x)=0$ for a given function. Methods include the bisection method, which retains a bracket around a root, and derivative-based iteration. Finding a root numerically is distinct from the root as a mathematical object.

Suppose $f$ is continuous on an interval, differentiable in its interior, and $|f^{\prime }|\ge m>0$ throughout the interior. If $x_{\ast }$ is a root in the interval and $\hat{x}$ is another point in it, the mean value theorem gives $f(\hat{x})-f(x_{\ast })=f^{\prime }(\xi )(\hat{x}-x_{\ast })$ for an intermediate point $\xi$. Taking absolute values proves the stated bound from the residual of a root equation. This converts an observed residual into a stopping certificate, provided the evaluation error in that residual is also controlled.

The residual of a root equation $f(x)=0$ at a proposed solution $\hat{x}$ is the value $f(\hat{x})$. It measures violation of the equation, while the forward error $|\hat{x}-x_{\ast }|$ measures distance from a chosen exact root. Rescaling $f$ rescales the residual of a root equation without moving its roots, so a small residual needs a scale or a derivative bound before it certifies a small forward error.

The secant method approximates a zero of a function by repeatedly taking the zero of a secant line through the two most recent sampled points. The formula follows by setting the line $f(x_k)+(x-x_k)(f(x_k)-f(x_{k-1}))/(x_k-x_{k-1})$ equal to zero. It requires distinct sampled positions and a nonzero difference of sampled values, unless a root has already been found. After initialization it needs one new function evaluation per step. Unlike bisection, it need not retain a bracket. For a sufficiently smooth function near a simple root, its usual local order of convergence is $(1+\sqrt{5})/2$.^[ref]