next up previous contents
Next: Υλοποίηση της Απαλοιφής Up: Επίλυση Γραμμικών Συστημάτων Previous: Απαλοιφή και Παραγοντοποίηση.   Contents

Οδήγηση

Υπάρχει ένα προφανές πρόβλημα με τη διαδικασία απαλοιφής 480#480 όπως την έχουμε περιγράψει, όπως επίσης και άλλο ένα, κατά κάποιο τρόπο πιο σύνθετο, πρόβλημα. Η προφανής πιθανή δυσκολία είναι ότι η διαδικασία καταρρέει άν το οδηγό διαγώνιο στοιχείο του εναπομένοντος μη απλοποιημένου τμήματος του πίνακα είναι μηδέν σε οποιοδήποτε στάδιο της απαλοιφής, αφού ο υπολογισμός τον πολλαπλασιαστών 481#481 για μία δεδομένη στήλη απαιτεί διαίρεση με το διαγώνο στοιχείο αυτής της στήλης. Η λύση στο πρόβλημα αυτό είναι σχεδόν εξίσου προφανής: εάν το στοιχείο της διαγωνίου είναι μηδέν στο στάδιο 482#482 τότε εναλλάσσουμε τη γραμμή 432#432 του συστήματος με μία επόμενη γραμμή της οποίας το στοιχείο που έχει στην 432#432 στήλη είναι μη μηδενικό. Οπως γνωρίζουμε από το Παράδειγμα 2.2, μία τέτοια εναλλαγή δε μεταβάλλει τη λύση του συστήματος. Με ένα μη μηδενικό στοιχείο της διαγωνίου ως οδηγό, η διαδικασία μπορεί να συνεχιστεί ως συνήθως.

Αλλά τι συμβαίνει αν δεν υπάρχει κανένα μη μηδενικό στοιχείο στη διαγώνιο ή κάτω από αυτή στη στήλη 483#483 Τότε δεν υπάρχει κάτι που θα μπορούσαμε να κάνουμε στο στάδιο αυτό αφού όλα τα στοιχεία που θα έπρεπε να μηδενιστούν είναι ήδη μηδέν, επομένως μπορούμε απλά να προχωρήσουμε στην επόμενη στήλη (δηλαδή, 484#484). Σημειώστε ότι αυτό το βήμα αφήνει ένα μηδενικό στη διαγώνιο και για το λόγο αυτό ο άνω τριγωνικός πίνακας 108#108 που θα προκύψει θα είναι ιδιάζων, αλλά η 2#2 παραγοντοποίηση μπορεί ακόμη να ολοκληρωθεί. Σημαίνει, όμως, ότι η προς τα πίσω αντικατάσταση που θα επακολουθήσει θα αποτύχει, αφού απαιτεί διαίρεση με κάθε ένα στοιχείο της διαγωνίου του 485#485 Αυτό όμως δε μας εκπλήσσει, αφού ο αρχικός πίνακας θα πρέπει να ήταν έτσι κι αλλιώς ιδιάζων. Ενα ακόμη λιγότερο εμφανές πρόβλημα είναι ότι στην αριθμητική κινητής υποδιαστολής είναι πιθανόν να μην πάρουμε μηδέν ακριβώς, αλλά μόνον ένα πολύ μικρό διαγώνιο στοιχείο, κάτι το οποίο μας φέρνει σε ένα πιο λεπτό σημείο.

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

Οι απαιτούμενες εναλλαγές των γραμμών της μερικής οδήγησης περιπλέκουν λίγο την τυπική περιγραφή της 2#2 παραγοντοποίησης που δόθηκε προηγουμένως. Πιο αναλυτικά, κάθε στοιχειώδης πίνακας απαλοιφής 486#486 ακολουθεί ένα μεταθετικό πίνακα 487#487 ο οποίος εναλλάσσει τις γραμμές για να φέρει το μεγαλύτερου μεγέθους στοιχείο στη διαγώνια θέση οδηγού. Ακόμη έχουμε ότι 488#488, όπου ο 108#108 είναι άνω τριγωνικός, αλλά τώρα


489#489

. Ο 490#490 εξακολουθεί να είναι τριγωνικός υπό τη γενική έννοια που ορίσαμε προηγουμένως αλλά λόγω των μεταθέσεων, ο 490#490 δεν είναι απαραίτητα κάτω τριγωνικός, αν και εξακολουθούμε να τον συμβολίζουμε με 107#107. Ετσι, η "2#2" παραγοντοποίηση δε σημαίνει ακριβώς "ο κάτω επί τον άνω" τριγωνικό, αλλά είναι ακόμη εξίσου χρήσιμη στην επίλυση γραμμικών συστημάτων με διαδοχικές αντικαταστάσεις.

Σημειώστε ότι ο μεταθετικός πίνακας

491#491

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

492#492

όπου τώρα ο 107#107 είναι πραγματικά κάτω τριγωνικός. Για να λύσουμε το σύστημα 383#383, πρώτα επιλύουμε το κάτω τριγωνικό σύστημα 493#493 με προς τα μπρος αντικατάσταση και μετά το άνω τριγωνικό σύστημα 470#470 με προς τα πίσω αντικατάσταση.

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

494#494

όπου ο 107#107 είναι κάτω τριγωνικός, ο 108#108 άνω τριγωνικός και οι 398#398 και 495#495 είναι μεταθετικοί πίνακες που αναδιατάσσουν τις γραμμές και τις στήλες, αντίστοιχα, του πίνακα 369#369. Για να επιλύσουμε το γραμμικό σύστημα 383#383, πρώτα λύνουμε το κάτω τριγωνικό σύστημα 493#493 με προς τα μπρος αντικατάσταση, έπειτα το άνω τριγωνικό σύστημα 496#496 με προς τα πίσω αντικατάσταση και τέλος μεταθέτουμε τις συνιστώσες της λύσης για να λάβουμε 497#497 Αν και η αριθμητική ευστάθεια της ολικής οδήγησης είναι θεωρητικά υπέρτερη, απαιτεί μια πολύ πιο αντιοικονομική αναζήτηση για το οδηγό στοιχείο από τη μερική οδήγηση. Επειδή η μερική οδήγηση είναι περισσότερο από επαρκής στην πράξη, χρησιμοποιείται σχεδόν αποκλειστικά για την επίλυση γραμμικών συτημάτων με τη μέθοδο απαλοιφής του 1#1.

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


27#27

Παράδειγμα 2.7   Οδήγηση. Στη συνέχεια δίνονται μερικά παραδείγματα που παρουσιάζουν το απαραίτητο της οδήγησης, στη θεωρία και στην πράξη, για την υλοποίηση μιας ευσταθούς απαλοιφής 498#498 Παρατηρούμε πρώτα ότι η ανάγκη για οδήγηση δεν έχει να κάνει τίποτα με το εάν ο πίνακας είναι ιδιάζων ή σχεδόν ιδιάζων. Για παράδειγμα, ο πίνακας


499#499

είναι μη ιδιάζων αλλά δεν επιδέχεται 2#2 παραγοντοποίηση εκτός κι αν εναλλάξουμε γραμμές, ενώ ο ιδιάζων πίνακας


500#500

επιδέχεται 2#2 παραγοντοποίηση.

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


501#501

όπου 143#143 είναι ένας θετικός αριθμός μικρότερος από την ακρίβεια της μηχανής 139#139 σε ένα δοσμένο σύστημα αρίθμησης κινητής υποδιαστολής. Εάν δεν εναλλάξουμε γραμμές, τότε το οδηγό στοιχείο είναι 143#143 και ο πολλαπλασιαστής είναι 502#502, έτσι ο στοιχειώδης πίνακας απαλοιφής είναι

503#503

επομένως


504#504

σε αριθμητική κινητής υποδιαστολής. Αλλά τότε


505#505

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

507#507

και επομένως


508#508

σε αριθμητική κινητής υποδιαστολής. Επομένως έχουμε


509#509

που είναι το ακριβές αποτέλεσμα μετά τη μετάθεση.

Αν και το προηγούμενο παράδειγμα είναι μάλλον ακραίο, γενικά ισχύει η αρχή ότι όσο μεγαλύτερα είναι τα οδηγά στοιχεία τόσο μικρότεροι πολλαπλασιαστές προκύπτουν και συνεπώς μικρότερα σφάλματα. Συγκεκριμένα, αν ως οδηγό στοιχείο σε κάθε στήλη χρησιμοποιείται το μεγαλύτερο σε μέγεθος στοιχείο που βρίσκεται επί της διαγωνίου ή κάτω από αυτή (μερική οδήγηση), τότε οι πολλαπλασιαστές φράσσονται σε μέγεθος από τη μονάδα. Στο Παράδειγμα 2.6, δε χρησιμοποιήσαμε εναλλαγή γραμών, και κάποιοι από τους πολλαπλασιαστές ήταν σε μέγεθος μεγαλύτεροι από 39#39. Για διευκρίνιση, επαναλαμβάνουμε τώρα αυτό το παράδειγμα, όπου αυτή τη φορά θα χρησιμοποιήσουμε μερική οδήγηση. Το σύστημα του Παραδείγματος 2.6 είναι


473#473

Το μεγαλύτερο σε μέγεθος στοιχείο της πρώτης στήλης είναι το 510#510, έτσι εναλλάσουμε τις δυο πρώτες γραμμές χρησιμοποιώντας το μεταθετικό πίνακα


511#511

λαμβάνοντας το μετασχηματισμένο σύστημα


512#512

Για να μηδενίσουμε τα κάτω από τη διαγώνιο στοιχεία της πρώτης στήλης, χρησιμοποιούμε τον πίνακα απαλοιφής


513#513

λαμβάνοντας το μετασχηματισμένο σύστημα


514#514

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


516#516

λαμβάνοντας το ματασχηματισμένο σύστημα


517#517

Για να μηδενίσουμε το κάτω από τη διαγώνιο στοιχείο της δεύτερης στήλης, χρησιμοποιούμε τον πίνακα απαλοιφής


518#518

λαμβάνοντας το μετασχημετισμένο σύστημα


519#519

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

Για να γράψουμε αναλυτικά την 2#2 παραγοντοποίηση, έχουμε


520#520


521#521

επομένως


522#522

Σημειώστε ότι ο 107#107 δεν είναι κάτω τριγωνικός αλλά είναι κάτω τριγωνικός με τη γενικότερη έννοια (είναι μια μετάθεση ενός κάτω τριγωνικού πίνακα). Εναλλακτικά, μπορούμε να πάρουμε


523#523

και


524#524

έτσι ώστε


525#525

όπου ο 107#107 είναι τώρα πράγματι κάτω τριγωνικός αλλά ο 369#369 είναι μετατιθεμένος.


27#27

Οπως μόλις είδαμε, η οδήγηση απαιτείται γενικά για να είναι η απαλοιφή 1#1 ευσταθής. Ομως, υπάρχουν κάποιες κατηγορίες πινάκων για τους οποίους η απαλοιφή 1#1 είναι ευσταθής και χωρίς οδήγηση. Για παράδειγμα, αν ο πίνακας 363#363 είναι αυστηρά διαγώνια υπέρτερος κατά στήλες, που σημαίνει ότι κάθε στοιχείο της διαγωνίου είναι μεγαλύτερο σε μέτρο από το άθροισμα των μέτρων των υπόλοιπων στοιχείων της ίδιας στήλης,


526#526

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


next up previous contents
Next: Υλοποίηση της Απαλοιφής Up: Επίλυση Γραμμικών Συστημάτων Previous: Απαλοιφή και Παραγοντοποίηση.   Contents
Manolis Vavalis 2000-03-24