应用迭代分析

Preface to the Series in Information and Computational Science
Preface
Chapter 1 Introduction 1
1.1 Background in linear algebra 1
1.1.1 Basic symbols, notations, and de.nitions 1
1.1.2 Vector norm 2
1.1.3Matrix norm 4
1.1.4 Spectral radii 8
1.2 Spectralresultsofmatrix 10
1.3 Specialmatrices 15
1.3.1 Reducible and irreducible matrices 15
1.3.2 Diagonally dominant matrices 16
1.3.3 Nonnegative matrices 20
1.3.4 p-cyclic matrices 22
1.3.5 Toeplitz, Hankel, Cauchy, Cauchy-like and Hessenberg matrices 24
1.4 Matrix decomposition 27
1.4.1 LU decomposition 27
1.4.2 Singular value decomposition 28
1.4.3 Conjugate decomposition 30
1.4.4 QZ decomposition 32
1.4.5 S & T decomposition 33
1.5 Exercises 37
Chapter 2 Basic Methods and Convergence 40
2.1 Basic concepts 40
2.2 The Jacobi method 43
2.3 The Gauss-Seidel method 46
2.4 The SOR method 49
2.5 M-matrices and splitting methods 58
2.5.1 M-matrix 58
2.5.2 Splitting methods 60
2.5.3 Comparison theorems 62
2.5.4 Multi-splitting methods 66
2.5.5 Generalized Ostrowski-Reich theorem 67
2.6 Error analysis of iterative methods 69
27 Iterative re.nement 70
2.8 Exercises 75
Chapter 3 Non-stationary Methods 78
3.1 Conjugategradientmethods 79
3.1.1 Steepest descent method 79
3.1.2 Conjugate gradient method 80
3.1.3 Preconditioned conjugate gradient method 83
3.1.4 Generalized conjugate gradient method 85
3.1.5 Theoretical results on the conjugate gradient method 85
3.1.6 Generalized product-type methods based on Bi-CG 91
3.1.7 Inexact preconditioned conjugate gradient method 92
3.2 Lanczos method 93
3.3 GMRES method and QMR method 95
3.3.1 GMRES method 95
3.3.2 QMR method 98
3.3.3 Variants of the QMR method 100
3.4 Direct projection method 101
3.4.1 Theory of the direct projection method 102
3.4.2 Direct projection algorithms 105
3.5 Semi-conjugate direction method 107
3.5.1 Semi-conjugate vectors 107
3.5.2 Left conjugate direction method 110
3.5.3 One possible way to .nd left conjugate vector set 112
3.5.4 Remedy for breakdown 117
3.5.5 Relation with Gaussian elimination 119
3.6 Krylov subspace methods 121
3.7 Exercises 122
Chapter 4 Iterative Methods for Least Squares Problems 126
4.1 Introduction 126
4.2 Basic iterative methods 128
4.3 BlockSOR methods 131
4.3.1 Block SOR algorithms 131
4.3.2 Convergence and optimal factors 132
4.3.3 Example 135
4.4 Preconditioned conjugate gradient methods 136
4.5 Generalized least squares problems 138
4.5.1 Block SOR methods 139
4.5.2 Preconditioned conjugate gradient method 142
4.5.3 Comparison 143
4.5.4 SOR-like methods 144
4.6 Rank de.cient problems 148
4.6.1 Augmented system of normal equation 149
4.6.2 Block SOR algorithms 150
4.6.3 Convergence and optimal factor 151
4.6.4 Preconditioned conjugate gradient method 154
4.6.5 Comparison results 158
4.7 Exercises 161
Chapter 5 Preconditioners 163
5.1 LU decomposition and orthogonal transformations 164
5.1.1 Gilbert and Peierls algorithm for LU decomposition 164
5.1.2 Orthogonal transformations 166
5.2 Stationary preconditioners 167
5.2.1 Jacobi preconditioner 167
5.2.2 SSOR preconditioner 168
5.3 Incompletefactorization 169
5.3.1 Point incomplete factorization 170
5.3.2 Modi.ed incomplete factorization 172
5.3.3 Block incomplete factorization 172
5.4 Diagonally dominant preconditioner 173
5.5 Preconditionerforleastsquaresproblems 177
5.5.1 Preconditioner by LU decomposition 179
5.5.2 Preconditioner by direct projection method 181
5.5.3 Preconditioner by QR decomposition 182
5.6 Exercises 186
Chapter 6 Singular Linear Systems 188
6.1 Introduction 188
6.2 Properties of singular systems 191
6.3 Splittingmethodsforsingularsystems 195
6.4 NonstationarymethodsforSingularsystems 219
6.4.1 symmetric and positive semide.nite systems 219
6.4.2 General systems 222
6.5 Exercises 225
Bibliography 228
Index 249
《信息与计算科学丛书》 253