Improved condition number for spectral methods

Heinrichs, Wilhelm

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

Improved condition number for spectral methods
HTML articles powered by AMS MathViewer

by Wilhelm Heinrichs PDF

Math. Comp. 53 (1989), 103-119 Request permission

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.

References

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
C. Canuto and A. Quarteroni, Approximation results for orthogonal polynomials in Sobolev spaces, Math. Comp. 38 (1982), no. 157, 67–86. MR 637287, DOI 10.1090/S0025-5718-1982-0637287-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
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, DOI 10.1007/BF02576357
Daniele Funaro, A preconditioning matrix for the Chebyshev differencing operator, SIAM J. Numer. Anal. 24 (1987), no. 5, 1024–1031. MR 909062, DOI 10.1137/0724067
David Gottlieb and Steven A. Orszag, Numerical analysis of spectral methods: theory and applications, CBMS-NSF Regional Conference Series in Applied Mathematics, No. 26, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1977. MR 0520152
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, DOI 10.1016/0021-9991(79)90097-4
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
Wilhelm Heinrichs, Line relaxation for spectral multigrid methods, J. Comput. Phys. 77 (1988), no. 1, 166–182. MR 954308, DOI 10.1016/0021-9991(88)90161-1
Wilhelm Heinrichs, Collocation and full multigrid methods, Appl. Math. Comput. 26 (1988), no. 1, 35–43. MR 931622, DOI 10.1016/0096-3003(88)90085-9
Wilhelm Heinrichs, Konvergenzaussagen für Kollokationsverfahren bei elliptischen Randwertaufgaben, Numer. Math. 54 (1989), no. 6, 619–637 (German, with English summary). MR 981295, DOI 10.1007/BF01396486

J. Numer. Anal.

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
Theodor Meis and Ulrich Marcowitz, Numerische Behandlung partieller Differentialgleichungen, Hochschultext [University Textbooks], Springer-Verlag, Berlin-New York, 1978 (German). MR 513829
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
Steven A. Orszag, Spectral methods for problems in complex geometries, J. Comput. Phys. 37 (1980), no. 1, 70–92. MR 584322, DOI 10.1016/0021-9991(80)90005-4
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
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
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, DOI 10.1016/0021-9991(82)90063-8