Numerical linear algebra and matrix factorizations

Foreword
Preface
	Acknowledgments
Contents
List of Figures
List of Tables
Listings
1 A Short Review of Linear Algebra
	1.1 Notation
	1.2 Vector Spaces and Subspaces
		1.2.1 Linear Independence and Bases
		1.2.2 Subspaces
		1.2.3 The Vector Spaces Rn and Cn
	1.3 Linear Systems
		1.3.1 Basic Properties
		1.3.2 The Inverse Matrix
	1.4 Determinants
	1.5 Eigenvalues, Eigenvectors and Eigenpairs
	1.6 Exercises Chap. 1
		1.6.1 Exercises Sect. 1.1
		1.6.2 Exercises Sect. 1.3
		1.6.3 Exercises Sect. 1.4
Part I LU and QR Factorizations
	2 Diagonally Dominant Tridiagonal Matrices; Three Examples
		2.1 Cubic Spline Interpolation
			2.1.1 Polynomial Interpolation
			2.1.2 Piecewise Linear and Cubic Spline Interpolation
			2.1.3 Give Me a Moment
			2.1.4 LU Factorization of a Tridiagonal System
		2.2 A Two Point Boundary Value Problem
			2.2.1 Diagonal Dominance
		2.3 An Eigenvalue Problem
			2.3.1 The Buckling of a Beam
		2.4 The Eigenpairs of the 1D Test Matrix
		2.5 Block Multiplication and Triangular Matrices
			2.5.1 Block Multiplication
			2.5.2 Triangular Matrices
		2.6 Exercises Chap. 2
			2.6.1 Exercises Sect. 2.1
			2.6.2 Exercises Sect. 2.2
			2.6.3 Exercises Sect. 2.3
			2.6.4 Exercises Sect. 2.4
			2.6.5 Exercises Sect. 2.5
		2.7 Review Questions
	3 Gaussian Elimination and LU Factorizations
		3.1 3 by 3 Example
		3.2 Gauss and LU
		3.3 Banded Triangular Systems
			3.3.1 Algorithms for Triangular Systems
			3.3.2 Counting Operations
		3.4 The PLU Factorization
			3.4.1 Pivoting
			3.4.2 Permutation Matrices
			3.4.3 Pivot Strategies
		3.5 The LU and LDU Factorizations
			3.5.1 Existence and Uniqueness
		3.6 Block LU Factorization
		3.7 Exercises Chap. 3
			3.7.1 Exercises Sect. 3.3
			3.7.2 Exercises Sect. 3.4
			3.7.3 Exercises Sect. 3.5
			3.7.4 Exercises Sect. 3.6
		3.8 Review Questions
	4 LDL* Factorization and Positive Definite Matrices
		4.1 The LDL* Factorization
		4.2 Positive Definite and Semidefinite Matrices
			4.2.1 The Cholesky Factorization
			4.2.2 Positive Definite and Positive Semidefinite Criteria
		4.3 Semi-Cholesky Factorization of a Banded Matrix
		4.4 The Non-symmetric Real Case
		4.5 Exercises Chap. 4
			4.5.1 Exercises Sect. 4.2
		4.6 Review Questions
	5 Orthonormal and Unitary Transformations
		5.1 Inner Products, Orthogonality and Unitary Matrices
			5.1.1 Real and Complex Inner Products
			5.1.2 Orthogonality
			5.1.3 Sum of Subspaces and Orthogonal Projections
			5.1.4 Unitary and Orthogonal Matrices
		5.2 The Householder Transformation
		5.3 Householder Triangulation
			5.3.1 The Algorithm
			5.3.2 The Number of Arithmetic Operations
			5.3.3 Solving Linear Systems Using Unitary Transformations
		5.4 The QR Decomposition and QR Factorization
			5.4.1 Existence
		5.5 QR and Gram-Schmidt
		5.6 Givens Rotations
		5.7 Exercises Chap. 5
			5.7.1 Exercises Sect. 5.1
			5.7.2 Exercises Sect. 5.2
			5.7.3 Exercises Sect. 5.4
			5.7.4 Exercises Sect. 5.5
			5.7.5 Exercises Sect. 5.6
		5.8 Review Questions
Part II Eigenpairs and Singular Values
	6 Eigenpairs and Similarity Transformations
		6.1 Defective and Nondefective Matrices
			6.1.1 Similarity Transformations
			6.1.2 Algebraic and Geometric Multiplicity of Eigenvalues
		6.2 The Jordan Factorization
		6.3 The Schur Factorization and Normal Matrices
			6.3.1 The Schur Factorization
			6.3.2 Unitary and Orthogonal Matrices
			6.3.3 Normal Matrices
			6.3.4 The Rayleigh Quotient
			6.3.5 The Quasi-Triangular Form
			6.3.6 Hermitian Matrices
		6.4 Minmax Theorems
			6.4.1 The Hoffman-Wielandt Theorem
		6.5 Left Eigenvectors
			6.5.1 Biorthogonality
		6.6 Exercises Chap. 6
			6.6.1 Exercises Sect. 6.1
			6.6.2 Exercises Sect. 6.2
			6.6.3 Exercises Sect. 6.3
			6.6.4 Exercises Sect. 6.4
		6.7 Review Questions
	7 The Singular Value Decomposition
		7.1 The SVD Always Exists
			7.1.1 The Matrices A*A, AA*
		7.2 Further Properties of SVD
			7.2.1 The Singular Value Factorization
			7.2.2 SVD and the Four Fundamental Subspaces
		7.3 A Geometric Interpretation
		7.4 Determining the Rank of a Matrix Numerically
			7.4.1 The Frobenius Norm
			7.4.2 Low Rank Approximation
		7.5 Exercises Chap. 7
			7.5.1 Exercises Sect. 7.1
			7.5.2 Exercises Sect. 7.2
			7.5.3 Exercises Sect. 7.4
		7.6 Review Questions
Part III Matrix Norms and Least Squares
	8 Matrix Norms and Perturbation Theory for Linear Systems
		8.1 Vector Norms
		8.2 Matrix Norms
			8.2.1 Consistent and Subordinate Matrix Norms
			8.2.2 Operator Norms
			8.2.3 The Operator p-Norms
			8.2.4 Unitary Invariant Matrix Norms
			8.2.5 Absolute and Monotone Norms
		8.3 The Condition Number with Respect to Inversion
			8.3.1 Perturbation of the Right Hand Side in a Linear Systems
			8.3.2 Perturbation of a Square Matrix
		8.4 Proof That the p-Norms Are Norms
			8.4.1 p-Norms and Inner Product Norms
		8.5 Exercises Chap. 8
			8.5.1 Exercises Sect. 8.1
			8.5.2 Exercises Sect. 8.2
			8.5.3 Exercises Sect. 8.3
			8.5.4 Exercises Sect. 8.4
		8.6 Review Questions
	9 Least Squares
		9.1 Examples
			9.1.1 Curve Fitting
		9.2 Geometric Least Squares Theory
		9.3 Numerical Solution
			9.3.1 Normal Equations
			9.3.2 QR Factorization
			9.3.3 Singular Value Decomposition, Generalized Inverses and Least Squares
		9.4 Perturbation Theory for Least Squares
			9.4.1 Perturbing the Right Hand Side
			9.4.2 Perturbing the Matrix
		9.5 Perturbation Theory for Singular Values
			9.5.1 The Minmax Theorem for Singular Values and the Hoffman-Wielandt Theorem
		9.6 Exercises Chap. 9
			9.6.1 Exercises Sect. 9.1
			9.6.2 Exercises Sect. 9.2
			9.6.3 Exercises Sect. 9.3
			9.6.4 Exercises Sect. 9.4
			9.6.5 Exercises Sect. 9.5
		9.7 Review Questions
Part IV Kronecker Products and Fourier Transforms
	10 The Kronecker Product
		10.1 The 2D Poisson Problem
			10.1.1 The Test Matrices
		10.2 The Kronecker Product
		10.3 Properties of the 2D Test Matrices
		10.4 Exercises Chap. 10
			10.4.1 Exercises Sects. 10.1, 10.2
			10.4.2 Exercises Sect. 10.3
		10.5 Review Questions
	11 Fast Direct Solution of a Large Linear System
		11.1 Algorithms for a Banded Positive Definite System
			11.1.1 Cholesky Factorization
			11.1.2 Block LU Factorization of a Block Tridiagonal Matrix
			11.1.3 Other Methods
		11.2 A Fast Poisson Solver Based on Diagonalization
		11.3 A Fast Poisson Solver Based on the Discrete Sine and Fourier Transforms
			11.3.1 The Discrete Sine Transform (DST)
			11.3.2 The Discrete Fourier Transform (DFT)
			11.3.3 The Fast Fourier Transform (FFT)
			11.3.4 A Poisson Solver Based on the FFT
		11.4 Exercises Chap. 11
			11.4.1 Exercises Sect. 11.3
		11.5 Review Questions
Part V Iterative Methods for Large Linear Systems
	12 The Classical Iterative Methods
		12.1 Classical Iterative Methods; Component Form
			12.1.1 The Discrete Poisson System
		12.2 Classical Iterative Methods; Matrix Form
			12.2.1 Fixed-Point Form
			12.2.2 The Splitting Matrices for the Classical Methods
		12.3 Convergence
			12.3.1 Richardson\'s Method
			12.3.2 Convergence of SOR
			12.3.3 Convergence of the Classical Methods for the Discrete Poisson Matrix
			12.3.4 Number of Iterations
			12.3.5 Stopping the Iteration
		12.4 Powers of a Matrix
			12.4.1 The Spectral Radius
			12.4.2 Neumann Series
		12.5 The Optimal SOR Parameter ω
		12.6 Exercises Chap. 12
			12.6.1 Exercises Sect. 12.3
			12.6.2 Exercises Sect. 12.4
		12.7 Review Questions
	13 The Conjugate Gradient Method
		13.1 Quadratic Minimization and Steepest Descent
		13.2 The Conjugate Gradient Method
			13.2.1 Derivation of the Method
			13.2.2 The Conjugate Gradient Algorithm
			13.2.3 Numerical Example
			13.2.4 Implementation Issues
		13.3 Convergence
			13.3.1 The Main Theorem
			13.3.2 The Number of Iterations for the Model Problems
			13.3.3 Krylov Spaces and the Best Approximation Property
		13.4 Proof of the Convergence Estimates
			13.4.1 Chebyshev Polynomials
			13.4.2 Convergence Proof for Steepest Descent
			13.4.3 Monotonicity of the Error
		13.5 Preconditioning
		13.6 Preconditioning Example
			13.6.1 A Variable Coefficient Problem
			13.6.2 Applying Preconditioning
		13.7 Exercises Chap. 13
			13.7.1 Exercises Sect. 13.1
			13.7.2 Exercises Sect. 13.2
			13.7.3 Exercises Sect. 13.3
			13.7.4 Exercises Sect. 13.4
			13.7.5 Exercises Sect. 13.5
		13.8 Review Questions
Part VI Eigenvalues and Eigenvectors
	14 Numerical Eigenvalue Problems
		14.1 Eigenpairs
		14.2 Gershgorin\'s Theorem
		14.3 Perturbation of Eigenvalues
			14.3.1 Nondefective Matrices
		14.4 Unitary Similarity Transformation of a Matrix into Upper Hessenberg Form
			14.4.1 Assembling Householder Transformations
		14.5 Computing a Selected Eigenvalue of a Symmetric Matrix
			14.5.1 The Inertia Theorem
			14.5.2 Approximating λm
		14.6 Exercises Chap. 14
			14.6.1 Exercises Sect. 14.1
			14.6.2 Exercises Sect. 14.2
			14.6.3 Exercises Sect. 14.3
			14.6.4 Exercises Sect. 14.4
			14.6.5 Exercises Sect. 14.5
		14.7 Review Questions
	15 The QR Algorithm
		15.1 The Power Method and Its Variants
			15.1.1 The Power Method
			15.1.2 The Inverse Power Method
			15.1.3 Rayleigh Quotient Iteration
		15.2 The Basic QR Algorithm
			15.2.1 Relation to the Power Method
			15.2.2 Invariance of the Hessenberg Form
			15.2.3 Deflation
		15.3 The Shifted QR Algorithms
		15.4 Exercises Chap. 15
			15.4.1 Exercises Sect. 15.1
		15.5 Review Questions
Part VII Appendix
	16 Differentiation of Vector Functions
References
Index