next up previous contents
Next: Περιστροφή Up: Μέθοδοι Ορθογωνοποίησης Previous: Paragwntopoihsh QR   Contents

?


760#760


761#761


762#762


763#763


764#764


27#27

Παράδειγμα 3.4   ΜΕΤΑΤΡΟΠΗ 765#765.

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


766#766

Γι' αυτό το σκοπό, επιλέγουμε το διάνυσμα


767#767

όπου 768#768 . Αφού το 769#769 πρέπει να είναι θετικό, μπορούμε να αποφύγουμε την ακύρωση επιλέγοντας το αρνητικό πρόσημο για το 641#641. Επομένως έχουμε:


770#770

Για να επιβεβαιώσουμε το ότι η μετατροπή 771#771 λειτουργεί όπως θα περιμέναμε να λειτουργεί, υπολογίζουμε το


772#772

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


27#27

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


775#775

που είναι πραγματικά πιο οικονομικό στον υπολογισμό από ότι ένας πολλαπλασιασμός ενός τυχαίου διανύσματος με πίνακα και το μόνο που χρειάζεται είναι να γνωρίζουμε το διάνυσμα 774#774.

Η διαδικασία που μόλις περιγράψαμε παράγει μία παραγοντοποίηση της μορφής


776#776

όπου ο 777#777 είναι άνω τριγωνικός. Και το ίδιο το γινόμενο των διαδοχικών μετατροπών 771#771 778#778 είναι ένας ορθογώνιος πίνακας. Άρα, αν πάρουμε


779#779

τότε


780#780

Άρα, έχουμε πράγματι υπολογίσει την παραγοντοποίηση 8#8 του πίνακα 363#363, την οποία μπορούμε τώρα να χρησιμοποιήσουμε για να λύσουμε το γραμμικό πρόβλημα των ελαχίστων τετραγώνων. Όμως, για να προστατέψουμε τη λύση, πρέπει να μετατρέψουμε το διάνυσμα 86#86 του δεξιού μέλους σύμφωνα με τον ίδιο αλγόριθμο της μετατροπής 771#771. Τότε μπορούμε να λύσουμε το ισοδύναμο τριγωνικό πρόβλημα ελαχίστων τετραγώνων


781#781

Για να λύσουμε το γραμμικό πρόβλημα των ελαχίστων τετραγώνων, ο παράγοντας ?? που προέρχεται από τις μετατροπές 771#771 δεν χρειάζεται να είναι σχηματισμένος επ' ακριβώς. Στο μεγαλύτερο μέρος του λογισμικού που χρησιμοποιείται για αυτό το πρόβλημα, ο πίνακας 777#777 αποθηκεύεται στο άνω τριγωνικό μέρος του αρχικού πίνακα που περιείχε τον 369#369, ενώ τα διανύσματα v που απαιτούνται για τις ξεχωριστές μετατροπές 771#771 αποθηκεύονται στο (τώρα μηδενικό) κάτω τριγωνικό τμήμα του 369#369. (Τεχνικά, απαιτείται ένα επιπλέον διάνυσμα για αποθήκευση, αφού πρέπει να αποθηκευτούν και οι κύριες διαγώνιοι των ?? και ??.) Όπως έχουμε δει, οι μετατροπές 771#771 εφαρμόζονται ούτως ή άλλως πιο εύκολα όταν είναι σε αυτή τη μορφή (σε αντίθεση με τον ακριβή πολλαπλασιασμό πίνακα με διάνυσμα), οπότε τα διανύσματα v είναι τα μόνα που χρειαζόμαστε για να λύσουμε το αρχικό πρόβλημα των ελαχίστων τετραγώνων, όπως και καθένα από τα προβλήματα που ακολουθούν και έχουν τον ίδιο πίνακα αλλά διαφορετικά διανύσματα στο δεξί μέλος. Παρόλα αυτά, αν ο πίνακας ?? χρειάζεται να υπολογιστεί ακριβώς για κάποιον άλλο λόγο, τότε μπορεί να υπολογιστεί πολλαπλασιάζοντας κάθε μετατροπή 771#771 που παράγεται, με έναν πίνακα ο οποίος αρχικά είναι ο ταυτοτικός, αλλά αυτός ο υπολογισμός θα απαιτήσει επιπρόσθετο χώρο αποθήκευσης.


27#27

Παράδειγμα 3.5   Παραγοντοποίηση 782#782.

Θα παρουσιάσουμε την (? 783#783?) χρησιμοποιώντας την για να λύσουμε το τετραγωνικό πολυωνυμικό πρόβλημα (?784#784?) του παραδείγματος 3.2, με


785#785

Το (786#786) διάνυσμα 787#787 για την απαλοιφή των κάτω από την διαγώνιο στοιχείων της πρώτης στήλης του ?????? είναι


788#788

Η εφαρμογή του αλγορίθμου μετατροπής Householder 789#789 μας δίνει τον τροποποιημένο πίνακα και το αριστερό μέλος


790#790

Το διάνυσμα 771#771 791#791 για την απαλοιφή των κάτω από την διαγώνιο στοιχείων για τη δεύτερη στήλη του ?????? είναι


792#792

Η εφαρμογή του αλγορίθμου μετατροπής 771#771 793#793 μας δίνει


794#794

Το διάνυσμα 771#771 795#795 για την απαλοιφή των κάτω από την διαγώνιο στοιχείων για την τρίτη στήλη του 796#796 είναι


797#797

Η εφαρμογή του αλγορίθμου μετατροπής 771#771 798#798 μας δίνει


799#799

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


743#743


27#27


next up previous contents
Next: Περιστροφή Up: Μέθοδοι Ορθογωνοποίησης Previous: Paragwntopoihsh QR   Contents
Manolis Vavalis 2000-03-24