next up previous contents
Next: Εκτίμηση Ακρίβειας Up: Ακρίβεια Λύσεων Previous: Ακρίβεια Λύσεων   Contents

Υπόλοιπο μιας Λύσης

Διαισθητικά, ο πιο προφανής τρόπος να ελέγξουμε την εγκυρότητα μίας λύσης είναι να την αντικαταστήσουμε στην εξίσωση για να δούμε πόσο κοντά είναι τα δύο μέλη της. Το διάνυσμα υπόλοιπο μιας προσεγγιστικής λύσης 47#47 ενός 371#371 γραμμικού συστήματος 383#383 ορίζεται ως


657#657

Θεωρητικά, όταν ο 369#369 δεν είναι ιδιάζων, τότε το σφάλμα ικανοποιεί την 658#658 αν και μόνο αν 659#659. Ομως, στην πράξη, αυτές οι ποσότητες δεν είναι απαραίτητο να είναι ταυτόχρονα μικρές. Αν η λύση 47#47 που υπολογίστηκε ικανοποιεί ακριβώς τη σχέση


660#660

τότε


661#661

έτσι ώστε έχουμε την ανισότητα

662#662

η οποία συνδέει το σχετικο υπόλοιπο προς τη σχετική αλλαγή (διαταραχή) του πίνακα. Αρα, ένα μεγάλο σχετικό υπόλοιπο συνεπάγεται μεγάλο προς τα πίσω σφάλμα στον πίνακα, το οποίο σημαίνει ότι ο αλγόριθμος που χρησιμοποιήθηκε για τον υπολογισμό της λύσης είναι ασταθής.

Αλλά πόσο μεγάλη μπορεί να γίνει η 663#663 στην πράξη; Ο 664#664 [273] έδειξε ότι όσον αφορά την παραγοντοποίηση 2#2 με απαλοιφή 1#1, υπάρχει ένα φράγμα της μορφής

665#665

όπου το ρ, που λέγεται παράγοντας αύξησης, είναι το πηλίκο του απόλυτα μεγαλύτερου στοιχείου του 108#108 προς το απόλυτα μεγαλύτερο στοιχείο του πίνακα 369#369. Χωρίς οδήγηση, το ρ μπορεί να γίνει πολύ μεγάλο, και άρα η απαλοιφή 1#1 χωρίς οδήγηση είναι ασταθής, όπως έχουμε ήδη δεί. Με μερική οδήγηση, ο παράγοντας αύξησης μπορεί να είναι μέχρι και 666#666 (αφού στη χειρότερη περίπτωση το μέγεθος των στοιχείων μπορεί να διπλασιάζεται σε κάθε στάδιο της απαλοιφής), αλλά μία τέτοια συμπεριφορά είναι πάρα πολύ σπάνια. Στην πράξη, υπάρχει μόνο μικρή ή και καθόλου αύξηση στο μέγεθος των στοιχείων, έτσι ώστε

667#667

Αυτή η σχέση σημαίνει ότι επιλύοντας ένα γραμμικό σύστημα με απαλοιφή 1#1 με μερική οδήγηση ακολουθούμενη από προς τα πίσω αντικατάσταση σχεδόν πάντα δίνει πολύ μικρό σχετικό υπόλοιπο, ανεξάρτητα από το πόσο κακής κατάστασης μπορεί να είναι το σύστημα. Αρα, ένα μικρό σχετικό υπόλοιπο δεν αποτελεί απαραίτητα μία καλή ένδειξη ότι η λύση που υπολογίστηκε βρίσκεται κοντά στην "αληθή" λύση, εκτός και αν το σύστημα είναι καλής κατάστασης.

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


27#27

Παράδειγμα 2.11   Μικρό Υπόλοιπο. Χρησιμοποιώντας αριθμητική τριών σημαντικών ψηφίων για να επιλύσουμε το σύστημα

668#668

η απαλοιφή 1#1 με μερική οδήγηση δίνει το τριγωνικό σύστημα

669#669

και η προς τα πίσω αντικατάσταση τότε δίνει τιμή για την υπολογισθείσα λύση

670#670

Το ακριβές υπόλοιπο για τη λύση αυτή είναι

671#671

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

672#672

οπότε το σφάλμα είναι περίπου τόσο μεγάλο όσο η λύση. Η αιτία γι' αυτό το φαινόμενο είναι ότι ο πίνακας είναι σχεδόν ιδιάζων (ο δείκτης κατάστασής του είναι πάνω από 673#673). Η διαίρεση που προσδιορίζει το 674#674 είναι διαίρεση μεταξύ δύο ποσοτήτων οι οποίοι είναι και οι δύο της τάξης του σφάλματος στρογγύλευσης, και άρα το αποτέλεσμα είναι ουσιαστικά οποιοδήποτε. Ακόμη, εκ κατασκευής, όταν αυτή η οποιαδήποτε τιμή του 674#674 αντικαταθίσταται τότε στην αρχική εξίσωση, υπολογίζεται μία τιμή για το 675#675 ώστε να ικανοποιείται η αρχική εξίσωση. Αρα, παίρνουμε μικρό υπόλοιπο, αλλά μια κακή προσέγγιση της λύσης.


27#27



Manolis Vavalis 2000-03-24