next up previous contents
Next: Ορθογωνιοποίηση Up: Μέθοδοι Ορθογωνοποίησης Previous: ?   Contents

Περιστροφή 4#4

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

Ψάχνουμε για έναν ορθογώνιο πίνακα που απαλείφει μόνο ένα δοσμένο στοιχείο ενός διανύσματος. Ένας τέτοιος πίνακας είναι μία περιοχή περιστροφής, που συχνά λέγεται περιστροφή 4#4 όταν αναφερόμαστε στην παραγοντοποίηση 8#8. Δοσμένου ενός δισδιάστατου διανύσματος 801#801, θέλουμε να επιλέξουμε δύο αριθμούς 655#655 και 802#802, οι οποίοι μπορούν να αναπαρασταθούν από το συνημίτονο και το ημίτονο της γωνίας που δημιουργείται από την περιστροφή, τέτοια ώστε


803#803

με 804#804, ή, ισοδύναμα, 805#805. Στην πράξη, θα περιστρέψουμε το 641#641 τόσο ώστε να γίνει παράλληλο στον πρώτο άξονα αναφοράς. Τότε το δεύτερο στοιχείο του θα μηδενιστεί. Η παραπάνω ισότητα μπορεί να γραφτεί ως


806#806

Τώρα μπορούμε να εφαρμόσουμε την απαλοιφή 1#1 σε αυτό το σύστημα για να πάρουμε το τριγωνικό σύστημα


807#807

Η προς τα πίσω αντικατάσταση θα δώσει


808#808

Τελικά, η απαίτηση ότι 804#804 ή ότι 805#805 δείχνει ότι


809#809

Όπως και με την μετατροπή 771#771, η περιττή υπερχείλιση ή υποεκχείλιση μπορεί να αποφευχθεί με την κατάλληλη κλιμάκωση. Αν 810#810, τότε μπορούμε να δουλέψουμε με την εφαπτομένη της γωνίας περιστροφής, 811#811, έτσι ώστε το συνημίτονο και το ημίτονο δίνεται από τις


812#812

Αν, από την άλλη, 813#813, τότε μπορούμε να χρησιμοποιήσουμε τους αντίστοιχους τύπους που εμπλέκουν τη συνεφαπτομένη 814#814, για να πάρουμε


815#815

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


27#27

Παράδειγμα 3.6   Περιστροφή 816#816. Για να παρουσιάσουμε τη μέθοδο που μόλις περιγράψαμε, θα υλοποιήσουμε μία περιστροφή 4#4 η οποία απαλείφει το δεύτερο στοιχείο του διανύσματος


817#817

Για αυτό το πρόβλημα, μπορούμε να υπολογίσουμε με ασφάλεια το συνημίτονο και το ημίτονο, για να πάρουμε


818#818

ή, ισοδύναμα, μπορούμε να χρησιμοποιήσουμε την εφαπτομένη 819#819 για να πάρουμε


820#820

Άρα, η περιστροφή δίνεται από


821#821

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


822#822

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


27#27

Έχουμε δει πώς να σχεδιάζουμε μία περιοχή περιστροφής για να απαλείψουμε ένα δοσμένο στοιχείο ενός διανύσματος στις δύο διαστάσεις. Για να απαλείψουμε ένα επιλεγμένο στοιχείο ενός διανύσματος στις 366#366 διαστάσεις, μπορούμε να εφαρμόσουμε την ίδια τεχνική περιστρέφοντας το συγκεκριμένο στοιχείο, έστω 573#573, μαζί με ένα άλλο στοιχείο, έστω 824#824. Τα δύο επιλεγμένα στοιχεία ενός διανύσματος χρησιμοποιούνται όπως και πριν για να υπολογίσουν τον κατάλληλο 387#387 πίνακα περιστροφής, ο οποίος τότε περιορίζεται σε έναν 387#387 υποπίνακα με γραμμές και στήλες τα 824#824 και 573#573 του 366#366-διάστατου ταυτοτικού πίνακα, όπως παρουσιάζεται εδώ για την περίπτωση 825#825 :


826#826

Χρησιμοποιώντας μία ακολουθία τέτοιων περιστροφών 4#4, μπορούμε επιλεκτικά και συστηματικά να απαλείψουμε εισόδους του πίνακα 369#369 για να τον μειώσουμε σε έναν πίνακα άνω τριγωνικής μορφής. Ο μόνος περιορισμός στην σειρά με την οποία απαλείφουμε τα στοιχεία είναι ότι θα πρέπει να αποφύγουμε να ξαναεισάγουμε μη μηδενικές τιμές στις θέσεις του πίνακα, οι οποίες έχουν απαλειφθεί πιο πριν, όμως και αυτό μπορεί να επιτευχθεί με έναν αριθμό από διαφορετικές σειρές απαλοιφής. Για άλλη μία φορά, το ίδιο το προϊόν όλων των περιστροφών είναι ένας ορθογώνιος πίνακας ο οποίος μας δίνει την επιθυμητή παραγοντοποίηση 8#8.

Μία απευθείας εκτέλεση της μεθόδου 4#4 για την επίλυση γενικών γραμμικών προβλημάτων ελαχίστων τετραγώνων απαιτεί περίπου 50 τοις εκατό περισσότερη δουλειά από τη μέθοδο 771#771. Επίσης απαιτεί περισσότερο χώρο αποθήκευσης, αφού κάθε περιστροφή απαιτεί δύο αριθμούς, 655#655 και 802#802 για να οριστεί (και άρα δεν μπορούμε να ικανοποιήσουμε και την αποθήκευση του μηδενισμένου στοιχείου 827#827).

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

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


27#27

Παράδειγμα 3.7   ΠΑΡΑΓΟΝΤΟΠΟΙΗΣΗ 829#829. Θα δείξουμε την παραγοντοποίηση 8#8 χρησιμοποιώντας την για να λύσουμε το τετραγωνικό πολυωνυμικό πρόβλημα (?784#784?) του παραδείγματος 3.2, με:


830#830

Μπορούμε να απαλείψουμε το στοιχείο (5, 1) του 369#369 χρησιμοποιώντας μία περιστροφή 4#4 βασισμένη στο πέμπτο και έκτο στοιχείο της πρώτης στήλης. Η κατάλληλη περιστροφή δίνεται από τα 831#831 Εφαρμόζοντας αυτή την περιστροφή 832#832 στα 369#369 και 365#365 παίρνουμε


833#833

και


834#834

Στη συνέχεια απαλείφουμε το στοιχείο (4, 1) χρησιμοποιώντας μία περιστροφή 4#4 βασισμένη στο τρίτο και τέταρτο στοιχείο της πρώτης στήλης. Η κατάλληλη περιστροφή δίνεται από τα 835#835. Εφαρμόζοντας αυτή την περιστροφή 836#836 παίρνουμε


837#837

και

838#838

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


839#839

όπου 840#840 είναι το προϊόν όλων των περιστροφών 4#4 που χρησιμοποιήθηκαν. Τώρα μπορούμε να λύσουμε το άνω τριγωνικό σύστημα με προς τα πίσω αντικατάσταση για να πάρουμε


743#743


27#27


next up previous contents
Next: Ορθογωνιοποίηση Up: Μέθοδοι Ορθογωνοποίησης Previous: ?   Contents
Manolis Vavalis 2000-03-24