On optimality of adaptive FEM and BEM

Abstract

Im Rahmen elliptischer partieller Differentialgleichungen (PDE) betrachten wir die Finite Elemente Methode (FEM) und die Randelementmethode (BEM). Wir entwickeln sowie analysieren adaptive Algorithmen, die nicht nur die adaptive Netzverfeinerung steuern, sondern auch die Terminierung von geeigneten Lösern, d.h., die Linearisierung im Fall von nichtlinearen Differentialgleichungen und das iterative Lösen der sich ergebenden linearen Gleichungssysteme.Zum einen betrachten wir elliptische PDEs zweiter Ordnung, bei denen die auftretenden diskreten Systeme nicht exakt gelöst werden. Für kontrahierende iterative Löser formulieren wir einen adaptiven Algorithmus, der die adaptive Netzverfeinerung sowie die inexakte Lösung der auftretenden nichtlinearen bzw. linearen Systeme überwacht und steuert. Wir beweisen, dass die vorgeschlagene Strategie zu linearer Konvergenz mit optimalen algebraischen Raten führt. Hierbei fokussieren wir uns auf Konvergenzraten in Bezug auf den gesamten Rechenaufwand. Unsere Analysis ist anwendbar auf lineare Probleme, bei denen die linearen Systeme mittels optimal vorkonditionierter CG-Verfahren (PCG) gelöst werden, sowie nichtlineare Probleme mit stark monotoner Nichtlinearität, die mittels der sogenannten Zarantonello-Iteration linearisiert werden.Wir kombinieren die zuvor genannten Resultate im Rahmen elliptischer Randwertprobleme zweiter Ordnung mit stark monotoner und Lipschitz-stetiger Nichtlinearität. Wir präsentieren einen erweiterten adaptiven Algorithmus für die Berechnung der numerischen Approximation, der neben der adaptiven Gitterverfeinerung und der Zarantonello-Linearisierung auch einen kontrahierenden algebraischen Löser für die auftretenden linearen Gleichungssysteme steuert. Wir ermitteln Abbruchsbedingungen für den algebraischen Löser, die einerseits nicht zu einschränkend, aber andererseits ausreichend dafür sind, dass die inexakte Zarantonello-Linearisierung kontrahierend bleibt. In ähnlicher Weise ermitteln wir geeignete Abbruchsbedingungen für die Zarantonello-Iteration, sodass der Linearisierungsfehler sich nicht nachteilig auf den residualen a posteriori Fehlerschätzer auswirkt und die adaptive Netzverfeinerung zuverlässig gesteuert wird. Wir beweisen die Kontraktion der (geschachtelten) inexakten Iteration, die auf lineare Konvergenz des Gesamtverfahrens führt. Desweiteren beweisen wir, dass das Verfahren mit der optimalen Rate in Bezug auf die Freiheitsgrade konvergiert. Schließlich beweisen wir, dass es auch mit derselben optimalen Rate in Bezug auf den gesamten Rechenaufwand konvergiert.Zum anderen betrachten wir Adaptivität und PCG im Rahmen von Randwertproblemen für elliptische Integralgleichungen erster Art. Ähnlich wie zuvor steuert der präsentierte adaptive Algorithmus die Terminierung von PCG sowie die lokale Netzverfeinerung. Neben Konvergenz mit optimalen algebraischen Raten beweisen wir, dass das Verfahren mit fastoptimaler Rate in Bezug auf den gesamten Rechenaufwand konvergiert.

In the framework of elliptic partial differential equations (PDEs), we consider the finite element method (FEM) as well as the boundary element method (BEM). We design and analyze adaptive algorithms which do not only steer the adaptive mesh-refinement but also the termination of appropriate iterative solvers, namely, iterative linearization of nonlinear equations as well as iterative solvers for the arising linear systems.On the one hand, we consider a general framework for treating linear and nonlinear second-order elliptic PDEs, where the arising discrete systems are not solved exactly. For contractive iterative solvers, we formulate an adaptive algorithm which monitors and steers the adaptive mesh-refinement as well as the inexact solution of the arising discrete systems. We prove that the proposed strategy leads to linear convergence with optimal algebraic rates, where we focus on convergence rates with respect to the overall computational cost. Our analysis covers linear PDEs where the linear systems are solved by an optimally preconditioned conjugate gradient method (PCG) as well as nonlinear PDEs with strongly monotone nonlinearity which are linearized by the so-called Zarantonello iteration.Furthermore, we combine and extend the aforementioned results in the frame of second-order elliptic boundary value problems with strongly monotone and Lipschitz-continuous nonlinearity. We introduce an extended adaptive algorithm for the computation of the numerical approximation, which steers the adaptive mesh-refinement, the Zarantonello linearization, and a contractive algebraic solver to solve the arising linear systems. We identify stopping criteria for the algebraic solver that on the one hand do not request an overly tight tolerance, but on the other hand are sufficient for the inexact Zarantonello linearization to remain contractive. Similarly, we identify suitable stopping criteria for the Zarantonello iteration that leave an amount of linearization error that is not harmful for the residual a posteriori error estimator to steer the adaptive mesh-refinement reliably. We prove a contraction of the (nested) inexact iterations leading to linear convergence of the overall adaptive algorithm. Furthermore, we prove that the adaptive algorithm converges with optimal rates with respect to the number of degrees of freedom. Finally, we prove that the adaptive algorithm converges with the same optimal rate also with respect to the overall computational cost.On the other hand, we consider the interplay of adaptive mesh-refinement and PCG in the frame of BEM for elliptic integral equations of the first kind. As before, the proposed algorithm steers the termination of PCG as well as the local mesh-refinement. Besides convergence with optimal algebraic rates with respect to the number of degrees of freedom, we also prove that the algorithm converges with almost optimal rates with respect to the overall computational cost.