Optimal complexity of standard and goal-oriented adaptive FEM for general second-order linear elliptic PDEs

Abstract

Adaptive Finite-Element-Methoden (AFEMn) sind ein unverzichtbares Werkzeug für die effiziente numerische Simulation von partiellen Differentialgleichungen (PDG) mit einer Vielzahl von Anwendungen, insbesondere im Ingenieurwesen. Das Ziel besteht darin, eine zuverlässige numerische Approximation der unbekannten Lösung mit minimalen Rechenkosten zu berechnen. Diese Dissertation entwickelt adaptive Algorithmen zur effizienten Lösung von unsymmetrischen linearen elliptischen PDG zweiter Ordnung. Dazu verfeinern wir die adaptive Prozedur von Standard-AFEM: Berechne die Lösung der diskreten Formulierung und schätze den Approximationsfehler, markiere Dreiecke mit größerem Fehlerbeitrag und führe eine Verfeinerung des Gitters damit durch. Hierzu verwenden wir einen geschalteten iterativen Löser im SOLVE-Modul des adaptiven Algorithmus, der sich aus einer kontraktiven Symmetrisierung und der anschließenden Lösung dieses symmetrischen Problems mittels algebraischem Löser zusammensetzt. Hierbei ist es entscheidend, dass das Verfahren den Fehler in der zugehörigen Sobolev-Norm kontrahiert und der Löser lineare Komplexität aufweist. Die Abbruchkriterien werden so formuliert, dass sie die verschiedenen Fehlerkomponenten von Diskretisierung, Symmetrisierung und Algebra ausbalancieren. Diese Strategie garantiert volle R-lineare Konvergenz des Fehlers, d.h. im Wesentlichen Kontraktion eines geeigneten Quasi-Fehlers in jedem Schritt des Algorithmus. Eine hinreichend kleine Wahl der Parameter garantiert auch optimale Konvergenzraten bezüglich der Freiheitsgrade und Rechenkosten. Darüber hinaus wird die Methode auf zielorientierte adaptive Algorithmen erweitert, die die effiziente Berechnung eines Funktionalwertes der Lösung der PDG ermöglichen. Die Arbeit umfasst folgende Hauptbeiträge: Zur iterativen Lösung der linearen Gleichungssysteme von symmetrischen PDG präsentieren wir ein neuartiges geometrisches Mehrgitterverfahren, welches robust in Bezug auf den Polynomgrad \(p \ge 1\) und die (lokale) Netzweite \(h\) kontrahiert. Darüber hinaus wird bewiesen, dass der eingebaute algebraische Fehlerschätzer \(hp\)-robust äquivalent zum algebraischen Fehler ist und die Anwendung des Mehrgitterverfahrens auf symmetrische PDG optimale Komplexität garantiert. Zweitens wird gezeigt, dass das kontraktive inexakte Lösungsverfahren für eine unsymmetrische PDG zu optimaler Komplexität des Algorithmus führt. Eine neue Beweisstrategie ermöglicht es, die bisherigen Einschränkungen an die Parameter in vorherigen Arbeiten abzuschwächen. Zudem wird der übliche Beweisschritt über eine (Quasi-)Pythagoras-Identität durch eine verallgemeinerte Quasi-Orthogonalität ersetzt. Insgesamt ebnet die neue Beweisstrategie den Weg für Erweiterungen der Analyse auf allgemeine inf-sup-stabile Probleme jenseits von Energieminimierungs-Problemen. Schließlich wird ein zielorientierter adaptiver Algorithmus analysiert, der die effiziente Berechnung einer Zielgröße ermöglicht, die von der Lösung \(u^\star\) einer unsymmetrischen PDG abhängt. Es wird eine zielorientierte adaptive iterativ symmetrisierte Finite-Element-Methode präsentiert und analysiert. Es wird gezeigt, dass der vorgeschlagene Algorithmus volle R-lineare Konvergenz und optimale Konvergenzraten hinsichtlich sowohl der Freiheitsgrade als auch der Rechenkosten garantiert.

Adaptive finite element methods (AFEMs) have become an indispensable tool for efficient numerical simulations of partial differential equations (PDEs). Such methods successfully cover a wide range of applications, in particular, in engineering. However, what one strives to achieve in practice is computing a reliable numerical approximation of the unavailable solution at the lowest possible computational cost and therewith time. In this thesis, adaptive mesh-refining algorithms are developed for the efficient solution of nonsymmetric linear elliptic PDEs of second order. Standard AFEM employs the feedback loop: given a computational mesh, solve the discrete problem yielding an approximation, estimate its error, and mark certain elements for mesh-refinement. A centerpiece of this thesis consists of embedding a nested procedure in the SOLVE module including a contractive symmetrization and a contractive algebraic linear solver such that the error contracts in the PDE-related norm. Furthermore, it is crucial that the iterative linear solver is of linear complexity. Suitable stopping criteria are then formulated to equilibrate the error components (coming from discretization, symmetrization, and algebraic solver). We show that such an adaptive strategy leads to full R-linear convergence of the error, i.e., essentially a contraction of an appropriate quasi-error in every step of the adaptive algorithm. Moreover, a sufficiently small choice of adaptivity parameters guarantees optimal convergence rates with respect to the computational cost, i.e., optimal complexity. Furthermore, we show that this approach can be extended to goal-oriented adaptive algorithms, where the quantity of interest is a functional value of the PDE solution. Overall, the thesis comprises the following main contributions. First, we design an optimal local multigrid method for the iterative solution of the discrete systems arising from the finite element discretization of symmetric second-order linear elliptic diffusion problems. We show that the iterative solver contracts the algebraic error robustly with respect to the polynomial degree \(p \ge 1\) and the (local) mesh size \(h\). This is achieved by an overlapping additive Schwarz smoother. Moreover, embedding the solver into the AFEM framework for symmetric PDEs, we prove that this leads to the optimal convergence rate with respect to the overall cost. Second, we show that the proposed combined symmetrization-algebra procedure leads to a contractive inexact solver for nonsymmetric problems. The resulting AFEM algorithm is shown to be of optimal complexity. Initially, the analysis requires several fine-tuned parameters. However, a redesign of the proofs via a summability criterion for R-linear convergence allows us to relax such restrictions. Moreover, the usual proof via a (quasi-)Pythagorean identity is replaced by a generalized notion of quasi-orthogonality. Importantly, this paves the way towards extending the analysis to general inf-sup stable problems beyond the energy minimization setting. Finally, we consider the problem of efficiently computing a quantity of interest depending on the solution of a general second-order linear elliptic, yet nonsymmetric PDE. To this end, we propose a goal-oriented adaptive iteratively symmetrized finite element method (GOAISFEM) by combining the previous approaches for nonsymmetric problems. We show that this algorithm guarantees full R-linear convergence and, thus, allows for the proof of optimal convergence rates with respect to both degrees of freedom and total computational cost.