Μέθοδος ορθοκανονικοποίησης των Gram–Schmidt

Η διανυσματική προβολή ενός διανύσματος  σε ένα μη μηδενικό διάνυσμα  ορίζεται ως εξής

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

 Η μέθοδος Gram-Schmidt

Η διανυσματική προβολή ενός διανύσματος  σε ένα μη μηδενικό διάνυσμα  ορίζεται ως εξής 

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

Με βάση τα διανύσματα   η μέθοδος Gram-Schmidt ορίζει τα διανύσματα  
 as follows:

Η ακολουθία  είναι το απαιτούμενο σύστημα ορθογώνιων διανυσμάτων και τα κανονικοποιημένα διανύσματα  σχηματίζουν ένα ορθοκανονικό σύνολο. Ο υπολογισμός της ακολουθίας  είναι γνωστός ως ορθογωνιοποίηση Gram-Schmidt, και ο υπολογισμός της ακολουθίας  είναι γνωστός ως ορθοκανονικοποίηση Gram-Schmidt.

Για να ελεγχθεί ότι αυτοί οι τύποι δίνουν μια ορθογώνια ακολουθία, υπολογίζουμε πρώτα  αντικαθιστώντας τον παραπάνω τύπο για το u2:: παίρνουμε μηδέν. Στη συνέχεια χρησιμοποιούμε αυτό για να υπολογίσουμε  πάλι αντικαθιστώντας τον τύπο για το u3: παίρνουμε μηδέν. Η γενική απόδειξη γίνεται με μαθηματική επαγωγή.

Η μέθοδος Gram-Schmidt εφαρμόζεται επίσης σε μια γραμμικά ανεξάρτητη μετρήσιμη άπειρη ακολουθία  . Το αποτέλεσμα είναι μια ορθογώνια (ή ορθοκανονική) ακολουθία  τέτοια ώστε για φυσικό αριθμό n: το αλγεβρικό εύρος των  είναι το ίδιο με αυτό των .

Εάν η μέθοδος Gram-Schmidt εφαρμόζεται σε μια γραμμικά εξαρτημένη ακολουθία, εξάγει το διάνυσμα  στο i-th βήμα, υποθέτοντας ότι το  είναι ένας γραμμικός συνδυασμός των . Εάν πρόκειται να δημιουργηθεί μια ορθοκανονική βάση, τότε ο αλγόριθμος θα πρέπει να εξετάσει για μηδενικά διανύσματα στην έξοδο και να τα απορρίψει, διότι κανένα πολλαπλάσιο ενός μηδενικού διανύσματος δεν μπορεί να έχει μήκος 1. Ο αριθμός των διανυσμάτων που εξάγονται από τον αλγόριθμο θα είναι τότε η διάσταση του χώρου που καλύπτεται από τις αρχικές εισόδους.

Μια παραλλαγή της μεθόδου Gram-Schmidt που χρησιμοποιεί τη διαπεραστική αναδρομή και εφαρμόζεται σε μια (ενδεχομένως μη αναρίθμητη) άπειρη ακολουθία διανυσμάτων  δίνει ένα σύνολο ορθοκανονικών διανυσμάτων  με  έτσι ώστε για κάθε , η ολοκλήρωση της έκτασης της  είναι η ίδια με εκείνη του . Ειδικότερα, όταν εφαρμόζεται σε μια (αλγεβρική) βάση ενός χώρου Hilbert (ή, γενικότερα, σε μια βάση οποιουδήποτε πυκνού υποχώρου), δίνει μια (λειτουργική-αναλυτική) ορθοκανονική βάση. Σημειώστε ότι στη γενική περίπτωση συχνά ισχύει η αυστηρή ανισότητα , ακόμη και αν το αρχικό σύνολο ήταν γραμμικά ανεξάρτητο, και η έκταση του  δεν χρειάζεται να είναι υποχώρος της έκτασης του  (μάλλον, είναι ένας υποχώρος της ολοκλήρωσής του).

Παράδειγμα

Ευκλείδειος χώρος
Ας θεωρήσουμε το ακόλουθο σύνολο διανυσμάτων στο

 (με το συμβατικό εσωτερικό γινόμενο)

Εφαρμόστε τώρα τη μέθοδο Gram-Schmidt για να λάβετε ένα σύνολο ορθογώνιων διανυσμάτων:

Ελέγχουμε ότι τα διανύσματα   και   είναι πράγματι ορθογώνια:

σημειώνοντας ότι αν το τετραγωνικό γινόμενο δύο διανυσμάτων είναι 0, τότε είναι ορθογώνια.

Ιδιότητες

Σημειώστε με   το αποτέλεσμα της εφαρμογής της διαδικασίας Gram-Schmidt σε μια συλλογή διανυσμάτων . Έτσι προκύπτει ένας χάρτης GS : .

Έχει τις ακόλουθες ιδιότητες:
 Είναι συνεχής
 Διατηρεί τον προσανατολισμό με την έννοια ότι .
 Συναλλάσσεται με ορθογώνιους χάρτες:

Έστω  να είναι ορθογώνιο (ως προς το δεδομένο εσωτερικό γινόμενο). Τότε έχουμε

Περαιτέρω, μια παραμετρική εκδοχή της μεθόδου Gram-Schmidt δίνει μια (ισχυρή) παραμορφωτική ανάκληση της γενικής γραμμικής ομάδας  στην ορθογώνια ομάδα .

Αριθμητική σταθερότητα
Όταν αυτή η διαδικασία εκτελείται σε υπολογιστή, τα διανύσματα   συχνά δεν είναι αρκετά ορθογώνια, λόγω σφαλμάτων στρογγυλοποίησης. Για τη μέθοδο Gram-Schmidt που περιγράφηκε παραπάνω (μερικές φορές αναφέρεται ως "κλασική μέθοδος Gram-Schmidt"), αυτή η απώλεια ορθογωνιότητας είναι ιδιαίτερα σοβαρή, γι' αυτό και η (κλασική) μέθοδος Gram-Schmidt χαρακτηρίζεται αριθμητικά ασταθής.

Η μέθοδος Gram-Schmidt μπορεί να σταθεροποιηθεί με μια μικρή τροποποίηση- αυτή η έκδοση ονομάζεται μερικές φορές τροποποιημένη Gram-Schmidt ή MGS. Αυτή η προσέγγιση δίνει το ίδιο αποτέλεσμα με τον αρχικό τύπο στην ακριβή αριθμητική και εισάγει μικρότερα σφάλματα στην αριθμητική ακριβείας.
Αντί για τον υπολογισμό του διανύσματος  ως 

υπολογίζεται ως εξής

Αυτή η μέθοδος χρησιμοποιείται στην προηγούμενη κινούμενη εικόνα, όταν το ενδιάμεσο διάνυσμα  χρησιμοποιείται κατά την ορθογωνοποίηση του μπλε διανύσματος .

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

Αλγόριθμος
Ο ακόλουθος αλγόριθμος MATLAB υλοποιεί την κλασική ορθοκανονικοποίηση Gram-Schmidt. Τα διανύσματα   (στήλες του πίνακα V, έτσι ώστε V(:,j) να είναι το jοστό διάνυσμα) αντικαθίστανται από ορθοκανονικά διανύσματα (στήλες του U) που καλύπτουν τον ίδιο υποχώρο.

function U = gramschmidt(V)
    [n, k] = size(V);
    U = zeros(n,k);
    U(:,1) = V(:,1) / norm(V(:,1));
    for i = 2:k
        U(:,i) = V(:,i);
        for j = 1:i-1
            U(:,i) = U(:,i) - (U(:,j)'*U(:,i)) * U(:,j);
        end
        U(:,i) = U(:,i) / norm(U(:,i));
    end
end

Το κόστος αυτού του αλγορίθμου είναι ασυμπτωτικά  πράξεις κινητής υποδιαστολής, όπου  είναι η διαστατικότητα των διανυσμάτων.

 Μέσω απαλοιφής Γκάους 
Εάν οι γραμμές  γράφονται ως πίνακας , τότε η εφαρμογή της απαλοιφής Γκάους στον επαυξημένο πίνακα  θα παράγει τα ορθογωνιοποιημένα διανύσματα στη θέση του . Ωστόσο, ο πίνακας  πρέπει να μετατραπεί σε μορφή echelon γραμμής, χρησιμοποιώντας μόνο την πράξη γραμμής της πρόσθεσης ενός κλιμακωτού πολλαπλάσιου μιας γραμμής σε μια άλλη. Για παράδειγμα, λαμβάνοντας όπως παραπάνω, έχουμε

Και αν το αναγάγουμε αυτό σε μορφή σειρών επιπέδων παράγει

Τα κανονικοποιημένα διανύσματα είναι στη συνέχεια

όπως στο παραπάνω παράδειγμα.

 Προσδιοριστικός τύπος 
Το αποτέλεσμα της μεθόδου Gram-Schmidt μπορεί να εκφραστεί με έναν μη αναδρομικό τύπο χρησιμοποιώντας προσδιοριστές.

όπου D0=1 και, για j ≥ 1, Djείναι ο προσδιοριστής Gram

Σημειώστε ότι η έκφραση για το u'k είναι ένας "τυπικός" προσδιοριστής, δηλαδή ο πίνακας περιέχει και τα δύο κλιμάκια όσο και διανύσματα- η έννοια αυτής της έκφρασης ορίζεται ως το αποτέλεσμα μιας συνδιαστολής κατά μήκος της γραμμής των διανυσμάτων.

Ο προσδιοριστικός τύπος για τον Gram-Schmidt είναι υπολογιστικά πιο αργός (εκθετικά πιο αργός) από τους αναδρομικούς αλγορίθμους που περιγράφονται παραπάνω- έχει κυρίως θεωρητικό ενδιαφέρον.

Εκφραση με χρήση γεωμετρικής άλγεβρας

Εκφρασμένα με χρήση συμβολισμού που χρησιμοποιείται στη γεωμετρική άλγεβρα, τα μη ομαλοποιημένα αποτελέσματα της μεθόδου Gram-Schmidt εκφράζονται ως εξής

η οποία είναι ισοδύναμη με την έκφραση που χρησιμοποιεί τον τελεστή  που ορίζεται παραπάνω. Τα αποτελέσματα μπορούν ισοδύναμα να εκφραστούν ως 

η οποία είναι στενά συνδεδεμένη με την έκφραση με χρήση προσδιοριστικών παραγόντων παραπάνω.

ναλλακτικές λύσεις
Άλλοι αλγόριθμοι ορθογωνοποίησης χρησιμοποιούν μετασχηματισμούς Χάουσχολντερ ή περιστροφές Γκίβενς. Οι αλγόριθμοι που χρησιμοποιούν μετασχηματισμούς Χάουσχολντερ είναι πιο σταθεροί από τη σταθεροποιημένη μέθοδο Gram-Schmidt. Από την άλλη πλευρά, η μέθοδος Gram-Schmidt παράγει το j jοστό ορθογωνοποιημένο διάνυσμα μετά την th επανάληψη, ενώ η ορθογωνοποίηση που χρησιμοποιεί ανακλάσεις Χάουσχολντερ παράγει όλα τα διανύσματα μόνο στο τέλος. Αυτό καθιστά μόνο τη μέθοδο Gram-Schmidt εφαρμόσιμη για επαναληπτικές μεθόδους όπως η επανάληψη Αρνόλντι.

Μια άλλη λύση έχει ως κίνητρο τη χρήση της αποσύνθεσης Τσολέσκι για την αντιστροφή του πίνακα των κανονικών εξισώσεων σε γραμμικά ελάχιστα τετράγωνα. Έστω  ένας πίνακας πλήρους τάξης του οποίου οι στήλες πρέπει να είναι ορθογωνοποιημένες. Ο πίνακας  είναι ερμιτιανός και θετικά ορισμένος, οπότε μπορεί να γραφεί στη μορφή  χρησιμοποιώντας την αποσύνθεση Τσολέσκι. Ο κάτω τριγωνικός πίνακας  με αυστηρά θετικές διαγώνιες καταχωρήσεις είναι αντιστρέψιμος. Οι στήλες του πίνακα  είναι τότε ορθοκανονικές και καλύπτουν τον ίδιο υποχώρο με τις στήλες του αρχικού πίνακα . Η ρητή χρήση του γινομένου  καθιστά τον αλγόριθμο ασταθή, ιδιαίτερα αν ο αριθμός των όρων του γινομένου είναι μεγάλος. Παρ' όλα αυτά, ο αλγόριθμος αυτός χρησιμοποιείται στην πράξη και υλοποιείται σε ορισμένα λογισμικά λόγω της υψηλής αποδοτικότητας και απλότητας του.

Στην κβαντομηχανική υπάρχουν διάφορα σχήματα ορθογωνοποίησης με χαρακτηριστικά που είναι καλύτερα προσαρμοσμένα για ορισμένες εφαρμογές από τα αρχικά σχήματα Gram-Schmidt. Παρόλα αυτά, παραμένει ένας δημοφιλής και αποτελεσματικός αλγόριθμος ακόμα και για τους μεγαλύτερους υπολογισμούς ηλεκτρονικής δομής.

Εξωτερικοί Σύνδεσμοι  
 Harvey Mudd College Math Tutorial on the Gram-Schmidt algorithm
 Earliest known uses of some of the words of mathematics: G The entry "Gram-Schmidt orthogonalization" has some information and references on the origins of the method.
 Demos: Gram Schmidt process in plane and Gram Schmidt process in space
 Gram-Schmidt orthogonalization applet
 NAG Gram–Schmidt orthogonalization of n vectors of order m routine
 Proof: Raymond Puzio, Keenan Kidwell. "proof of Gram-Schmidt orthogonalization algorithm" (version 8). PlanetMath.org.

Πηγές
 .
 .
 .
 .

Παραπομπές




Κατηγορία:Γραμμική άλγεβρα 
Κατηγορία:Συναρτησιακή ανάλυση