Accuracy and Stability of Numerical Algorithms

Contents
List of Figures
List of Tables
Preface
About the Dedication
Chapter 1. Principles of Finite Precision Computation
	1.1. Notation and Background
	1.2. Relative Error and Significant Digits
	1.3. Sources of Errors
	1.4. Precision Versus Accuracy
	1.5. Backward and Forward Errors
	1.6. Conditioning
	1.7. Cancellation
	1.8. Solving a Quadratic Equation
	1.9. Computing the Sample Variance
	1.10. Solving Linear Equations
	1.11. Accumulation of Rounding Errors
	1.12. Instability Without Cancellation
	1.13. Increasing the Precision
	1.14. Cancellation of Rounding Errors
	1.15. Rounding Errors Can Be Beneficial
	1.16. Stability of an Algorithm Depends on the Problem
	1.17. Rounding Errors Are Not Random
	1.18. Designing Stable Algorithms
	1.19. Misconceptions
	1.20. Rounding Errors in Numerical Analysis
	1.21. Notes and References
	Problems
Chapter 2. Floating Point Arithmetic
	2.1. Floating Point Number System
	2.2. Model of Arithmetic
	2.3. IEEE Arithmetic
	2.4. Aberrant Arithmetics
	2.5. Choice of Base and Distribution of Numbers
	2.6. Statistical Distribution of Rounding Errors
	2.7. Alternative Number Systems
	2.8. Accuracy Tests
	2.9. Notes and References
	Problems
Chapter 3. Basics
	3.1. Inner and Outer Products
	3.2. The Purpose of Rounding Error Analysis
	3.3. Running Error Analysis
	3.4. Notation for Error Analysis
	3.5. Matrix Multiplication
	3.6. Complex Arithmetic
	3.7. Miscellany
	3.8. Error Analysis Demystified
	3.9. Other Approaches
	3.10. Notes and References
	Problems
Chapter 4. Summation
	4.1. Summation Methods
	4.2. Error Analysis
	4.3. Compensated Summation
	4.4. Other Summation Methods
	4.5. Statistical Estimates of Accuracy
	4.6. Choice of Method
	4.7. Notes and References
	Problems
Chapter 5. Polynomials
	5.1. Horner’s Method
	5.2. Evaluating Derivatives
	5.3. The Newton Form and Polynomial Interpolation
	5.4. Notes and References
	Problems
Chapter 6. Norms
	6.1. Vector Norms
	6.2. Matrix Norms
	6.3. The Matrix p-Norm
	6.4. Notes and References
	Problems
Chapter 7. Perturbation Theory for Linear Systems
	7.1. Normwise Analysis
	7.2. Componentwise Analysis
	7.3. Scaling to Minimize the Condition Number
	7.4. The Matrix Inverse
	7.5. Extensions
	7.6. Numerical Stability
	7.7. Practical Error Bounds
	7.8. Perturbation Theory by Calculus
	7.9. Notes and References
	Problems
Chapter 8. Triangular Systems
	8.1. Backward Error Analysis
	8.2. Forward Error Analysis
	8.3. Bounds for the Inverse
	8.4. A Parallel Fan-In Algorithm
	8.5. Notes and References
	Problems
Chapter 9. LU Factorization and Linear Equations
	9.1. Gaussian Elimination
	9.2. Error Analysis
	9.3. The Growth Factor
	9.4. Special Matrices
	9.5. Tridiagonal Matrices
	9.6. Historical Perspective
	9.7. Scaling
	9.8. A Posteriori Stability Tests
	9.9. Sensitivity of the LU Factorization
	9.10. Notes and References
	Problems
Chapter 10. Cholesky Factorization
	10.1. Symmetric Positive Definite
	10.2. Sensitivity of the Cholesky Factorization
	10.3. Positive Semidefinite Matrices
	10.4. Symmetric Indefinite Matrices and Diagonal Pivoting Method
	10.5. Nonsymmetric Positive Definite Matrices
	10.6. Notes and References
	Problems
Chapter 11. Iterative Refinement
	11.1. Convergence of Iterative Refinement
	11.2. Iterative Refinement Implies Stability
	11.3. Notes and References
	Problems
Chapter 12. Block LU Factorization
	12.1. Block Versus Partitioned LU Factorization
	12.2. Error Analysis of Partitioned LU Factorization
	12.3. Error Analysis of Block LU Factorization
	12.4. Notes and References
	Problems
Chapter 13. Matrix Inversion
	13.1. Use and Abuse of the Matrix Inverse
	13.2. Inverting a Triangular Matrix
	13.3. Inverting a Full Matrix by LU Factorization
	13.4. Gauss–Jordan Elimination
	13.5. The Determinant
	13.6. Notes and References
	Problems
Chapter 14. Condition Number Estimation
	14.1. How to Estimate Componentwise Condition Numbers
	14.2. The p-Norm Power Method
	14.3. LAPACK 1-Norm Estimator
	14.4. Other Condition Estimators
	14.5. Condition Numbers of Tridiagonal Matrices
	14.6. Notes and References
	Problems
Chapter 15. The Sylvester Equation
	15.1. Solving the Sylvester Equation
	15.2. Backward Error
	15.3. Perturbation Result
	15.4. Practical Error Bounds
	15.5. Extensions
	15.6. Notes and References
	Problems
Chapter 16. Stationary Iterative Methods
	16.1. Survey of Error Analysis
	16.2. Forward Error Analysis
	16.3. Backward Error Analysis
	16.4. Singular Systems
	16.5. Stopping an Iterative Method
	16.6. Notes and References
	Problems
Chapter 17. Matrix Powers
	17.1. Matrix Powers in Exact Arithmetic
	17.2. Bounds for Finite Precision Arithmetic
	17.3. Application to Stationary Iteration
	17.4. Notes and References
	Problems
Chapter 18. QR Factorization
	18.1. Householder Transformations
	18.2. QR Factorization
	18.3. Error Analysis of Householder Computations
	18.4. Aggregated Householder Transformations
	18.5. Givens Rotations
	18.6. Iterative Refinement
	18.7. Gram–Schmidt Orthogonalization
	18.8. Sensitivity of the QR Factorization
	18.9. Notes and References
	Problems
Chapter 19. The Least Squares Problem
	19.1. Perturbation Theory
	19.2. Solution by QR Factorization
	19.3. Solution by the Modified Gram–Schmidt Method
	19.4. The Normal Equations
	19.5. Iterative Refinement
	19.6. The Seminormal Equations
	19.7. Backward Error
	19.8. Proof of Wedin’s Theorem
	19.9. Notes and References
	Problems
Chapter 20. Underdetermined Systems
	20.1. Solution Methods
	20.2. Perturbation Theory
	20.3. Error Analysis
	20.4. Notes and References
	Problems
Chapter 21. Vandermonde Systems
	21.1. Matrix Inversion
	21.2. Primal and Dual Systems
	21.3. Stability
	21.4. Notes and References
	Problems
Chapter 22. Fast Matrix Multiplication
	22.1. Methods
	22.2. Error Analysis
	22.3. Notes and References
	Problems
Chapter 23. The Fast Fourier Transform and Applications
	23.1. The Fast Fourier Transform
	23.2. Circulant Linear Systems
	23.3. Notes and References
	Problems
Chapter 24. Automatic Error Analysis
	24.1. Exploiting Direct Search Optimization
	24.2. Direct Search Methods
	24.3. Examples of Direct Search
	24.4. Interval Analysis
	24.5. Other Work
	24.6. Notes and References
	Problems
Chapter 25. Software Issues in Floating Point Arithmetic
	25.1. Exploiting IEEE Arithmetic
	25.2. Subtleties of Floating Point Arithmetic
	25.3. Cray Peculiarities
	25.4. Compilers
	25.5. Determining Properties of Floating Point Arithmetic
	25.6. Testing a Floating Point Arithmetic
	25.7. Portability
	25.8. Avoiding Underflow and Overflow
	25.9. Multiple Precision Arithmetic
	25.10. Patriot Missile Software Problem
	25.11. Notes and References
	Problems
Chapter 26. A Gallery of Test Matrices
	26.1. The Hilbert and Cauchy Matrices
	26.2. Random Matrices
	26.3. “Randsvd” Matrices
	26.4. The Pascal Matrix
	26.5. Tridiagonal Toeplitz Matrices
	26.6. Companion Matrices
	26.7. Notes and References
	Problems
Appendix A. Solutions to Problems
1.1-1.4
1.5-1.7
1.8-1.9
1.10-2.1
2.2-2.7
2.8-2.15
2.17-2.21
2.22-2.24
2.25-2.27
3.1-3.3
3.4-3.7
3.8-3.10
3.11-3.12
4.1-4.3
4.4-4.8
5.1-5.3
5.4-6.2
6.3-6.8
6.9-6.14
6.15-7.1
7.2-7.7
7.8-7.9
7.10-7.11
7.12-7.13
7.14-8.4
8.5-8.8
8.10-9.3
9.4-9.9
9.10-10.3
10.4-10.9
10.10-10.14
10.15-10.17
11.1-12.1
12.2-12.5
12.7-13.5
13.6-13.7
13.11-13.14
13.15-15.2
15.3-16.2
17.1-17.2
18.1-18.8
18.9-18.12
18.13-19.3
19.4-19.6
19.7-21.4
21.5-21.10
22.1-25.1
25.3-25.4
25.5-25.8
Appendix B. Singular Value Decomposition, M-Matrices
Appendix C. Acquiring Software
Appendix D. Program Libraries
Appendix E. The Test Matrix Toolbox
Bibliography
1-13
14-29
30-44
45-58
59-73
74-89
90-104
105-121
122-137
138-152
153-169
170-186
187-203
204-218
219-234
235-250
251-267
268-285
286-299
300-313
314-329
330-346
347-364
365-379
380-396
397-412
413-428
429-444
445-460
461-478
479-492
493-507
508-524
525-541
542-557
558-570
571-587
588-602
603-617
618-632
633-649
650-666
667-682
683-698
699-717
718-737
738-756
757-775
776-794
795-812
813-830
831-846
847-864
865-882
883-898
899-915
916-931
932-949
950-968
969-985
986-1001
1002-1016
1017-1034
1035-1052
1053-1066
1067-1082
1083-1099
1100-1114
1115-1134
Name Index
Subject Index