Introduction Notes Theory HOWTO Examples Engineering Error Questions Matlab Maple

Problem

Given a polynomial of one variable, p(x), find a value r (called a root) such that p(r) = 0.

Assumptions

This method will work for non-polynomial functions, but it is more appropriate for finding the roots of polynomials due to its ability to jump from real to complex iterates.

Tools

We will use sampling, quadratic interpolation, and iteration.

Initial Requirements

We have three initial approximation x₀, x₁, and x₂ of the root. It would be useful if |f(x₀)| > |f(x₁)| > |f(x₂)|, that is, the points are in descending absolute value when evaluated by f.

Iteration Process

Given three approximation x_{n - 2}, x_{n - 1}, and x_n, can find an interpolating quadratic polynomial which passes through the points:

(x_{n − 2} − x_{n − 1}, f(x_{n − 2}))
(0, f(x_{n − 1}))
(x_n − x_{n − 1}, f(x_n))

In this case, it is easiest (and numerically stable) to use the Vandermonde method to find the interpolating quadratic polynomial ax² + bx + c:

Having found the coefficients of the interpolating polynomial, we may now choose to find the root. There are two formulae for finding the roots of a quadratic polynomial: one with the radical in the numerator, the other with the radical in the denominator:

and

Because we are assuming that the three points x_{n - 2}, x_{n - 1}, and x_n are good approximations to the root, it follows that we want to find the root closest to these points, that is, the smallest root of the polynomial we found. The second formula is more numerically stable for finding the smallest root of a quadratic polynomial, and therefore we set:

where the sign in the denominator is equal to the sign of b.

Halting Conditions

There are three conditions which may cause the iteration process to halt (these are the same as the halting conditions for Newton's method):

We halt if both of the following conditions are met:
- The step between successive iterates is sufficiently small, |x_n + 1 - x_n| < ε_step, and
- The function evaluated at the point x_{n + 1} is sufficiently small, |f(x_n + 1)| < ε_abs.
If the system does not have a solution, we halt.
If we have iterated some maximum number of times, say N, and have not met Condition 1, we halt and indicate that a solution was not found.

If we halt due to Condition 1, we state that x_{n + 1} is our approximation to the root.

If we halt due to either Condition 2 or 3, we may either choose a different initial approximations x₀ and x₁, or state that a solution may not exist.