next up previous contents
Next: Έλλειψη διαστάσεων. Up: Μέθοδοι Ορθογωνοποίησης Previous: Περιστροφή   Contents

Ορθογωνιοποίηση 5#5

Μία άλλη μέθοδος υπολογισμού της παραγοντοποίησης 8#8 είναι η διαδικασία ορθογωνιοποίησης 6#6, την οποία μπορεί να έχετε συναντήσει σε ένα υπολογιστικό μάθημα ή σε ένα μάθημα γραμμικής άλγεβρας. Δοσμένων δύο διανυσμάτων 841#841 και 842#842, μπορούμε να καταλήξουμε σε δύο διανύσματα 843#843 και 844#844 με ορθογώνιες νόρμες τα οποία εκτείνονται στον ίδιο υπόχωρο αν ορθογωνιοποιήσουμε τι ένα από τα δοσμένα διανύσματα ως προς το άλλο, όπως φαίνεται στο σχήμα 3.3.

Αυτή η διαδικασία μπορεί να επεκταθεί για όσα διανύσματα 436#436 επιθυμούμε (ως τη διάσταση του διαστήματος) με το να ορθογωνιοποιούμε κάθε διαδοχικό διάνυσμα ως προς όλα τα προηγούμενα, εφαρμόζοντας την κλασσική διαδικασία ορθογωνιοποίησης 6#6:


		 845#845

846#846
847#847
848#848
849#849
850#850
851#851
849#849

Figure: Ένα από τα βήματα της ορθογωνιοποίησης 6#6
852#852

Αν θεωρήσουμε τα 436#436 ως τα στοιχεία των στηλών του πίνακα 369#369, τότε τα 853#853 που προκύπτουν είναι οι στήλες του 495#495 και τα 854#854 είναι στοιχεία του άνω τριγωνικού πίνακα 777#777 στην παραγοντοποίηση 8#8 του 369#369.

Δυστυχώς, η κλασσική διαδικασία 6#6 απαιτεί ξεχωριστό χώρο αποθήκευσης για τα 363#363, 495#495, και 777#777 επειδή τα αρχικά 436#436 χρειάζονται για τον εσωτερικό βρόγχο, και άρα τα 853#853 δεν μπορούν να υπερεγγράψουν τις στήλες του 369#369. Αυτό το μειονέκτημα μπορεί, παρόλα αυτά, να ξεπεραστεί αν ορθογωνιοποιούμε καθένα από τα επιλεγμένα διανύσματα με τη σειρά, ως προς τα επόμενα διανύσματα, παράγοντας ως αποτέλεσμα τον άνω τριγωνικό πίνακα 777#777 μέσω γραμμών αντί μέσω στηλών. Αυτή η αναθεώρηση του τρόπου υπολογισμού είναι γνωστή ως τροποποιημένη ορθογωνιοποίηση 6#6:


		 845#845

855#855
856#856
857#857
858#858
859#859
849#849
849#849

Συνεχώς γράφουμε τα 436#436 και 853#853 χωριστά ώστε να είναι πιο ξεκάθαρα, αλλά τώρα μπορούν, στην πραγματικότητα, να μοιράζονται τις ίδιες θέσεις μνήμης. (Ένας προγραμματιστής θα είχε φτιάξει τον αλγόριθμο με αυτή τη μορφή ευθύς εξ' αρχής.) Δυστυχώς, εξακολουθεί να απαιτείται ξεχωριστή θέση μνήμης για τους 495#495 και 777#777, ένα μειονέκτημα της ίδιας μορφής με αυτό της μεθόδου 771#771, για την οποία οι 495#495 και 777#777 μπορούν να μοιράζονται τον ίδιο χώρο μνήμης όπου αρχικά φυλασσόταν ο 369#369. Από την άλλη μεριά, η μέθοδος 6#6 παρέχει μία ξεκάθαρη αναπαράσταση του πίνακα 495#495, ο οποίος, αν το επιθυμούσαμε, θα απαιτούσε επιπλέον χώρο αποθήκευσης με τη μέθοδο 771#771.

Εκτός από το γεγονός ότι απαιτεί λιγότερο χώρο αποθήκευσης από ότι η κλασσική διαδικασία, να επιπρόσθετο πλεονέκτημα της τροποποιημένης 6#6 είναι ότι είναι αριθμητικά ανώτερη της κλασσικής διαδικασίας 6#6: οι δύο διαδικασίες είναι μαθηματικά ισοδύναμες, αλλά στην αριθμητική πεπερασμένης ακρίβειας η κλασσική διαδικασία τείνει να χάσει την ορθογώνια σχέση που έχουν μεταξύ τους τα 853#853 που υπολογίσαμε. Επίσης, η τροποποιημένη διαδικασία επιτρέπει ακόμα και την οδήγηση στηλών για να αντιμετωπίσει την πιθανή έλλειψη κάποιας διάστασης (βλ. Ενότητα 3.4.8). Παρόλο που η τροποποιημένη διαδικασία 6#6 έχει πλεονεκτήματα σε κάποιες περιπτώσεις, για την επίλυση προβλημάτων ελαχίστων τετραγώνων είναι κατά κάποιο τρόπο κατώτερη της μεθόδου 771#771 ως προς το χώρο αποθήκευσης που χρειάζεται, την εργασία που απαιτείται και την ακρίβεια.


27#27

Παράδειγμα 3.8   ΠΑΡΑΓΟΝΤΟΠΟΙΗΣΗ 860#860.

Θα δείξουμε την τροποποιημένη ορθογωνιοποίηση 6#6 με το να λύσουμε ξανά το τετραγωνικό πολυωνυμικό πρόβλημα εύρεσης δεδομένων του παραδείγματος 3.2, με


830#830

Κανονικοποιώντας την πρώτη στήλη του 369#369, μπορούμε να υπολογίσουμε


861#861

Ορθογωνιοποιώντας την πρώτη στήλη ως προς τις υπόλοιπες στήλες, παίρνουμε


862#862

ώστε ο πίνακας μετασχηματίζεται στον


863#863

Κανονικοποιώντας τη δεύτερη στήλη, υπολογίζουμε


864#864

Ορθογωνιοποιώντας τη δεύτερη στήλη ως προς την τρίτη στήλη, παίρνουμε


865#865

ώστε η τρίτη στήλη δεν επηρεάζεται. Τελικά, κανονικοποιούμε την τρίτη στήλη


866#866

Άρα έχουμε πάρει την παραγοντοποίηση 8#8


867#867

Το μετασχηματισμένο δεξί μέλος το παίρνουμε από


868#868

Τώρα μπορούμε να λύσουμε το άνω τριγωνικό σύστημα 869#869 με προς τα πίσω αντικατάσταση για να πάρουμε


870#870


27#27


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