A new collocation method using near-minimal Chebyshev quadrature nodes on a square. (English) Zbl 1498.65211
Summary: A new collocation method using near-minimal Chebyshev quadrature nodes is proposed on the square \([ - 1, 1 ]^2\). For a (total) degree of precision \(2 n - 1\), the number of nodes of this near-minimal quadrature rule amounts only to \(\frac{ n(n + 1)}{ 2} + \lfloor \frac{ n}{ 2} \rfloor + 1\), which is one more than the Möller’s lower bound, \(\frac{ n(n + 1)}{ 2} + \lfloor \frac{ n}{ 2} \rfloor\), i.e., the minimal number of nodes in a quadrature rule of degree \(2 n - 1\) in two dimensions. Firstly, a new Chebyshev interpolation based on the near-minimal Chebyshev quadrature rule is constructed. An optimal error estimate on the new interpolation is obtained, and fast algorithms for the corresponding discrete Chebyshev transformation (DCT) between the function values and the discrete Chebyshev coefficients are then devised. Next, spectral differentiation schemes are developed both in the physical space and in the frequency space. Finally, a new Chebyshev collocation method, which uses nearly half nodes of the tensorial Chebyshev collocation method, is proposed to solve second order partial differential equations on the square. Numerical experiments illustrate that our new Chebyshev collocation method also possesses an exponential order of convergence for smooth problems. In comparison to the tensorial collocation method, it can offer better accuracy for most problems with the same degrees of freedom.
MSC:
| 65N35 | Spectral, collocation and related methods for boundary value problems involving PDEs |
Keywords:
Chebyshev collocation; near-minimal quadrature; Chebyshev interpolation; fast Chebyshev transforms; differentiation schemes; numerical analysisReferences:
| [1] | Bojanov, Borislav; Petrova, Guergana, On minimal cubature formulae for product weight functions, Am. J. Comput. Appl. Math., 85, 1, 113-121 (1997) · Zbl 0887.41026 |
| [2] | Bos, Len; De Marchi, Stefano; Vianello, Marco, On the Lebesgue constant for the Xu interpolation formula, J. Approx. Theory, 141, 2, 134-141 (2006) · Zbl 1099.41002 |
| [3] | Botella, Olivier, On the solution of the Navier-Stokes equations using Chebyshev projection schemes with third-order accuracy in time, Comput. Fluids, 26, 2, 107-116 (1997) · Zbl 0898.76077 |
| [4] | Boyd, John P., Chebyshev and Fourier Spectral Methods (2001), Courier Corporation: Courier Corporation New York · Zbl 0994.65128 |
| [5] | Caliari, Marco; De Marchi, Stefano; Sommariva, Alvise; Vianello, Marco, Padua2DM: fast interpolation and cubature at the Padua points in Matlab/Octave, Numer. Algorithms, 56, 1, 45-60 (2011) · Zbl 1206.65028 |
| [6] | Caliari, Marco; De Marchi, Stefano; Vianello, Marco, Bivariate Lagrange interpolation at the Padua points: computational aspects, Am. J. Comput. Appl. Math., 221, 2, 284-292 (2008) · Zbl 1152.65018 |
| [7] | Canuto, Claudio; Yousuff Hussaini, M.; Quarteroni, Alfio; Zang, Thomas A., Spectral Methods: Evolution to Complex Geometries and Applications to Fluid Dynamics (2007), Springer Science & Business Media: Springer Science & Business Media Berlin · Zbl 1121.76001 |
| [8] | Canuto, Claudio; Yousuff Hussaini, M.; Quarteroni, Alfio; Zang, Thomas A., Spectral Methods: Fundamentals in Single Domains (2007), Springer Science & Business Media: Springer Science & Business Media Berlin · Zbl 1121.76001 |
| [9] | Curtiss, J. H., Interpolation with harmonic and complex polynomials to boundary values, J. Math. Mech., 9, 2, 167-192 (1960) · Zbl 0092.29301 |
| [10] | Peter Dencker, Wolfgang Erb, a unifying theory for multivariate polynomial interpolation on general Lissajous-Chebyshev nodes, Preprint, 2017. · Zbl 1367.41023 |
| [11] | Deville, Michel; Mund, Ernest, Chebyshev pseudospectral solution of second-order elliptic equations with finite element preconditioning, J. Comput. Phys., 60, 3, 517-533 (1985) · Zbl 0585.65073 |
| [12] | Deville, Michel O.; Mund, Ernest H., Finite-element preconditioning for pseudospectral solutions of elliptic problems, SIAM J. Sci. Stat. Comput., 11, 2, 311-342 (1990) · Zbl 0701.65075 |
| [13] | Driscoll, Tobin A.; Hale, Nicholas; Trefethen, Lloyd N., Chebfun Guide (2014), Pafnuty Publications: Pafnuty Publications Oxford |
| [14] | Ehrenstein, U.; Peyret, R., A Chebyshev collocation method for the Navier-Stokes equations with application to double-diffusive convection, Int. J. Numer. Methods Fluids, 9, 4, 427-452 (1989) · Zbl 0665.76107 |
| [15] | Fox, L.; Parker, I. B., Chebyshev Polynomials in Numerical Analysis (1968), Oxford U. Press: Oxford U. Press Oxford · Zbl 0153.17502 |
| [16] | Gottlieb, David; Lustman, Liviu, The spectrum of the Chebyshev collocation operator for the heat equation, SIAM J. Numer. Anal., 20, 5, 909-921 (1983) · Zbl 0537.65085 |
| [17] | Gottlieb, David; Orszag, Steven A., Numerical Analysis of Spectral Methods: Theory and Applications, vol. 26 (1977), SIAM: SIAM Philadelphia · Zbl 0412.65058 |
| [18] | Guo, Benyu, Spectral Methods and Their Applications (1998), World Scientific: World Scientific Singapore · Zbl 0929.35136 |
| [19] | Haldenwang, P.; Labrosse, G.; Abboudi, S.; Deville, M., Chebyshev 3-D spectral and 2-D pseudospectral solvers for the Helmholtz equation, J. Comput. Phys., 55, 1, 115-128 (1984) · Zbl 0544.65071 |
| [20] | Hammad, D. A.; El-Azab, M. S., Chebyshev-Chebyshev spectral collocation method for solving the generalized regularized long wave (GRLW) equation, Appl. Math. Comput., 285, 228-240 (2016) · Zbl 1410.65395 |
| [21] | Hussaini, M. Yousuff; Streett, Craig L.; Zang, Thomas A., Spectral methods for partial differential equations, 883-925 (1984), Army Res. Office Trans. of the 1st Army Conf. on Appl. Math and Computing |
| [22] | Kasperski, G., A parallel Schwarz preconditioner for the Chebyshev Gauss-Lobatto collocation \((\frac{ \text{d}^2}{ \text{d} x^2} - h^2)\) operator, J. Comput. Phys., 296, 101-112 (2015) · Zbl 1352.65209 |
| [23] | Khader, M. M., On the numerical solutions for the fractional diffusion equation, Commun. Nonlinear Sci. Numer. Simul., 16, 6, 2535-2542 (2011) · Zbl 1221.65263 |
| [24] | Khater, A. H.; Temsah, R. S.; Hassan, M. M., A Chebyshev spectral collocation method for solving Burgers’-type equations, J. Comput. Appl. Math., 222, 2, 333-350 (2008) · Zbl 1153.65102 |
| [25] | Dong Kim, Sang; Parter, Seymour V., Preconditioning Chebyshev spectral collocation by finite-difference operators, SIAM J. Numer. Anal., 34, 3, 939-958 (1997) · Zbl 0874.65088 |
| [26] | Kopriva, David A., A conservative staggered-grid Chebyshev multidomain method for compressible flows. II. A semi-structured method, J. Comput. Phys., 128, 2, 475-488 (1996) · Zbl 0866.76064 |
| [27] | Li, Huiyuan; Sun, Jiachang; Xu, Yuan, Cubature formula and interpolation on the cubic domain, Numer. Math. Theor. Meth. Appl., 2, 2, 119-152 (2009) · Zbl 1212.41002 |
| [28] | Liu, W. B.; Shen, Jie, A new efficient spectral Galerkin method for singular perturbation problems, J. Sci. Comput., 11, 4, 411-437 (1996) · Zbl 0891.76066 |
| [29] | Martucci, Stephen A., Symmetric convolution and the discrete sine and cosine transforms, IEEE Trans. Signal Process., 42, 5, 1038-1051 (1994) |
| [30] | Möller, H. Michael, Lower bounds for the number of nodes in cubature formulae, Numer. Integr., 45, 221-230 (1979) · Zbl 0416.65019 |
| [31] | Morrow, C. R.; Patterson, T. N.L., Construction of algebraic cubature rules using polynomial ideal theory, SIAM J. Numer. Anal., 15, 5, 953-976 (1978) · Zbl 0402.65013 |
| [32] | Orszag, Steven A., Spectral methods for problems in complex geometrics, (Numerical Methods for Partial Differential Equations (1979), Elsevier), 273-305 · Zbl 0448.65072 |
| [33] | Patera, Anthony T., A spectral element method for fluid dynamics: laminar flow in a channel expansion, J. Comput. Phys., 54, 3, 468-488 (1984) · Zbl 0535.76035 |
| [34] | Peyret, Roger, Spectral Methods for Incompressible Viscous Flow (2002), Springer Science & Business Media: Springer Science & Business Media New York · Zbl 1005.76001 |
| [35] | Pfeiffer, Harald P.; Kidder, Lawrence E.; Scheel, Mark A.; Teukolsky, Saul A., A multidomain spectral method for solving elliptic equations, Comput. Phys. Commun., 152, 3, 253-273 (2003) · Zbl 1196.65179 |
| [36] | Shen, Jie, Efficient spectral-Galerkin method II. Direct solvers of second- and fourth-order equations using Chebyshev polynomials, SIAM J. Sci. Comput., 16, 1, 74-87 (1995) · Zbl 0840.65113 |
| [37] | Shen, Jie; Tang, Tao, Spectral and High-Order Methods with Applications (2006), Science Press: Science Press Beijing · Zbl 1234.65005 |
| [38] | Shen, Jie; Tang, Tao; Wang, Li-Lian, Spectral Methods: Algorithms, Analysis and Applications, Springer Series in Computational Mathematics, vol. 41 (2011), Springer Science & Business Media: Springer Science & Business Media Berlin · Zbl 1227.65117 |
| [39] | Shen, Jie; Wang, Feng; Xu, Jinchao, A finite element multigrid preconditioner for Chebyshev-collocation methods, Appl. Numer. Math., 33, 1-4, 471-477 (2000) · Zbl 0964.65133 |
| [40] | Shen, Jie; Wang, Li-Lian, Sparse spectral approximations of high-dimensional problems based on hyperbolic cross, SIAM J. Numer. Anal., 48, 4, 1087-1109 (2010) · Zbl 1215.65179 |
| [41] | Shen, Jie; Wang, Li-Lian; Yu, Haijun, Approximations by orthonormal mapped Chebyshev functions for higher-dimensional problems in unbounded domains, J. Comput. Appl. Math., 265, 264-275 (2014) · Zbl 1293.65161 |
| [42] | Shen, Jie; Wang, Yingwei; Xia, Jianlin, Fast structured direct spectral methods for differential equations with variable coefficients. I. The one-dimensional case, SIAM J. Sci. Comput., 38, 1, A28-A54 (2016) · Zbl 1330.65124 |
| [43] | Shen, Jie; Yu, Haijun, Efficient spectral sparse grid methods and applications to high-dimensional elliptic problems, SIAM J. Sci. Comput., 32, 6, 3228-3250 (2010) · Zbl 1233.65094 |
| [44] | Shen, Jie; Yu, Haijun, Efficient spectral sparse grid methods and applications to high-dimensional elliptic equations II. Uunbounded domains, SIAM J. Sci. Comput., 34, 2, A1141-A1164 (2012) · Zbl 1269.65130 |
| [45] | Trefethen, Lloyd N., Spectral Methods in MATLAB, vol. 10 (2000), SIAM: SIAM Philadelphia · Zbl 0953.68643 |
| [46] | Welfert, Bruno D., Generation of pseudospectral differentiation matrices I, SIAM J. Numer. Anal., 34, 4, 1640-1657 (1997) · Zbl 0889.65013 |
| [47] | Xu, Yuan, Common Zeros of Polynomials in Several Variables and Higher Dimensional Quadrature, Pitman Research Notes in Mathematics Series (1994), Longman Scientific & Technical: Longman Scientific & Technical Essex · Zbl 0898.26004 |
| [48] | Xu, Yuan, Christoffel functions and Fourier series for multivariate orthogonal polynomials, J. Approx. Theory, 82, 2, 205-239 (1995) · Zbl 0874.42018 |
| [49] | Xu, Yuan, Lagrange interpolation on Chebyshev points of two variables, J. Approx. Theory, 87, 2, 220-238 (1996) · Zbl 0864.41002 |
| [50] | Xu, Yuan, Minimal cubature rules and polynomial interpolation in two variables, J. Approx. Theory, 164, 1, 6-30 (2012) · Zbl 1236.65024 |
| [51] | Xu, Yuan, Minimal cubature rules and polynomial interpolation in two variables II, J. Approx. Theory, 214, 49-68 (2017) · Zbl 1356.41002 |
| [52] | Xu, Yuan, Optimal points for cubature rules and polynomial interpolation on a square, (Dick, Josef; Kuo, Frances Y.; Woźniakowski, Henryk, Contemporary Computational Mathematics - A Celebration of the 80th Birthday of Ian Sloan (2018), Springer International Publishing: Springer International Publishing Cham), 1287-1305 · Zbl 1405.65034 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
