next up previous contents
Next: Μέθοδοι Ενημέρωσης των Up: ΠΟΛΥΔΙΑΣΤΑΤΗ ΦΥΣΙΚΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ Previous: Η Μέθοδος   Contents

Μέθοδοι 15#15

Η μέθοδος Newton συνήθως συγκλίνει πολύ γρήγορα όταν πλησιάζει τη λύση, αλλά απαιτεί πολλή δουλειά για κάθε επανάληψη, συγκεκριμένα 1312#1312 αριθμητικές και 1313#1313 βαθμωτές εκτιμήσεις συναρτήσεων για κάθε επανάληψη για ένα @dense@ πρόβλημα. Αυτό το μειονέκτημα έδωσε κίνητρα για την ανάπτυξη μεθόδων (quasi-Newton) οι οποίες συγκλίνουν κάπως πιο αργά αλλά απαιτούν πολύ λιγότερη δουλειά για κάθε επανάληψη (και επίσης συχνά είναι και πιο (robust)).

Πολλές διαφοροποιήσεις της μεθόδου 14#14 έχουν αναπτυχθεί για να βελτιώσουν την αξιοπιστία του και να μειώσουν τις πολλές πράξεις που απαιτούνται. Αυτές οι 1314#1314 μέθοδοι έχουν τη μορφή

1315#1315

, όπου το 1286#1286 είναι μία παράμετρος αναζήτησης ευθείας και ο 1316#1316 είναι κάποια προσέγγιση του Εσσιανού πίνακα τον οποίο παίρνουμε με οποιονδήποτε από ένα πλήθος τρόπων, συμπεριλαμβανομένης της ενημέρωσης του (secant), των πεπερασμένων διαφορών, των περιοδικών επανεκτιμήσεων, ή της αμέλειας κάποιων τμημάτων του πραγματικού Εσσιανού της συνάρτησης κόστους.

Πολλές 1314#1314 μέθοδοι είναι πιο 1317#1317 από αυτή καθαυτή τη μέθοδο 14#14, είναι υπεργραμμικά συγκλίνουσες, και απαιτούν αξιοσημείωτα λιγότερες πράξεις σε κάθε επανάληψη. Για παράδειγμα, οι μέθοδοι ενημέρωσης του 16#16 για αυτό το πρόβλημα δεν απαιτούν δεύτερη βαθμωτή εκτίμηση, απαιτούν μόνο μία βαθμωτή εκτίμηση σε κάθε επανάληψη, και επιλύουν το απαραίτητο γραμμικό σύστημα σε κάθε επανάληψη μέσω μεθόδων ενημέρωσης οι οποίες απαιτούν μόνο 1313#1313 εργασία σε αντίθεση με την 1312#1312 εργασία η οποία θα απαιτείτω αν παραγοντοποιούσαμε τον πίνακα σε κάθε βήμα. Αυτό το μεγάλο κέρδος στην εργασία για κάθε επανάληψη αντισταθμίζει με το παραπάνω τον κάπως αργό ρυθμό σύγκλισης αυτών των μεθόδων (γενικά υπεργραμμικός αλλά όχι τετραγωνικός), οπότε συνήθως απαιτούν λιγότερο συνολικό χρόνο για να βρουν μία λύση.



Manolis Vavalis 2000-03-24