Numerical Linear Algebra Trefethen

NUMERICAL\nLINEAR\nALGEBRA\nLloyd N. Trefethen\nDavid Bau, III\nsiam Notation\nFor square or rectangular matrices A \\in \\mathbb{C}^{m \\times n}, m \\geq n:\nQR factorization: A = QR\nReduced QR factorization: A = \\hat{Q} \\hat{R}\nSVD: A = U \\Sigma V^*\nReduced SVD: A = \\tilde{U} \\tilde{\\Sigma} V^*\n\nFor square matrices A \\in \\mathbb{C}^{m \\times m}:\nLU factorization: PA = LU\nCholesky factorization: A = R^T R\nEigenvalue decomposition: A = X \\Lambda X^{-1}\nSchur factorization: A = U T U^*\nOrthogonal projector: P = QQ^*\n\nHouseholder reflector: F = I - 2 \\frac{uu^*}{v^T u}\n\nQR algorithm: A^{(k)} = Q^{(k)}R^{(k)}, A^{(k+1)} = (Q^{(k)})^T A Q^{(k)}\nArnoldi iteration: A Q_n = Q_{n+1} H_n, H_n = Q_n^T A Q_n\nLanczos iteration: A Q_n = Q_{n+1} \\alpha_n, \\beta_n = Q_n^T A Q_n NUMERICAL\nLINEAR\nALGEBRA NUMERICAL\nLINEAR\nALGBRA\n\nLLOYD N. TRETHEEN\nCornell University\nIthaca, New York\n\nDAVID BAU, III\nMicrosoft Corporation\nRedmond, Washington\n\nsiam.\nSociety for Industrial and Applied Mathematics\nPhiladelphia Copyright ©1997 by the Society for Industrial and Applied Mathematics.\n\n1098765432\n\nAll rights reserved. Printed in the United States of America. No part of this book may be repro- \nduced, stored, or transmitted in any manner without the written permission of the publisher. For \ninformation, write to the Society for Industrial and Applied Mathematics, 3600 University City \nScience Center, Philadelphia, PA 19104-2688.\n\nTrademarked names may be used in this book without the inclusion of a trademark symbol. These \nnames are used in an editorial context only; no infringement of trademark is intended.\n\nLibrary of Congress Cataloging-in-Publication Data\n\nTrefethen, Lloyd N. (Lloyd Nicholas)\n Numerical linear algebra / Lloyd N. Trefethen, David Bau III.\n p. cm.\n Includes bibliographical references and index.\n ISBN 0-89871-361-7 (pbk.)\n I. Algebras, Linear. 2. Numerical calculations. I. Bau, David.\n II. Title.\n QA184.T74 1997 96-52458\n 512'.5--dc21\n\nCover Illustration. The four curves reminiscent of water drops are polynomial lemniscates in the\ncomplex plane associated with steps 5,6,7,8 of an Arnold iteration. The small dots are the eigen- \nvalues of the underlying matrix A, and the large dots are the Ritz values of the Arnoldi iteration. As the\niteration proceeds, the lemniscate first reaches out to engulf one of the eigenvalues λ, then pinches\noff and shrinks steadily to a point. The Ritz value inside it thus converges geometrically to λ. See \nFigure 34.3 on p. 263.\n\nsiam is a registered trademark. To our parents\nFlorence and Lloyd MacG. Trefthcen\nand\nRachel and Paul Bau Contents\n\nPreface ix\nAcknowledgments xi\n\nI Fundamentals 1\nLecture 1 Matrix-Vector Multiplication 3\nLecture 2 Orthogonal Vectors and Matrices 11\nLecture 3 Norm 17\nLecture 4 The Singular Value Decomposition 25\nLecture 5 More on the SVD 32\n\nII QR Factorization and Least Squares 39\nLecture 6 Projections 41\nLecture 7 QR Factorization 48\nLecture 8 Gram-Schmidt Orthogonalization 56\nLecture 9 MATLAB 63\nLecture 10 Householder Triangularization 69\nLecture 11 Least Squares Problems 77\n\nIII Conditioning and Stability 87\nLecture 12 Conditioning and Condition Numbers 89\nLecture 13 Floating Point Arithmetic 97\nLecture 14 Stability 102\nLecture 15 More on Stability 108\nLecture 16 Stability of Householder Triangularization 114\nLecture 17 Stability of Back Substitution 121\nLecture 18 Conditioning of Least Squares Problems 129\nLecture 19 Stability of Least Squares Algorithms 137 IV Systems of Equations\nLecture 20 Gaussian Elimination\nLecture 21 Pivoting\nLecture 22 Stability of Gaussian Elimination\nLecture 23 Cholesky Factorization\n\nV Eigenvalues\nLecture 24 Eigenvalue Problems\nLecture 25 Overview of Eigenvalue Algorithms\nLecture 26 Reduction to Hessenberg or Tridiagonal Form\nLecture 27 Rayleigh Quotient, Inverse Iteration\nLecture 28 QR Algorithm without Shifts\nLecture 29 QR Algorithm with Shifts\nLecture 30 Other Eigenvalue Algorithms\nLecture 31 Computing the SVD\n\nVI Iterative Methods\nLecture 32 Overview of Iterative Methods\nLecture 33 The Arnoldi Iteration\nLecture 34 How Arnoldi Locates Eigenvalues\nLecture 35 GMRES\nLecture 36 The Lanczos Iteration\nLecture 37 From Lanczos to Gauss Quadrature\nLecture 38 Conjugate Gradients\nLecture 39 Biorthogonalization Methods\nLecture 40 Preconditioning\n\nAppendix The Definition of Numerical Analysis\nNotes\nBibliography\nIndex