Numerical linear algebra

1. Introduction

1.1. Discretization of a Differential Equation

1.2. Least Squares Fitting

1.3. Vibrations of a Mechanical System

1.4. The Vibrating String

1.5. Image Compression by the SVD Factorization

2. Definition and Properties of Matrices

2.1. Gram-Schmidt Orthonormalization Process

2.2. Matrices

2.2.1. Trace and Determinant

2.2.2. Special Matrices

2.2.3. Rows and Columns

2.2.4. Row and Column Permutation

2.2.5. Block Matrices

2.3. Spectral Theory of Matrices

2.4. Matrix Triangularization

2.5. Matrix Diagonalization

2.6. Min-Max Principle

2.7. Singular Values of a Matrix

2.8. Exercises

3. Matrix Norms, Sequences, and Series

3.1. Matrix Norms and Subordinate Norms

3.2. Subordinate Norms for Rectangular Matrices

3.3. Matrix Sequences and Series

3.4. Exercises

4. Introduction to Algorithmics

4.1. Algorithms and pseudolanguage

4.2. Operation Count and Complexity

4.3. The Strassen Algorithm

4.4. Equivalence of Operations

4.5. Exercises

5. Linear Systems

5.1. Square Linear Systems

5.2. Over- and Underdetermined Linear Systems

5.3. Numerical Solution

5.3.1. Floating-Point System

5.3.2. Matrix Conditioning

5.3.3. Conditioning of a Finite Difference Matrix

5.3.4. Approximation of the Condition Number

5.3.5. Preconditioning

5.4. Exercises

6. Direct Methods for Linear Systems

6.1. Gaussian Elimination Method

6.2. LU Decomposition Method

6.2.1. Practical Computation of the LU Factorization

6.2.2. Numerical Algorithm

6.2.3. Operation Count

6.2.4. The Case of Band Matrices

6.3. Cholesky Method

6.3.1. Practical Computation of the Cholesky Factorization

6.3.2. Numerical Algorithm

6.3.3. Operation Count

6.4. QR Factorization Method

6.4.1. Operation Count

6.5. Exercises

7. Least Squares Problems

7.1. Motivation

7.2. Main Results

7.3. Numerical Algorithms

7.3.1. Conditioning of Least Squares Problems

7.3.2. Normal Equation Method

7.3.3. QR Factorization Method

7.3.4. Householder Algorithm

7.4. Exercises

8. Simple Iterative Methods

8.1. General Setting

8.2. Jacobi, Gauss-Seidel, and Relaxation Methods

8.2.1. Jacobi Method

8.2.2. Gauss-Seidel Method

8.2.3. Successive Overrelaxation Method (SOR)

8.3. The Special Case of Tridiagonal Matrices

8.4. Discrete Laplacian

8.5. Programming Iterative Methods

8.6. Block Methods

8.7. Exercises

9. Conjugate Gradient Method

9.1. The Gradient Method

9.2. Geometric Interpretation

9.3. Some Ideas for Further Generalizations

9.4. Theoretical Definition of the Conjugate Gradient Method

9.5. Conjugate Gradient Algorithm

9.5.1. Numerical Algorithm

9.5.2. Number of Operations

9.5.3. Convergence Speed

9.5.4. Preconditioning

9.5.5. Chebyshev Polynomials

9.6. Exercises

10. Methods for Computing Eigenvalues

10.1. Generalities

10.2. Conditioning

10.3. Power Method

10.4. Jacobi Method

10.5. Givens-Householder Method

10.6. QR Method

10.7. Lanczos Method

10.8. Exercises

11. Solutions and Programs

11.1. Exercises of Chapter 2

11.2. Exercises of Chapter 3

11.3. Exercises of Chapter 4

11.4. Exercises of Chapter 5

11.5. Exercises of Chapter 6

11.6. Exercises of Chapter 7

11.7. Exercises of Chapter 8

11.8. Exercises of Chapter 9

11.9. Exercises of Chapter 10

References

Index

Index of Programs