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.

Tools

We will use sampling, bracketing, and iteration.

Initial Requirements

We have an initial bound [a, b] on the root, that is, f(a) and (b) have opposite signs.

Iteration Process

Given the interval [a, b], define c = (a + b)/2. Then

if f(c) = 0 (unlikely in practice), then halt, as we have found a root,
if f(c) and f(a) have opposite signs, then a root must lie on [a, c], so assign b = c,
else f(c) and f(b) must have opposite signs, and thus a root must lie on [c, b], so assign a = c.

Halting Conditions

There are three conditions which may cause the iteration process to halt:

As indicated, if f(c) = 0.
We halt if both of the following conditions are met:
- The width of the interval (after the assignment) is sufficiently small, that is b - a < ε_step, and
- The function evaluated at one of the end point |f(a)| or |f(b)| < ε_abs.
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 c is our approximation to the root. If we halt according to Condition 2, we choose either a or b, depending on whether |f(a)| < |f(b)| or |f(a)| > |f(b)|, respectively.

If we halt due to Condition 3, then we indicate that a solution may not exist (the function may be discontinuous).