next up previous contents
Next: Επίλυση Τροποποιημένων Προβλημάτων Up: Επίλυση Γραμμικών Συστημάτων Previous: Πολυπλοκότητα της Επίλυσης Γραμμικών   Contents

Η Απαλοιφή 3#3

Το κίνητρο για την απαλοιφή 1#1 είναι το να μετασχηματιστεί ένας γενικής μορφής πίνακας σε μία τριγωνική μορφή, επειδή το γραμμικό σύστημα που προκύπτει είναι εύκολο να λυθεί. Ομως, τα διαγώνια γραμμικά συστήματα είναι ακόμα πιο εύκολο να επιλυθούν, οπότε, η διαγώνια μορφή θα φαινόταν να είναι ακόμη πιο επιθυμητός σκοπός. Η απαλοιφή 1#1 - 556#556 είναι μία τροποποίηση της πρότυπης απαλοιφής 1#1 κατά την οποία ο πίνακας μετασχηματίζεται σε διαγώνια μορφή, παρά απλά σε τριγωνική μορφή. Ο ίδιος τρόπος συνδυασμού γραμμών χρησιμοποιείται για την απαλοιφή των στοιχείων του πίνακα όπως στην πρότυπη απαλοιφή 1#1 χρησιμοποιείται για την απαλοιφή στοιχείων του πίνακα κάτω και πάνω από την κύρια διαγώνιο. Ετσι, ο πίνακας απαλοιφής που χρησιμοποιείται για ένα δοσμένο διάνυσμα-στήλη 431#431 είναι της μορφής


557#557

όπου 558#558, 559#559. Αυτή η διαδικασία απαιτεί περίπου 560#560 πολλαπλασιασμούς και περίπου άλλες τόσες προσθέσεις, που είναι 561#561 περισσότερες πράξεις από την τυπική απαλοιφή 1#1.

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

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

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


27#27

Παράδειγμα 2.8   Απαλοιφή 3#3

Θα δείξουμε την απαλοιφή 1#1-556#556 χρησιμοποιώντας την για τον υπολογσμό του αντίστροφου του πίνακα του Παραδείγματος 2.6. Για λόγους απλότητας, παραλείπουμε τη χρήση οδήγησης. Αρχίζουμε με τον πίνακα 369#369 επαυξημένο με τον ταυτοτικό πίνακα σαν το δεξιό μέλος, και εφαρμόζουμε επανειλημμένα πίνακες απαλοιφής για να μηδενίσουμε τα εκτός της διαγωνίου στοιχεία του 369#369 έως ότου φθάσουμε σε διαγώνια μορφή, οπότε και διαιρούμε τις γραμμές του επαυξημένου πίνακα με τα αντίστοιχα διαγώνια στοιχεία, ώστε να παραχθεί ο ταυτοτικός πίνακας στη θέση που αρχικά κατείχε ο 369#369.


27#27

Παράδειγμα 2.9   Απαλοιφή 1#1-556#556

562#562


563#563


564#564


565#565

άρα


566#566


27#27



Manolis Vavalis 2000-03-24