Iterative Solution of Large Sparse Systems of Equations

Frontmatter

1. Introduction

Abstract

Iterative methods are almost 170 years old. The first iterative method for systems of linear equations is due to Carl Friedrich Gauß (the less correct spelling is: Gauss). His least squares method led him to a system of equations that was too large for the use of direct Gauß elimination. The iterative method described in „Supplementum theoriae combinationis observationum erroribus minime obnoxiae“ (1819–1822) today would be called the blockwise Gauß-Seidel method. The value that Gauß attributed to his iterative method can be seen in the excerpt from his letter of 1823 preceding the foreword of this book.

Wolfgang Hackbusch

2. Recapitulation of Linear Algebra

Abstract

According to Remark 1.2.1, the indices of the vectors are considered as nonordered. The (always finite) index set is denoted by I. A vector b ∈ ℝ ^I or b ∈ ℂ ^I is a mapping \( b:\,I\, \to \,K \) into \( K\, = \,r \) (real case) or \( K\, = \,c \) (complex case). The value of b at α ∈ I is denoted as vector component b_α. A vector composed of its components b_α is written in the form

$$ b\, = \,{\left( {{b_\alpha }} \right)_{\alpha \in I}}. $$

If the index set is ordered, we will identify the indices with 1, 2, ..., n := # I (number of elements in I) except when another notation is explicitly given. While the indices α, β, γ, ... are used for nonordered indices, we use i, j, k, ... in the ordered case.

Wolfgang Hackbusch

3. Iterative Methods

Abstract

In this chapter we consider the general properties of iterative methods. Such properties are consistency, ensuring the connection between the iterative method and the given system of equations, as well as convergence, guaranteeing the success of the iteration. The most important result of this chapter is the characterisation of the convergence of linear iterations by the spectral radius of the iteration matrix (cf. §3.1.3). Since we consider iterative methods for systems with regular matrices only, iterative methods for singular systems or those with rectangular matrices will not be studied. Concerning this topic, we refer to Maess [2], Marek [1], and Kosmol-Zhou [1].

Wolfgang Hackbusch

4. Methods of Jacobi and Gauß-Seidel and SOR Iteration in the Positive Definite Case

Abstract

The methods of Jacobi and Gauß-Seidel and the SOR method are closely connected and therefore they will be analysed simultaneously. The analysis, however, is essentially different for the case of positive definite matrices A discussed below and other cases studied in §§5–6. The introductory Section 4.1 underlines the fact that the positive definite case is of practical interest: The Poisson-model matrix is positive definite. Chapter 4.2 is a recapitulation and generalisation of the algorithms already known from §1.4. Simple modifications of these iterations are discussed in §4.3 and §4.6. The convergence results of the qualitative and quantitative kind are given in §4.4. Section 4.8 introduces the symmetric iterations and, in particular, the SSOR method.

Wolfgang Hackbusch

5. Analysis in the 2-Cyclic Case

Abstract

For the class of problems studied in this chapter, we succeed in obtaining quantitative convergence statements for the classical methods (Jacobi, Gauß-Seidel, and SOR iteration).

Wolfgang Hackbusch

6. Analysis for M-Matrices

Abstract

The positive definiteness A > 0 establishes a partial-order relation in the algebra of the Hermitian matrices. Another order relation in the algebra of all real matrices is defined by elementwise inequalities:

$$ A\, > \,B\,: \Leftrightarrow \,{a_{\alpha \beta }}\, > \,{b_{\alpha \beta }}\,\,for\,all\,\alpha ,\,\beta \, \in \,I, $$

(6.1.1a)

$$ A\; \ge \;B: \Leftrightarrow {a_{\alpha \beta }}\; \ge \;{b_{\alpha \beta }}\;\;{\rm{for all }}\alpha {\rm{,}}\;\beta \; \in \;I. $$

(6.1.1b)

In this chapter, we use the signs «>» and «≥» only in the componentwise sense (1a, b).

Wolfgang Hackbusch

7. Semi-Iterative Methods

Abstract

Let Φ be a linear and consistent but not necessarily convergent iteration (in the following it will also be called the basic iteration) with an iteration matrix M. Assume that for a starting iterate x⁰, the iterates

$$ {x^{m = 1}}\, = \,M{x^m}\, + \,Nb\, = \,\Phi \left( {{x^m},\,b} \right) $$

(7.1.1)

are computed. Up to now, the last computed iterate x ^m has been regarded as the result of an iteration Φ. The previously calculated x ^j (0 ≤ j ≤ m − 1) are forgotten.

Wolfgang Hackbusch

8. Transformations, Secondary Iterations, Incomplete Triangular Decompositions

Abstract

To describe the variety of iterative methods applied nowadays, one needs further techniques producing new iterations from already known ones or introducing new features. Techniques of the former kind are the transformations described in §§8.1–3 and the composed methods from §8.4 generated by a secondary iteration, whereas the ILU decomposition from §8.5 is of the latter kind, since it produces a new method.

Wolfgang Hackbusch

9. Conjugate Gradient Methods

Abstract

In the following, A ∈ ℝ ^{I x I} and b ∈ ℝ ^I are real. We consider a system

$$ Ax\, = \,b $$

(9.1.1)

and assume that

$$ A\,is\,positive\,definite. $$

(9.1.2)

System (1) is associated with the function

$$ F\left( x \right): = \,\frac{1}{2}\left\langle {Ax,\,x} \right\rangle \, - \,\left\langle {b,\,x} \right\rangle . $$

(9.1.3)

The derivative (gradient) of F is \( F'\left( x \right): = \,\frac{1}{2}\left( {A\, + \,{A^T}} \right)x\, - \,b \). Since A = A^T by assumption (2), the derivative equals

$$ F{\text{'}}'\left( x \right)\, = \,grad\,F\left( x \right)\, = \,Ax\, - \,b. $$

(9.1.4)

Wolfgang Hackbusch

10. Multi-Grid Methods

Abstract

Multi-grid methods belongs to the class of fastest iterations, because their convergence rate is independent of the step size h. Furthermore, their applicability does not require symmetry or positive definiteness, as, e.g., the standard conjugate gradient methods.

Wolfgang Hackbusch

11. Domain Decomposition Methods

Abstract

Various iterative methods can be classified as domain decomposition methods. Although a prototype of this iteration due to H. A. Schwarz (Viertelsjahresschrift der Naturforschenden Gesellschaft in Zürich, Vol. 15, 1870) is already 120 years old, this class of algorithms has attracted the interest of numerical analysts only recently.

Wolfgang Hackbusch

Backmatter