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

Abstract

In this dissertation the problem of finding reliably and with certainty all the zeros a parameterized equation f(x,fp1) = 0, of a continuously differentiate function f is considered, where [p] is an interval vector describing all the parameters of the Equation, which are formed with interval numbers. For this kind of problem, methods of Interval Analysis are used. The incentive to this scientific research was emerged from a classic numerical analysis problem the numerical solution of polynomial systems of equations using interval analysis In particular, a heuristic reordering technique of the initial polynomial systems of equations is proposed. This approach seems to improve significantly the used solver. The proposed technique, as well as the results of this publication are presented in Chapter 2 of this dissertation. In the next Chapter 3, a methodology is proposed for solving reliably and efficiently parameterized (interval) equations. Firstly, a new formulation of interval arithmetic is given and the equivalence with the classic one is proved. Then, an extension of interval Newton method is proposed and developed, based on the new formulation of interval arithmetic. The new method is able to solve not only classic non-linear equations but, non-linear parameterised (interval) equation too. In Chapter 4 a new approach on solving the Box Constrained Global Optimization problem is proposed, based on the results of Chapter 3. In details, the Box Constrained Global Optimization problem is reduced to a problem of solving interval equations. The solution of this reduction is attainable through the methodology developed in Chapter 3. In the last Chapter of this dissertation a new algorithmic approach is given for the problem of solving reliably and with certainty an interval polynomial equation of degree $n$. This approach consists in a generalization of the work of Hansen and Walster. Hansen and Walster proposed a method for solving only quadratic interval polynomial equations.

Η παρούσα διδακτορική διατριβή πραγματεύεται το θέμα της αποδοτικής και με βεβαιότητα εύρεσης όλων των ριζών της παραμετρικής εξίσωσης f(x,fp1) = 0, μιας συνεχώς διαφορίσιμης συνάρτησης f με [ρ] ένα διάνυσμα που περιγράφει όλες τις παραμέτρους της παραμετρικής εξίσωσης και τυποποιούνται με τη μορφή διαστημάτων. Για την επίλυση αυτού του προβλήματος χρησιμοποιήθηκαν εργαλεία της Διαστηματικής Ανάλυσης. Το κίνητρο για την ερευνητική ενασχόληση με το παραπάνω πρόβλημα προέκυψε μέσα από ένα κλασσικό πρόβλημα αριθμητικής ανάλυσης: την αριθμητική επίλυση σύστημα των πολυωνυμικών εξισώσεων μέσω διαστηματικής ανάλυσης. Πιο συγκεκριμένα, προτάθηκε μια ευρετική τεχνική αναδιάταξης του αρχικού πολυωνυμικού συστήματος που φαίνεται να βελτιώνει σημαντικά, κάθε φορά, τον χρησιμοποιούμενο επιλυτή. Η ανάπτυξη, καθώς και τα αποτελέσματα αυτής της εργασίας αποτυπώνονται στο Κεφάλαιο 2 της παρούσας διατριβής. Στο επόμενο Κεφάλαιο 3, προτείνεται μια μεθοδολογία για την αποδοτική και αξιόπιστη επίλυση μη γραμμικών εξισώσεων με διαστηματικές παραμέτρους, δηλαδή την αποδοτική και αξιόπιστη επίλυση διαστηματικών εξισώσεων. Πρώτα, δίνεται μια νέα διατύπωση της Διαστηματικής Αριθμητικής και αποδεικνύεται η ισοδυναμία της με τον κλασσικό ορισμό. Στη συνέχεια, χρησιμοποιείται η νέα διατύπωση της Διαστηματικής Αριθμητικής ως θεωρητικό εργαλείο για την ανάπτυξη μιας επέκτασης της διαστηματικής μεθόδου Newton που δύναται να επιλύσει όχι μόνο κλασσικές μη παραμετρικές μη γραμμικές εξισώσεις, άλλα και παραμετρικές (διαστηματικές) μη γραμμικές εξισώσεις. Στο Κεφάλαιο 4 προτείνεται μια νέα προσέγγιση για την αριθμητική επίλυση του προβλήματος της Ολικής Βελτιστοποίησης με περιορισμούς διαστήματα, χρησιμοποιώντας τα αποτελέσματα του Κεφαλαίου 3. Το πρόβλημα της ολικής βελτιστοποίησης, ανάγεται σε πρόβλημα επίλυσης διαστηματικών εξισώσεων, και γίνεται εφικτή η επίλυσή του με τη βοήθεια των θεωρητικών αποτελεσμάτων και της αντίστοιχης μεθοδολογίας του Κεφαλαίου 3. Στο τελευταίο Κεφάλαιο δίνεται μια νέα αλγοριθμική προσέγγιση για το πρόβλημα της επίλυσης διαστηματικών πολυωνυμικών εξισώσεων. Η νέα αυτή προσέγγιση, βασίζεται και γενικεύει την εργασία των Hansen και Walster, οι οποίοι πρότειναν μια μέθοδο για την επίλυση διαστηματικών πολυωνυμικών εξισώσεων 2ου βαθμού.