Μέθοδοι υποχώρων krylov για την επίλυση γραμμικών συστημάτων Toeplitz

Abstract

In this thesis we study the preconditioning of square, non-symmetric and real Toeplitz systems. We prove theoretical results, which constitute sufficient conditions for the efficiency of the proposed preconditioners and the fast convergence to the solution of the system, by the Preconditioned Generalized Minimal Residual method (PGMRES) as well as by the Preconditioned Conjugate Gradient method applied to the system of Normal Equations (PCGN).As introduction, in the first chapter, we give the basic definitions and theorems/lemmas that we use to prove the theoretical results of the thesis. These are dealing with the clustering of the eigenvalues, as well as of the singular values, which is a criterion for the efficiency of the preconditioner.In the second chapter we construct a band Toeplitz preconditioner for well-conditioned, as well as for ill-conditioned systems. The preconditioning technique is based on the elimination of the roots of the generating function (if there exist), by a trigonometric polynomial, and on a further approximation. The clustering of the eigenvalues and the singular values of the preconditioned system has been proven.In the next chapter we construct a circulant preconditioner dealing with well-conditioned Toeplitz systems and a band-times-circulant preconditioner for ill-conditioned ones. We prove analogous theoretical results and we give a comparison with the preconditioner proposed previously at the numerical results of the last section.In the fourth and last chapter of the thesis we study Toeplitz systems, having an unknown generating function. We adapt the preconditioners constructed at the previous chapters. After estimating the generating function, its roots and the multiplicities of them, we construct the corresponding preconditioners.

Στην παρούσα διδακτορική διατριβή γίνεται μελέτη της προρρύθμισης τετραγωνικών, μη-συμμετρικών και πραγματικών συστημάτων Toeplitz. Αποδεικνύονται θεωρητικά αποτελέσματα, τα οποία αποτελούν ικανές συνθήκες για την αποτελεσματικότητα των προτεινόμενων προρρυθμιστών και την ταχεία σύγκλιση στη λύση του συστήματος, με μεθόδους όπως η Προρρυθμισμένη Γενικευμένη μέθοδος Ελαχίστων Υπολοίπων (PGMRES) και η Προρρυθμισμένη μέθοδος Συζυγών Κλίσεων για το σύστημα των Κανονικών Εξισώσεων (PCGN).Στο πρώτο κεφάλαιο παραθέτουμε βασικές εισαγωγικές έννοιες, ορισμούς και θεωρητικά αποτελέσματα, τα οποία χρησιμοποιήσαμε για να αποδείξουμε τα θεωρητικά αποτελέσματα της διατριβής. Αυτά έχουν να κάνουν κυρίως με τη συσσώρευση του φάσματος, αλλά και των ιδιαζουσών τιμών, αφού αυτή αποτελεί κριτήριο για το πόσο αποτελεσματικός είναι κάποιος προρρυθμιστής.Στο δεύτερο κεφάλαιο κατασκευάζουμε έναν ταινιωτό Toeplitz προρρυθμιστή, για συστήματα με καλή, αλλά και κακή κατάσταση. Η τεχνική προρρύθμισης βασίζεται στην εύρεση ενός κατάλληλου τριγωνομετρικού πολυωνύμου για την άρση των ριζών της γεννήτριας συνάρτησης (αν υπάρχουν), σε συνδυασμό με προσέγγιση από κάποιο άλλο τριγωνομετρικό πολυώνυμο. Αποδείχθηκε η συσσώρευση των ιδιοτιμών, καθώς και των ιδιαζουσών τιμών του προρρυθμισμένου συστήματος.Στο τρίτο κεφάλαιο κατασκευάζουμε έναν κυκλοειδή (circulant) προρρυθμιστή για συστήματα Toeplitz με καλή κατάσταση, καθώς κι έναν ταινιωτό-επί-κυκλοειδή (band-times-circulant) προρρυθμιστή για συστήματα με κακή κατάσταση. Αποδεικνύονται αντίστοιχα θεωρητικά αποτελέσματα, ενώ γίνεται και σύγκριση με τον προρρυθμιστή του προηγούμενου κεφαλαίου στα αριθμητικά αποτελέσματα, της τελευταίας ενότητας.Στο τέταρτο και τελευταίο κεφάλαιο της διατριβής μελετάμε συστήματα Toeplitz, των οποίων η γεννήτρια συνάρτηση υπάρχει, αλλά δεν είναι γνωστή εκ των προτέρων. Γίνεται κατάλληλη προσαρμογή των προρρυθμιστών που κατασκευάστηκαν στα προηγούμενα κεφάλαια. Με τεχνικές εκτίμησης της γεννήτριας συνάρτησης, των ριζών αυτής και της πολλαπλότητας των εν λόγω ριζών, κατασκευάζουμε αντίστοιχους προρρυθμιστές.