Έρευνα για Χρυσή Τομή

Θεωρείστε ότι η 51#51 είναι μία συνάρτηση πραγματικών τιμών που έχει ένα μόνο μέγιστο στο διάστημα 1060#1060. Έστω ότι τα 1183#1183 και 426#426 είναι δύο σημεία μέσα στο διάστημα, με 1227#1227. Η σύγκριση των τιμών 1228#1228 και 1229#1229 της συνάρτησης και η χρήση της ιδιότητάς της να έχει μοναδικό μέγιστο θα μας επιτρέψουν να απορρίψουμε ένα υποδιάστημα, είτε το 1230#1230 είτε το 1231#1231, και να ξέρουμε ότι το ελάχιστο της συνάρτησης βρίσκεται μέσα στο υποδιάστημα που απομένει. Πιο συγκεκριμένα, αν 1232#1232, τότε το ελάχιστο δεν μπορεί να βρίσκεται στο διάστημα 1233#1233. Και αν 1232#1232, τότε το ελάχιστο δε μπορεί να βρίσκεται στο διάστημα 1234#1234. ’ρα, έχουμε μείνει με ένα μικρότερο διάστημα, είτε το 1235#1235 είτε το 1236#1236, αντίστοιχα. Επομένως, θα χρειαστεί να υπολογίσουμε μόνο μία νέα αποτίμηση της συνάρτησης για να επαναλάβουμε αυτή τη διαδικασία.

Για να πετύχουμε μία αντίστοιχη πρόοδο στη μείωση της έκτασης του διαστήματος που περιέχει το ελάχιστο, θα θέλαμε για κάθε νέο ζεύγος στοιχείων να έχουν την ίδια σχέση με το νέο διάστημα που είχε και το προηγούμενο ζεύγος με το προηγούμενο διάστημα. Μία τέτοια συμφωνία θα μας επιτρέπει να μειώνουμε την έκταση του διαστήματος κατά ένα σταθερό κλάσμα σε κάθε επανάληψη, σε μεγάλο βαθμό όπως μειώνουμε στο μισό σε κάθε επανάληψη το μήκος, κατά τη μέθοδο διχοτόμισης για τον υπολογισμό των ριζών των συναρτήσεων.

Για να πετύχουμε αυτό το στόχο, επιλέγουμε τις σχετικές θέσεις δύο σημείων όπως τ και 1 - τ, όπου 1237#1237, έτσι ώστε 1238#1238 και 1239#1239. Με αυτή την επιλογή, ανεξάρτητα από το ποιό υποδιάστημα έχει απομείνει, η έκτασή του θα σχετίζεται με το προηγούμενο διάστημα σε ένα πεδίο τ, και το εσωτερικό σημείο που απομένει θα σχετίζεται με το νέο διάστημα σε ένα πεδίο τ ή 1 - τ. Aρα, πρέπει να υπολογίσουμε μόνο μία νέα τιμή της συνάρτησης, στο συμπληρωματικό σημείο, για να συνεχίσουμε την επανάληψη. Αυτή η επιλογή των δειγματοληπτικών σημείων λέγεται έρευνα για χρυσή τομή. Ο πλήρης αλγόριθμος είναι αυτός που ακολουθεί:

Αρχική είσοδος: μία συνάρτηση 51#51, ένα διάστημα 1060#1060 στο οποίο η 51#51 έχει μοναδικό μέγιστο, και μία ανεκτικότητα στα σφάλματα tol.

 		 1240#1240


1241#1241


1242#1242


1243#1243


1244#1244


1245#1245


1246#1246


1247#1247


1248#1248


1249#1249


1243#1243


1244#1244


1072#1072


1250#1250


1251#1251


1252#1252


1241#1241


1242#1242


849#849


849#849

Η έρευνα για χρυσή τομή είναι ασφαλής αλλά αργά συγκλίνουσα. Πιο συγκεκριμένα, είναι γραμμικά συγκλίνουσα, με 1054#1054 και 1253#1253.

Παρόλο που η ιδιότητα μίας συνάρτησης να έχει μοναδικό μέγιστο παίζει κάποιο ρόλο στην βελτιστοποίηση ανάλογα με το ρόλο που παίζει μία αλλαγή προσήμου στην εύρεση ριζών, υπάρχουν σημαντικές διαφορές στην πράξη. Μία αλλαγή στο πρόσημο περιορίζει τη ρίζα μίας εξίσωσης ανεξάρτητα από το πόσο μεγάλο μπορεί να είναι το διάστημα στο οποίο την περιορίζει. Το ίδιο ισχύει και για το μοναδικό μέγιστο, αλλά στην πράξη για τις πιο πολλές συναρτήσεις δεν μπορούμε να περιμένουμε να έχουν μοναδικό μέγιστο εκτός και αν το διάστημα είναι ικανοποιητικά κοντά σε ένα ελάχιστο διάστημα. ’ρα, μπορεί να απαιτούνται ακόμα πιο πολλές δοκιμές και σφάλματα για να βρούμε ένα κατάλληλο αρχικό διάστημα το οποίο θα πρέπει να βελτιστοποιήσουμε από αυτές που συνήθως απαιτούνται για να βρούμε τις ρίζες μίας συνάρτησης. Στην πράξη μπορεί κανείς να αναζητά απλώς τρία σημεία τέτοια ώστε η τιμή που παίρνει η συνάρτηση κόστους για το εσωτερικό σημείο να είναι μικρότερη από την τιμή που παίρνει για καθένα από τα δύο εξωτερικά σημεία. Παρόλο που η έρευνα για χρυσή τομή συγκλίνει πάντα, δεν μπορεί να σας εγγυηθεί κανείς ότι θα βρείτε το ολικό ελάχιστο, ή έστω ότι θα βρείτε ένα τοπικό ελάχιστο, εκτός και αν η συνάρτηση κόστους έχει μόνο ένα μέγιστο στο αρχικό διάστημα.