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

Ezzirani, Abdelkrim; Guessab, Allal

doi:10.1090/S0025-5718-99-01001-7

A fast algorithm for Gaussian type quadrature formulae with mixed boundary conditions and some lumped mass spectral approximations
HTML articles powered by AMS MathViewer

by Abdelkrim Ezzirani and Allal Guessab PDF

Math. Comp. 68 (1999), 217-248 Request permission

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

Richard Askey, Positive quadrature methods and positive polynomial sums, Approximation theory, V (College Station, Tex., 1986) Academic Press, Boston, MA, 1986, pp. 1–29. MR 903680
P. Berckmann, Orthogonal polynomials for engineers and physicists, The Golem Press, Boulder, Colorado, 1973.
Christine Bernardi and Yvon Maday, Some spectral approximations of one-dimensional fourth-order problems, Progress in approximation theory, Academic Press, Boston, MA, 1991, pp. 43–116. MR 1114769
Christine Bernardi and Yvon Maday, Approximations spectrales de problèmes aux limites elliptiques, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 10, Springer-Verlag, Paris, 1992 (French, with French summary). MR 1208043
Borislav D. Bojanov, Dietrich Braess, and Nira Dyn, Generalized Gaussian quadrature formulas, J. Approx. Theory 48 (1986), no. 4, 335–353. MR 865436, DOI 10.1016/0021-9045(86)90008-0
Borislav Bojanov and Geno Nikolov, Comparison of Birkhoff type quadrature formulae, Math. Comp. 54 (1990), no. 190, 627–648. MR 1010595, DOI 10.1090/S0025-5718-1990-1010595-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.
B. Bojanov and A. Guessab, Gaussian quadrature formula of Birkhoff’s type, to appear.
Claudio Canuto, M. Yousuff Hussaini, Alfio Quarteroni, and Thomas A. Zang, Spectral methods in fluid dynamics, Springer Series in Computational Physics, Springer-Verlag, New York, 1988. MR 917480, DOI 10.1007/978-3-642-84108-8
Philippe G. Ciarlet, The finite element method for elliptic problems, Studies in Mathematics and its Applications, Vol. 4, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. MR 0520174
Philip J. Davis and Philip Rabinowitz, Methods of numerical integration, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1984. MR 760629
S. Minakshi Sundaram, On non-linear partial differential equations of the parabolic type, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 479–494. MR 0000088, DOI 10.1007/BF03046993
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.
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).
Daniele Funaro, Polynomial approximation of differential equations, Lecture Notes in Physics. New Series m: Monographs, vol. 8, Springer-Verlag, Berlin, 1992. MR 1176949, DOI 10.1007/978-3-540-46783-0
Walter Gautschi, A survey of Gauss-Christoffel quadrature formulae, E. B. Christoffel (Aachen/Monschau, 1979) Birkhäuser, Basel-Boston, Mass., 1981, pp. 72–147. MR 661060
Walter Gautschi and Shikang Li, Gauss-Radau and Gauss-Lobatto quadratures with double end points, J. Comput. Appl. Math. 34 (1991), no. 3, 343–360. MR 1102590, DOI 10.1016/0377-0427(91)90094-Z
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.
Gene H. Golub and John H. Welsch, Calculation of Gauss quadrature rules, Math. Comp. 23 (1969), 221-230; addendum, ibid. 23 (1969), no. 106, loose microfiche suppl, A1–A10. MR 0245201, DOI 10.1090/S0025-5718-69-99647-1
Gene H. Golub, Some modified matrix eigenvalue problems, SIAM Rev. 15 (1973), 318–334. MR 329227, DOI 10.1137/1015032
G. H. Golub and J. Kautský, Calculation of Gauss quadratures with multiple free and fixed knots, Numer. Math. 41 (1983), no. 2, 147–163. MR 703119, DOI 10.1007/BF01390210
A. Guessab and Q. I. Rahman, Quadrature formulae and polynomial inequalities, J. Approx. Theory, v. 90, 1997, pp. 255-282.
A. Guessab and G. V. Milovanović, An algorithm for Gauss-Birkhoff type quadrature formulae, to appear.
Thomas J. R. Hughes, The finite element method, Prentice Hall, Inc., Englewood Cliffs, NJ, 1987. Linear static and dynamic finite element analysis; With the collaboration of Robert M. Ferencz and Arthur M. Raefsky. MR 1008473
Kurt Jetter, A new class of Gaussian quadrature formulas based on Birkhoff type data, SIAM J. Numer. Anal. 19 (1982), no. 5, 1081–1089. MR 672579, DOI 10.1137/0719078
Samuel Karlin and William J. Studden, Tchebycheff systems: With applications in analysis and statistics, Pure and Applied Mathematics, Vol. XV, Interscience Publishers John Wiley & Sons, New York-London-Sydney, 1966. MR 0204922
C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
George G. Lorentz, Kurt Jetter, and Sherman D. Riemenschneider, Birkhoff interpolation, Encyclopedia of Mathematics and its Applications, vol. 19, Addison-Wesley Publishing Co., Reading, Mass., 1983. MR 680938
Avraham A. Melkman, Interpolation by splines satisfying mixed boundary conditions, Israel J. Math. 19 (1974), 369–381. MR 372475, DOI 10.1007/BF02757500
C. A. Micchelli and Allan 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), no. 2, 206–230. MR 435669, DOI 10.1137/0508015
C. A. Micchelli and T. J. Rivlin, Numerical integration rules near Gaussian quadrature, Israel J. Math. 16 (1973), 287–299. MR 366003, DOI 10.1007/BF02756708
C. A. Micchelli and T. J. Rivlin, Quadrature formulae and Hermite-Birkhoff interpolation, Advances in Math. 11 (1973), 93–112. MR 318743, DOI 10.1016/0001-8708(73)90004-2
Gradimir V. Milovanović, Construction of $s$-orthogonal polynomials and Turán quadrature formulae, Numerical methods and approximation theory, III (Niš, 1987) Univ. Niš, Niš, 1988, pp. 311–328. MR 960351
Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR 570116
Franz Peherstorfer, Characterization of positive quadrature formulas, SIAM J. Math. Anal. 12 (1981), no. 6, 935–942. MR 635246, DOI 10.1137/0512079
Franz Peherstorfer, Characterization of quadrature formula. II, SIAM J. Math. Anal. 15 (1984), no. 5, 1021–1030. MR 755862, DOI 10.1137/0515079
Alfio Quarteroni and Alberto Valli, Numerical approximation of partial differential equations, Springer Series in Computational Mathematics, vol. 23, Springer-Verlag, Berlin, 1994. MR 1299729, DOI 10.1007/978-3-540-85268-1
Theodore J. Rivlin, Chebyshev polynomials, 2nd ed., Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1990. From approximation theory to algebra and number theory. MR 1060735
H. J. Schmid, A note on positive quadrature rules, Rocky Mountain J. Math. 19 (1989), no. 1, 395–404. Constructive Function Theory—86 Conference (Edmonton, AB, 1986). MR 1016190, DOI 10.1216/RMJ-1989-19-1-395
D. D. Stancu, Sur quelques formules générales de quadrature du type Gauss-Christoffel, Mathematica (Cluj) 1(24) (1959), no. 1, 167–182 (French). MR 120323
Gábor Szegő, Orthogonal polynomials, 4th ed., American Mathematical Society Colloquium Publications, Vol. XXIII, American Mathematical Society, Providence, R.I., 1975. MR 0372517
David S. Watkins, Some perspectives on the eigenvalue problem, SIAM Rev. 35 (1993), no. 3, 430–471. MR 1234638, DOI 10.1137/1035090
Yuan Xu, Quasi-orthogonal polynomials, quadrature, and interpolation, J. Math. Anal. Appl. 182 (1994), no. 3, 779–799. MR 1272153, DOI 10.1006/jmaa.1994.1121
Yuan Xu, A characterization of positive quadrature formulae, Math. Comp. 62 (1994), no. 206, 703–718. MR 1223234, DOI 10.1090/S0025-5718-1994-1223234-0