Optimal adaptive wavelet methods for solving first order system least squares

Abstract

The ecient numerical approximation of the solution of a partial dierential equation (PDE) requires the use of an approximation space with a local resolution that is adjusted to the local smoothness of the solution. Since a priori this solution is unknown, such a space has to be created adaptively by means of a loop in which increasingly more accurate approximations to the solution are built. Two instances of such adaptive solution methods are adaptive finite element methods (afem) and adaptive wavelet-Galerkin methods (awgm). It is fair to say that the latter methods are more cumbersome to implement, but on the other hand their use is not restrictedto essentially elliptic PDEs. Any well-posed operator equation on a Hilbert space equipped with a Riesz basis has an equivalent formulation as an bi-infinite matrix-vector equation. Given a finite Λ ⊂ N, and having computed a (quasi-) best approximation to the solution by a vector supported on Λ, the norm of the residual vector of this approximation is proportional to the norm of its error. By adding those indices of the residual vector that correspond to its largest entries to the set Λ an extended set is created, and the loop can be repeated. Generally the aforementioned residual vector has infinite support, and therefore has to be approximated. This residual vector is the dierence of the infinite load vector and the bi-infinite stiness matrix applied to the current approximation vector. The standard approach is to approximate both terms separately, the second one using the nonlinear approximate matrix-vector multiplication routine, known as the apply-routine. In contrast to their dierence, being the residual vector, the aforementioned terms do not tend to zero when the iteration proceeds. Therefore, in order to approximate the residual within some fixed relative tolerance, they have to be approximated within a relative tolerance that gets increasingly smaller. In order to improve the quantitative properties of the adaptive wavelet method, Chapter 2 of this thesis is devoted to an approach to approximate the residual vector without splitting it. In order to do so, it is needed to be able to represent both parts of the residual in a common dictionary. In the standard setting of a PDE of 2nd order and continuous piecewise polynomial wavelets, the operator applied to a wavelet is a distribution, and the splitting cannot be avoided. Therefore, we consider a reformulation of such a PDE as a first order system by introducing the flux as a separate unknown. We show that any well-posed semi-linear PDE of 2nd order allowsa reformulation as a well-posed first order system least squares (FOSLS) problem. For such system we design an alternative, more ecient approximate residual evaluation scheme that, in case of a linear PDE, depends linearly on the current approximation. In Chapter 4 we apply this machinery to parabolic evolutionary PDEs in a simultaneously space-time variational formulation. In the recent years, one witnesses a growing interest in such formulations as an alternative for the usual time marching schemes that are inherently sequential, and that are not suited to eciently approximating singularities that are local in both space and time. The arising Hilbert spaces in this setting are (intersections of) Bochner spaces that are most naturally equipped with Riesz bases that are tensor products of temporal and spatial wavelet bases. These tensor product wavelet bases require a modified, more complicated routine for the approximate residual evaluation, since one cannot aort a transformation to a locally single representation. On the other hand, they give the major advantage of an eective dimension reduction known from sparse-grid methods in a non-adaptive setting. We will be able to solve the whole time evolution at a complexity equal to that of solving one stationary problem.For running the awgm, wavelet bases are needed for the generally non-square domains on which the equations are posed. Several constructions of continuous piecewise linear wavelets on general polygonal or polyhedral domains are known. Because of ourFOSLS formulation, we need in addition a wavelet Riesz basis consisting of piecewise quadratics. Such bases are constructed in Chapter 3. Finally, in Chapter 5 details are provided on several aspects of the implementation of the various routines that we have developed.

Η αποδοτική αριθμητική προσέγγιση της λύσης μιας μερικής διαφορικής εξίσωσης (ΜΔΕ) απαιτεί τη χρήση ενός συναρτησιακού χώρου προσέγγισης με τοπική ανάλυση προσαρμοσμένου στην τοπική ομαλότητα της λύσης. Δεδομένου ότι αυτή η λύση είναι άγνωστη εκ των προτέρων, ένας τέτοιος χώρος πρέπει να δημιουργηθεί προσαρμοστικά με τη χρήση ενός επαναληπτικού σχήματος κατά το οποίο κατασκευάζονται ολοένα και πιο ακριβείς προσεγγίσεις της λύσης. Δύο παραδείγματα τέτοιων προσαρμοστικών μεθόδων επίλυσης είναι οι προσαρμοστικές μέθοδοι πεπερασμένων στοιχείων και οι προσαρμοστικές μέθοδοι κυματοδηγών (wavelets) Galerkin. Οι τελευταίες μέθοδοι είναι ουσιαστικά πιο περίπλοκες στην εφαρμογή τους, όμως έχουν το σημαντικό πλεονέκτημα πως η χρήση τους δεν περιορίζεται σε ελλειπτικές ΜΔΕ. Κάθε καλά τοποθετημένη εξίσωση τελεστή σε έναν χώρο Hilbert, εφοδιασμένο με μια βάση τύπου Riesz, έχει ισοδύναμη διατύπωση σε μια εξίσωση (άπειρου) πίνακα επί διάνυμα. Δεδομένου ενός πεπερασμένου συνόλου δεικτών Λ ⊂ Ν, και έχοντας υπολογίσει μια (ψευδο-) καλύτερη προσέγγιση της λύσης με ένα διάνυσμα με δείκτες στο Λ, η νόρμα του διανύσματος υπολοίπου αυτής της προσέγγισης είναι ανάλογη με τη νόρμα του σφάλματός της. Προσθέτοντας αυτούς τους δείκτες του διανύσματος υπολοίπου που αντιστοιχούν στις μεγαλύτερες κατα απόλυτη τιμή καταχωρήσεις του στο σύνολο Λ δημιουργείται ένα επεκταμένο σύνολο, και ο βρόχος μπορεί να επαναληφθεί. Γενικά το αναφερόμενο διάνυσμα υπολοίπου έχει άπειρη διάσταση, και συνεπώς πρέπει να προσεγγιστεί. Αυτό το διάνυσμα υπολοίπου είναι η διαφορά του άπειρου διανύσματος και του άπειρης διάστασης πίνακα ακαμψίας εφαρμοσμένου στο τρέχον διάνυσμα προσέγγισης. Η τυπική προσέγγιση είναι να προσεγγίσουμε και τους δύο όρους ξεχωριστά, τον δεύτερο χρησιμοποιώντας τη μη γραμμική προσεγγιστική ρουτίνα πολλαπλασιασμού πίνακα-διανύσματος, γνωστής στη σχετική βιβλιογραφία ως η ρουτίνα APPLY. Σε αντίθεση με τη διαφορά τους, που είναι το διανυσματικό υπόλοιπο, οι προαναφερθέντες όροι δεν τείνουν στο μηδέν με το πέρας των επαναλήψων. Ως εκ τούτου, για να προσεγγίσουμε το υπόλοιπο εντός κάποιας σταθερής σχετικής ανοχής ακρίβειας, πρέπει να τους προσεγγίσουμε εντός μιας σχετικής ανοχής που γίνεται ολοένα και μικρότερη. Για να βελτιωθούν οι ποσοτικές ιδιότητες της προσαρμοστικής μεθόδου κυματοδιγών, το Κεφάλαιο 2 αυτής της διατριβής αφιερώνεται σε μια προσεγγιστική μέθοδο για την εκτίμηση του διανύσματος υπολοίπου χωρίς την διάσπασή του. Για να γίνει αυτό, απαιτείται η δυνατότητα αναπαράστασης και των δύο μερών του υπολοίπου σε ένα κοινό λεξικό. Στην τυπική διaδικασία, για μια μερική διαφορική εξίσωση δεύτερης τάξης και κατα τμήματα συνεχείς πολυωνυμικούς κυματοδηγούς, ο τελεστής που εφαρμόζεται σε έναν κυματοδηγό είναι μια κατανομή, και η διάσπαση δεν μπορεί να αποφευχθεί. Ως εκ τούτου, εξετάζουμε μια αναδιατύπωση μιας τέτοιας εξίσωσης ως σύστημα πρώτης τάξης με την εισαγωγή της ροής ως ξεχωριστή άγνωστη μεταβλητή. Δείχνουμε ότι κάθε καλά τοποθετημένη ημι-γραμμική ΜΔΕ δεύτερης τάξης επιτρέπει μια αναδιατύπωση ως καλά ορισμένο πρόβλημα ελαχίστων τετραγώνων συστήματος πρώτης τάξης (FOSLS). Για ένα τέτοιο σύστημα σχεδιάζουμε μια εναλλακτική, πιο αποδοτική μέθοδο προσέγγισης της αξιολόγησης του υπολοίπου, η οποία, σε περίπτωση μιας γραμμικής ΜΔΕ, εξαρτάται γραμμικά από την τρέχουσα προσέγγιση. Στο Κεφάλαιο 4 εφαρμόζουμε αυτό το μηχανισμό σε παραβολικές εξελικτικές ΜΔΕ σε μια ταυτόχρονη χωρό-χρονική μεταβολική διατύπωση. Τα τελευταία χρόνια, παρατηρείται αυξανόμενο ενδιαφέρον για τέτοιες διατυπώσεις ως εναλλακτική για τα συνήθη πολυβηματικά σχήματα στο χρόνο που είναι από φύση τους σειριακά και δεν είναι κατάλληλα για την αποδοτική προσέγγιση των ανωμαλιών της λύσης που είναι τοπικές τόσο στον χώρο όσο και στον χρόνο. Οι χώροι Hilbert που προκύπτουν σε αυτή τη διατύπωση είναι χώροι τύπου Bochner που εξοπλίζονται φυσικά με βάσεις τύπου Riesz που είναι τανυστικά γινόμενα χρονικών και χωρικών βάσεων κυματοδηγών. Αυτές οι βάσεις κυματοδηγών τανυστικού γινομένου απαιτούν μια τροποποιημένη, πιο περίπλοκη διαδικασία για την προσεγγιστική αξιολόγηση του υπολοίπου, καθώς δεν είναι δυνατή μια μετατροπή σε μια τοπικά μοναδική αναπαράσταση μιας κλίμακας. Από την άλλη πλευρά, παρέχουν το μεγάλο πλεονέκτημα μιας αποτελεσματικής μείωσης της διάστασης γνωστή από τις μεθόδους αραιού πλέγματος (sparse-grids) σε ένα μη προσαρμοστικό πλαίσιο. Θα είμαστε σε θέση να λύσουμε ολόκληρo το χωρο-χρονικό πρόβλημα με πολυπλοκότητα ίση με αυτή της επίλυσης ενός στατικού προβλήματος. Για την εκτέλεση της προσαρμοστικής μεθόδου κυματοδηγών Galerkin, χρειάζονται βάσεις κυματοδηγών για τα γενικά μη τετράγωνα χωρία στα οποία ορίζονται οι εξισώσεις. Είναι γνωστές αρκετές κατασκευές κατα τμήματα συνεχών γραμμικών κυματοδηγών σε γενικά πολυγωνικά ή πολυεδρικά χωρία. Λόγω της διατύπωσης FOSLS που χρησιμοποιούμε, χρειαζόμαστε επιπλέον μια βάση τύπου Riesz κυματοδηγών αποτελούμενη από κατα τμήματα τετραγωνικές συναρτήσεις. Τέτοιες βάσεις κατασκευάζονται στο Κεφάλαιο 3. Τέλος, στο Κεφάλαιο 5 παρέχονται λεπτομέρειες για διάφορες πτυχές της υλοποίησης των αλγορίθμων που έχουμε αναπτύξει.