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

Αποκομμένες Μέθοδοι 14#14

Παρόλη αυτή τη γρήγορη ασυμπτωτική σύγκλιση, η μέθοδος Newton μπορεί να είναι αποκρουστική εξαιτίας του μεγάλου της κόστους σε κάθε επανάληψη, ειδικά για πολύ μεγάλα προβλήματα, για τα οποία η ανάγκη αποθηκευτικού χώρου είναι ένα ακόμα σημαντικό θέμα που πρέπει να λάβουμε υπ' όψιν μας. Ένας άλλος τρόπος ενδεχόμενης μείωσης της εργασίας σε κάθε επανάληψη είναι η επίλυση του γραμμικού συστήματος για το βήμα της μεθόδου 14#14,

1352#1352

όπου το 1326#1326 είναι ο πραγματικός ή ο προσεγγιστικός Εσσιανός πίνακας, μέσω μίας επαναληπτικής μεθόδου (δείτε την Ενότητα 11.5) παρά μέσω μίας άμεσης μεθόδου που βασίζεται στην παραγοντοποίηση του 1326#1326. Ένα πλεονέκτημα είναι ότι μόνο μερικές επαναλήψεις της επαναληπτικής μεθόδου μπορεί να είναι αρκετές για να παράγουν ένα βήμα 1300#1300 το οποίο είναι σχεδόν όσο καλό όσο και το πραγματικο βήμα 14#14. Πράγματι, μακρυά από το ελάχιστο το πραγματικό βήμα 14#14 δε μπορεί να προσφέρει πολλά πλεονεκτήματα, και ακόμα μπορεί να κοστίσει πολύ για να υπολογιστεί επ' ακριβώς. Μία τέτοια προσέγγιση λέγεται ανακριβής ή αποκομμένη μέθοδος 14#14, εφόσον το γραμμικό σύστημα του βήματος 14#14 δεν επιλύεται επ' ακριβώς τερματίζοντας τη γραμμική μέθοδο επίλυσης πριν επιτευχθεί η σύγκλιση.

Μία καλή επιλογή για τη γραμμική μέθοδο επίλυσης είναι η μέθοδος της μέγιστης αρνητικής κλίσης (δείτε την Ενότητα 11.5.5). Η μέθοδος της μέγιστης αρνητικής κλίσης ξεκινάει με το αρνητικό διάνυσμα της κλίσης και τελικά συγκλίνει στο πραγματικό βήμα 14#14, οπότε η αποκοπή των επαναλήψεων παράγει ένα βήμα το οποίο μεσολαβεί σε αυτά τα δύο διανύσματα και είναι πάντα μία διεύθυνση προς τα κάτω υπό την προυπόθεση ότι το 1326#1326 είναι θετικά ορισμένο. Επιπλέον, εφόσον η μέθοδος κοινών χαρακτηριστικών των κλίσεων απαιτεί μόνο γινόμενα πινάκων - διανύσμάτων, ο Εσσιανός πίνακας δεν χρειάζεται να μορφοποιηθεί σαφώς, γεγονός το οποίο μπορεί να σημαίνει μία σημαντική οικονομία στον χώρο αποθήκευσης. Για να πάρετε το γινόμενο 1353#1353, για παράδειγμα, μπορείτε αντί αυτού να υπολογίσετε την προσέγγιση της πεπερασμένης διαφοράς

1354#1354

χωρίς να φορμάρετε ποτέ τον 1326#1326.

Κατά την υλοποίηση της αποκομμένης μεθόδου 14#14, το κριτήριο του τελικού αποτελέσματος για την εσωτερική επανάληψη πρέπει να επιλεχθεί προσεκτικά ώστε να διατηρεί το βαθμό υπεργραμμικής σύγκλισης της εξωτερικής επανάληψης. Επιπλέον, μπορεί να απαιτούνται ειδικά μέτρα αν ο πίνακας 1326#1326 δεν είναι θετικά ορισμένος. Παρόλα αυτά, οι αποκομμένες μέθοδοι 14#14 είναι συνήθως πολύ αποδοτικές στην πράξη και βρίσκονται ανάμεσα στις καλύτερες διαθέσιμες μεθόδους για μεγάλα αραιά προβλήματα.


Manolis Vavalis 2000-03-24