This book is the second volume in a projected five-volume survey of numerical linear algebra and matrix algorithms. This volume treats the numerical solution of dense and large-scale eigenvalue problems with an emphasis on algorithms and the theoretical background required to understand them. Stressing depth over breadth, Professor Stewart treats the derivation and implementation of the more important algorithms in detail. The notes and references sections contain pointers to other methods along with historical comments.
The book is divided into two parts: dense eigenproblems and large eigenproblems. The first part gives a full treatment of the widely used QR algorithm, which is then applied to the solution of generalized eigenproblems and the computation of the singular value decomposition. The second part treats Krylov sequence methods such as the Lanczos and Arnoldi algorithms and presents a new treatment of the Jacobi-Davidson method.
The volumes in this survey are not intended to be encyclopedic. By treating carefully selected topics in depth, each volume gives the reader the theoretical and practical background to read the research literature and implement or modify new algorithms. The algorithms treated are illustrated by pseudocode that has been tested in MATLAB implementations.
Audience
The volumes in the series are intermediate-level monographs, suitable for self-study by professionals and graduate students in the sciences and engineering. The first volume, Matrix Algorithms, Volume I: Basic Decompositions , was published by SIAM in 1998 (ISBN 0-89871-414-1).
Author(s): G. W. Stewart
Edition: 1
Publisher: SIAM: Society for Industrial and Applied Mathematics
Year: 2001
Language: English
Pages: 490
Cover......Page 1
Table of Contents......Page 6
Table of Algorithms......Page 16
Preface......Page 18
1 The Algebra of Eigensystems......Page 22
1.1 Eigenvalues & eigenvectors......Page 23
1.2 Geometric multiplicity & defective matrices......Page 27
1.3 Similarity transformations......Page 29
1.4 Schur Decompositions......Page 31
1.5 Block diagonalization & Sylvester's equation......Page 36
1.6 Jordan form......Page 41
1.7 Notes & references......Page 44
2.1 Matrix & vector norms......Page 46
2.2 The spectral radius......Page 51
2.3 Matrix powers......Page 54
2.4 Notes & references......Page 57
3.1 The perturbation of eigenvalues......Page 58
3.2 Simple eigenpairs......Page 65
3.3 Notes & references......Page 73
2 The QR Algorithm......Page 76
1.1 The power method......Page 77
1.2 The inverse power method......Page 87
1.3 Notes & references......Page 90
2 The Explicitly Shifted QR Algorithm......Page 92
2.1 The QR algorithm & the inverse power method......Page 93
2.2 The unshifted QR algorithm......Page 96
2.3 Hessenberg form......Page 101
2.4 The explicitly shifted algorithm......Page 115
2.5 Bits & pieces......Page 125
2.6 Notes & references......Page 131
3.1 Real Schur form......Page 134
3.2 The uniqueness of Hessenberg reduction......Page 137
3.3 The implicit double shift......Page 138
3.4 Notes & references......Page 149
4 The Generalized Eigenvalue Problem......Page 150
4.1 The theoretical background......Page 151
4.2 Real Schur & Hessenberg-triangularforms......Page 164
4.3 The doubly shifted QZ algorithm......Page 168
4.4 Important miscellanea......Page 173
4.5 Notes & References......Page 176
3 The Symmetric Eigenvalue Problem......Page 178
1.1 Reduction to tridiagonal form......Page 179
1.2 The symmetric tridiagonal QR algorithm......Page 184
1.3 Notes & references......Page 190
2.1 Rank-one updating......Page 192
2.2 A Divide-and-conqueralgorithm......Page 202
2.3 Eigenvalues & eigenvectors of band matrices......Page 207
2.4 Notes & References......Page 222
3.1 Background......Page 224
3.2 Thecross-productalgorithm......Page 231
3.3 Reduction to bidiagonaIform......Page 236
3.4 The QR algorithm......Page 238
3.6 Notes & references......Page 247
4.1 Theory......Page 250
4.2 Wilkinson's algorithm......Page 252
4.3 Notes & references......Page 255
4 Eigenspaces & Their Approximation......Page 260
1.1 Definitions......Page 261
1.2 Simple eigenspaces......Page 265
1.3 Notes & references......Page 268
2.1 Canonical angles......Page 269
2.2 Residual analysis......Page 272
2.3 Perturbation theory......Page 279
2.4 Residual bounds for Hermitian matrices......Page 283
2.5 Notes & references......Page 285
3.1 Krylov sequences & Krylov spaces......Page 287
3.2 Convergence......Page 290
3.3 Block Krylov sequences......Page 298
3.4 Notes & references......Page 300
4 Rayleigh-Ritz Approximation......Page 301
4.1 Rayleigh-Ritz methods......Page 302
4.2 Convergence......Page 305
4.3 Refined Ritz vectors......Page 310
4.4 Harmonic Ritz vectors......Page 313
4.5 Notes & references......Page 316
1 Krylov Decompositions......Page 318
1.1 Arnoldi decompositions......Page 319
1.2 Lanczos decompositions......Page 327
1.3 Krylov decompositions......Page 329
1.4 Computation of refined & Harmonic Ritz vectors......Page 335
1.5 Notes & references......Page 336
2 The Restarted Arnoldi Method......Page 337
2.1 The implicitly restarted Arnoldi method......Page 338
2.2 Krylov-Schur restarting......Page 346
2.3 Stability, convergence, & deflation......Page 353
2.4 Rational Krylov Transformations......Page 363
2.5 Notes & references......Page 365
3 The Lanczos Algorithm......Page 368
3.1 Reorthogonalization & the Lanczos aJgorithm......Page 369
3.2 Full reorthogonalization & restarting......Page 372
3.3 Semiorthogonal methods......Page 373
3.4 Notes & references......Page 386
4 The Generalized Eigenvalue Problem......Page 388
4.1 Transformation & convergence......Page 389
4.2 Positive definite B......Page 391
4.3 Notes & references......Page 400
1 Subspace Iteration......Page 402
1.1 Theory......Page 403
1.2 Implementation......Page 407
1.3 Symmetric matrices......Page 412
1.4 Notes & references......Page 415
2 Newton-Based Methods......Page 416
2.1 Approximate Newton methods......Page 417
2.2 The Jacobi-Davidson method......Page 425
2.3 Notes & references......Page 439
1 Scalars, vectors, & matrices......Page 442
2 Linear algebra......Page 445
4 The LU decomposition......Page 446
6 The QR decomposition......Page 447
7 Projectors......Page 448
References......Page 450
Index......Page 472
