MATRICES, MOMENTS AND QUADRATURE
|
Gene H. Golub (1932-2007) |
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
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
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
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
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
7.1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . 112 7.2. The case u=v. . . . . . . . . . . . . . . . . . . . . . . . . 113 7.3. The case u ne v . . . . . . . . . . . . . . . . . . . . . . . 114 7.4. The block case. . . . . . . . . . . . . . . . . . . . . . . . 115 7.5. Other algorithms for u ne v . . . . . . . . . . . . . . . . . 115
8.1. Rules based on the nonsymmetric Lanczos algorithm . . . . . . 118 8.2. Rules based on the Arnoldi algorithm. . . . . . . . . . . . . 119
9.1. Examples of secular equations . . . . . . . . . . . . . . . . 122 9.2. Secular equation solvers. . . . . . . . . . . . . . . . . . . 129 9.3. Numerical experiments . . . . . . . . . . . . . . . . . . . . 134
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
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
12.1. Estimates of norms of errors in solving linear systems. . . . 200 12.2. Formulas for the A-norm of the error in CG. . . . . . . . . . 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 with finite element problems . . . . . . . . . . . . 212 12.8. Numerical experiments . . . . . . . . . . . . . . . . . . . . 214
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
14.1. Introduction to total least squares . . . . . . . . . . . . . 256 14.2. Scaled total least squares. . . . . . . . . . . . . . . . . . 259 14.3. Total least squares secular equation solvers. . . . . . . . . 261
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. Comparisons of methods for computing the regularization parameter . . . . . . . . . . . . . . . . . . . . . . . . . . 335