Numerical Linear Algebra

This is a concise, insightful introduction to the field of numerical linear algebra. The clarity and eloquence of the presentation make it popular with teachers and students alike. The text aims to expand the reader's view of the field and to present standard material in a novel way. All of the most important topics in the field are covered with a fresh perspective, including iterative methods for systems of equations and eigenvalue problems and the underlying principles of conditioning and stability. Presentation is in the form of 40 lectures, which each focus on one or two central ideas. The unity between topics is emphasized throughout, with no risk of getting lost in details and technicalities. The book breaks with tradition by beginning with the QR factorization - an important and fresh idea for students, and the thread that connects most of the algorithms of numerical linear algebra. Contents: Preface; Acknowledgments; Part I: Fundamentals. Lecture 1: Matrix-Vector Multiplication; Lecture 2: Orthogonal Vectors and Matrices; Lecture 3: Norms; Lecture 4: The Singular Value Decomposition; Lecture 5: More on the SVD; Part II: QR Factorization and Least Squares. Lecture 6: Projectors; Lecture 7: QR Factorization; Lecture 8: Gram-Schmidt Orthogonalization; Lecture 9: MATLAB; Lecture 10: Householder Triangularization; Lecture 11: Least Squares Problems; Part III: Conditioning and Stability. Lecture 12: Conditioning and Condition Numbers; Lecture 13: Floating Point Arithmetic; Lecture 14: Stability; Lecture 15: More on Stability; Lecture 16: Stability of Householder Triangularization; Lecture 17: Stability of Back Substitution; Lecture 18: Conditioning of Least Squares Problems; Lecture 19: Stability of Least Squares Algorithms; Part IV: Systems of Equations. Lecture 20: Gaussian Elimination; Lecture 21: Pivoting; Lecture 22: Stability of Gaussian Elimination; Lecture 23: Cholesky Factorization; Part V: Eigenvalues. Lecture 24: Eigenvalue Problems; Lecture 25: Overview of Eigenvalue Algorithms; Lecture 26: Reduction to Hessenberg or Tridiagonal Form; Lecture 27: Rayleigh Quotient, Inverse Iteration; Lecture 28: QR Algorithm without Shifts; Lecture 29: QR Algorithm with Shifts; Lecture 30: Other Eigenvalue Algorithms; Lecture 31: Computing the SVD; Part VI: Iterative Methods. Lecture 32: Overview of Iterative Methods; Lecture 33: The Arnoldi Iteration; Lecture 34: How Arnoldi Locates Eigenvalues; Lecture 35: GMRES; Lecture 36: The Lanczos Iteration; Lecture 37: From Lanczos to Gauss Quadrature; Lecture 38: Conjugate Gradients; Lecture 39: Biorthogonalization Methods; Lecture 40: Preconditioning; Appendix: The Definition of Numerical Analysis; Notes; Bibliography; Index. Audience: Written on the graduate or advanced undergraduate level, this book can be used widely for teaching. Professors looking for an elegant presentation of the topic will find it an excellent teaching tool for a one-semester graduate or advanced undergraduate course. A major contribution to the applied mathematics literature, most researchers in the field will consider it a necessary addition to their personal collections. Front Cover......Page 1 Back Cover......Page 2 Notation......Page 3 Title Page......Page 6 Copyright......Page 7 Contents......Page 10 Preface......Page 12 Acknowledgments......Page 14 I. Fundamentals......Page 16 1. Matrix-Vector Multiplication......Page 18 2. Orthogonal Vectors and Matrices......Page 26 3. Norms......Page 32 4. The Singular Value Decomposition......Page 40 5. More on the SVD......Page 47 II. QR Factorization and Least Squares......Page 54 6. Projectors......Page 56 7. QR Factorization......Page 63 8. Gram-Schmidt Orthogonalization......Page 71 9. MATLAB......Page 78 10. Householder Triangularization......Page 84 11. Least Squares Problems......Page 92 III. Conditioning and Stability......Page 102 12. Conditioning and Condition Numbers......Page 104 13. Floating Point Arithmetic......Page 112 14. Stability......Page 117 15. More on Stability......Page 123 16. Stability of Householder Triangularization......Page 129 17. Stability of Back Substitution......Page 136 18. Conditioning of Least Squares Problems......Page 144 19. Stability of Least Squares Algorithms......Page 152 IV. Systems of Equations......Page 160 20. Gaussian Elimination......Page 162 21. Pivoting......Page 170 22. Stability of Gaussian Elimination......Page 178 23. Cholesky Factorization......Page 187 V. Eigenvalues......Page 194 24. Eigenvalue Problems......Page 196 25. Overview of Eigenvalue Algorithms......Page 205 26. Reduction to Hessenberg or Tridiagonal Form......Page 211 27. Rayleigh Quotient, Inverse Iteration......Page 217 28. QR Algorithm without Shifts......Page 226 29. QR Algorithm with Shifts......Page 234 30. Other Eigenvalue Algorithms......Page 240 31. Computing the SVD......Page 249 VI. Iterative Methods......Page 256 32. Overview of Iterative Methods......Page 258 33. The Arnoldi Iteration......Page 265 34. How Arnoldi Locates Eigenvalues......Page 272 35. GMRES......Page 281 36. The Lanczos Iteration......Page 291 37. From Lanczos to Gauss Quadrature......Page 300 38. Conjugate Gradients......Page 308 39. Biorthogonalization Methods......Page 318 40. Preconditioning......Page 328 Appendix. The Definition of Numerical Analysis......Page 336 Notes......Page 344 Bibliography......Page 358 Index......Page 368 An Introduction To The Field Of Numerical Linear Algebra. It Aims To Present The Core, Standard Material In A Novel Way. Topics Include Iterative Methods For Systems Of Equations And Eigenvalue Problems And The Underlying Principles Of Conditioning And Stability. Fundamentals -- Qr Factorization And Least Squares -- Conditioning And Stability -- Systems Of Equations -- Eigenvalues -- Iterative Methods. Lloyd N. Trefethen, David Bau Iii. Includes Bibliographical References (p. 343-352) And Index.