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

Βελτίωση της Ακρίβειας

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

Θυμηθείτε από το Παράδειγμα 2.3 ότι η διαγώνια στάθμιση ενός γραμμικού συστήματος είτε αφήνει τη λύση αμετάβλητη (στάθμιση γραμμών), είτε την αλλάζει με τρόπο τέτοιο ώστε εύκολα επαναποκτάται (στάθμιση στηλών). Στην πράξη, όμως, η στάθμιση επηρεάζει την κατάσταση του συστήματος και την επιλογή των οδηγών στην απαλοιφή 1#1, και αυτά τα δύο με τη σειρά τους επηρεάζουν την ακρίβεια της λύσης που υπολογίζουμε. Αρα, η στάθμιση γραμμών και στηλών ενός γραμμικού συστήματος μπορούν να βελτιώσουν (ή να μειώσουν) σημαντικά την αριθμητική ευστάθεια του συστήματος και την ακρίβεια της λύσης.

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


27#27

Παράδειγμα 2.12   Στάθμιση. Ως ένα απλό παράδειγμα, το γραμμικό σύστημα

700#700

έχει δείκτη κατάστασης 701#701 επομένως αν το 143#143 είναι πολύ μικρό, το σύστημα είναι πολύ κακής κατάστασης. Αυτή η κακή κατάσταση σημαίνει ότι μικρές διαταράξεις στα δεδομένα εισόδου μπορούν να προκαλέσουν σχετικά μεγάλες διαταράξεις στη λύση. Για παράδειγμα, διαταράσσοντας το δεξιό μέλος με το διάνυσμα 702#702 αλλάζει τη λύση από 703#703 σε 704#704. Ομως, αν η δεύτερη γραμμή πολλαπλασιαστεί πρώτα επί 701#701 τότε το σύστημα έχει τελείως καλή κατάσταση. Αρα, η προφανής κακή κατάσταση του συστήματος οφειλόταν απλά σε κακή στάθμιση. Δυστυχώς, το πως μπορεί να κατορθωθεί η διόρθωση της κακής στάθμισης για γενικούς πίνακες δεν είναι τόσο προφανής.


27#27

Η Επαναληπτική Βελτίωση αποτελεί ένα άλλο μέσον πιθανής βελτίωσης της ακρίβειας της υπολογισθείσας λύσης. Δεδομένης μιας προσεγγιστικής λύσης 675#675 για το γραμμικό σύστημα 383#383 υπολογίστε το υπόλοιπο

705#705

Τώρα λύστε το γραμμικό σύστημα

706#706

και θεωρείστε

707#707

ως μία νέα και «καλύτερη» προσεγγιστική λύση, αφού

708#708

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

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

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


Manolis Vavalis 2000-03-24