Mathematics of Computation

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

Author(s): Abdelkrim Ezzirani; Allal Guessab.
Journal: Math. Comp. 68 (1999), 217-248.
MSC (1991): Primary 65D30, 65D32, 65N35
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

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

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

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
Email: guessab@univ-pau.fr

DOI: 10.1090/S0025-5718-99-01001-7
PII: S 0025-5718(99)01001-7
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.
Copyright of article: Copyright 1999, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS