Adaptive wavelet methods for elliptic operator equations: Convergence rates

Cohen, Albert; Dahmen, Wolfgang; DeVore, Ronald

doi:10.1090/S0025-5718-00-01252-7

Adaptive wavelet methods for elliptic operator equations: Convergence rates
HTML articles powered by AMS MathViewer

by Albert Cohen, Wolfgang Dahmen and Ronald DeVore HTML | PDF

Math. Comp. 70 (2001), 27-75 Request permission

Abstract:

This paper is concerned with the construction and analysis of wavelet-based adaptive algorithms for the numerical solution of elliptic equations. These algorithms approximate the solution $u$ of the equation by a linear combination of $N$ wavelets. Therefore, a benchmark for their performance is provided by the rate of best approximation to $u$ by an arbitrary linear combination of $N$ wavelets (so called $N$-term approximation), which would be obtained by keeping the $N$ largest wavelet coefficients of the real solution (which of course is unknown). The main result of the paper is the construction of an adaptive scheme which produces an approximation to $u$ with error $O(N^{-s})$ in the energy norm, whenever such a rate is possible by $N$-term approximation. The range of $s>0$ for which this holds is only limited by the approximation properties of the wavelets together with their ability to compress the elliptic operator. Moreover, it is shown that the number of arithmetic operations needed to compute the approximate solution stays proportional to $N$. The adaptive algorithm applies to a wide class of elliptic problems and wavelet bases. The analysis in this paper puts forward new techniques for treating elliptic problems as well as the linear systems of equations that arise from the wavelet discretization.

References

Lawrence M. Graves, The Weierstrass condition for multiple integral variation problems, Duke Math. J. 5 (1939), 656–660. MR 99
I. Babuška and A. Miller, A feedback finite element method with a posteriori error estimation. I. The finite element method and some basic properties of the a posteriori error estimator, Comput. Methods Appl. Mech. Engrg. 61 (1987), no. 1, 1–40. MR 880421, DOI 10.1016/0045-7825(87)90114-9
I. Babuška and W. C. Rheinboldt, Error estimates for adaptive finite element computations, SIAM J. Numer. Anal. 15 (1978), no. 4, 736–754. MR 483395, DOI 10.1137/0715049
R. S. Stepleman (ed.), Scientific computing, IMACS Transactions on Scientific Computation, I, International Association for Mathematics and Computers in Simulation (IMACS), New Brunswick, NJ; North-Holland Publishing Co., Amsterdam, 1983. Papers from the 10th IMACS world congress on systems simulation and scientific computation held in Montreal, Que., August 8–13, 1982. MR 751597
R. E. Bank and A. Weiser, Some a posteriori error estimators for elliptic partial differential equations, Math. Comp. 44 (1985), no. 170, 283–301. MR 777265, DOI 10.1090/S0025-5718-1985-0777265-X
A. Barinka, T. Barsch, P. Charton, A. Cohen, S. Dahlke, W. Dahmen, K. Urban, Adaptive wavelet schemes for elliptic problems—implementation and numerical experiments, IGPM Report # 173, RWTH Aachen, June 1999.
S. Bertoluzza, A posteriori error estimates for the wavelet Galerkin method, Appl. Math. Lett. 8 (1995), no. 5, 1–6. MR 1356289, DOI 10.1016/0893-9659(95)00057-W
Silvia Bertoluzza, An adaptive collocation method based on interpolating wavelets, Multiscale wavelet methods for partial differential equations, Wavelet Anal. Appl., vol. 6, Academic Press, San Diego, CA, 1997, pp. 109–135. MR 1474998, DOI 10.1016/S1874-608X(97)80005-2
S. Bertoluzza, Wavelet stabilization of the Lagrange multiplier method, to appear in Numer. Math.
S. Bertoluzza, C. Canuto, K. Urban, On the adaptive computation of integrals of wavelets, Preprint No. 1129, Istituto di Analisi Numerica del C.N.R. Pavia, 1999, to appear in Appl. Numer. Anal.
G. Beylkin, R. Coifman, and V. Rokhlin, Fast wavelet transforms and numerical algorithms. I, Comm. Pure Appl. Math. 44 (1991), no. 2, 141–183. MR 1085827, DOI 10.1002/cpa.3160440202
Gregory Beylkin and James M. Keiser, An adaptive pseudo-wavelet approach for solving nonlinear partial differential equations, Multiscale wavelet methods for partial differential equations, Wavelet Anal. Appl., vol. 6, Academic Press, San Diego, CA, 1997, pp. 137–197. MR 1474999, DOI 10.1016/S1874-608X(97)80006-4
Folkmar A. Bornemann, Bodo Erdmann, and Ralf Kornhuber, A posteriori error estimates for elliptic problems in two and three space dimensions, SIAM J. Numer. Anal. 33 (1996), no. 3, 1188–1204. MR 1393909, DOI 10.1137/0733059
Dietrich Braess, Finite elements, Cambridge University Press, Cambridge, 1997. Theory, fast solvers, and applications in solid mechanics; Translated from the 1992 German original by Larry L. Schumaker. MR 1463151, DOI 10.1007/978-3-662-07233-2
Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, Texts in Applied Mathematics, vol. 15, Springer-Verlag, New York, 1994. MR 1278258, DOI 10.1007/978-1-4757-4338-8
C. Canuto and I. Cravero, Wavelet-based adaptive methods for advection-diffusion problems, Preprint, University of Torino, 1996.
A. Cohen, Wavelet methods in Numerical Analysis, to appear in the Handbook of Numerical Analysis, vol. VII, 1998.
A. Cohen and R. Masson, Wavelet adaptive methods for elliptic equations - Preconditioning and adaptivity, Preprint, LAN, Université Pierre et Marie Curie, Paris, 1997, to appear in SIAM J. Sci. Comp.
Stephan Dahlke, Wolfgang Dahmen, and Ronald A. DeVore, Nonlinear approximation and adaptive techniques for solving elliptic operator equations, Multiscale wavelet methods for partial differential equations, Wavelet Anal. Appl., vol. 6, Academic Press, San Diego, CA, 1997, pp. 237–283. MR 1475001, DOI 10.1016/S1874-608X(97)80008-8
Stephan Dahlke, Wolfgang Dahmen, Reinhard Hochmuth, and Reinhold Schneider, Stable multiscale bases and local error estimation for elliptic problems, Appl. Numer. Math. 23 (1997), no. 1, 21–47. Multilevel methods (Oberwolfach, 1995). MR 1438079, DOI 10.1016/S0168-9274(96)00060-8
Stephan Dahlke and Ronald A. DeVore, Besov regularity for elliptic boundary value problems, Comm. Partial Differential Equations 22 (1997), no. 1-2, 1–16. MR 1434135, DOI 10.1080/03605309708821252
S. Dahlke, R. Hochmuth, K. Urban, Adaptive wavelet methods for saddle point problems, IGPM Report # 170, RWTH Aachen, Feb. 1999.
Wolfgang Dahmen, Wavelet and multiscale methods for operator equations, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 55–228. MR 1489256, DOI 10.1017/S0962492900002713
W. Dahmen, A. Kunoth, R. Schneider, Wavelet least squares methods for boundary value problems, IGPM Report # 175, RWTH Aachen, Sep. 1999.
Wolfgang Dahmen, Siegfried Müller, and Thomas Schlinkmann, Multigrid and multiscale decompositions, Large-scale scientific computations of engineering and environmental problems (Varna, 1997) Notes Numer. Fluid Mech., vol. 62, Friedr. Vieweg, Braunschweig, 1998, pp. 18–41. MR 1691506
Wolfgang Dahmen, Siegfried Prössdorf, and Reinhold Schneider, Multiscale methods for pseudo-differential equations on smooth closed manifolds, Wavelets: theory, algorithms, and applications (Taormina, 1993) Wavelet Anal. Appl., vol. 5, Academic Press, San Diego, CA, 1994, pp. 385–424. MR 1321437, DOI 10.1016/B978-0-08-052084-1.50023-5
W. Dahmen and R. Schneider, Wavelets on manifolds I, Construction and domain decomposition, IGPM-Report # 149, RWTH Aachen, Jan 1998.
W. Dahmen and R. Schneider, Wavelets on manifolds II, Application to boundary integral equations, in preparation.
W. Dahmen, R. Stevenson, Element-by-element construction of wavelets—stability and moment conditions, IGPM-Report # 145, RWTH Aachen, Dec. 1997.
Ingrid Daubechies, Ten lectures on wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 61, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1162107, DOI 10.1137/1.9781611970104
R. DeVore, Nonlinear approximation, Acta Numerica 7, Campbridge University Press, 1998, 51-150.
Ronald A. DeVore, Björn Jawerth, and Vasil Popov, Compression of wavelet decompositions, Amer. J. Math. 114 (1992), no. 4, 737–785. MR 1175690, DOI 10.2307/2374796
R. A. DeVore and V. A. Popov, Interpolation spaces and nonlinear approximation, Function spaces and applications (Lund, 1986) Lecture Notes in Math., vol. 1302, Springer, Berlin, 1988, pp. 191–205. MR 942269, DOI 10.1007/BFb0078875
R. A. DeVore and V. N. Temlyakov, Some remarks on greedy algorithms, Adv. Comput. Math. 5 (1996), no. 2-3, 173–187. MR 1399379, DOI 10.1007/BF02124742
Willy Dörfler, A convergent adaptive algorithm for Poisson’s equation, SIAM J. Numer. Anal. 33 (1996), no. 3, 1106–1124. MR 1393904, DOI 10.1137/0733054
Kenneth Eriksson, Don Estep, Peter Hansbo, and Claes Johnson, Introduction to adaptive methods for differential equations, Acta numerica, 1995, Acta Numer., Cambridge Univ. Press, Cambridge, 1995, pp. 105–158. MR 1352472, DOI 10.1017/S0962492900002531
Michael Frazier, Björn Jawerth, and Guido Weiss, Littlewood-Paley theory and the study of function spaces, CBMS Regional Conference Series in Mathematics, vol. 79, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1991. MR 1107300, DOI 10.1090/cbms/079
Erich Rothe, Topological proofs of uniqueness theorems in the theory of differential and integral equations, Bull. Amer. Math. Soc. 45 (1939), 606–613. MR 93, DOI 10.1090/S0002-9904-1939-07048-1
E. Novak, On the power of adaptation, J. Complexity, 12(1996), 199–237.
Tobias von Petersdorff and Christoph Schwab, Fully discrete multiscale Galerkin BEM, Multiscale wavelet methods for partial differential equations, Wavelet Anal. Appl., vol. 6, Academic Press, San Diego, CA, 1997, pp. 287–346. MR 1475002, DOI 10.1016/S1874-608X(97)80009-X
R. Schneider, Multiskalen- und Wavelet-Matrixkompression: Analysisbasierte Methoden zur effizienten Lösung großer vollbesetzter Gleichungssysteme, Habilitationsschrift, Technische Hochschule, Darmstadt, 1995.
P. Tchamitchian, Wavelets, Functions, and Operators, in: Wavelets: Theory and Applications, G. Erlebacher, M.Y. Hussaini, and L. Jameson (eds.), ICASE/LaRC Series in Computational Science and Engineering, Oxford University Press, 1996, 83–181.