Ανάπτυξη υπολογιστικών μεθόδων για την επίλυση προβλημάτων της θεωρίας ελέγχου

Abstract

The purpose of this thesis is the development of computational methods for solving problems of Control Theory. The computational method evaluation-interpolation enables us to solve several Control Theory problems. The advantage of the method evaluation-interpolation against analytical solutions of the corresponding problems is the use of numerical analysis (interpolation) through which the problems that arise in the analytical solutions are avoided i.e. many complex operations, inability to resolve etc. In many Control Theory problems the solution is one or more two-variable polynomials (e.g. calculation of the determinant of a two-variable polynomial matrix, calculation of the inverse of a two-variable polynomial matrix, calculation of the greatest common divisor of two-variable polynomials, etc.). With the method evaluation-interpolation we can compute these polynomials. This thesis is focused on the analysis of the two-variable Newton polynomialinterpolation method, the programming implementation of the method and also in finding methods to minimize the computations. Specifically, in the first chapter the basic concepts of polynomial interpolation of functions of one and two variables are presented. In the second chapter new recursive types and corresponding algorithms for the implementation of Newton polynomial interpolation method are introduced. Additionally, we propose a new basis for calculating polynomial interpolation. In the third chapter, the implementation of programming algorithms and their comparison regarding the execution times and the tolerance in arithmetic precision are illustrated. In the fourth chapter we present a theoretical approach of the algorithms with parallel processing techniques. Finally, in the fifth chapter new computational methods that incorporate the proposed algorithms and technique evaluation-interpolation to solve Control Theory problems are developed.

Αντικείμενο της παρούσας διατριβής αποτελεί η ανάπτυξη υπολογιστικών μεθόδων για την επίλυση προβλημάτων της θεωρίας ελέγχου. Η υπολογιστική μέθοδος υπολογισμού-παρεμβολής (evaluation-interpolation) μας δίνει τη δυνατότητα να επιλύσουμε αρκετά προβλήματα της θεωρίας ελέγχου. Το πλεονέκτημα της μεθόδου υπολογισμού-παρεμβολής έναντι των αναλυτικών λύσεων των αντίστοιχων προβλημάτων είναι η χρήση της αριθμητικής ανάλυσης (παρεμβολή) μέσω της οποίας αποφεύγουμε τα προβλήματα που προκύπτουν στις αναλυτικές λύσεις δηλαδή, πολλές και σύνθετες πράξεις, αδυναμία επίλυσης κ.α. Σε αρκετά προβλήματα της θεωρίας ελέγχου η λύση είναι ένα ή περισσότερα πολυώνυμα δυο μεταβλητών (π.χ. υπολογισμός ορίζουσας πολυωνυμικού πίνακα δυο μεταβλητών, υπολογισμός αντίστροφου πολυωνυμικού πίνακα δυο μεταβλητών, υπολογισμός μέγιστου κοινού διαιρέτη πολυωνύμων δύο μεταβλητών κ.α.). Με την μέθοδο υπολογισμού-παρεμβολής έχουμε τη δυνατότητα να υπολογίσουμε τα συγκεκριμένα πολυώνυμα. Στα πλαίσια της διατριβής επικεντρωθήκαμε στην ανάλυση της πολυωνυμικής παρεμβολής με τη μέθοδο Newton, στην προγραμματιστική υλοποίηση της μεθόδου και παράλληλα στην εύρεση μεθόδων για την ελαχιστοποίηση των υπολογισμών. Αναλυτικότερα, στο πρώτο κεφάλαιο αναφέρονται εισαγωγικές έννοιες της πολυωνυμικής παρεμβολής συναρτήσεων μιας και δύο μεταβλητών. Στο δεύτερο κεφάλαιο προτείνονται νέοι αναδρομικοί τύποι και οι αντίστοιχοι αλγόριθμοι για την υλοποίηση της πολυωνυμικής παρεμβολής με τη μέθοδο Newton. Επίσης, προτείνεται και μια νέα βάση υπολογισμού πολυωνύμου παρεμβολής. Στο τρίτο κεφάλαιο παρουσιάζεται η προγραμματιστική υλοποίηση των αλγορίθμων καθώς επίσης και η σύγκρισή τους ως προς τον χρόνο εκτέλεσης και την αριθμητική ακρίβεια. Στο τέταρτο κεφάλαιο παρουσιάζεται μια θεωρητική προσέγγιση των αλγορίθμων με τεχνικές παράλληλης επεξεργασίας. Τέλος, στο πέμπτο κεφάλαιο αναπτύσσονται νέες υπολογιστικές μέθοδοι που ενσωματώνουν τους προτεινόμενους αλγορίθμους και την τεχνική υπολογισμού-παρεμβολής για την επίλυση προβλημάτων της θεωρίας ελέγχου.