Ξεχάσατε τον κωδικό σας?
Αποκομμένες Μέθοδοι
Document Actions
Next: Παρεμβολή Up: ΠΟΛΥΔΙΑΣΤΑΤΗ ΦΥΣΙΚΗ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ Previous: Μέθοδος Κοινών Χαρακτηριστικών των Contents
Αποκομμένες Μέθοδοι 14#14
Παρόλη αυτή τη γρήγορη ασυμπτωτική σύγκλιση, η μέθοδος Newton μπορεί να είναι αποκρουστική εξαιτίας του μεγάλου της κόστους σε κάθε επανάληψη, ειδικά για πολύ μεγάλα προβλήματα, για τα οποία η ανάγκη αποθηκευτικού χώρου είναι ένα ακόμα σημαντικό θέμα που πρέπει να λάβουμε υπ' όψιν μας. Ένας άλλος τρόπος ενδεχόμενης μείωσης της εργασίας σε κάθε επανάληψη είναι η επίλυση του γραμμικού συστήματος για το βήμα της μεθόδου 14#14,όπου το 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, για παράδειγμα, μπορείτε αντί
αυτού να υπολογίσετε την προσέγγιση της πεπερασμένης διαφοράς
χωρίς να φορμάρετε ποτέ τον 1326#1326.
Κατά την υλοποίηση της αποκομμένης μεθόδου 14#14, το κριτήριο του
τελικού αποτελέσματος για την εσωτερική επανάληψη πρέπει να
επιλεχθεί προσεκτικά ώστε να διατηρεί το βαθμό υπεργραμμικής
σύγκλισης της εξωτερικής επανάληψης. Επιπλέον, μπορεί να
απαιτούνται ειδικά μέτρα αν ο πίνακας 1326#1326 δεν είναι θετικά
ορισμένος. Παρόλα αυτά, οι αποκομμένες μέθοδοι 14#14 είναι
συνήθως πολύ αποδοτικές στην πράξη και βρίσκονται ανάμεσα στις
καλύτερες διαθέσιμες μεθόδους για μεγάλα αραιά προβλήματα.
Manolis Vavalis 2000-03-24
