Previous: Introduction
Up: ContentsNext: Preconditioners
Previous Page: What Methods Are Covered?
Next Page: Overview of the Methods

Iterative Methods

The term ``iterative method'' refers to a wide range of techniques that use successive approximations to obtain more accurate solutions to a linear system at each step. In this book we will cover two types of iterative methods. Stationary methods are older, simpler to understand and implement, but usually not as effective. Nonstationary methods are a relatively recent development; their analysis is usually harder to understand, but they can be highly effective. The nonstationary methods we present are based on the idea of sequences of orthogonal vectors. (An exception is the Chebyshev iteration method, which is based on orthogonal polynomials.)

The rate at which an iterative method converges depends greatly on the spectrum of the coefficient matrix. Hence, iterative methods usually involve a second matrix that transforms the coefficient matrix into one with a more favorable spectrum. The transformation matrix is called a preconditioner. The use of a good preconditioner improves the convergence of the iterative method, sufficiently to overcome the extra cost of constructing and applying the preconditioner. Indeed, without a preconditioner the iterative method may even fail to converge.

• Linear: some measure of the distance to the solution decreases by a constant factor in each iteration.
• Superlinear: the measure of the error decreases by a growing constant.
• Smooth: the measure of the error decreases in all or most iterations, though not necessarily by the same factor.
• Irregular: the measure of the error decreases in some iterations and increases in others. This observation unfortunately does not imply anything about the ultimate convergence of the method.
• Stalled: the measure of the error stays more or less constant during a number of iterations. As above, this does not imply anything about the ultimate convergence of the method.

• Overview of the Methods
• Stationary Iterative Methods
  • The Jacobi Method
    • Convergence of the Jacobi method
  • The Gauss-Seidel Method
  • The Successive Overrelaxation Method
    • Choosing the Value of Omega
  • The Symmetric Successive Overrelaxation Method
  • Notes and References
• Nonstationary Iterative Methods
  • Conjugate Gradient Method (CG)
    • Theory
    • Convergence
    • Implementation
    • Further references
  • MINRES and SYMMLQ
    • Theory
  • CG on the Normal Equations, CGNE and CGNR
    • Theory
  • Generalized Minimal Residual (GMRES)
    • Theory
    • Implementation
  • BiConjugate Gradient (BiCG)
    • Convergence
    • Implementation
  • Quasi-Minimal Residual (QMR)
    • Convergence
    • Implementation
  • Conjugate Gradient Squared Method (CGS)
    • Convergence
    • Implementation
  • BiConjugate Gradient Stabilized (Bi-CGSTAB)
    • Convergence
    • Implementation
  • Chebyshev Iteration
    • Comparison with other methods
    • Convergence
    • Implementation
• Summary of the Methods
• A short history of Krylov methods
• Survey of recent Krylov methods