Next: Solving Linear Algebraic Equations Up: Preliminaries Previous: Sensitivity and Conditioning

## Order and rate of convergence

Iteration is a common approach widely used in various numerical methods. It is the hope that an iteration in the general form of will eventually converge to the true solution of the problem at the limit when . The concern is whether this iteration will converge, and, if so, the rate of convergence. Specifically we use the following to represent how quickly the error converges to zero:

Here is called the order of convergence, the constant is the rate of convergence or asymptotic error constant.

This expression may be better understood when it is interpreted as when . Obviously, the larger and the smaller , the more quickly the sequence converges. Specially, we consider the following cases:

• If and , , then
• if , the convergence is sublinear
• if , the convergence is linear with the rate of convergence of .
• if , the convergence is superlinear
• If , , the convergence is quadratic.
• If , , the convergence is cubic.

The iteration can be written in terms of the errors and . Consider the Taylor expansion:

Subtracting from both sides, we get

At the limit , all higher order error terms become zero, we have

If , then the convergence is linear. However, if , then

and we have

the convergence is quadratic. We see that if the iteration function has zero derivative at the fixed point, the iteration may be accelerated.

Examples:

• , the sequence is

This is a sublinear convergence as only when will the limit be a constant .

• , the sequence is

This is a linear convergence of order and rate .
• , the sequence is

This is superlinear, specifically quadratic, convergence of order and rate .

From these examples we see that there is a unique exponent , the order of convergence, so that

In practice, the true solution is unknown and so is the error . However, it can be estimated if the convergence is superlinear, satisfying

Consider:

i.e., when ,

The order and rate of convergence can be estimated by

Next: Solving Linear Algebraic Equations Up: Preliminaries Previous: Sensitivity and Conditioning
Ruye Wang 2015-02-12