Preface
Table of Contents
Princeton University Press


MATRICES, MOMENTS AND QUADRATURE
WITH APPLICATIONS

Gene H. GOLUB and Gérard MEURANT

Princeton University Press
2010
ISBN 978-0-691-14341-5
363 pages



Gene H. Golub (1932-2007)


The aim of this book is to describe and explain the beautiful mathematical relationships between matrices, moments, orthogonal polynomials, quadrature rules and the Lanczos and the conjugate gradient algorithms. It should be useful for researchers in numerical linear algebra or more generally to people interested in matrix computations. It can be of interest too to scientists and engineers solving problems in which computation of bilinear forms arise naturally.

Preface

The project of this book was initiated by Gene Golub mid 2005 during a visit to Cerfacs in Toulouse, France. Gene had been working on the relations between matrix computations, quadrature rules and orthogonal polynomials for more than thirty years. We collaborated on these topics during the nineties and he was seeing the writing of this book as being a summary of our findings and of his achievements with many other collaborators. We met many times during the last years, specially during his sabbatical in Oxford in 2007, to work on this project. Gene was always very enthusiastic about it because this topic and the many applications that can be done were one of his favorites.

Unfortunately Gene Golub passed away on November 16, 2007. So, he was not able to see the end of this work. This book can be considered as a tribute to the work he had done during more than three decades.

The aim of this book is to describe and explain the beautiful mathematical relationships between matrices, moments, orthogonal polynomials, quadrature rules and the Lanczos and the conjugate gradient algorithms. Even though we recall the mathematical basis of the algorithms, this book is computationally oriented. The main goal is to obtain efficient numerical methods to estimate or in some cases to bound quantities like I[f]=u^T f(A)v where u and v are given vectors, A is a symmetric nonsingular matrix and f is a smooth function. The main idea developed in this book is to write I[f] as a Riemann-Stieltjes integral and then to apply Gauss quadrature rules to compute estimates or bounds of the integral. The nodes and weights of these quadrature rules are given by the eigenvalues and eigenvectors of tridiagonal matrices whose nonzero coefficients are describing the three-term recurrences satisfied by the orthogonal polynomials associated with the measure of the Riemann-Stieltjes integral. Beautifully, these orthogonal polynomials can be generated by the Lanczos algorithm when u=v or by its variants in the other case. All these topics have a long and rich history starting in the nineteenth century. Our aim is to bring together results and algorithms from different areas. Results about orthogonal polynomials and quadrature rules may not be so well known from the matrix computations community and conversely the applications in matrix computations that can be done with orthogonal polynomials and quadrature rules may be not too familiar to the community of researchers working on these topics. We will see that it can be very fruitful to mix techniques coming from different areas.

There are many instances in which one would like to compute bilinear forms like u^T f(A)v. A first obvious application is the computation of some elements of the matrix f(A) when it is not desired or feasible to compute all of f(A). Computation of quadratic forms r^T A^(-i)r for i=1,2 is interesting to obtain estimates of error norms when one has an approximate solution of a linear system Ax=b and r is the corresponding residual vector. Bilinear or quadratic forms arise also naturally for the computation of parameters in some numerical methods for solving least squares or total least squares problems and also in Tikhonov regularization for solving ill-posed problems.

A first part of the book provides the necessary mathematical background and explains the theory when a second part describes applications of these results, gives implementation details and study improvements of some of the algorithms reviewed in the first part.


Table of Contents

1/ Introduction [TOC]



2/ Orthogonal polynomials  [TOC]


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/ Properties of tridiagonal matrices  [TOC]


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/ The Lanczos and conjugate gradient algorithms  [TOC]


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/ Computation of the Jacobi matrices  [TOC]


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/ Gauss quadrature  [TOC]


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/ Bounds for bilinear forms u^T f(A)v  [TOC]


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/ Extensions to nonsymmetric matrices  [TOC]


8.1.  Rules based on the nonsymmetric Lanczos algorithm . . . . . . 118
8.2.  Rules based on the Arnoldi algorithm. . . . . . . . . . . . . 119



9/ Solving secular equations  [TOC]


9.1.  Examples of secular equations . . . . . . . . . . . . . . . . 122
9.2.  Secular equation solvers. . . . . . . . . . . . . . . . . . . 129
9.3.  Numerical experiments . . . . . . . . . . . . . . . . . . . . 134



10/ Examples of Gauss quadrature rules  [TOC]


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/ Bounds and estimates for elements of f(A)  [TOC]


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/ Estimates of norms of errors in the conjugate gradient algorithm  [TOC]


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/ Least squares problems  [TOC]


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/ Total least squares  [TOC]


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/ Discrete ill-posed problems  [TOC]


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



Bibliography  [TOC]

There are 353 references.




  •  References. [download]