Ξεχάσατε τον κωδικό σας?
Επίλυση Τροποποιημένων Προβλημάτων
Document Actions
Next: Νόρμες και Αριθμοί Κατάστασης Up: Επίλυση Γραμμικών Συστημάτων Previous: Η Απαλοιφή Contents
Επίλυση Τροποποιημένων Προβλημάτων
Πολλές φορές στην πράξη τα γραμμικά συστήματα δεν παρουσιάζονται απομονωμένα αλλά ως μέρος μιας σειράς σχετιζόμενων προβλημάτων τα οποία αλλάζουν με κάποιο συστηματικό τρόπο. Για παράδειγμα, μπορεί κάποιος να επιθυμεί να λύσει μια σειρά από γραμμικά συστήματα της μορφής 383#383 που έχουν τον ίδιο πίνακα 363#363 αλλά διαφορετικά δεξιά μέλη 365#365. Αφού θα έχει λυθεί το αρχικό σύστημα με την απαλοιφή 1#1, τότε οι παράγοντες 107#107 και 108#108 που έχουν ήδη υπολογισθεί μπορούν να χρησιμοποιηθούν για την επίλυση των επιπρόσθετων συστημάτων με προς τα μπρος και προς τα πίσω αντικατάσταση. Η φάση της παραγοντοποίησης δε χρειάζεται να επαναλαμβάνεται κατά την επίλυση των επόμενων γραμμικών συστημάτων, εκτός και αν αλλάξει ο πίνακας 369#369. Αυτή η διαδικασία παρέχει ουσιώδη εξοικονόμηση σε εργασία, αφού οι επιπρόσθετες τριγωνικές λύσεις «κοστίζουν» μόνο 567#567, σε αντίθεση με το κόστος 568#568 της παραγοντοποίησης.
Στην ουσία, σε ορισμένες σημαντικές ειδικές περιπτώσεις, μία νέα παραγοντοποίηση μπορεί να αποφευχθεί ακόμα και όταν ο πίνακας αλλάζει. Μία τέτοια περίπτωση που συναντάται συχνά είναι η πρόσθεση ενός πίνακα που είναι εξωτερικό γινόμενο 569#569 δύο μη μηδενικών διανυσμάτων 570#570 και 571#571. Αυτό λέγεται αλλαγή βαθμού ένα γιατί ο πίνακας του εξωτερικού γινομένου 569#569 έχει βαθμό (572#572) ένα (π.χ. μόνο μία γραμμικώς ανεξάρτητη γραμμή ή στήλη), και κάθε πίνακας βαθμού ένα μπορεί να εκφραστεί ως ένα τέτοιο εξωτερικό γινόμενο δύο διανυσμάτων. Για παράδειγμα, αν ένα μόνο στοιχείο του πίνακα 363#363 αλλάξει (ας πούμε ότι το στοιχείο (573#573,432#432) αλλάζει από 574#574 σε 575#575), τότε ο νέος πίνακας είναι 576#576 όπου 577#577 και 441#441 είναι οι αντίστοιχες στήλες του ταυτοτικού πίνακα και 578#578.
Ο τύπος των 579#579-580#580 δίνει τον αντίστροφο ενός πίνακα που προκύπτει από την εφαρμογή μιας αλλαγής βαθμού ένα σε έναν πίνακα του οποίου ο αντίστροφος είναι ήδη γνωστός:
, όπου 570#570 και 571#571 είναι 366#366-διάστατα διανύσματα. Ο υπολογισμός αυτού του τύπου απαιτεί κόστος εργασίας μόνο 567#567 (για πολλαπλασιασμούς πίνακα επί διάνυσμα) αντί για εργασία κόστους 582#582 που θα απαιτούσε μία κανονική αντιστροφή πίνακα.
Για να επιλύσουμε ένα γραμμικό σύστημα της μορφής 583#583 με το νέο πίνακα, μπορούμε να χρησιμοποιήσουμε τον προηγούμενο πίνακα 369#369 για να πάρουμε
. Παρ' όλα αυτά, θα προτιμούσαμε να αποφύγουμε την αναλυτική αντιστροφή καθ' ολοκληρίαν. Αν έχουμε την παραγοντοποίηση 2#2 του πίνακα 363#363, τότε τα παρακάτω βήματα μπορούν να υπολογιστούν εύκολα για να πάρουμε τη λύση του τροποποιημένου συστήματος:
- Επίλυση του 585#585 ως προς 386#386, οπότε 586#586.
- Επίλυση του 587#587 ως προς 170#170, οπότε 588#588.
- Υπολογισμός του 589#589.
Ο τύπος του 590#590, στον οποίο αντί των διανυσμάτων 570#570 και 571#571 έχουμε τους 591#591 πίνακες 108#108 και 592#592, γενικεύει τον τύπο των 579#579 - 580#580 για αλλαγές βαθμού 432#432 στον πίνακα:
. Χρησιμοποιώντας παρόμοιες τεχνικές, είναι δυνατό να ενημερώσουμε την παραγοντοποίηση αντί για την αντιστροφή ή τη λύση. Παρ' όλα αυτά, πρέπει να προσέχουμε όταν χρησιμοποιούμε αυτούς τους τύπους ενημέρωσης, γιατί γενικά , δεν υπάρχει εγγύηση όσον αφορά στην αριθμητική ευστάθεια όταν ο πίνακας αλλάζει με διαδοχικές ενημερώσεις.
το οποίο είναι μία τροποποίηση βαθμού ένα του συστήματος του Παραδείγματος 2.6 (μόνο το στοιχείο (3,2) έχει αλλάξει). Θεωρούμε τον πίνακα 363#363 του Παραδείγματος 2.6, οπότε μπορούμε να χρησιμοποιήσουμε την παραγοντοποίηση 2#2 που έχει ήδη υπολογιστεί. Ενας τρόπος να επιλέξουμε τα διανύσματα της ενημέρωσης είναι
έτσι ώστε ο πίνακας του νέου συστήματος να είναι ο 596#596 και το διάνυσμα 365#365 του δεξιού μέλους να μην έχει αλλάξει. Μπορούμε να χρησιμοποιήσουμε την παραγοντοποίηση 2#2 του πίνακα 597#597 που υπολογίσαμε προηγουμένως για να επιλύσουμε το 598#598 και να πάρουμε 599#599. Ομως, είχαμε ήδη λύσει το 600#600 και είχαμε πάρει 601#601. Τώρα, το τελικό βήμα είναι για να υπολογίσουμε την ενημερωμένη λύση είναι
Μ' αυτόν τον τρόπο έχουμε υπολογίσει τη λύση του νέου συστήματος χωρίς να παραγοντοποιήσουμε ξανά τον τροποποιημένο πίνακα.
Manolis Vavalis 2000-03-24
