Root-finding algorithm

A computational procedure for finding exact or approximate solutions to an equation by locating zeros of a function. Methods differ in their assumptions, convergence behavior, and computational cost.

Bisection method: A root-finding method that repeatedly halves an interval whose endpoint values have opposite signs. It guarantees convergence for a continuous function on a sign-changing interval.
Root of a function: An input at which a function evaluates to zero. The target of every root-finding procedure is a zero of the chosen function.
Bracketing method: A root-finding approach that maintains an interval known to contain a root. This broad family prioritizes preserving a root-containing interval over aggressive local steps.
Nonlinear equation: An equation involving at least one nonlinear function of its unknowns. Root-finding algorithms are standard tools for solving nonlinear equations numerically.
Multiple root: A polynomial zero whose multiplicity is greater than one. Standard Newton iteration loses its usual quadratic convergence at multiple roots.
Newton's method: An iterative method that estimates a root using the function's tangent line at the current approximation. Its fast local convergence contrasts with its sensitivity to starting values and derivatives.
Intermediate value theorem: A theorem stating that a continuous function takes every value between its values at two points. It establishes that a sign-changing interval contains at least one root.
Open method: A root-finding method that updates estimates without maintaining a guaranteed root-containing interval. Open methods can converge rapidly but may fail without suitable starting estimates.
Newton–Raphson method for systems: An extension of Newton's method that solves coupled nonlinear equations using Jacobian matrices. It applies derivative-based root finding to systems rather than a single scalar equation.
Global convergence: Convergence of an algorithm from a broad set of starting points rather than only nearby initial values. Guaranteeing convergence beyond a local neighborhood remains a central method-design challenge.

Linked from 10 pages