没有合适的资源?快使用搜索试试~ 我知道了~
首页Numerical methods for large eigenvalue problems .pdf
Numerical methods for large eigenvalue problems .pdf
需积分: 10 196 浏览量
更新于2023-05-30
评论
收藏 2.18MB PDF 举报
Matrix eigenvalue problems arise in a large number of disciplines of sciences and engineering. They constitute the basic tool used in designing buildings, bridges, and turbines, that are resistent to vibrations. They allow to model queueing networks, and to analyze stability of electrical networks or fluid flow. They also allow the scientist to understand local physical phenonema or to study bifurcation patterns in dynamical systems. In fact the writing of this book was motivated mostly by the second class of problems.
资源详情
资源评论
资源推荐

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
NUMERICAL METHODS FOR LARGE
EIGENVALUE PROBLEMS
Second edition
Yousef Saad
Copyright
c
2011 by the Society for Industrial and Applied Mathematics


Contents
Preface to Classics Edition xiii
Preface xv
1 Background in Matrix Theory and Linear Algebra 1
1.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Square Matrices and Eigenvalues . . . . . . . . . . . . . . . 2
1.3 Types of Matrices . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.1 Matrices with Special Srtuctures . . . . . . . . 4
1.3.2 Special Matrices . . . . . . . . . . . . . . . . . 5
1.4 Vector Inner Products and Norms . . . . . . . . . . . . . . . 6
1.5 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.7 Orthogonal Vectors and Subspaces . . . . . . . . . . . . . . 11
1.8 Canonical Forms of Matrices . . . . . . . . . . . . . . . . . 12
1.8.1 Reduction to the Diagonal Form . . . . . . . . . 14
1.8.2 The Jordan Canonical Form . . . . . . . . . . . 14
1.8.3 The Schur Canonical Form . . . . . . . . . . . 18
1.9 Normal and Hermitian Matrices . . . . . . . . . . . . . . . . 21
1.9.1 Normal Matrices . . . . . . . . . . . . . . . . . 21
1.9.2 Hermitian Matrices . . . . . . . . . . . . . . . 23
1.10 Nonnegative Matrices . . . . . . . . . . . . . . . . . . . . . 25
2 Sparse Matrices 29
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Storage Schemes . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3 Basic Sparse Matrix Operations . . . . . . . . . . . . . . . . 34
2.4 Sparse Direct Solution Methods . . . . . . . . . . . . . . . 35
2.5 Test Problems . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.5.1 Random Walk Problem . . . . . . . . . . . . . 36
2.5.2 Chemical Reactions . . . . . . . . . . . . . . . 38
2.5.3 The Harwell-Boeing Collection . . . . . . . . . 40
2.6 SPARSKIT . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.7 The New Sparse Matrix Repositories . . . . . . . . . . . . . 43
ix

x CONTENTS
2.8 Sparse Matrices in Matlab . . . . . . . . . . . . . . . . . . . 43
3 Perturbation Theory and Error Analysis 47
3.1 Projectors and their Properties . . . . . . . . . . . . . . . . . 47
3.1.1 Orthogonal Projectors . . . . . . . . . . . . . . 48
3.1.2 Oblique Projectors . . . . . . . . . . . . . . . . 50
3.1.3 Resolvent and Spectral Projector . . . . . . . . 51
3.1.4 Relations with the Jordan form . . . . . . . . . 53
3.1.5 Linear Perturbations of A . . . . . . . . . . . . 55
3.2 A-Posteriori Error Bounds . . . . . . . . . . . . . . . . . . . 59
3.2.1 General Error Bounds . . . . . . . . . . . . . . 59
3.2.2 The Hermitian Case . . . . . . . . . . . . . . . 61
3.2.3 The Kahan-Parlett-Jiang Theorem . . . . . . . . 66
3.3 Conditioning of Eigen-problems . . . . . . . . . . . . . . . 70
3.3.1 Conditioning of Eigenvalues . . . . . . . . . . . 70
3.3.2 Conditioning of Eigenvectors . . . . . . . . . . 72
3.3.3 Conditioning of Invariant Subspaces . . . . . . 75
3.4 Localization Theorems . . . . . . . . . . . . . . . . . . . . 77
3.5 Pseudo-eigenvalues . . . . . . . . . . . . . . . . . . . . . . 79
4 The Tools of Spectral Approximation 85
4.1 Single Vector Iterations . . . . . . . . . . . . . . . . . . . . 85
4.1.1 The Power Method . . . . . . . . . . . . . . . . 85
4.1.2 The Shifted Power Method . . . . . . . . . . . 88
4.1.3 Inverse Iteration . . . . . . . . . . . . . . . . . 88
4.2 Deflation Techniques . . . . . . . . . . . . . . . . . . . . . 90
4.2.1 Wielandt Deflation with One Vector . . . . . . . 91
4.2.2 Optimality in Wieldant’s Deflation . . . . . . . 92
4.2.3 Deflation with Several Vectors. . . . . . . . . . 94
4.2.4 Partial Schur Decomposition. . . . . . . . . . . 95
4.2.5 Practical Deflation Procedures . . . . . . . . . . 96
4.3 General Projection Methods . . . . . . . . . . . . . . . . . . 96
4.3.1 Orthogonal Projection Methods . . . . . . . . . 97
4.3.2 The Hermitian Case . . . . . . . . . . . . . . . 100
4.3.3 Oblique Projection Methods . . . . . . . . . . . 106
4.4 Chebyshev Polynomials . . . . . . . . . . . . . . . . . . . . 108
4.4.1 Real Chebyshev Polynomials . . . . . . . . . . 108
4.4.2 Complex Chebyshev Polynomials . . . . . . . . 109
5 Subspace Iteration 115
5.1 Simple Subspace Iteration . . . . . . . . . . . . . . . . . . . 115
5.2 Subspace Iteration with Projection . . . . . . . . . . . . . . 118
5.3 Practical Implementations . . . . . . . . . . . . . . . . . . . 121
5.3.1 Locking . . . . . . . . . . . . . . . . . . . . . 121
5.3.2 Linear Shifts . . . . . . . . . . . . . . . . . . . 123

CONTENTS xi
5.3.3 Preconditioning . . . . . . . . . . . . . . . . . 123
6 Krylov Subspace Methods 125
6.1 Krylov Subspaces . . . . . . . . . . . . . . . . . . . . . . . 125
6.2 Arnoldi’s Method . . . . . . . . . . . . . . . . . . . . . . . 128
6.2.1 The Basic Algorithm . . . . . . . . . . . . . . . 128
6.2.2 Practical Implementations . . . . . . . . . . . . 131
6.2.3 Incorporation of Implicit Deflation . . . . . . . 134
6.3 The Hermitian Lanczos Algorithm . . . . . . . . . . . . . . 136
6.3.1 The Algorithm . . . . . . . . . . . . . . . . . . 137
6.3.2 Relation with Orthogonal Polynomials . . . . . 138
6.4 Non-Hermitian Lanczos Algorithm . . . . . . . . . . . . . . 138
6.4.1 The Algorithm . . . . . . . . . . . . . . . . . . 139
6.4.2 Practical Implementations . . . . . . . . . . . . 143
6.5 Block Krylov Methods . . . . . . . . . . . . . . . . . . . . 145
6.6 Convergence of the Lanczos Process . . . . . . . . . . . . . 147
6.6.1 Distance between K
m
and an Eigenvector . . . 147
6.6.2 Convergence of the Eigenvalues . . . . . . . . . 149
6.6.3 Convergence of the Eigenvectors . . . . . . . . 150
6.7 Convergence of the Arnoldi Process . . . . . . . . . . . . . . 151
7 Filtering and Restarting Techniques 163
7.1 Polynomial Filtering . . . . . . . . . . . . . . . . . . . . . . 163
7.2 Explicitly Restarted Arnoldi’s Method . . . . . . . . . . . . 165
7.3 Implicitly Restarted Arnoldi’s Method . . . . . . . . . . . . 166
7.3.1 Which Filter Polynomials? . . . . . . . . . . . 169
7.4 Chebyshev Iteration . . . . . . . . . . . . . . . . . . . . . . 169
7.4.1 Convergence Properties. . . . . . . . . . . . . . 173
7.4.2 Computing an Optimal Ellipse . . . . . . . . . 174
7.5 Chebyshev Subspace Iteration . . . . . . . . . . . . . . . . . 177
7.5.1 Getting the Best Ellipse. . . . . . . . . . . . . . 178
7.5.2 Parameters k and m. . . . . . . . . . . . . . . . 178
7.5.3 Deflation . . . . . . . . . . . . . . . . . . . . . 178
7.6 Least Squares - Arnoldi . . . . . . . . . . . . . . . . . . . . 179
7.6.1 The Least Squares Polynomial . . . . . . . . . . 179
7.6.2 Use of Chebyshev Bases . . . . . . . . . . . . . 181
7.6.3 The Gram Matrix . . . . . . . . . . . . . . . . 182
7.6.4 Computing the Best Polynomial . . . . . . . . . 184
7.6.5 Least Squares Arnoldi Algorithms . . . . . . . . 188
8 Preconditioning Techniques 193
8.1 Shift-and-invert Preconditioning . . . . . . . . . . . . . . . 193
8.1.1 General Concepts . . . . . . . . . . . . . . . . 194
8.1.2 Dealing with Complex Arithmetic . . . . . . . . 195
8.1.3 Shift-and-Invert Arnoldi . . . . . . . . . . . . . 197
剩余284页未读,继续阅读














安全验证
文档复制为VIP权益,开通VIP直接复制

评论0