Rate optimality of adaptive algorithms

Abstract

Diese Arbeit schafft einen axiomatischen Rahmen für den Beweis von optimalen Konvergenzraten adaptiver Algorithmen. Das Hauptanwendungsfeld hierfür sind die Finite-Element-Methode sowie auch die Randelement-Methode. Drei Axiome für den Fehlerschätzer und drei weitere für die zugehörige Netzverfeinerung garantieren optimale Konvergenzraten. Der axiomatische Zugang erlaubt es, spezielle Fragen nach der Notwendigkeit von (diskreten) unteren Fehlerschranken, dem Einsatz von approximativen Lösern, der Einbindung von inhomogenen Randdaten oder auch der Verwendung von äquivalenten Fehlerschätzern zu beantworten. Die Weiterentwicklungen und Verbesserungen im Vergleich zum aktuellen Stand der Forschung (ausgenommen der eigenen Arbeit [Feischl et al., 2014], welche in dieser Dissertation teilweise erweitert wird) werden im Folgenden zusammengefasst: Es wird ein einheitlicher und komplett abstrakter theoretischer Rahmen geschaffen, der die aktuelle Literatur zum Thema optimaler Konvergenzraten umfasst. Die abstrakte Form erlaubt es, lineare sowie nichtlineare Probleme zu behandeln, und sie ist unabhängig von der zugrundeliegenden (konformen, nicht-konformen, gemischten) Methode. Verwendet und analysiert wird einzig der Fehlerschätzer, welcher als Funktion der Triangulierung betrachtet wird. Dieser Zugang ermöglicht es, Axiome zu formulieren, die unabhängig von allen Annahmen an das konkrete Modell sind. Die Beweise für Konvergenz und Konvergenz mit optimaler Rate kommen ohne Effizienz des Fehlerschätzers aus. Effizienz wird in dieser Arbeit nur verwendet, um die Approximationsklasse mittels Best-Approximationsfehler und Datenfehler zu charakterisieren. Als Konsequenz davon und im Unterschied zur gegenwärtigen Literatur hängt die obere Schranke für optimale Markierungsparameter nicht mehr von der Effizienzkonstante ab. Die Arbeit führt eine allgemeine Quasi-Galerkinorthogonalität ein, die nicht nur hinreichend, sondern auch notwendig für die R-lineare Konvergenz des Fehlerschätzers ist. Betrachtet man die optimale Konvergenzrate des Fehlerschätzers bezüglich der Komplexität des Verfahrens (das heißt: die Komplexität der Berechnung des aktuellen Schritts und die Komplexität aller vorausgegangenen Schritte), so stellt sich die R-lineare Konvergenz selbst als notwendig heraus. Die optimale Komplexität wird dann als Konsequenz der optimalen Konvergenzraten des Fehlerschätzers bewiesen. Anstatt der Overlay-Eigenschaft (eine übliche Annahme in aktueller Literatur) verwendet diese Arbeit eine tieferliegende Eigenschaft der Netzverfeinerung. Dies erlaubt es, auch für populäre Verfeinerungsmethoden wie die Rot-Grün-Blau-Verfeinerung, optimale Konvergenzraten zu beweisen. Schlussendlich behandelt diese Arbeit equivalente Fehlerschätzer, approximative Löser sowie inhomogene und gemischte Randdaten. Zusätzlich wird eine neue Methode zur adaptiven Geometrie-Approximation für eine spezielle Randelement-Methode eingeführt und deren Konvergenz bewiesen.

This work aims first at the development of an axiomatic framework for the proof of optimal convergence rates for adaptive algorithms, with the main field of application being the finite element method and the boundary element method. Second, the axiomatic view allows refinements of particular questions like the avoidance of (discrete) lower bounds, inexact solvers, inhomogeneous boundary data, or the use of equivalent error estimators. Three axioms which are related to the estimator guarantee optimal convergence rates in terms of the error estimator for any refinement strategy which satisfies additional three triangulation related axioms. Compared to the state of the art in the literature (except for the recent own work [Feischl et al.,2014] which is partially generalized), the improvements of this work can be summarized as follows: First, a general and completely abstract framework is presented which covers the existing literature on rate optimality of adaptive algorithms. The abstract analysis covers linear as well as nonlinear problems and is independent of the underlying (conforming, non-conforming, or mixed) finite element or boundary element method. Solely, the error estimator, considered as a function of the underlying triangulation, is used and analyzed. This allows to formulate axioms which are not restricted to any concrete model assumption. Second, efficiency of the error estimator is neither needed to prove convergence nor quasi-optimal convergence behavior of the error estimator. In this work, efficiency exclusively characterizes the approximation classes involved in terms of the best-approximation error and data resolution. Therefore, the upper bound on the optimal marking parameters does not depend on the efficiency constant. Third, some general quasi-Galerkin orthogonality is not only sufficient, but also necessary for the R-linear convergence of the error estimator, which turns out to be necessary itself when it comes to optimal complexity estimates. The latter means the optimality of the adaptive algorithm when considering the overall cost of the algorithm (which includes the computation of all previous steps) and is proved as a by-product of rate optimality. Fourth, we circumvent the use of the overlay estimate of the refinement strategy, which is a standard assumption in the recent literature, to include popular refinement schemes like red-green-blue refinement into the analysis. Finally, the general analysis allows for equivalent error estimators and inexact solvers as well as different non-homogeneous and mixed boundary conditions and is even employed to prove convergence of some novel adaptive geometry approximation for a certain boundary element method.