Numerical Linear Algebra

ISBN 0898713617
NUMERICAL LINEAR ALGEBRA
Contents
Preface
Acknowledgments
Part I Fundamentals
Lecture 1. Matrix-Vector Multiplication
Familiar Definitions
A Matrix Times a Vector
A Matrix Times a Matrix
Range and Null Space
Rank
Matrix Inverse Times a Vector
A Note on m and n
Exercises
Lecture 2. Orthogonal Vectors and Matrices
Adjoint
Inner Product
Orthogonal Vectors
Components of a Vector
Unitary Matrices
Multiplication by a Unitary Matrix
Exercises
Lecture 3. Norms
Vector Norms
Matrix Norms Induced by Vector Norms
Exercises
Cauchy-Shwarz and Holder Inequalities
Bounding ||AB|| in an Induced Matrix Norm
General Matrix Norms
Invariance under Unitary Multiplication
Exercises
Lecture 4. The Singular Value Decomposition
A Geometric Observation
Reduced SVD
Full SVD
Formal Definition
Existence and Uniqueness
Exercises
Lecture 5. More on the SVD
A Change of Bases
SVD vs. Eigen Value Decomposition
Matrix Properties via SVD
Low-Rank Approximations
Computation of SVD
Exercises
Part II QR Factorization and Least Squares
Lecture 6. Projectors
Projectors
Complementary Projectors
Orthogonal Projectors
Projection with an Orthogonal Basis
Projection with an Arbitrary Basis
Exercises
Lecture 7. QR Factorization
Reduced QR Factorization
Full QR Factorization
Gram-Schmidt Orthogonalization
Existence and Uniqueness
When Vectors Become Continuous Functions
Solution Ax=b by QR Factorization
Exercises
Lecture 8. Gram-Schmidt Orthogonalization
Gram-Schmidt Projections
Modified Gram-Schmidt Algorithm
Operation Count
Counting Operations Geometrically
Gram-Schmidt as Triangular Orthogonalization
Exercises
Lecture 9. MATLAB
MATLAB
Experiment 1: Discrete Legendre Polynomials
Experiment 2: Classical vs Modified Gram-Schmidt
Experiment 3: Numerical Loss of Orthogonality
Exercises
Lecture 10. Householder Triangularization
Householder and Gram-Schmidt
Triangulization by Introducing Zeros
Householders Reflectors
The Better of Two Reflectors
The Algorithm
Applying or Forming Q
Operation Count
Exercises
Lecture 11. Least Squares Problems
The Problem
Example: Polynomial Fitting
Orthogonal Projection and the Normal Equations
Pseudoinverse
Normal Equations
QR Factorization
SVD
Comparision of Algorithms
Exercises
Part III Conditioning and Stability
Lecture 12. Conditioning and Condition Numbers
Condition of a Problem
Absolute Condition Number
Relative Condition Number
Condition of Matrix-Vector Multiplication
Condition Number of a Matrix
Condition of a System of Equations
Exercises
Lecture 13. Floating Point Arithmetic
Limits of Digital Representations
Floating Point Numbers
Machine Epsilon
Floating Point Arithmetic
Machine Epsilon, Again
Complex Floating Point Arithmetic
Exercises
Lecture 14. Stability
Algorithms
Accuracy
Stability
Backwards Stability
The Meaning of O()
Dependence on m and n, not on A and b
Independence of Norm
Exercises
Lecture 15. More on Stability
Stability of Floating Point Arithmetic
Further Examples
An Unstable Algorithm
Accuracy of Backward Stable Algorithm
Backward Error Analysis
Exercises
Lecture 16. Stability of Householder Triangularization
Experiment
Theorem
Analyzing an Algorithm to Solve Ax=b
Exercises
Lecture 17. Stability of Back Substitution
Triangular Systems
Backward Stability Theorem
m=1
m=2
m=3
General m
Remarks
Exercises
Lecture 18. Conditioning of Least Squares Problems
Four Conditioning Problems
Theorem
Transformation to a Diagonal Matrix
Sensitivity of y to Perturbations in b
Sensitivity of x to Perturbations in b
Tilting the Range of A
Sensitivity of y to Perturbations in A
Sensitivity of x to Perturbations in A
Exercises
Lecture 19. Stability of Least Squares Algorithms
Example
Householder Triangulation
Gram-Schmidt Orthogonalization
Normal Equations
SVD
Rank Deficient Least Square Problems
Exercises
Part IV Systems of Equations
Lecture 20. Gaussian Elimination
LU Factorization
Example
General Formulas and Two Stokes of Luck
Operation Count
Solution of Ax=b by LU Factorization
Instability of Gaussian Elimination without Pivoting
Exercises
Lecture 21. Pivoting
Pivots
Partial Pivoting
Example
PA=LU Factorization and a Third Stroke Luck
Complete Pivoting
Exercises
Lecture 22. Stability of Gaussian Elimination
Stability and Size of L and U
Growth Factors
Worst-Case Instability
Stability in Practice
Explanation
Exercises
Lecture 23. Cholesky Factorization
Hermitian Positive Definitive Matrices
Symmetric Gaussian Elimination
Cholesky Factorization
The Algorithm
Operation Count
Stability
Solution to Ax=b
Exercises
Part V Eigenvalues
Lecture 24. Eigenvalue Problems
Eigenvalues and Eigen Vectors
Eigenvalue Decomposition
Geometric Multiplicity
Characteristic Polynomial
Algebriac Multiplicity
Similarity Transformations
Defective Eigenvalues and Matrices
Diagnolizability
Determinant and Trace
Unitary Diagnolization
Schur Factorization
Eigenvalue-Revealing Factorizations
Exercises
Lecture 25. Overview of Eigenvalue Algorithms
Shortcomings of Obvious Algorithms
A Fundamental Difficulty
Schur Factorization and Diagnolization
Two Phases of Eigenvalue Computations
Exercises
Lecture 26. Reduction to Hessenberg or Tridiagonal Form
A Bad Idea
A Good Idea
Operation Count
The Hermitian Case: Reduction to Tridiagonal Form
Stability
Exercises
Lecture 27. Rayleigh Quotient, Inverse Iteration
Restrictions to Real Symmetric Matrices
Rayleigh Quotient
Power Iteration
Inverse Iteration
Rayleigh Quotient Iteration
Operation Counts
Exercises
Lecture 28. QR Algorithm without Shifts
The QR Algorithm
Unnormalized Simultaneous Iteration
Simultaneous Iteration
Simultaneous Iteration ⇔ QR Algorithm
Convergence of QR Algorithm
Exercises
Lecture 30. Other Eigenvalue Algorithms
Jacobi
Bisection
Divide and Conquer
Exercises
Lecture 31. Computing the SVD
SVD of A and Eigenvalues of A*A
A Different Reduction to an Eigenvalue Problem
Two Phases
Golub-Kahan Bidiagonalization
Faster Methods for Phase I
Phase 2
Exercises
Part VI Iterative Methods
Lecture 32. Overview of Iterative Methods
Why Iterate?
Structure, Sparsity, and Black Boxes
Projection into Krylov Subspaces
Number of Steps, Work per Step, and Preconditioning
Exact vs. Approximate Solutions
Direct Methods That Beat O(m^3)
Exercises
Lecture 33. The Arnold! Iteration
The Arnoldi/Gram-Schmidt Analogy
Mechanics of the Arnoldi Iteration
QR Factorization of a Krylov Matrix
Projection onto Krylov Subspaces
Exercises
Lecture 34. How Arnold! Locates Eigenvalues
Computing Eigenvalues by the Arnoldi Iteration
Note on Caution: Nonnormality
Arnold and Polynomial Approximation
Invariance Properties
How Arnoldi Locates Eigenvalues
Arnoldi Lemniscates
Geometric Convergence
Exercises
Lecture 35. GMRES
Residual Minimization in K_n
Mechanics of GMRES
GMRES and Polynomial Approximation
Convergence of GMRES
Polynomials Small on the Spectrum
Exercises
Lecture 36. The Lanczos Iteration
Three-Term Recurrence
The Lanczos Iteration
Lanczos and Electric Charge Distriutions
Example
Rounding Errors and 'Ghost' Eigenvalues
Exercises
Lecture 37. From Lanczos to Gauss Quadrature
Orthogonal Polynomials
Jacobi Matrices
The Characterstic Polynomial
Quadrature Formules
Guass Quadrature
Guass Quadrature via Jacobi Matrices
Exercises
Lecture 38. Conjugate Gradients
Minimizing the 2-norm of the Residual
Minimizing the A-Norm of the Error
The Conjugate Gradient Iteration
Optimality of CG
CG as an Optimization Algorithm
CG and Polynomial Approximation
Rate of Convergence
Example
Exercises
Lecture 39. Biorthogonalization Methods
Where we Stand
CGN=CG Applied to the Normal Equations
Tridiagonal Biorthogonalization
BCG=Biconjugate Gradients
Example
QMR and Other Varaiants
Exercises
Lecture 40. Preconditioning
Preconditioners Ax=b
Left,Right and Hermitian Preconditioners
Example
Survey of Preconditioners of Ax=b
Preconditioners for Eigenvalue Problems
A Closing Note
Exercises
Appendix. The Definition of Numerical Analysis
Notes
Bibliography
Index