Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On sensitivity of Gauss–Christoffel quadrature

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

In numerical computations the question how much does a function change under perturbations of its arguments is of central importance. In this work, we investigate sensitivity of Gauss–Christoffel quadrature with respect to small perturbations of the distribution function. In numerical quadrature, a definite integral is approximated by a finite sum of functional values evaluated at given quadrature nodes and multiplied by given weights. Consider a sufficiently smooth integrated function uncorrelated with the perturbation of the distribution function. Then it seems natural that given the same number of function evaluations, the difference between the quadrature approximations is of the same order as the difference between the (original and perturbed) approximated integrals. That is perhaps one of the reasons why, to our knowledge, the sensitivity question has not been formulated and addressed in the literature, though several other sensitivity problems, motivated, in particular, by computation of the quadrature nodes and weights from moments, have been thoroughly studied by many authors. We survey existing particular results and show that even a small perturbation of a distribution function can cause large differences in Gauss–Christoffel quadrature estimates. We then discuss conditions under which the Gauss–Christoffel quadrature is insensitive under perturbation of the distribution function, present illustrative examples, and relate our observations to known conjectures on some sensitivity problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Beckermann B., Bourreau E. (1998). How to choose modified moments?. J. Comput. Appl. Math. 98(1): 81–98

    Article  MATH  MathSciNet  Google Scholar 

  2. Boley D., Golub G.H. (1987). A survey of matrix inverse eigenvalue problems. Inverse Probl 3(41): 595–622

    Article  MATH  MathSciNet  Google Scholar 

  3. de Boor C., Golub G.H. (1978). The numerically stable reconstruction of a Jacobi matrix from spectral data. Linear Algebra Appl. 21(3): 245–260

    Article  MATH  MathSciNet  Google Scholar 

  4. Carpraux J.F., Godunov S.K., Kuznetsov S.V. (1996). Condition number of the Krylov bases and subspaces. Linear Algebra Appl. 248: 137–160

    Article  MATH  MathSciNet  Google Scholar 

  5. Dahlquist, G., Golub, G.H., Nash, S.G.: Bounds for the error in linear systems. In: Semi-infinite programming (Proc. Workshop, Bad Honnef, 1978). Lecture Notes in Control and Information Sci., vol. 15, pp. 154–172. Springer, Berlin (1979)

  6. Davis, P.J., Rabinowitz, P.: Methods of numerical integration, 2nd edn. Computer Science and Applied Mathematics. Academic, Orlando (1984)

  7. Demmel J., Kahan W. (1990). Accurate singular values of bidiagonal matrices. SIAM J. Sci. Stat. Comput. 11(5): 873–912

    Article  MATH  MathSciNet  Google Scholar 

  8. Dhillon, I.S.: A new O(n 2) algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem. PhD Thesis, University of California, Berkeley (1997)

  9. Dhillon I.S., Parlett B.N. (2003). Orthogonal eigenvectors and relative gaps. SIAM J. Matrix Anal. Appl. (electronic) 25(3): 858–899

    Article  MathSciNet  Google Scholar 

  10. Dhillon I.S., Parlett B.N. (2004). Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices. Linear Algebra Appl. 387: 1–28

    Article  MATH  MathSciNet  Google Scholar 

  11. Druskin V., Borcea L., Knizhnerman L. (2005). On the sensitivity of Lanczos recursions to the spectrum. Linear Algebra Appl. 396: 103–125

    Article  MATH  MathSciNet  Google Scholar 

  12. Elhay S., Golub G.H., Kautsky J. (1991). Updating and downdating of orthogonal polynomials with data fitting applications. SIAM J. Matrix Anal. Appl. 12(2): 327–353

    Article  MATH  MathSciNet  Google Scholar 

  13. Elhay S., Golub G.H., Kautsky J. (1992). Jacobi matrices for sums of weight functions. BIT 32(1): 143–166

    Article  MATH  MathSciNet  Google Scholar 

  14. Fischer H.J. (1998). On generating orthogonal polynomials for discrete measures. Z. Anal. Anwendungen 17(1): 183–205

    MATH  MathSciNet  Google Scholar 

  15. Gautschi W. (1968). Construction of Gauss-Christoffel quadrature formulas. Math. Comp. 22: 251–270

    Article  MATH  MathSciNet  Google Scholar 

  16. Gautschi W. (1970). On the construction of Gaussian quadrature rules from modified moments. Math. Comp. 24: 245–260

    Article  MATH  MathSciNet  Google Scholar 

  17. Gautschi, W.: Questions on numerical condition related to polynomials. In: Recent Advances in Numerical Analysis (Madison, 1978), pp. 45–72. Academic, New York (1978)

  18. Gautschi, W.: A survey of Gauss–Christoffel quadrature formulae. In: Butzer, P.L., Fehér, F. (eds.) E.B. Christoffel: The Influence of His Work on Mathematics and Physics, pp. 72–147. Birkhäuser, Basel (1981)

  19. Gautschi W. (1982). On generating orthogonal polynomials. SIAM J. Sci. Stat. Comput. 3(3): 289–317

    Article  MATH  MathSciNet  Google Scholar 

  20. Gautschi W. (1993). Is the recurrence relation for orthogonal polynomials always stable?. BIT 33(2): 277–284

    Article  MATH  MathSciNet  Google Scholar 

  21. Gautschi, W.: Numerical analysis: an introduction. Birkhäuser Boston Inc., Boston (1997)

  22. Gautschi W. (2002). The interplay between classical analysis and (numerical) linear algebra—a tribute to Gene H. Golub. Electron. Trans. Numer. Anal. (electronic) 13: 119–147

    MATH  MathSciNet  Google Scholar 

  23. Gautschi W. (2004). Orthogonal polynomials: computation and approximation. Numerical Mathematics and Scientific Computation. Oxford University Press, New York

    Google Scholar 

  24. Gautschi W. (2005). Orthogonal polynomials (in Matlab). J. Comput. Appl. Math. 178(1–2): 215–234

    Article  MATH  MathSciNet  Google Scholar 

  25. Gautschi W., Varga R.S. (1983). Error bounds for Gaussian quadrature of analytic functions. SIAM J. Numer. Anal. 20(6): 1170–1186

    Article  MATH  MathSciNet  Google Scholar 

  26. Golub, G.H.: Matrix computation and the theory of moments. In: Proceedings of the International Congress of Mathematicians, vol. 1, 2 (Zürich, 1994), pp. 1440–1448. Birkhäuser, Basel (1995)

  27. Golub, G.H., Van Loan, C.F.: Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, 2nd edn. Johns Hopkins University Press, Baltimore (1989)

  28. Golub, G.H., Welsch, J.H.: Calculation of Gauss quadrature rules. Math. Comp. 23 (1969), 221-230; addendum, ibid. 23(106, loose microfiche suppl), A1–A10 (1969)

  29. Gragg W.B., Harrod W.J. (1984). The numerically stable reconstruction of Jacobi matrices from spectral data. Numer. Math. 44(3): 317–335

    Article  MATH  MathSciNet  Google Scholar 

  30. Grosser B., Lang B. (2005). On symmetric eigenproblems induced by the bidiagonal SVD. SIAM J. Matrix Anal. Appl. (electronic) 26(3): 599–620

    Article  MATH  MathSciNet  Google Scholar 

  31. Hestenes M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Standards 49, 409–436 (1953) (1952)

    Google Scholar 

  32. Isaacson E., Keller H.B. (1966). Analysis of numerical methods. Wiley, New York

    MATH  Google Scholar 

  33. Kautský J., Golub G.H. (1983). On the calculation of Jacobi matrices. Linear Algebra Appl. 52/53: 439–455

    Google Scholar 

  34. Kuznetsov S.V. (1997). Perturbation bounds of the Krylov bases and associated Hessenberg forms. Linear Algebra Appl. 265: 1–28

    Article  MATH  MathSciNet  Google Scholar 

  35. Lanczos, C.: Applied analysis. Prentice Hall, Inc., Englewood Cliffs (1956)

  36. Laurie D.P. (1999). Accurate recovery of recursion coefficients from Gaussian quadrature formulas. J. Comput. Appl. Math. 112(1–2): 165–180

    Article  MATH  MathSciNet  Google Scholar 

  37. Laurie, D.P.: Questions related to Gaussian quadrature formulas and two-term recursions. In: Applications and computation of orthogonal polynomials (Oberwolfach, 1998). Int. Ser. Numer. Math. 131, 133–144 (1999)

  38. Laurie D.P. (2001). Computation of Gauss-type quadrature formulas. J. Comput. Appl. Math. 127(1–2): 201–217

    Article  MATH  MathSciNet  Google Scholar 

  39. Li R.C. (1997). Relative perturbation theory. III. More bounds on eigenvalue variation. Linear Algebra Appl. 266: 337–345

    Article  MATH  MathSciNet  Google Scholar 

  40. Meurant G., Strakoš Z. (2006). Lanczos and conjugate gradient algorithms in finite precision arithmetic. Acta Numer. 15: 471–542

    Article  MATH  MathSciNet  Google Scholar 

  41. Milne-Thomson L.M. (1960). The Calculus of Finite Differences. MacMillan & Co., New York

    Google Scholar 

  42. Natterer, F.: Discrete Gel’fand–Levitan theory, www page of the author (1999)

  43. Nevai P.G. (1979). Orthogonal polynomials. Mem. Am. Math. Soc. 18(213): v+185

    MathSciNet  Google Scholar 

  44. O’Leary D.P., Stewart G.W., Vandergraft J.S. (1979). Estimating the largest eigenvalue of a positive definite matrix. Math. Comp. 33(148): 1289–1292

    Article  MATH  MathSciNet  Google Scholar 

  45. Paige, C.C., Van Dooren, P.: Sensitivity analysis of the Lanczos reduction. Numer. Linear Algebra Appl. 6(1), 29–50 (1999). Czech-US Workshop in Iterative Methods and Parallel Computing, Part I (Milovy, 1997)

  46. Parlett, B.N., Dhillon, I.S.: Relatively robust representations of symmetric tridiagonals. In: Proceedings of the International Workshop on Accurate Solution of Eigenvalue Problems (University Park, PA, 1998), vol. 309, pp. 121–151 (2000)

  47. Parlett B.N., Simon H., Stringer G. (1982). On estimating the largest eigenvalue with the Lanczos algorithm. Math. Comp. 38: 153–165

    Article  MATH  MathSciNet  Google Scholar 

  48. Reichel L. (1991). Fast QR decomposition of Vandermonde-like matrices and polynomial least squares approximation. SIAM J. Matrix Anal. Appl. 12(3): 552–564

    Article  MATH  MathSciNet  Google Scholar 

  49. van der Sluis A., van der Vorst H. (1986). The rate of convergence of conjugate gradients. Numer. Math. 48: 543–560

    Article  MATH  MathSciNet  Google Scholar 

  50. van der Sluis A., van der Vorst H. (1987). The convergence behavior of Ritz values in the presence of close eigenvalues. Linear Algebra Appl. 88: 651–694

    Article  MathSciNet  Google Scholar 

  51. Strakoš Z. (1991). On the real convergence rate of the conjugate gradient method. Linear Algebra Appl. 154–156: 535–549

    Article  Google Scholar 

  52. Strakoš Z., Tichý P. (2002). On error estimation in the conjugate gradient method and why it works in finite precision computations. Electron. Trans. Numer. Anal. (electronic) 13: 56–80

    MATH  Google Scholar 

  53. Stroud, A.H., Secrest, D.: Gaussian quadrature formulas. Prentice-Hall Inc., Englewood Cliffs (1966)

  54. Swarztrauber P.N. (2002). On computing the points and weights for Gauss-Legendre quadrature. SIAM J. Sci. Comput. (electronic) 24(3): 945–954

    Article  MATH  MathSciNet  Google Scholar 

  55. Szegö G. (1939). Orthogonal Polynomials. Colloquium Publications, vol. XXIII. American Mathematical Society, New York

    Google Scholar 

  56. Uvarov V.B. (1969). The connection between systems of polynomials that are orthogonal with respect to different distribution functions. ŽVyčisl. Mat. i Mat. Fiz. 9: 1253–1262

    MATH  MathSciNet  Google Scholar 

  57. Vorobyev, Y.V.: Methods of moments in applied mathematics. Translated from the Russian by Bernard Seckler. Gordon and Breach Science Publishers, New York (1965)

  58. Willems P., Lang B., Vömel C. (2006). Computing the bidiagonal SVD using multiple relatively robust representations. SIAM J. Matrix Anal. Appl. 28(4): 907–926

    Article  MathSciNet  MATH  Google Scholar 

  59. Xu S.F. (1993). A stability analysis of the Jacobi matrix inverse eigenvalue problem. BIT 33(4): 695–702

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD, 20742, USA

    Dianne P. O’Leary

  2. Institute of Computer Science and Faculty of Mathematics and Physics, Academy of Sciences of the Czech Republic and Charles University, Prague, Czech Republic

    Zdeněk Strakoš

  3. Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, Czech Republic

    Petr Tichý

Authors
  1. Dianne P. O’Leary
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zdeněk Strakoš
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Petr Tichý
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dianne P. O’Leary.

Additional information

The work of the first author was supported by the National Science Foundation under Grants CCR-0204084 and CCF-0514213. The work of the other two authors was supported by the Program Information Society under project 1ET400300415 and by the Institutional Research Plan AV0Z100300504.

P. Tichý in the years 2003–2006 on leave at the Institute of Mathematics, TU Berlin, Germany.

Rights and permissions

Reprints and permissions

About this article

Cite this article

O’Leary, D.P., Strakoš, Z. & Tichý, P. On sensitivity of Gauss–Christoffel quadrature. Numer. Math. 107, 147–174 (2007). https://doi.org/10.1007/s00211-007-0078-x

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-007-0078-x

Keywords

Search

Navigation