next up previous

2.2.4 Convergence Characterization

The convergence properties of an algorithm are described by two analytic quantities: convergence order and convergence ratio. A sequence is said to converge to if the following holds: . The sequence is said to converge to with order p if p is the largest nonnegative number for which a finite limit exists, where

When p=1 and , the sequence is said to converge linearly (e.g., for n=1); when p=1 and , the sequence converges superlinearly (e.g., ); and when p=2, the convergence is quadratic (e.g., ). Thus, quadratic convergence is more rapid than superlinear, which in turn is faster than linear. The constant is the associated convergence ratio.

(See exercise 6.)