Spectral analysis and preconditioned iterative solvers for large structured linear systems

Abstract

In this thesis, the numerical solution of three different classes of problems have been studied. Specifically, new techniques have been proposed and their theoretical analysis has been performed, accompanied by a wide set of numerical experiments, for investigating further and comparing the effectiveness and performance of the presented approach. The first two belong to the research area of numerical linear algebra and concern the spectral analysis and preconditioning for Krylov subspace methods of the coefficient matrix of large structured linear systems. The third concerns a problem from the area of financial computing namely the pricing of an American put option.In the first set of problems, the asymptotic spectra of large matrices coming from the summarization of Toeplitz structure functions was studied. The spectral asymptotic behavior of this matrix sequences was provided analytically. Taking advantage of this analysis circulant preconditioners were proposed, and the eigenvalue distribution of the preconditioned matrix sequences was given. All theoretical results were numerically confirmed. The second problem that was studied concerns the theoretical and numerical exploration of proper preconditioners based on the spectral symbols of the coefficient matrix arising from the discretization of Fractional order Differential Equations problems. Beside the theoretical study, a comparison between the already propose in the literature techniques was conducted. The numerical experiments show that in the one dimensional case, the proposed preconditioners perform similarly with the best known techniques for this problem. However, in the challenging and more interesting for the applications multivariate setting the proposed preconditioners show their superiority against all the competitors.For the pricing of an American put option an iterative algorithm based on the theory of dynamic programming was proposed. Taking advantage of the already known characteristics of the optimal value function it was proved theoretically and numerically confirmed that the proposed algorithm obtains monotonically increasing value functions and converges to the optimal one.

Στην παρούσα διδακτορική διατριβή εξετάζεται η αριθμητική επίλυση για τρεις κατηγορίες προβλημάτων. Για τα προβλήματα αυτά, προτείνονται νέες τεχνικές επίλυσης μαζί με την θεωρητική τους ανάλυση και την αριθμητική τους επιβεβαίωση μέσω αριθμητικών πειραμάτων. Οι δύο πρώτες κατηγορίες είναι από το ερευνητικό πεδίο της αριθμητικής γραμμικής άλγεβρας και αφορούν την φασματική ανάλυση με εφαρμογές στην προρρύθμιση μεθόδων υποχώρων Krylov, των συντελεστών πινάκων, μεγάλων δομημένων γραμμικών συστημάτων. Η τρίτη κατηγορία είναι από το πεδίο των υπολογιστικών οικονομικών και αφορά το πρόβλημα της αποτίμησης ενός Αμερικανικού δικαιώματος (American put option).Στην πρώτη κατηγορία προβλημάτων εξετάζεται η ασυμπτωτική φασματική κατανομή μεγάλων πινάκων που προκύπτουν ως συναρτήσεις πινάκων Toeplitz. Συγκεκριμένα χαρακτηρίζεται αναλυτικά η συνάρτηση που περιγράφει την κατανομή των ιδιοτιμών. Λαμβάνοντας υπόψη την συνάρτηση αυτή προτείνονται κυκλοειδείς (circulant) προρρυθμιστές και αποδεικνύεται αναλυτικά η κατανομή των ιδιοτιμών των προρρυθμισμένων πινάκων. Όλα τα θεωρητικά αποτελέσματα επιβεβαιώνονται αριθμητικά.Η δεύτερη κατηγορία αφορά την θεωρητική και αριθμητική διερεύνηση κατάλληλων προρρυθμιστών, βασισμένων στο φασματικό σύμβολο, συντελεστών πινάκων που παράγονται από την διακριτοποίηση κλασματικών διαφορικών εξισώσεων (Fractional Differential Equations). Πέρα από την θεωρητική ανάλυση γίνεται και αριθμητική σύγκριση μεταξύ των προτεινόμενων προρρυθμιστών με τις υπάρχουσες τεχνικές επίλυσης. Τα αριθμητικά πειράματα δείχνουν η μέθοδος να είναι της ίδιας δυναμικής με τις υπάρχουσες αποδοτικότερες μεθόδους της διεθνούς βιβλιογραφίας αλλά να υπερτερεί εμφανώς στην πιο ενδιαφέρουσα από πλευράς εφαρμογών περίπτωση όπου η χωρική μεταβλητή είναι δυο διαστάσεων. Για την αποτίμηση του Αμερικανικού δικαιώματος χρησιμοποιούμε την τεχνική του δυναμικού προγραμματισμού κατάλληλα τροποοποιημένη για το συγκεκριμένο πρόβλημα. Χρησιμοποιώντας γνωστά χαρακτηριστικά της βέλτιστης συνάρτησης αποτίμησης του δικαιώματος, αποδεικνύεται θεωρητικά και επιβεβαιώνεται αριθμητικά ότι ο προτεινόμενος επαναληπτικός αλγόριθμος επιτυγχάνει μια αύξουσα ακολουθία συναρτήσεων αποτίμησης και εντέλει συγκλίνει με τετραγωνική τάξη στην βέλτιστη λύση. Αριθμητικά πειράματα δείχνουν την αποδοτικότητα της μεθόδου.