Iterative Methods for Sparse Linear Systems (2nd Edition) - Yousef Saad [2003](ISBN 0898715342)(O)(567s)_MNl_.pdf

(2648 KB) Pobierz
Iterative Methods
for Sparse
Linear Systems
Second Edition
0.19E+0
0.10E-0
Yousef Saad
Copyright c 2003 by the Society for Industrial and Applied Mathematics
Contents
Preface
Preface to second. edition. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . .
Preface to first edition . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . .
1 Background in Linear Algebra
1.1
Matrices . . . . . . . . . . . . . . . . . . . . . .
1.2
Square Matrices and Eigenvalues . . . . . . . . .
1.3
Types of Matrices . . . . . . . . . . . . . . . . .
1.4
Vector Inner Products and Norms . . . . . . . . .
1.5
Matrix Norms . . . . . . . . . . . . . . . . . . .
1.6
Subspaces, Range, and Kernel . . . . . . . . . . .
1.7
Orthogonal Vectors and Subspaces . . . . . . . .
1.8
Canonical Forms of Matrices . . . . . . . . . . .
1.8.1
Reduction to the Diagonal Form . . .
1.8.2
The Jordan Canonical Form . . . . .
1.8.3
The Schur Canonical Form . . . . .
1.8.4
Application to Powers of Matrices .
1.9
Normal and Hermitian Matrices . . . . . . . . . .
1.9.1
Normal Matrices . . . . . . . . . . .
1.9.2
Hermitian Matrices . . . . . . . . .
1.10
Nonnegative Matrices, M-Matrices . . . . . . . .
1.11
Positive-Definite Matrices . . . . . . . . . . . . .
1.12
Projection Operators . . . . . . . . . . . . . . . .
1.12.1
Range and Null Space of a Projector
1.12.2
Matrix Representations . . . . . . .
1.12.3
Orthogonal and Oblique Projectors .
1.12.4
Properties of Orthogonal Projectors .
1.13
Basic Concepts in Linear Systems . . . . . . . . .
1.13.1
Existence of a Solution . . . . . . .
1.13.2
Perturbation Analysis . . . . . . . .
xiii
xiii
xix
1
1
3
4
6
8
10
11
15
16
17
17
20
21
21
25
27
32
34
34
36
37
38
39
40
41
47
47
47
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Discretization of PDEs
2.1
Partial Differential Equations . . . . . . . . . . . . . . . . . .
2.1.1
Elliptic Operators . . . . . . . . . . . . . . . . .
v
vi
CONTENTS
2.1.2
The Convection Diffusion Equation . . . . . . .
Finite Difference Methods . . . . . . . . . . . . . . . . . . .
2.2.1
Basic Approximations . . . . . . . . . . . . . .
2.2.2
Difference Schemes for the Laplacean Operator
2.2.3
Finite Differences for 1-D Problems . . . . . . .
2.2.4
Upwind Schemes . . . . . . . . . . . . . . . .
2.2.5
Finite Differences for 2-D Problems . . . . . . .
2.2.6
Fast Poisson Solvers . . . . . . . . . . . . . . .
The Finite Element Method . . . . . . . . . . . . . . . . . .
Mesh Generation and Refinement . . . . . . . . . . . . . . .
Finite Volume Method . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
50
50
50
52
53
54
56
58
62
69
69
75
75
76
77
78
79
79
81
83
91
92
95
96
97
97
98
105
105
108
112
114
115
118
119
122
123
127
2.2
2.3
2.4
2.5
3 Sparse Matrices
3.1
Introduction . . . . . . . . . . . . . . . . . . . .
3.2
Graph Representations . . . . . . . . . . . . . . .
3.2.1
Graphs and Adjacency Graphs . . . .
3.2.2
Graphs of PDE Matrices . . . . . . .
3.3
Permutations and Reorderings . . . . . . . . . . .
3.3.1
Basic Concepts . . . . . . . . . . . .
3.3.2
Relations with the Adjacency Graph
3.3.3
Common Reorderings . . . . . . . .
3.3.4
Irreducibility . . . . . . . . . . . . .
3.4
Storage Schemes . . . . . . . . . . . . . . . . . .
3.5
Basic Sparse Matrix Operations . . . . . . . . . .
3.6
Sparse Direct Solution Methods . . . . . . . . . .
3.6.1
Minimum degree ordering . . . . . .
3.6.2
Nested Dissection ordering . . . . .
3.7
Test Problems . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4 Basic Iterative Methods
4.1
Jacobi, Gauss-Seidel, and SOR . . . . . . . . . . .
4.1.1
Block Relaxation Schemes . . . . . .
4.1.2
Iteration Matrices and Preconditioning
4.2
Convergence . . . . . . . . . . . . . . . . . . . . .
4.2.1
General Convergence Result . . . . . .
4.2.2
Regular Splittings . . . . . . . . . . .
4.2.3
Diagonally Dominant Matrices . . . .
4.2.4
Symmetric Positive Definite Matrices .
4.2.5
Property A and Consistent Orderings .
4.3
Alternating Direction Methods . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 Projection Methods
133
5.1
Basic Definitions and Algorithms . . . . . . . . . . . . . . . . 133
5.1.1
General Projection Methods . . . . . . . . . . . . 134
CONTENTS
5.1.2
Matrix Representation . . . . . . . .
General Theory . . . . . . . . . . . . . . . . . .
5.2.1
Two Optimality Results . . . . . . .
5.2.2
Interpretation in Terms of Projectors
5.2.3
General Error Bound . . . . . . . . .
One-Dimensional Projection Processes . . . . . .
5.3.1
Steepest Descent . . . . . . . . . . .
5.3.2
Minimal Residual (MR) Iteration . .
5.3.3
Residual Norm Steepest Descent . .
Additive and Multiplicative Processes . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
vii
135
137
137
138
140
142
142
145
147
147
157
157
158
160
160
162
165
167
168
171
172
173
174
179
179
180
185
190
193
194
194
195
196
196
200
201
203
204
206
208
209
210
214
5.2
5.3
5.4
6 Krylov Subspace Methods Part I
6.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . .
6.2
Krylov Subspaces . . . . . . . . . . . . . . . . . . . . . .
6.3
Arnoldi’s Method . . . . . . . . . . . . . . . . . . . . . .
6.3.1
The Basic Algorithm . . . . . . . . . . . . . .
6.3.2
Practical Implementations . . . . . . . . . . .
6.4
Arnoldi’s Method for Linear Systems (FOM) . . . . . . . .
6.4.1
Variation 1: Restarted FOM . . . . . . . . . .
6.4.2
Variation 2: IOM and DIOM . . . . . . . . .
6.5
GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5.1
The Basic GMRES Algorithm . . . . . . . . .
6.5.2
The Householder Version . . . . . . . . . . .
6.5.3
Practical Implementation Issues . . . . . . . .
6.5.4
Breakdown of GMRES . . . . . . . . . . . .
6.5.5
Variation 1: Restarting . . . . . . . . . . . . .
6.5.6
Variation 2: Truncated GMRES Versions . . .
6.5.7
Relations between FOM and GMRES . . . . .
6.5.8
Residual smoothing . . . . . . . . . . . . . .
6.5.9
GMRES for complex systems . . . . . . . . .
6.6
The Symmetric Lanczos Algorithm . . . . . . . . . . . . .
6.6.1
The Algorithm . . . . . . . . . . . . . . . . .
6.6.2
Relation with Orthogonal Polynomials . . . .
6.7
The Conjugate Gradient Algorithm . . . . . . . . . . . . .
6.7.1
Derivation and Theory . . . . . . . . . . . . .
6.7.2
Alternative Formulations . . . . . . . . . . .
6.7.3
Eigenvalue Estimates from the CG Coefficients
6.8
The Conjugate Residual Method . . . . . . . . . . . . . .
6.9
GCR, ORTHOMIN, and ORTHODIR . . . . . . . . . . . .
6.10
The Faber-Manteuffel Theorem . . . . . . . . . . . . . . .
6.11
Convergence Analysis . . . . . . . . . . . . . . . . . . . .
6.11.1
Real Chebyshev Polynomials . . . . . . . . .
6.11.2
Complex Chebyshev Polynomials . . . . . . .
6.11.3
Convergence of the CG Algorithm . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin