Improved condition number for spectral methods

Heinrichs, Wilhelm

doi:10.1090/S0025-5718-1989-0972370-0

Improved condition number for spectral methods

Author: Wilhelm Heinrichs
Journal: Math. Comp. 53 (1989), 103-119
MSC: Primary 65N30
DOI: https://doi.org/10.1090/S0025-5718-1989-0972370-0
MathSciNet review: 972370
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For the known spectral methods (Galerkin, Tau, Collocation) the condition number behaves like $O({N^4})$ (N: maximal degree of polynomials). We introduce a spectral method with an $O({N^2})$ condition number. The advantages with respect to propagation of rounding errors and preconditioning are demonstrated. A direct solver for constant coefficient problems is given. Extensions to variable coefficient problems and first-order problems are discussed. Numerical results are presented, showing the effectiveness of our methods.

[1] Ivo Babuška and A. K. Aziz, Survey lectures on the mathematical foundations of the finite element method, The mathematical foundations of the finite element method with applications to partial differential equations (Proc. Sympos., Univ. Maryland, Baltimore, Md., 1972) Academic Press, New York, 1972, pp. 1–359. With the collaboration of G. Fix and R. B. Kellogg. MR 0421106
[2] C. Canuto and A. Quarteroni, Approximation results for orthogonal polynomials in Sobolev spaces, Math. Comp. 38 (1982), no. 157, 67–86. MR 637287, https://doi.org/10.1090/S0025-5718-1982-0637287-3
[3] Claudio Canuto and Alfio Quarteroni, Variational methods in the theoretical analysis of spectral approximations, Spectral methods for partial differential equations (Hampton, Va., 1982) SIAM, Philadelphia, PA, 1984, pp. 55–78. MR 758262
[4] C. Canuto and A. Quarteroni, Spectral and pseudospectral methods for parabolic problems with nonperiodic boundary conditions, Calcolo 18 (1981), no. 3, 197–217. MR 647825, https://doi.org/10.1007/BF02576357
[5] Daniele Funaro, A preconditioning matrix for the Chebyshev differencing operator, SIAM J. Numer. Anal. 24 (1987), no. 5, 1024–1031. MR 909062, https://doi.org/10.1137/0724067
[6] David Gottlieb and Steven A. Orszag, Numerical analysis of spectral methods: theory and applications, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1977. CBMS-NSF Regional Conference Series in Applied Mathematics, No. 26. MR 0520152
[7] Thomas Zang and Dale B. Haidvogel, The accurate solution of Poisson’s equation by expansion in Chebyshev polynomials, J. Comput. Phys. 30 (1979), no. 2, 167–180. MR 528198, https://doi.org/10.1016/0021-9991(79)90097-4
[8] Wilhelm Heinrichs, Kollokationsverfahren und Mehrgittermethoden bei elliptischen Randwertaufgaben, Berichte der Gesellschaft für Mathematik und Datenverarbeitung [Reports of the Society for Mathematics and Data Processing], vol. 168, Gesellschaft für Mathematik und Datenverarbeitung mbH, St. Augustin; R. Oldenbourg Verlag, Munich, 1987 (German). MR 944528
[9] Wilhelm Heinrichs, Line relaxation for spectral multigrid methods, J. Comput. Phys. 77 (1988), no. 1, 166–182. MR 954308, https://doi.org/10.1016/0021-9991(88)90161-1
[10] Wilhelm Heinrichs, Collocation and full multigrid methods, Appl. Math. Comput. 26 (1988), no. 1, 35–43. MR 931622, https://doi.org/10.1016/0096-3003(88)90085-9
[11] Wilhelm Heinrichs, Konvergenzaussagen für Kollokationsverfahren bei elliptischen Randwertaufgaben, Numer. Math. 54 (1989), no. 6, 619–637 (German, with English summary). MR 981295, https://doi.org/10.1007/BF01396486
[12] W. Heinrichs, "Strong convergence estimates for pseudospectral methods," Submitted to SIAM J. Numer. Anal.
[13] M. A. Krasnosel′skiĭ, G. M. Vaĭnikko, P. P. Zabreĭko, Ya. B. Rutitskii, and V. Ya. Stetsenko, Approximate solution of operator equations, Wolters-Noordhoff Publishing, Groningen, 1972. Translated from the Russian by D. Louvish. MR 0385655
[14] Theodor Meis and Ulrich Marcowitz, Numerische Behandlung partieller Differentialgleichungen, Springer-Verlag, Berlin-New York, 1978 (German). Hochschultext. MR 513829
[15] Jindřich Nečas, Sur une méthode pour résoudre les équations aux dérivées partielles du type elliptique, voisine de la variationnelle, Ann. Scuola Norm. Sup. Pisa Cl. Sci. (3) 16 (1962), 305–326 (French). MR 163054
[16] Steven A. Orszag, Spectral methods for problems in complex geometries, J. Comput. Phys. 37 (1980), no. 1, 70–92. MR 584322, https://doi.org/10.1016/0021-9991(80)90005-4
[17] T. N. Phillips, T. A. Zang, and M. Y. Hussaini, Spectral multigrid methods for Dirichlet problems, Multigrid methods for integral and differential equations (Bristol, 1983) Inst. Math. Appl. Conf. Ser. New Ser., vol. 3, Oxford Univ. Press, New York, 1985, pp. 231–252. MR 849377
[18] Johann Schröder, Operator inequalities, Mathematics in Science and Engineering, vol. 147, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. MR 578001
[19] Thomas A. Zang, Yau Shu Wong, and M. Y. Hussaini, Spectral multigrid methods for elliptic equations, J. Comput. Phys. 48 (1982), no. 3, 485–501. MR 755459, https://doi.org/10.1016/0021-9991(82)90063-8