Ξεχάσατε τον κωδικό σας?
Οδήγηση στηλών
Document Actions
Next: Σύγκριση Μεθόδων Up: Μέθοδοι Ορθογωνοποίησης Previous: Έλλειψη διαστάσεων. Contents
Οδήγηση στηλών
Τις στήλες ενός πίνακα μπορούμε να τις δούμε ως ένα σύνολο από μη διατεταγμένα διανύσματα από το οποίο θέλουμε να συλλέξουμε το μέγιστο γραμμικώς ανεξάρτητο υποσύνολο. Αντί να επεξεργαζόμαστε τις στήλες με τη φυσική τους σειρά κατά τον υπολογισμό της παραγοντοποίησης 8#8, συλλέγουμε σε κάθε στάδιο, προκειμένου να την μειώσουμε, τη στήλη που έχει τη μεγαλύτερη Ευκλείδεια νόρμα, και η οποία ανήκει στον υποπίνακα που απομένει αμείωτος. Αυτή η στήλη αλλάζει θέση (άμεσα ή έμμεσα) με τη στήλη που ακολουθεί στη φυσική σειρά και τότε μηδενίζονται τα στοιχεία της που βρίσκονται κάτω από την διαγώνιο με τον συνήθη τρόπο. Η τροποποίηση που απαιτείται για να γίνει αυτό πρέπει να εφαρμοστεί στις υπόλοιπες αμείωτες στήλες, και η διαδικασία επαναλαμβάνεται. Η διαδικασία που μόλις περιγράψαμε λέγεται οδήγηση στηλών.
Αν 875#875, τότε μετά από 432#432 βήματα αυτής της διαδικασίας, οι νόρμες των στηλών που έχουν απομείνει αμείωτες θα είναι μηδέν (ή «αμελητέες», όπως θα λέγαμε στην αριθμητική πεπερασμένης ακρίβειας) κάτω από τη στήλη 432#432. Άρα, έχουμε παράγει μία ορθογώνια παραγοντοποίηση της μορφής
όπου ο 777#777 είναι 877#877, άνω τριγωνικός, και μη ιδιάζον, και ο 398#398 είναι ένας πίνακας εναλλαγής που υλοποιεί τις εναλλαγές στηλών. Σε αυτό το σημείο, μία βασική λύση (π.χ., μία λύση με μόνο 432#432 μη μηδενικά στοιχεία) στο πρόβλημα ελαχίστων τετραγώνων 878#878 μπορεί να υπολογιστεί λύνοντας το τριγωνικό σύστημα 879#879, όπου 655#655 είναι ένα διάνυσμα που αποτελείται από τα πρώτα 432#432 στοιχεία του 880#880, οπότε παίρνουμε
Σε ότι έχει να κάνει με (?784#784?), αυτή η διαδικασία έχει το πλεονέκτημα ότι αγνοεί στοιχεία του μοντέλου τα οποία είναι περιττά ή όχι καλά ορισμένα. Αν, παρόλα αυτά, επιθυμούμε μία λύση ελάχιστης νόρμας, μπορεί να υπολογιστεί πληρώνοντας το κόστος κάποιων επιπρόσθετων διαδικασιών (από τα δεξιά) για να απαλείψουμε και το 882#882.
Στην πράξη, η διάσταση του 369#369 είναι συνήθως άγνωστη, οπότε η μέθοδος οδήγησης στηλών χρησιμοποιείται για να βρούμε τη διάσταση παρατηρώντας τις νόρμες των στηλών που παραμένουν αμείωτες και διαλύοντας την παραγοντοποίηση όταν η μέγιστη τιμή πέσει κάτω από κάποιο σχετικό όριο απόκλισης.
Manolis Vavalis 2000-03-24
