Adaptive wavelet methods for elliptic operator equations: Convergence rates

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<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="u"><mml:semantics><mml:mi>u</mml:mi><mml:annotation encoding="application/x-tex">u</mml:annotation></mml:semantics></mml:math></inline-formula>of the equation by a linear combination of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"><mml:semantics><mml:mi>N</mml:mi><mml:annotation encoding="application/x-tex">N</mml:annotation></mml:semantics></mml:math></inline-formula>wavelets. Therefore, a benchmark for their performance is provided by the rate of best approximation to<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="u"><mml:semantics><mml:mi>u</mml:mi><mml:annotation encoding="application/x-tex">u</mml:annotation></mml:semantics></mml:math></inline-formula>by an arbitrary linear combination of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"><mml:semantics><mml:mi>N</mml:mi><mml:annotation encoding="application/x-tex">N</mml:annotation></mml:semantics></mml:math></inline-formula>wavelets (so called<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"><mml:semantics><mml:mi>N</mml:mi><mml:annotation encoding="application/x-tex">N</mml:annotation></mml:semantics></mml:math></inline-formula>-term approximation), which would be obtained by keeping the<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"><mml:semantics><mml:mi>N</mml:mi><mml:annotation encoding="application/x-tex">N</mml:annotation></mml:semantics></mml:math></inline-formula>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<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="u"><mml:semantics><mml:mi>u</mml:mi><mml:annotation encoding="application/x-tex">u</mml:annotation></mml:semantics></mml:math></inline-formula>with error<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis upper N Superscript negative s Baseline right-parenthesis"><mml:semantics><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>N</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−</mml:mo><mml:mi>s</mml:mi></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">O(N^{-s})</mml:annotation></mml:semantics></mml:math></inline-formula>in the energy norm, whenever such a rate is possible by<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"><mml:semantics><mml:mi>N</mml:mi><mml:annotation encoding="application/x-tex">N</mml:annotation></mml:semantics></mml:math></inline-formula>-term approximation. The range of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="s greater-than 0"><mml:semantics><mml:mrow><mml:mi>s</mml:mi><mml:mo>&gt;</mml:mo><mml:mn>0</mml:mn></mml:mrow><mml:annotation encoding="application/x-tex">s&gt;0</mml:annotation></mml:semantics></mml:math></inline-formula>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<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"><mml:semantics><mml:mi>N</mml:mi><mml:annotation encoding="application/x-tex">N</mml:annotation></mml:semantics></mml:math></inline-formula>. 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.