Ξεχάσατε τον κωδικό σας?
Διαδοχική Παρεμβολή Παραβολών
Document Actions
Next: Μέθοδος Up: ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ ΣΕ ΜΙΑ ΔΙΑΣΤΑΣΗ Previous: Έρευνα για Χρυσή Τομή Contents
Διαδοχική Παρεμβολή Παραβολών
Όπως και κατά τη διχοτόμηση για την επίλυση μη γραμμικών εξισώσεων, η έρευνα για χρυσή τομή δε χρησιμοποιεί τις αριθμητικές τιμές της συνάρτησης για άλλο λόγο παρά μόνο για να τις συγκρίνει, οπότε θα μπορούσε κάποιος να εικάζεται ότι με το να χρησιμοποιούμε πιο πολύ τις τιμές της συνάρτησης θα οδηγούμασταν σε πιο γρήγορες μεθόδους. Πράγματι, όπως και κατά την επίλυση μη γραμμικών εξισώσεων, μπορούμε να πετύχουμε μεγαλύτερη σύγκληση με το να αντικαταστήσουμε τοπικά την συνάρτηση κόστους με μία απλή συνάρτηση της οποίας οι τιμές ταιριάζουν σε κάποια δειγματικά σημεία.
Ένα παράδειγμα αυτής της προσέγγισης είναι η διαδοχική παρεμβολή παραβολών. Αρχικά, η συνάρτηση εκτιμάται σε τρία σημεία και ένα πολυώνυμο δευτέρου βαθμού προσαρμόζεται στις τρεις τιμές που παίρνουμε. Το ελάχιστο της παραβολής, αν έχει ελάχιστο, το παίρνουμε ως μία νέα εκτίμηση για το ελάχιστο της συνάρτησης. Στη συνέχεια αυτό το νέο σημείο αντικαθιστά το πιο παλιό από τα τρία προηγούμενα σημεία και η διαδικασία επαναλαμβάνεται ως που να επιτευχθεί η σύγκλιση. Αυτή η διαδικασία παρουσιάζεται στο Σχήμα 6.3. Η διαδοχική παρεμβολή παραβολών είναι πιο ριψοκίνδυνη από την έρευνα χρυσών τομών, αφού δεν διατηρείται απαραίτητα σε ένα περιορισμένο διάστημα στο οποίο ξέρουμε ότι βρίσκεται η λύση, αλλά συγκλίνει ασυμπτωτικά υπεργραμμικα με βαθμό σύγκλισης 1263#1263.
Εκτιμούμε τη συνάρτηση σε τρία σημεία, ας πούμε, 1265#1265, και 1266#1266, παίρνοντας 1267#1267. Προσαρμόζουμε την παραβολή σε αυτά τα τρία σημεία και παίρνουμε το στοιχείο για το οποίο γίνεται ελάχιστη, 1268#1268, ως την επόμενη προσέγγιση στη λύση. Στη συνέχεια απορρίπτουμε το 1092#1092 και επαναλαμβάνουμε την διαδικασία με τα στοιχεία που απομένουν. Η πρώτη επανάληψη αναπαριστάνεται στο σχήμα 6.4, και η πλήρης διαδοχή των επαναλήψεων δίνεται αμέσως μετά.
Manolis Vavalis 2000-03-24
