没有合适的资源?快使用搜索试试~ 我知道了~
Numerical methods for large eigenvalue problems .pdf
需积分: 10 11 下载量 127 浏览量
2019-10-25
10:10:53
上传
评论
收藏 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页未读,继续阅读
资源评论
HollyYu0320
- 粉丝: 9
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功