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
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
- Email: guessab@univ-pau.fr
- 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 1999 American Mathematical Society
- Journal: Math. Comp. 68 (1999), 217-248
- MSC (1991): Primary 65D30, 65D32, 65N35
- DOI: https://doi.org/10.1090/S0025-5718-99-01001-7
- MathSciNet review: 1604332