Επαναληπτικές μέθοδοι για την αριθμητική επίλυση γραμμικών συστημάτων

Abstract

The objective of this thesis is the design and analysis of iterative methods for the numerical solution of large and sparse linear systems. This type of systems emerge from the discretization of Partial Differential Equations. Two special categories of linear systems are studied. The first category contains systems whose coefficient matrix is two cyclic whereas the second category includes the augmented linear systems. Initially, the Preconditioned Simultaneous Displacement (PSD) method is studied when the Jacobi iteration matrix is weakly cyclic and its eigenvalues are all real "real case" or all imaginary "imaginary case". It is proved that the PSD method has better convergence rate than the SSOR method. In particular, in the "imaginary case" its convergence is increased by an order of magnitude. In an attempt to further increase the convergence rate of the PSD method, more parameters were introduced. The new method is called the Modified PSD (MPSD) method. Under the same assumptions the convergence of the MPSD method is studied. It is shown that the optimum MPSD method is equivalent to the optimum MSOR method. Furthermore, it is studied the convergence analysis of the Generalized Modified Extrapolated SOR (GMESOR) and Generalized Modified Preconditioned Simultaneous Displacement (GMPSD) methods for the numerical solution of the augmented linear systems. The main result of our analysis is that both methods have the same rate of convergence and less complexity than the Preconditioned Conjugate Gradient (PCG) method. The last result is important since it proves that the addition of parameters in an iterative method incurs the same increase in the rate of convergence as that of the Conjugate Gradient (CG) method which belongs to the Krylov subspace methods.

Ο αντικειμενικός σκοπός της διδακτορικής διατριβής αφορά τον σχεδιασμό και την ανάλυση επαναληπτικών μεθόδων για την αριθμητική επίλυση μεγάλων και αραιών γραμμικών συστημάτων. Συστήματα με αυτά τα χαρακτηριστικά προκύπτουν από τη διακριτοποίηση Μερικών Dιαφορικών Εξισώσεων. Μελετώνται δύο ειδικές κατηγορίες συστημάτων. Η πρώτη κατηγορία περιλαμβάνει συστήματα των οποίων ο πίνακας συντελεστών των αγνώστων είναι δικυκλικός ενώ ή δεύτερη περιέχει τα επαυξημένα (augmented) συστήματα. Στη διδακτορική διατριβή μελετάται αρχικά η σύγκλιση της Preconditioned Simultaneous Displacement (PSD) μεθόδου, όταν ο επαναληπτικός πίνακας Jacobi είναι ασθενά κυκλικός με τις ιδιοτιμές του να είναι είτε όλες πραγματικές ¨πραγματική περίπτωση¨ είτε όλες Φανταστικές ¨φανταστική περίπτωση¨ και αποδεικνύεται ότι η ταχύτητα σύγκλισής της είναι μεγαλύτερη από εκείνη της SSOR μεθόδου. Ειδικά στη ¨φανταστική περίπτωση¨ η σύγκλισή της βελτιώνεται κατά μια τάξη μεγέθους. Σε μια προσπάθεια περαιτέρω αύξησης της ταχύτητας σύγκλισης της PSD μεθόδου, εισήχθησαν περισσότερες παράμετροι. Η νέα μέθοδος που δημιουργήθηκε ονομάστηκε Modified PSD (MPSD). Κάτω από τις ίδιες υποθέσεις μελετήθηκε η σύγκλιση της MPSD μεθόδου. Το κύριο αποτέλεσμα της ανάλυσης αυτής είναι ότι η MPSD μέθοδος καθίσταται ισοδύναμη με την Modified SOR (MSOR) μέθοδο για τις βέλτιστες τιμές των παραμέτρων τους. Επίσης, μελετάται η ανάλυση σύγκλισης των Generalized Modified Extrapolated SOR (GMESOR) και Generalized Modified Preconditioned Simultaneous Displacement (GMPSD) μεθόδων για την αριθμητική επίλυση επαυξημένων γραμμικών συστημάτων. Το κύριο αποτέλεσμα της ανάλυσης αυτής είναι ότι οι ανωτέρω μέθοδοι έχουν την ίδια ταχύτητα σύγκλισης και μικρότερη πολυπλοκότητα από την Preconditioned Conjugate Gradient (PCG) μέθοδο. Το τελευταίο αυτό αποτέλεσμα είναι σημαντικό διότι αποδεικνύει ότι η εισαγωγή παραμέτρων σε μια επαναληπτική μέθοδο επιφέρει την ίδια αύξηση της ταχύτητας σύγκλισης με την Conjugate Gradient (CG) μέθοδο, η οποία ανήκει στην κατηγορία των μεθόδων Krylov.