Ξεχάσατε τον κωδικό σας?
Μέθοδος Κοινών Χαρακτηριστικών των Κλίσεων
Document Actions
Next: Αποκομμένες Μέθοδοι Up: ΠΟΛΥΔΙΑΣΤΑΤΗ ΦΥΣΙΚΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ Previous: Μέθοδοι Ενημέρωσης των Contents
Μέθοδος Κοινών Χαρακτηριστικών των Κλίσεων
Η μέθοδος κοινών χαρακτηριστικών των κλίσεων είναι μία άλλη εναλλακτική μέθοδος για τη μέθοδο 14#14 η οποία δεν απαιτεί ρητά δεύτερες παραγώγους. Πράγματι, σε αντίθεση με τη μέθοδο ενημέρωσης 16#16, η μέθοδος κοινών χαρακτηριστικών των κλίσεων δεν αποθηκεύει καν μία προσέγγιση του Εσσιανού πίνακα, γεγονός που κάνει αυτή τη μέθοδο ιδιαίτερα κατάλληλη για πολύ μεγάλα προβλήματα.
Όπως είδαμε στην Ενότητα 6.3.2, η μέθοδος της μέγιστης αρνητικής κλίσης τείνει να ψάχνει προς τις ίδιες διευθύνσεις επαναλαμβανόμενα, οδηγώντας σε πολύ αργή σύγκλιση. Όπως δηλώνει και το όνομά της, η μέθοδος κοινών χαρακτηριστικών των κλίσεων χρησιμοποιεί και κλίσεις, αλλά αποφεύγει τις επαναλαμβανόμενες αναζητήσεις τροποποιώντας την κλίση σε κάθε βήμα ώστε να απορρίπτει τα στοιχεία που βρίσκονται σε προηγούμενες διευθύνσεις. Η ακολουθία που προκύπτει από τα καονά χαρακτηριστικά (δηλ., ορθογώνιες σε κάποιο εσωτερικό γινόμενο) διευθύνσεων αναζήτησης αναμφίβολα συσσωρεύει πληροφορίες σχετικά με τον Εσσιανό πίνακα όσο προχωράνε οι επαναλήψεις. Θεωρητικά, η μέθοδος είναι ακριβής μετά από το πολύ 366#366 επαναλήψεις για μία τετραγωνική συνάρτηση κόστους στις 366#366 διαστάσεις, αλλά συνήθως είναι αρκετά αποτελεσματική επίσης και για πιο γενικά φυσικά προβλήματα ελαχιστοποίησης. Το κίνητρο για αυτόν τον αλγόριθμο το μελετάμε στην Ενότητα 11.5.5.
Για να ελαχιστοποιήσουμε τη συνάρτηση 51#51 ξεκινώντας από μία αρχική υπόθεση 1092#1092, αρχικοποιούμε τα 1333#1333 και 1334#1334. Στη συνέχεια επαναλαμβάνονται τα ακόλουθα βήματα μέχρι να επιτευχθεί η σύγκλιση.
- 1335#1335
- 1336#1336
- 1337#1337
- 1338#1338
Η φόρμα για το 1339#1339 που δίνεται πιο πάνω οφείλεται στους 1340#1340 και 1341#1341. Μία εναλλακτική φόρμα, που οφείλεται στους 1342#1342 και 1343#1343, είναι η
Είναι συνηθισμένο να επαναξεκινάμε τον αλγόριθμο μετά από 366#366 επαναλήψεις, επαναρχικοποιώντας για να χρησιμοποιήσουμε την αρνητική κλίση στο τρέχον σημείο.
της οποίας η κλίση δίνεται από τη
Ξεκινώντας με το 1291#1291 η αρχική κατεύθυνση αναζήτησης είναι η αρνητική κλίση,
Το ακριβές ελάχιστο κατά μήκους αυτής της ευθείας δίνεται από την 1346#1346, οπότε η επόμενη προσέγγιση είναι η 1295#1295 και σε αυτό το σημείο υπολογίζουμε τη νέα κλίση,
Μέχρι εδώ δεν υπάρχει καμμία διαφορά με τη μέθοδο της μέγιστης αρνητικής κλίσης. Παρόλα αυτά, σε αυτό το σημείο αντί να ψάχνουμε κατά μήκος της νέας αρνητικής κλίσης, αντί αυτού υπολογίζουμε την ποσότητα
η οποία μας δίνει την επόμενη διεύθυνση αναζήτησης
Το ελάχιστο κατά μήκος αυτής της διεύθυνσης δίνεται από τη 1350#1350, η οποία δίνει την ακριβή λύση του αρχικού προβλήματος. Άρα, όπως θα περίμενε κανείς για μία τετραγωνική συνάρτηση, η μέθοδος κοινών χαρακτηριστικών των κλίσεων συγκλίνει σε 1351#1351 βήματα σε αυτή την περίπτωση.
Manolis Vavalis 2000-03-24
