Fundamentals of matrix computations

Preface. Acknowledgments. 1 Gaussian Elimination and Its Variants. 1.1 Matrix Multiplication. 1.2 Systems of Linear Equations. 1.3 Triangular Systems. 1.4 Positive Definite Systems; Cholesky Decomposition. 1.5 Banded Positive Definite Systems. 1.6 Sparse Positive Definite Systems. 1.7 Gaussian Elimination and the LU Decomposition. 1.8 Gaussain Elimination and Pivoting. 1.9 Sparse Gaussian Elimination. 2 Sensitivity of Linear Systems. 2.1 Vector and Matrix Norms. 2.2 Condition Numbers. 2.3 Perturbing the Coefficient Matrix. 2.4 A Posteriori Error Analysis Using the Residual. 2.5 Roundoff Errors; Backward Stability. 2.6 Propagation of Roundoff Errors. 2.7 Backward Error Analysis of Gaussian Elimination. 2.8 Scaling. 2.9 Componentwise Sensitivity Analysis. 3 The Least Squares Problem. 3.1 The Discrete Square Problem. 3.2 Orthogonal Matrices, Rotators and Reflectors. 3.3 Solution of the Least Squares Problem. 3.4 The Gram-Schmidt Process. 3.5 Geometric Approach. 3.6 Updating the QR Decomposition. 4 The Singular Value Decomposition. 4.1 Introduction. 4.2 Some Basic Applications of Singular Values. 4.3 The SVD and the Least Squares Problem. 4.4 Sensitivity of the Least Squares Problem. 5 Eigenvalues and Eigenvectors I. 5.1 Systems of Differential Equations. 5.2 Basic Facts. 5.3 The Power Method and Some Simple Extensions. 5.4 Similarity Transforms. 5.5 Reduction to Hessenberg and Tridiagonal Forms. 5.6 Francis's Algorithm. 5.7 Use of Francis's Algorithm to Calculate Eigenvectors. 5.8 The SVD Revisted. 6 Eigenvalues and Eigenvectors II. 6.1 Eigenspaces and Invariant Subspaces. 6.2 Subspace Iteration and Simultaneous Iteration. 6.3 Krylov Subspaces and Francis's Algorithm. 6.4 Large Sparse Eigenvalue Problems. 6.5 Implicit Restarts. 6.6 The Jacobi-Davidson and Related Algorithms. 7 Eigenvalues and Eigenvectors III. 7.1 Sensitivity of Eigenvalues and Eigenvectors. 7.2 Methods for the Symmetric Eigenvalue Problem. 7.3 Product Eigenvalue Problems. 7.4 The Generalized Eigenvalue Problem. 8 Iterative Methods for Linear Systems. 8.1 A Model Problem. 8.2 The Classical Iterative Methods. 8.3 Convergence of Iterative Methods. 8.4 Descent Methods; Steepest Descent. 8.5 On Stopping Criteria. 8.6 Preconditioners. 8.7 The Conjugate-Gradient Method. 8.8 Derivation of the CG Algorithm. 8.9 Convergence of the CG Algorithm. 8.10 Indefinite and Nonsymmetric Problems. References. Index. Index of MATLAB Terms CONTENTS ......Page 6 Preface ......Page 9 Acknowledgments ......Page 14 1.1 Matrix Multiplication ......Page 16 1.2 Systems of Linear Equations ......Page 27 1.3 Triangular Systems ......Page 39 1.4 Positive Definite Systems; Cholesky Decomposition ......Page 48 1.5 Banded Positive Definite Systems ......Page 70 1.6 Sparse Positive Definite Systems ......Page 79 1.7 Gaussian Elimination and the LU Decomposition ......Page 86 1.8 Gaussian Elimination with Pivoting ......Page 109 1.9 Sparse Gaussian Elimination ......Page 122 2 Sensitivity of Linear Systems ......Page 128 2.1 Vector and Matrix Norms ......Page 129 2.2 Condition Numbers ......Page 137 2.3 Perturbing the Coefficient Matrix ......Page 148 2.4 A Posteriori Error Analysis Using the Residual ......Page 152 2.5 Roundoff Errors; Backward Stability ......Page 154 2.6 Propagation of Roundoff Errors ......Page 164 2.7 Backward Error Analysis of Gaussian Elimination ......Page 172 2.8 Scaling ......Page 186 2.9 Componentwise Sensitivity Analysis ......Page 191 3.1 The Discrete Least Squares Problem ......Page 198 3.2 Orthogonal Matrices, Rotators, and Reflectors ......Page 202 3.3 Solution of the Least Squares Problem ......Page 230 3.4 The Gram-Schmidt Process ......Page 238 3.5 Geometric Approach ......Page 253 3.6 Updating the QR Decomposition......Page 262 4 The Singular Value Decomposition ......Page 274 4.1 Introduction ......Page 275 4.2 Some Basic Applications of Singular Values ......Page 279 4.3 The SVD and the Least Squares Problem ......Page 288 4.4 Sensitivity of the Least Squares Problem ......Page 294 5.1 Systems of Differential Equations ......Page 304 5.2 Basic Facts ......Page 320 5.3 The Power Method and Some Simple Extensions ......Page 329 5.4 Similarity Transforms ......Page 349 5.5 Reduction to Hessenberg and Tridiagonal Forms ......Page 365 5.6 Francis’s Algorithm ......Page 373 5.7 Use of Francis’s Algorithm to Calculate Eigenvectors ......Page 401 5.8 The SVD Revisited ......Page 404 6 Eigenvalues and Eigenvectors II ......Page 424 6.1 Eigenspaces and Invariant Subspaces ......Page 425 6.2 Subspace Iteration and Simultaneous Iteration ......Page 435 6.3 Krylov Subspaces and Francis’s Algorithm ......Page 443 6.4 Large Sparse Eigenvalue Problems ......Page 452 6.5 Implicit Restarts ......Page 471 6.6 The Jacobi-Davidson and Related Algorithms ......Page 481 7.1 Sensitivity of Eigenvalues and Eigenvectors ......Page 486 7.2 Methods for the Symmetric Eigenvalue Problem ......Page 500 7.3 Product Eigenvalue Problems ......Page 526 7.4 The Generalized Eigenvalue Problem ......Page 541 8 Iterative Methods for Linear Systems ......Page 560 8.1 A Model Problem ......Page 561 8.2 The Classical Iterative Methods ......Page 569 8.3 Convergence of Iterative Methods ......Page 583 8.4 Descent Methods; Steepest Descent ......Page 598 8.5 On Stopping Criteria ......Page 609 8.6 Preconditioners ......Page 611 8.7 The Conjugate-Gradient Method ......Page 617 8.8 Derivation of the CG Algorithm ......Page 622 8.9 Convergence of the CG Algorithm ......Page 630 8.10 Indefinite and Nonsymmetric Problems ......Page 636 References ......Page 642 Index ......Page 650 Index of MATLAB® Terms ......Page 658

A significantly revised and improved introduction to a critical aspect of scientific computation

Matrix computations lie at the heart of most scientific computational tasks. For any scientist or engineer doing large-scale simulations, an understanding of the topic is essential. Fundamentals of Matrix Computations, Second Edition explains matrix computations and the accompanying theory clearly and in detail, along with useful insights.

This Second Edition of a popular text has now been revised and improved to appeal to the needs of practicing scientists and graduate and advanced undergraduate students. New to this edition is the use of MATLAB for many of the exercises and examples, although the Fortran exercises in the First Edition have been kept for those who want to use them. This new edition includes:

* Numerous examples and exercises on applications including electrical circuits, elasticity (mass-spring systems), and simple partial differential equations

* Early introduction of the singular value decomposition

* A new chapter on iterative methods, including the powerful preconditioned conjugate-gradient method for solving symmetric, positive definite systems

* An introduction to new methods for solving large, sparse eigenvalue problems including the popular implicitly-restarted Arnoldi and Jacobi-Davidson methods

With in-depth discussions of such other topics as modern componentwise error analysis, reorthogonalization, and rank-one updates of the QR decomposition, Fundamentals of Matrix Computations, Second Edition will prove to be a versatile companion to novice and practicing mathematicians who seek mastery of matrix computation.

Booknews

A textbook for graduate and advanced undergraduate students who are familiar with elementary linear algebra and conversant in a high-level programming language such as Fortran, Pascal, or C. Concerned with the teaching efficient and accurate matrix computations, which underlie most scientific computer codes. Annotation c. Book News, Inc., Portland, OR (booknews.com)

This edition details matrix computations and the accompanying theory alongside the author's useful insights. Featuring many examples and exercises that use the MATLABlanguage, it presents algorithms of numerical linear algebra and helps readers to understand how the algorithms are developed and why they work