Μέθοδοι υποχώρων krylov για την επίλυση γραμμικών συστημάτων Toeplitz
Loading...
Date
Authors
Ταχυρίδης, Γρηγόριος
Journal Title
Journal ISSN
Volume Title
Publisher
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Abstract
Type
Type of the conference item
Journal type
Educational material type
Conference Name
Journal name
Book name
Book series
Book edition
Alternative title / Subtitle
Description
Στην παρούσα διδακτορική διατριβή γίνεται μελέτη της προρρύθμισης τετραγωνικών, μη-συμμετρικών και πραγματικών συστημάτων Toeplitz. Αποδεικνύονται θεωρητικά αποτελέσματα, τα οποία αποτελούν ικανές συνθήκες για την αποτελεσματικότητα των προτεινόμενων προρρυθμιστών και την ταχεία σύγκλιση στη λύση του συστήματος, με μεθόδους όπως η Προρρυθμισμένη Γενικευμένη μέθοδος Ελαχίστων Υπολοίπων (PGMRES) και η Προρρυθμισμένη μέθοδος Συζυγών Κλίσεων για το σύστημα των Κανονικών Εξισώσεων (PCGN).Στο πρώτο κεφάλαιο παραθέτουμε βασικές εισαγωγικές έννοιες, ορισμούς και θεωρητικά αποτελέσματα, τα οποία χρησιμοποιήσαμε για να αποδείξουμε τα θεωρητικά αποτελέσματα της διατριβής. Αυτά έχουν να κάνουν κυρίως με τη συσσώρευση του φάσματος, αλλά και των ιδιαζουσών τιμών, αφού αυτή αποτελεί κριτήριο για το πόσο αποτελεσματικός είναι κάποιος προρρυθμιστής.Στο δεύτερο κεφάλαιο κατασκευάζουμε έναν ταινιωτό Toeplitz προρρυθμιστή, για συστήματα με καλή, αλλά και κακή κατάσταση. Η τεχνική προρρύθμισης βασίζεται στην εύρεση ενός κατάλληλου τριγωνομετρικού πολυωνύμου για την άρση των ριζών της γεννήτριας συνάρτησης (αν υπάρχουν), σε συνδυασμό με προσέγγιση από κάποιο άλλο τριγωνομετρικό πολυώνυμο. Αποδείχθηκε η συσσώρευση των ιδιοτιμών, καθώς και των ιδιαζουσών τιμών του προρρυθμισμένου συστήματος.Στο τρίτο κεφάλαιο κατασκευάζουμε έναν κυκλοειδή (circulant) προρρυθμιστή για συστήματα Toeplitz με καλή κατάσταση, καθώς κι έναν ταινιωτό-επί-κυκλοειδή (band-times-circulant) προρρυθμιστή για συστήματα με κακή κατάσταση. Αποδεικνύονται αντίστοιχα θεωρητικά αποτελέσματα, ενώ γίνεται και σύγκριση με τον προρρυθμιστή του προηγούμενου κεφαλαίου στα αριθμητικά αποτελέσματα, της τελευταίας ενότητας.Στο τέταρτο και τελευταίο κεφάλαιο της διατριβής μελετάμε συστήματα Toeplitz, των οποίων η γεννήτρια συνάρτηση υπάρχει, αλλά δεν είναι γνωστή εκ των προτέρων. Γίνεται κατάλληλη προσαρμογή των προρρυθμιστών που κατασκευάστηκαν στα προηγούμενα κεφάλαια. Με τεχνικές εκτίμησης της γεννήτριας συνάρτησης, των ριζών αυτής και της πολλαπλότητας των εν λόγω ριζών, κατασκευάζουμε αντίστοιχους προρρυθμιστές.
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.
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.
Description
Keywords
Προρρύθμιση, Δομημένοι πίνακες, Μη-συμμετρικά συστήματα
Subject classification
Γραμμικά συστήματα
Citation
Link
Language
el
Publishing department/division
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Advisor name
Νούτσος, Δημήτριος
Examining committee
Νούτσος, Δημήτριος
Γαλλόπουλος, Ευστράτιος
Βασσάλος, Παρασκευάς
Βραχάτης, Μιχαήλ
Καρακατσάνη, Φωτεινή
Τσατσόμοιρος, Μιχαήλ
Ψαρράκος, Παναγιώτης
Γαλλόπουλος, Ευστράτιος
Βασσάλος, Παρασκευάς
Βραχάτης, Μιχαήλ
Καρακατσάνη, Φωτεινή
Τσατσόμοιρος, Μιχαήλ
Ψαρράκος, Παναγιώτης
General Description / Additional Comments
Institution and School/Department of submitter
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Table of contents
Sponsor
Bibliographic citation
Βιβλιογραφία: σ. 127-134
Name(s) of contributor(s)
Number of Pages
134 σ.
Course details
Collections
Endorsement
Review
Supplemented By
Referenced By
Creative Commons license
Except where otherwised noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 United States