contents 

1 Introduction

1.1 Basic Notation

1.2 Standard Problems of Numerical Linear Algebra

1.3 General Techniques

1.3.1 Matrix Factorizations

1.3.2 Perturbation Theory and Condition Numbers

1.3.3 Effects of Roundoff Error on Algorithms

1.3.4 Analyzing the Speed of Algorithms

1.3.5 Engineering Numerical Software

1.4 Example: Polynomial Evaluation

1.5 Floating Point Arithmetic

1.5.1 Further Details

1.6 Polynomial Evaluation Revisited

1.7 Vector and Matrix Norms

1.8 References and Other Topics for Chapter 1

1.9 Questions for Chapter 1

2 Linear Equation Solving

2.1 Introduction

2.2 Perturbation Theory

2.2.1 Relative Perturbation Theory

2.3 Gaussian Elimination

2.4 Error Analysis

2.4.1 The Need for Pivoting

2.4.2 Formal Error Analysis of Gaussian Elimination

2.4.3 Estimating Condition Numbers

2.4.4 Practical Error Bounds

2.5 Improving the Accuracy of a Solution

2.5.1 Single Precision Iterative Refinement

2.5.2 Equilibration

2.6 Blocking Algorithms for Higher Performance

2.6.1 Basic Linear Algebra Subroutines (BLAS)

2.6.2 How to Optimize Matrix Multiplication

2.6.3 Reorganizing Gaussian Elimination to Use Level 3 BLAS

2.6.4 More About Parallelism and Other Performance Issues.

2.7 Special Linear Systems

2.7.1 Real Symmetric Positive Definite Matrices

2.7.2 Symmetric Indefinite Matrices

2.7.3 Band Matrices

2.7.4 General Sparse Matrices

2.7.5 Dense Matrices Depending on Fewer Than O(n2) Parameters

2.8 References and Other Topics for Chapter 2

2.9 Questions for Chapter 2

3 Linear Least Squares Problems

3.1 Introduction

3.2 Matrix Factorizations That Solve the Linear Least Squares Problem 

3.2.1 Normal Equations

3.2.2 QR Decomposition 

3.2.3 Singular Value Decomposition

3.3 Perturbation Theory for the Least Squares Problem

3.4 Orthogonal Matrices

3.4.1 Householder Transformations

3.4.2 Givens Rotations

3.4.3 Roundoff Error Analysis for Orthogonal Matrices

3.4.4 Why Orthogonal Matrices?

3.5 Rank-Deficient Least Squares Problems

3.5.1 Solving Rank-Deficient Least Squares Problems Using the SVD

3.5.2 Solving Rank-Deficient Least Squares Problems Using QR with Pivoting

3.6 Performance Comparison of Methods for Solving Least SquaresProblems

3.7 References and Other Topics for Chapter 3

3.8 Questions for Chapter 3

4 Nonsymmetric Eigenvalue Problems

4.1 Introduction

4.2 Canonical Forms

4.2.1 Computing Eigenvectors from the Schur Form

4.3 Perturbation Theory

4.4 Algorithms for the Nonsymmetric Eigenproblem

4.4.1 Power Method

4.4.2 Inverse Iteration

4.4.3 Orthogonal Iteration

4.4.4 QR Iteration

4.4.5 Making QR Iteration Practical

4.4.6 Hessenberg Reduction