Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A fast algorithm for Gaussian type quadrature formulae with mixed boundary conditions and some lumped mass spectral approximations

Authors: Abdelkrim Ezzirani and Allal Guessab
Journal: Math. Comp. 68 (1999), 217-248
MSC (1991): Primary 65D30, 65D32, 65N35
MathSciNet review: 1604332
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: After studying Gaussian type quadrature formulae with mixed boundary conditions, we suggest a fast algorithm for computing their nodes and weights. It is shown that the latter are computed in the same manner as in the theory of the classical Gauss quadrature formulae. In fact, all nodes and weights are again computed as eigenvalues and eigenvectors of a real symmetric tridiagonal matrix. Hence, we can adapt existing procedures for generating such quadrature formulae. Comparative results with various methods now in use are given. In the second part of this paper, new algorithms for spectral approximations for second-order elliptic problems are derived. The key to the efficiency of our algorithms is to find an appropriate spectral approximation by using the most accurate quadrature formula, which takes the boundary conditions into account in such a way that the resulting discrete system has a diagonal mass matrix. Hence, our algorithms can be used to introduce explicit resolutions for the time-dependent problems. This is the so-called lumped mass method. The performance of the approach is illustrated with several numerical examples in one and two space dimensions.

References [Enhancements On Off] (What's this?)

  • 1. R. Askey, Positive quadrature methods and positive polynomial sums, Approximation Theory 5 (C.K. Chui, L. L. Schumaker and J. D. Ward, eds.), Academic Press, New York, 1986, 1-30. MR 88j:41065
  • 2. P. Berckmann, Orthogonal polynomials for engineers and physicists, The Golem Press, Boulder, Colorado, 1973.
  • 3. C. Bernardi and Y. Maday, Some spectral approximations of one-dimensional fourth-order problems, Progress in Approximation Theory, ( P. Nevai and A. Pinkus eds.) Academic Press, San Diego (1991), 43-116. MR 92j:65176
  • 4. C. Bernardi and Y. Maday, Approximations spectrales de problèmes aux limites elliptiques, Spinger-Verlag France, Paris, 1992. MR 94f:65112
  • 5. B. Bojanov, D. Braess and N. Dyn, Generalized Gaussian quadrature formulas, J. Approx. Theory, v. 48, 1986, pp. 335-353. MR 88c:41049
  • 6. B. Bojanov B. and G. Nikolov, Comparison of Birkhoff type quadrature formulae, Math. Comput., v. 54, 1990, pp. 627-648. MR 91e:65034
  • 7. B. Bojanov, G. Grozev and A. A. Zhensykbaev, Generalized Gaussian quadrature formulas for weak Chebychev systems, in Optimal Recovery of Functions, B. Bojanov and H. Wozniakowski (Eds.), Nova Sciences, New York, 1992, pp. 115-140.
  • 8. B. Bojanov and A. Guessab, Gaussian quadrature formula of Birkhoff's type, to appear.
  • 9. C. Canuto, M.Y. Hussaini, A. Quarteroni and T. A. Zang, Spectral methods in fluid dynamics, Springer-Verlag New York, 1988. MR 89m:76004
  • 10. Ph. G. Ciarlet, The finite element method for elliptic problems, North-Holland, Amsterdam, 1978. MR 58:25001
  • 11. Ph. J. Davis and Ph. Rabinowitz, Methods of numerical integration, Academic Press, London, 1984. MR 86d:65004
  • 12. E. A. Van Doorn, Representation and bounds for zeros of orthogonal polynomials and eigenvalues of sign-symmetric tri-diagonal matrices, J. Approx. Theory, v. 51, 1987, pp. 254-266. MR 88j:33018
  • 13. A. Ezzirani, Construction de formules de quadrature pour des systèmes de Chebychev avec applications aux méthodes spectrales, Thèse de l'Université de Pau, France, 1996.
  • 14. A. Ezzirani and A. Guessab, A fast algorithm for Gaussian type quadrature formulae with mixed boundary conditions, and some lumped mass spectral approximations, U.A. CNRS 1204. 6(1998).
  • 15. D. Funaro, Polynomial approximation of differential equations, Spinger-Verlag, Berlin, 1992. MR 94c:65078
  • 16. W. Gautschi, A survey of Gauss-Christoffel quadrature formulae, in E. B. Christoffel (P. L. Butzer and F. Fehér, Eds.), Birkhäuser, Basel, 1981, pp. 72-147. MR 83g:41031
  • 17. W. Gautschi and S. Li, Gauss-Radau and Gauss-Lobatto quadrature with double end points, J. Comput. Appl. Math., v. 34, 1991, pp. 343-360. MR 92c:65032
  • 18. W. Gautschi, Algorithm 726: ORTHPOL- A package of routines for generating orthogonal polynomials and Gauss-type quadrature rules, ACM Trans. Math. Software 20(1994), 21-62.
  • 19. G. H. Golub and J. H. Welsch, Calculation of Gauss quadrature rules, Math. Comp., v. 23, 1969, pp. 221-230. MR 39:6513
  • 20. G. H. Golub, Some modified matrix eigenvalue problems, SIAM Rev., v. 15, 2(1973), pp. 318-334. MR 48:7569
  • 21. G. H. Golub and J. Kautsky, Calculation of Gauss quadratures with multiple free and fixed knots, Numer. Math., v. 41, 1983, pp. 147-162. MR 84i:65030
  • 22. A. Guessab and Q. I. Rahman, Quadrature formulae and polynomial inequalities, J. Approx. Theory, v. 90, 1997, pp. 255-282. CMP 97:16
  • 23. A. Guessab and G. V. Milovanovi\'{c}, An algorithm for Gauss-Birkhoff type quadrature formulae, to appear.
  • 24. T. Hughes, The finite element method: linear static and dynamic finite element analysis, Prentice-Hall, 1987. MR 90i:65001
  • 25. K. Jetter, A new class of Gaussian quadrature formulae based on Birkhoff type data, SIAM J. Numer. Anal., v. 5, 1982, 1080-1089. MR 84d:41054
  • 26. S. Karlin and W. J. Studden, Tchebycheff systems: with applications in analysis and statistics, Wiley, 1966. MR 34:4757
  • 27. M. G. Krein, The ideas of P. L. Chebyshev and A. A. Markov in the theory of limiting values of integrals and their further developments, Uspekhi Mat. Nauk, v. 6, 1951, no. 4, 3-120 (Russian); Amer. Math. Soc. Transl. Ser. 2, 12 (1959), pp. 1-122. MR 13:445c; MR 22:3947a
  • 28. G. G. Lorentz, K. Jetter and S. D. Riemenschneider, Birkhoff interpolation, Encyclopedia of Mathematics and its Applications, 19, Addison-Wesley, Reading, Mass., 1983. MR 84g:41002
  • 29. A. A. Melkman, Interpolation by splines satisfying mixed boundary conditions, Israel J. Math.,19 (1974), pp. 369-381. MR 51:8683
  • 30. C. A. Micchelli and A. Pinkus, Moment theory for weak Chebyshev systems with applications to monosplines, quadrature formulae and best one-sided L$^{1}-$approximation by spline functions with fixed knots, SIAM J. Math. Anal. 8 (1977), pp. 206-230. MR 55:8627
  • 31. C. A. Micchelli and T. J. Rivlin, Numerical integration rules near Gaussian formulas, Israel J. Math., v. 16, 1973, pp. 267-299. MR 51:2255
  • 32. C. A. Micchelli and T. J. Rivlin, Quadrature formulae and Hermite-Birkhoff interpolation, Advances in Mathematics, v. 11, 1973, pp. 93-112. MR 47:7289
  • 33. G. V. Milovanovi\'{c}, Construction of s-orthogonal polynomials and Turán quadratures, in Approx. Theory III, Ni\v{s}, 1987, (ed. G. V. Milovanovi\'{c}) Univ. Ni\v{s}, 1988, pp. 311-328. MR 89g:65023
  • 34. B. N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Englewood Cliffs, 1980. MR 81j:65063
  • 35. F. Peherstorfer, Characterization of positive quadrature formulae, SIAM J. Math. Anal., v. 12, 1981, pp. 935-942. MR 82m:65021
  • 36. F. Peherstorfer, Characterization of positive quadrature formulae II, SIAM J. Math. Anal. v. 15, 1984, pp. 1021-1030. MR 86a:65025
  • 37. A. Quarteroni and A. Valli, Numerical approximation of partial differential equations, Spinger-Verlag, Berlin, (1994). MR 95i:65005
  • 38. T. J. Rivlin, ''Chebyshev polynomials: From approximation theory to algebra and number theory,'' 2nd ed., Wiley, New York, 1990. MR 92a:41016
  • 39. H. J. Schmid, A note on positive quadrature rules, Rocky Mountain J. Math., v. 19, 1989, pp. 395-404. MR 90k:41041
  • 40. D. D. Stancu, Sur quelques formules générales de quadrature du type Gauss-Christoffel, Mat. (Cluj), v. 1, 1959, pp. 167-182. MR 22:11078
  • 41. G. Szegö, Orthogonal Polynomials, Colloquium Publication, v. 23, 4th ed., Amer. Math. Soc., Providence, R. I., 1975. MR 51:8724
  • 42. D. S. Watkins, Some perspectives on the eigenvalue problem, SIAM Review, v. 35, 1993, pp. 430-471. MR 94h:65039
  • 43. Y. Xu, Quasi-orthogonal polynomials, quadrature, and interpolation, J. Math. Anal. Appl., v. 182, 1994, pp. 779-799. MR 95a:42035
  • 44. Y. Xu, A characterization of positive quadrature formulae, Math. Comp., 62, 1994, pp. 703-718. MR 94h:41067

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65D30, 65D32, 65N35

Retrieve articles in all journals with MSC (1991): 65D30, 65D32, 65N35

Additional Information

Abdelkrim Ezzirani
Affiliation: Laboratoire de Mathématiques Appliquées, UPRES A 5033, Associé au CNRS, Université de Pau, 64000, France

Allal Guessab
Affiliation: Laboratoire de Mathématiques Appliquées, UPRES A 5033, Associé au CNRS, Université de Pau, 64000, France

Keywords: Quadrature formulae, Gaussian quadrature formulae, spectral methods, lumped mass methods, quasi-orthogonal polynomials, algorithms
Received by editor(s): May 6, 1997
Additional Notes: The work of the second author was supported by the CNRS grant INTAS-94-4070.
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society