Gene H. Golub (1932-2007) was the Fletcher Jones Professor of Computer Science at Stanford University and the coauthor of "Matrix Computations". Gerard Meurant, the author of three books on numerical linear algebra, has worked in scientific computing for almost four decades. He is retired from France's Commissariat a l'Energie Atomique.

• Preface xi PART 1. THEORY 1 Chapter 1. Introduction 3 Chapter 2. Orthogonal Polynomials 8 2.1 Definition of Orthogonal Polynomials 8 2.2 Three-Term Recurrences 10 2.3 Properties of Zeros 14 2.4 Historical Remarks 15 2.5 Examples of Orthogonal Polynomials 15 2.6 Variable-Signed Weight Functions 20 2.7 Matrix Orthogonal Polynomials 21 Chapter 3. Properties of Tridiagonal Matrices 24 3.1 Similarity 24 3.2 Cholesky Factorizations of a Tridiagonal Matrix 25 3.3 Eigenvalues and Eigenvectors 27 3.4 Elements of the Inverse 29 3.5 The QD Algorithm 32 Chapter 4. The Lanczos and Conjugate Gradient Algorithms 39 4.1 The Lanczos Algorithm 39 4.2 The Nonsymmetric Lanczos Algorithm 43 4.3 The Golub-Kahan Bidiagonalization Algorithms 45 4.4 The Block Lanczos Algorithm 47 4.5 The Conjugate Gradient Algorithm 49 Chapter 5. Computation of the Jacobi Matrices 55 5.1 The Stieltjes Procedure 55 5.2 Computing the Coefficients from the Moments 56 5.3 The Modified Chebyshev Algorithm 58 5.4 The Modified Chebyshev Algorithm for Indefinite Weight Functions 61 5.5 Relations between the Lanczos and Chebyshev Semi-Iterative Algorithms 62 5.6 Inverse Eigenvalue Problems 66 5.7 Modifications of Weight Functions 72 Chapter 6. Gauss Quadrature 84 6.1 Quadrature Rules 84 6.2 The Gauss Quadrature Rules 86 6.3 The Anti-Gauss Quadrature Rule 92 6.4 The Gauss-Kronrod Quadrature Rule 95 6.5 The Nonsymmetric Gauss Quadrature Rules 99 6.6 The Block Gauss Quadrature Rules 102 Chapter 7. Bounds for Bilinear Forms uT f(A)v 112 7.1 Introduction 112 7.2 The Case u = v 113 7.3 The Case u <> v 114 7.4 The Block Case 115 7.5 Other Algorithms for u <> v 115 Chapter 8. Extensions to Nonsymmetric Matrices 117 8.1 Rules Based on the Nonsymmetric Lanczos Algorithm 118 8.2 Rules Based on the Arnoldi Algorithm 119 Chapter 9. Solving Secular Equations 122 9.1 Examples of Secular Equations 122 9.2 Secular Equation Solvers 129 9.3 Numerical Experiments 134 PART 2. APPLICATIONS 137 Chapter 10. Examples of Gauss Quadrature Rules 139 10.1 The Golub and Welsch Approach 139 10.2 Comparisons with Tables 140 10.3 Using the Full QR Algorithm 141 10.4 Another Implementation of QR 143 10.5 Using the QL Algorithm 144 10.6 Gauss-Radau Quadrature Rules 144 10.7 Gauss-Lobatto Quadrature Rules 146 10.8 Anti-Gauss Quadrature Rule 148 10.9 Gauss-Kronrod Quadrature Rule 148 10.10 Computation of Integrals 149 10.11 Modification Algorithms 155 10.12 Inverse Eigenvalue Problems 156 Chapter 11. Bounds and Estimates for Elements of Functions of Matrices 162 11.1 Introduction 162 11.2 Analytic Bounds for the Elements of the Inverse 163 11.3 Analytic Bounds for Elements of Other Functions 166 11.4 Computing Bounds for Elements of f(A) 167 11.5 Solving Ax = c and Looking at d T/x 167 11.6 Estimates of tr(A-1) and det(A) 168 11.7 Krylov Subspace Spectral Methods 172 11.8 Numerical Experiments 173 Chapter 12. Estimates of Norms of Errors in the Conjugate Gradient Algorithm 200 12.1 Estimates of Norms of Errors in Solving Linear Systems 200 12.2 Formulas for the A-Norm of the Error 202 12.3 Estimates of the A-Norm of the Error 203 12.4 Other Approaches 209 12.5 Formulas for the l2 Norm of the Error 210 12.6 Estimates of the l2 Norm of the Error 211 12.7 Relation to Finite Element Problems 212 12.8 Numerical Experiments 214 Chapter 13. Least Squares Problems 227 13.1 Introduction to Least Squares 227 13.2 Least Squares Data Fitting 230 13.3 Numerical Experiments 237 13.4 Numerical Experiments for the Backward Error 253 Chapter 14. Total Least Squares 256 14.1 Introduction to Total Least Squares 256 14.2 Scaled Total Least Squares 259 14.3 Total Least Squares Secular Equation Solvers 261 Chapter 15. Discrete Ill-Posed Problems 280 15.1 Introduction to Ill-Posed Problems 280 15.2 Iterative Methods for Ill-Posed Problems 295 15.3 Test Problems 298 15.4 Study of the GCV Function 300 15.5 Optimization of Finding the GCV Minimum 305 15.6 Study of the L-Curve 313 15.7 Comparison of Methods for Computing the Regularization Parameter 325 Bibliography 335 Index 361

Gene H. Golub (1932-2007) was the Fletcher Jones Professor of Computer Science at Stanford University and the coauthor of "Matrix Computations". Gerard Meurant, the author of three books on numerical linear algebra, has worked in scientific computing for almost four decades. He is retired from France's Commissariat a l'Energie Atomique.

• Preface xi PART 1. THEORY 1 Chapter 1. Introduction 3 Chapter 2. Orthogonal Polynomials 8 2.1 Definition of Orthogonal Polynomials 8 2.2 Three-Term Recurrences 10 2.3 Properties of Zeros 14 2.4 Historical Remarks 15 2.5 Examples of Orthogonal Polynomials 15 2.6 Variable-Signed Weight Functions 20 2.7 Matrix Orthogonal Polynomials 21 Chapter 3. Properties of Tridiagonal Matrices 24 3.1 Similarity 24 3.2 Cholesky Factorizations of a Tridiagonal Matrix 25 3.3 Eigenvalues and Eigenvectors 27 3.4 Elements of the Inverse 29 3.5 The QD Algorithm 32 Chapter 4. The Lanczos and Conjugate Gradient Algorithms 39 4.1 The Lanczos Algorithm 39 4.2 The Nonsymmetric Lanczos Algorithm 43 4.3 The Golub-Kahan Bidiagonalization Algorithms 45 4.4 The Block Lanczos Algorithm 47 4.5 The Conjugate Gradient Algorithm 49 Chapter 5. Computation of the Jacobi Matrices 55 5.1 The Stieltjes Procedure 55 5.2 Computing the Coefficients from the Moments 56 5.3 The Modified Chebyshev Algorithm 58 5.4 The Modified Chebyshev Algorithm for Indefinite Weight Functions 61 5.5 Relations between the Lanczos and Chebyshev Semi-Iterative Algorithms 62 5.6 Inverse Eigenvalue Problems 66 5.7 Modifications of Weight Functions 72 Chapter 6. Gauss Quadrature 84 6.1 Quadrature Rules 84 6.2 The Gauss Quadrature Rules 86 6.3 The Anti-Gauss Quadrature Rule 92 6.4 The Gauss-Kronrod Quadrature Rule 95 6.5 The Nonsymmetric Gauss Quadrature Rules 99 6.6 The Block Gauss Quadrature Rules 102 Chapter 7. Bounds for Bilinear Forms uT f(A)v 112 7.1 Introduction 112 7.2 The Case u = v 113 7.3 The Case u <> v 114 7.4 The Block Case 115 7.5 Other Algorithms for u <> v 115 Chapter 8. Extensions to Nonsymmetric Matrices 117 8.1 Rules Based on the Nonsymmetric Lanczos Algorithm 118 8.2 Rules Based on the Arnoldi Algorithm 119 Chapter 9. Solving Secular Equations 122 9.1 Examples of Secular Equations 122 9.2 Secular Equation Solvers 129 9.3 Numerical Experiments 134 PART 2. APPLICATIONS 137 Chapter 10. Examples of Gauss Quadrature Rules 139 10.1 The Golub and Welsch Approach 139 10.2 Comparisons with Tables 140 10.3 Using the Full QR Algorithm 141 10.4 Another Implementation of QR 143 10.5 Using the QL Algorithm 144 10.6 Gauss-Radau Quadrature Rules 144 10.7 Gauss-Lobatto Quadrature Rules 146 10.8 Anti-Gauss Quadrature Rule 148 10.9 Gauss-Kronrod Quadrature Rule 148 10.10 Computation of Integrals 149 10.11 Modification Algorithms 155 10.12 Inverse Eigenvalue Problems 156 Chapter 11. Bounds and Estimates for Elements of Functions of Matrices 162 11.1 Introduction 162 11.2 Analytic Bounds for the Elements of the Inverse 163 11.3 Analytic Bounds for Elements of Other Functions 166 11.4 Computing Bounds for Elements of f(A) 167 11.5 Solving Ax = c and Looking at d T/x 167 11.6 Estimates of tr(A-1) and det(A) 168 11.7 Krylov Subspace Spectral Methods 172 11.8 Numerical Experiments 173 Chapter 12. Estimates of Norms of Errors in the Conjugate Gradient Algorithm 200 12.1 Estimates of Norms of Errors in Solving Linear Systems 200 12.2 Formulas for the A-Norm of the Error 202 12.3 Estimates of the A-Norm of the Error 203 12.4 Other Approaches 209 12.5 Formulas for the l2 Norm of the Error 210 12.6 Estimates of the l2 Norm of the Error 211 12.7 Relation to Finite Element Problems 212 12.8 Numerical Experiments 214 Chapter 13. Least Squares Problems 227 13.1 Introduction to Least Squares 227 13.2 Least Squares Data Fitting 230 13.3 Numerical Experiments 237 13.4 Numerical Experiments for the Backward Error 253 Chapter 14. Total Least Squares 256 14.1 Introduction to Total Least Squares 256 14.2 Scaled Total Least Squares 259 14.3 Total Least Squares Secular Equation Solvers 261 Chapter 15. Discrete Ill-Posed Problems 280 15.1 Introduction to Ill-Posed Problems 280 15.2 Iterative Methods for Ill-Posed Problems 295 15.3 Test Problems 298 15.4 Study of the GCV Function 300 15.5 Optimization of Finding the GCV Minimum 305 15.6 Study of the L-Curve 313 15.7 Comparison of Methods for Computing the Regularization Parameter 325 Bibliography 335 Index 361

Gene H. Golub (1932-2007) was the Fletcher Jones Professor of Computer Science at Stanford University and the coauthor of "Matrix Computations". Gerard Meurant, the author of three books on numerical linear algebra, has worked in scientific computing for almost four decades. He is retired from France's Commissariat a l'Energie Atomique.

• Preface xi PART 1. THEORY 1 Chapter 1. Introduction 3 Chapter 2. Orthogonal Polynomials 8 2.1 Definition of Orthogonal Polynomials 8 2.2 Three-Term Recurrences 10 2.3 Properties of Zeros 14 2.4 Historical Remarks 15 2.5 Examples of Orthogonal Polynomials 15 2.6 Variable-Signed Weight Functions 20 2.7 Matrix Orthogonal Polynomials 21 Chapter 3. Properties of Tridiagonal Matrices 24 3.1 Similarity 24 3.2 Cholesky Factorizations of a Tridiagonal Matrix 25 3.3 Eigenvalues and Eigenvectors 27 3.4 Elements of the Inverse 29 3.5 The QD Algorithm 32 Chapter 4. The Lanczos and Conjugate Gradient Algorithms 39 4.1 The Lanczos Algorithm 39 4.2 The Nonsymmetric Lanczos Algorithm 43 4.3 The Golub-Kahan Bidiagonalization Algorithms 45 4.4 The Block Lanczos Algorithm 47 4.5 The Conjugate Gradient Algorithm 49 Chapter 5. Computation of the Jacobi Matrices 55 5.1 The Stieltjes Procedure 55 5.2 Computing the Coefficients from the Moments 56 5.3 The Modified Chebyshev Algorithm 58 5.4 The Modified Chebyshev Algorithm for Indefinite Weight Functions 61 5.5 Relations between the Lanczos and Chebyshev Semi-Iterative Algorithms 62 5.6 Inverse Eigenvalue Problems 66 5.7 Modifications of Weight Functions 72 Chapter 6. Gauss Quadrature 84 6.1 Quadrature Rules 84 6.2 The Gauss Quadrature Rules 86 6.3 The Anti-Gauss Quadrature Rule 92 6.4 The Gauss-Kronrod Quadrature Rule 95 6.5 The Nonsymmetric Gauss Quadrature Rules 99 6.6 The Block Gauss Quadrature Rules 102 Chapter 7. Bounds for Bilinear Forms uT f(A)v 112 7.1 Introduction 112 7.2 The Case u = v 113 7.3 The Case u <> v 114 7.4 The Block Case 115 7.5 Other Algorithms for u <> v 115 Chapter 8. Extensions to Nonsymmetric Matrices 117 8.1 Rules Based on the Nonsymmetric Lanczos Algorithm 118 8.2 Rules Based on the Arnoldi Algorithm 119 Chapter 9. Solving Secular Equations 122 9.1 Examples of Secular Equations 122 9.2 Secular Equation Solvers 129 9.3 Numerical Experiments 134 PART 2. APPLICATIONS 137 Chapter 10. Examples of Gauss Quadrature Rules 139 10.1 The Golub and Welsch Approach 139 10.2 Comparisons with Tables 140 10.3 Using the Full QR Algorithm 141 10.4 Another Implementation of QR 143 10.5 Using the QL Algorithm 144 10.6 Gauss-Radau Quadrature Rules 144 10.7 Gauss-Lobatto Quadrature Rules 146 10.8 Anti-Gauss Quadrature Rule 148 10.9 Gauss-Kronrod Quadrature Rule 148 10.10 Computation of Integrals 149 10.11 Modification Algorithms 155 10.12 Inverse Eigenvalue Problems 156 Chapter 11. Bounds and Estimates for Elements of Functions of Matrices 162 11.1 Introduction 162 11.2 Analytic Bounds for the Elements of the Inverse 163 11.3 Analytic Bounds for Elements of Other Functions 166 11.4 Computing Bounds for Elements of f(A) 167 11.5 Solving Ax = c and Looking at d T/x 167 11.6 Estimates of tr(A-1) and det(A) 168 11.7 Krylov Subspace Spectral Methods 172 11.8 Numerical Experiments 173 Chapter 12. Estimates of Norms of Errors in the Conjugate Gradient Algorithm 200 12.1 Estimates of Norms of Errors in Solving Linear Systems 200 12.2 Formulas for the A-Norm of the Error 202 12.3 Estimates of the A-Norm of the Error 203 12.4 Other Approaches 209 12.5 Formulas for the l2 Norm of the Error 210 12.6 Estimates of the l2 Norm of the Error 211 12.7 Relation to Finite Element Problems 212 12.8 Numerical Experiments 214 Chapter 13. Least Squares Problems 227 13.1 Introduction to Least Squares 227 13.2 Least Squares Data Fitting 230 13.3 Numerical Experiments 237 13.4 Numerical Experiments for the Backward Error 253 Chapter 14. Total Least Squares 256 14.1 Introduction to Total Least Squares 256 14.2 Scaled Total Least Squares 259 14.3 Total Least Squares Secular Equation Solvers 261 Chapter 15. Discrete Ill-Posed Problems 280 15.1 Introduction to Ill-Posed Problems 280 15.2 Iterative Methods for Ill-Posed Problems 295 15.3 Test Problems 298 15.4 Study of the GCV Function 300 15.5 Optimization of Finding the GCV Minimum 305 15.6 Study of the L-Curve 313 15.7 Comparison of Methods for Computing the Regularization Parameter 325 Bibliography 335 Index 361