Introduction Notes Theory HOWTO Examples Engineering Error Questions Matlab Maple

Problem

Given n functions, each of n variables (given by a vector x), f_i(x), find a vector r (called a root) such that f(r) = 0.

We will write the n functions as a vector-valued function f(x).

Assumptions

We will assume that each of the functions f_i(x) is continuous and has continuous partial derivatives.

Tools

We will use sampling, partial derivatives, iteration, and solving systems of linear equations. Information about the partial derivatives is derived from the model.

Initial Requirements

We have an initial approximation x₀ of the root.

We have calculated the Jacobian J(f)(x).

Iteration Process

Given the approximation x_n, we solve the system of linear equations defined by

J(f)(x_n) Δx_n = -f(x_n)

for Δx_n and then set:

x_{n + 1} = x_n + Δx_n

Halting Conditions

There are three conditions which may cause the iteration process to halt (where the norm used may be any of the 1, 2, or infinity norms):

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 Jacobian is indeterminate, that is, the determinant |J(f)(x_n)| = 0, the iteration process fails 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.