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

Πολυπλοκότητα της Επίλυσης Γραμμικών Συστημάτων

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

Ακόμη, μπορούμε να επιλύσουμε ένα γραμμικό σύστημα αντιστρέφοντας αναλυτικά τον πίνακα των συντελεστών, έτσι ώστε η λύση να δίνεται από την 381#381. Αλλά το να υπολογίσει κανείς τον 547#547 είναι ισοδύναμο σε πράξεις με το να επιλύσει 366#366 γραμμικά συστήματα: απαιτείται μία παραγοντοποίηση 2#2 του πίνακα 363#363 ακολουθούμενη από 366#366 προς τα μπρος και προς τα πίσω αντικαταστάσεις, μία για κάθε στήλη του ταυτοτικού πίνακα. Ο συνολικός αριθμός πράξεων είναι περίπου 548#548 πολλαπλασιασμοί και περίπου άλλες τόσες προσθέσεις (εκμεταλλευόμενοι τα μηδενικά στα διανύσματα των δεξιών μελών, κατά τις προς τα μπρος αντικατάστασεις).

Επομένως, η αναλυτική εύρεση του αντίστροφου πίνακα απαιτεί τρεις φορές περισσότερες πράξεις από την παραγοντοποίηση 2#2. Ο μετέπειτα πολλαπλασιασμός πίνακα επί διάνυσμα, 381#381, ώστε να λυθεί το γραμμικό σύστημα, απαιτεί περίπου 546#546 πολλαπλασιασμούς και περίπου άλλες τόσες προσθέσεις, που είναι παρόμοιο με το συνολικό κόστος της προς τα μπρος και προς τα πίσω αντικατάστασης. Αρα, ακόμη και όταν πρόκειται για πολλαπλά διανύσματα στο δεύτερο μέλος, η αντιστροφή του πίνακα κοστίζει πιο πολύ σε πράξεις από την παραγοντοποίηση 2#2 για την επίλυση των αντίστοιχων γραμμικών συστημάτων. Επί πλέον, η άμεση αντιστροφή δίνει μία μικρότερης ακρίβειας λύση. Ως ένα απλό παράδειγμα, αν λύσουμε το 549#549 γραμμικό σύστημα 550#550 με διαίρεση, παίρνουμε 551#551, αλλά η άμεση αντιστροφή θα έδινε 552#552 χρησιμοποιώντας αριθμητική τριών σημαντικών ψηφίων. Σ' αυτό το απλό παράδειγμα, η αντιστροφή απαιτεί μία επιπρόσθετη αριθμητική πράξη και δίνει ένα λιγότερο ακριβές αποτέλεσμα. Τα μειονεκτήματα της αντιστροφής γίνονται χειρότερα καθώς μεγαλώνει το μέγεθος του συστήματος.

Οι αναλυτικές εκφράσεις αντίστροφων πινάκων συχνά συναντώνται ως ευχρηστοι συμβολισμοί σε διάφορους μαθηματικούς τύπους, αλλά η πρακτική αυτή δε σημαίνει ότι μία αναλυτική εύρεση του αντίστροφου απαιτείται για την υλοποίηση του τύπου. Μπορεί κάποιος απλά να χρειάζεται να επιλύσει ένα γραμμικό σύστημα με ένα κατάλληλο δεξιό μέλος, το οποίο μπορεί να είναι και πίνακας. Ετσι, για παράδειγμα, ένα γινόμενο της μορφής 553#553 θα έπρεπε να υπολογιστεί χρησιμοποιώντας την παραγοντοποίηση 2#2 για τον πίνακα 363#363, ακολουθούμενη από τις προς τα μπρος κι προς τα πίσω αντικαταστάσεις χρησιμοποιώντας κάθε μια στήλη του 554#554. Πάρα πολύ σπάνια στην πράξη χρειάζεται αναλυτική εύρεση αντίστροφου πίνακα, συνεπώς όταν βλέπετε μία αντιστροφή πίνακα σε έναν μαθηματικό τύπο, θα πρέπει να σκέφτεστε: «λύσε ένα σύστημα» αντί του «αντίστρεψε τον πίνακα».

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



Manolis Vavalis 2000-03-24