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 has a continuous derivative.

Tools

We will use sampling, the derivative, and iteration. Information about the derivative is derived from the model. We use Taylor series for error analysis.

Initial Requirements

We have an initial approximation x₀ of the root.

Iteration Process

Given the approximation 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:

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 derivative f⁽¹⁾(x_n) = 0, 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 approximation x₀, or state that a solution may not exist.