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