Υπόλοιπο μιας Λύσης
Υπόλοιπο μιας Λύσης
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
Μικρό Υπόλοιπο.
Χρησιμοποιώντας αριθμητική τριών σημαντικών ψηφίων για να
επιλύσουμε το σύστημα
η απαλοιφή 1#1 με μερική οδήγηση δίνει το τριγωνικό σύστημα
και η προς τα πίσω αντικατάσταση τότε δίνει τιμή για την υπολογισθείσα λύση
Το ακριβές υπόλοιπο για τη λύση αυτή είναι
το οποίο είναι τόσο μικρό όσο θα περιμέναμε χρησιμοποιώντας αριθμητική μόνον τριών σημαντικών ψηφίων. Ακόμη, η ακριβής λύση για το σύστημα αυτό είναι προφανές ότι είναι η
οπότε το σφάλμα είναι περίπου τόσο μεγάλο όσο η λύση. Η αιτία γι' αυτό το φαινόμενο είναι ότι ο πίνακας είναι σχεδόν ιδιάζων (ο δείκτης κατάστασής του είναι πάνω από 673#673). Η διαίρεση που προσδιορίζει το 674#674 είναι διαίρεση μεταξύ δύο ποσοτήτων οι οποίοι είναι και οι δύο της τάξης του σφάλματος στρογγύλευσης, και άρα το αποτέλεσμα είναι ουσιαστικά οποιοδήποτε. Ακόμη, εκ κατασκευής, όταν αυτή η οποιαδήποτε τιμή του 674#674 αντικαταθίσταται τότε στην αρχική εξίσωση, υπολογίζεται μία τιμή για το 675#675 ώστε να ικανοποιείται η αρχική εξίσωση. Αρα, παίρνουμε μικρό υπόλοιπο, αλλά μια κακή προσέγγιση της λύσης.
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