Introduction Notes Theory HOWTO Examples Engineering Error Questions Matlab Maple

Problem

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

Assumptions

We will assume that the function f(x) is continuous and for the technique to converge, it is useful that the function is also differentiable, but this is only necessary for the error analysis.

Tools

We will use sampling, interpolation, and iteration.

Initial Requirements

We have two initial approximation x₀ and x₁ of the root. It would be useful if |f(x₀)| > |f(x₁)|, that is, the second point is a better approximation of the root.

Iteration Process

Given the approximations x_{n − 1} and x_n, the next approximation x_{n + 1} is defined to be

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 denominator is zero, in which case the iteration process fails (division-by-zero) and 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.