Real root finding of polynomials is a fundamental problem in mathematics with applications across various scientific and engineering disciplines. This article provides an overview of a common approach to solving this problem: real root isolation using interval bracketing. This method involves systematically partitioning the real number line into smaller and smaller intervals until each interval contains at most one root, effectively isolating all real roots.

Core Idea: Interval Splitting and Arithmetic

The core idea behind interval bracketing algorithms is to repeatedly subdivide an interval known to contain roots into smaller subintervals until we separated all roots into disjoint intervals. This process relies on interval arithmetic, where operations are performed on intervals rather than single numbers. This allows us to maintain rigorous bounds on the location of the roots. A common method for interval splitting is bisection.

Bisection Method

The bisection method is a simple and robust interval bracketing algorithm. It works by repeatedly halving an interval $[a, b]$ known to contain a root. The midpoint $c = (a + b) / 2$ is evaluated. If $f(c) = 0$, then $c$ is a root. Otherwise, the algorithm proceeds with either the interval $[a, c]$ or $[c, b]$, depending on the sign of $f(a)$ and $f(c)$ (or $f(c)$ and $f(b)$).

For the bisection method to work effectively, certain conditions must be met:

  • Finite Interval: The initial interval $[a, b]$ must be finite.
  • Sign Change/Existence of Root: The function $f(x)$ must be continuous on $[a, b]$, and $f(a)$ and $f(b)$ must have opposite signs. This guarantees the existence of at least one root in the interval by the Intermediate Value Theorem.
  • Direction of Update: The update rule (choosing either $[a, c]$ or $[c, b]$) must be consistent and based on the sign change of the function.

The bisection method offers guaranteed convergence, but its rate of convergence is linear. Variants like the Vincent-Collins-Akritas (VCA) bisection method can improve performance by incorporating information about the polynomial’s derivatives.

Continued Fractions and Vincent’s Theorem

Methods based on continued fractions offer an alternative approach to real root isolation. These methods leverage Vincent’s theorem, which states that by repeatedly applying transformations of the form $x = a + 1/y$ (where $a$ is a positive integer), a polynomial with only simple real roots can be transformed into a polynomial with at most one sign variation in its coefficients. This property allows for efficient root isolation.

The process typically involves the following steps:

  1. Transformation: Apply the transformation $x = a + 1/y$ to the polynomial, where $a$ is chosen to reduce the number of sign variations.
  2. Continued Fraction Expansion: This transformation generates a sequence of integers $a_1, a_2, a_3, …$, which form the coefficients of a continued fraction representation of the root.
  3. Root Isolation: The continued fraction expansion leads to a sequence of nested intervals that converge to the real root.

Algorithms based on Vincent’s theorem, such as the Vincent-Akritas-Strzebonski (VAS) algorithm, are known for their efficiency in isolating real roots, particularly for polynomials with well-separated roots. They often outperform bisection in terms of speed.

Bounds on Root Magnitudes

Before initiating the interval bracketing process, it’s often useful to establish bounds on the magnitudes of the roots. This helps define a suitable initial interval for the search. Common methods for determining root bounds include:

  • Cauchy’s Bound: Provides an upper bound on the magnitude of the roots based on the coefficients of the polynomial.
  • Lagrange’s Bound: Offers another method for calculating an upper bound on the magnitude of the roots, sometimes providing tighter bounds than Cauchy’s bound.

Ordering: Intermediate Value Theorem

The Intermediate Value Theorem (IVT) plays a crucial role in interval bracketing algorithms. It states that if a continuous function $f$ takes on values $f(a)$ and $f(b)$ at the endpoints of an interval $[a, b]$, then it also takes on any value between $f(a)$ and $f(b)$ at some point within the interval. This theorem justifies the use of sign changes to detect the presence of a root within an interval.

Counting Real Roots

To determine the number of real roots within a given interval, we can use the following methods:

  • Sturm’s Theorem: Provides a precise count of the number of distinct real roots of a polynomial within a given interval.
  • Descartes’ Rule of Signs: Gives an upper bound on the number of positive real roots of a polynomial by counting the sign changes in its coefficients.

Simplifications: Function Transformations

Certain function transformations can simplify the root-finding process:

  • Reflecting: Replacing $x$ with $-x$ reflects the polynomial across the y-axis, allowing us to find negative roots by finding positive roots of the transformed polynomial.
  • Scaling: Multiplying $x$ by a constant scales the roots.
  • Shifting: Replacing $x$ with $x - c$ shifts the polynomial horizontally.

Interval Refinement

Once an interval containing a root has been identified, various techniques can be used to refine the approximation of the root, reducing the interval size (and thus the distance between the computed and true root). This can involve further bisection steps or more advanced methods like Newton-Raphson (when applicable).

Further Reading