Root-finding algorithm

From Calculus
Jump to: navigation, search

Definition

The term root-finding algorithm is used for any algorithm, exact or numerical, for finding a root of a function. Explicitly, given a function f, the goal is to find a value x in the domain of f such that f(x) = 0.

The term is typically used for an algorithm that fins any root of a function, rather than all roots, though it may also be used for an algorithm intended to find all roots.

Types

Root-finding algorithms can be of two kinds:

  • Algorithms where we output nested intervals at intermediate stages, i.e., each interval is contained in the preceding one, and at every stage, the interval identified so far is guaranteed to contain at least one root.
  • Algorithms that involve successive point estimates for the root, but with no explicit guarantee that the actual root is within a particular distance of a point estimate.