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