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

Η τροποποιημένη μέθοδος Gram-Schmidt εκτελείται σε τρία γραμμικά ανεξάρτητα, μη ορθογώνια διανύσματα μιας βάσης για το R³. Πατήστε στην εικόνα για λεπτομέρειες. Η τροποποίηση εξηγείται στην ενότητα Αριθμητική σταθερότητα αυτού του άρθρου.

Η διανυσματική προβολή ενός διανύσματος $\mathbf {v}$ σε ένα μη μηδενικό διάνυσμα $\mathbf {u}$ ορίζεται ως εξής

$\operatorname {proj} _{\mathbf {u} }(\mathbf {v} )={\frac {\langle \mathbf {v} ,\mathbf {u} \rangle }{\langle \mathbf {u} ,\mathbf {u} \rangle }}\,\mathbf {u} ,$

όπου $\langle \mathbf {v} ,\mathbf {u} \rangle$ δηλώνει το εσωτερικό γινόμενο των διανυσμάτων $\mathbf {u}$ και $\mathbf {v}$. Αυτό σημαίνει ότι $\operatorname {proj} _{\mathbf {u} }(\mathbf {v} )$ είναι η ορθογώνια προβολή του $\mathbf {v}$ στην ευθεία που διατρέχει το $\mathbf {u}$. Αν $\mathbf {u}$ είναι το μηδενικό διάνυσμα, τότε $\operatorname {proj} _{\mathbf {u} }(\mathbf {v} )$ ορίζεται ως το μηδενικό διάνυσμα.

Η μέθοδος Gram-Schmidt

Η τροποποιημένη μέθοδος Gram-Schmidt εκτελείται σε τρία γραμμικά ανεξάρτητα, μη ορθογώνια διανύσματα μιας βάσης για το R'³. Κάντε κλικ στην εικόνα για λεπτομέρειες. Η τροποποίηση εξηγείται στην ενότητα Αριθμητική σταθερότητα αυτού του άρθρου.

Η διανυσματική προβολή ενός διανύσματος $\mathbf {v}$ σε ένα μη μηδενικό διάνυσμα $\mathbf {u}$ ορίζεται ως εξής $$\operatorname {proj} _{\mathbf {u} }(\mathbf {v} )={\frac {\langle \mathbf {v} ,\mathbf {u} \rangle }{\langle \mathbf {u} ,\mathbf {u} \rangle }}\,\mathbf {u} ,$$ όταν $\langle \mathbf {v} ,\mathbf {u} \rangle$ συμβολίζει το εσωτερικό γινόμενο των διανυσμάτων $\mathbf {u}$ και $\mathbf {v}$. Αυτό σημαίνει ότι $\operatorname {proj} _{\mathbf {u} }(\mathbf {v} )$ είναι η ορθογώνια προβολή του $\mathbf {v}$ στην ευθεία που διατρέχει το $\mathbf {u}$. Αν $\mathbf {u}$ είναι το μηδενικό διάνυσμα, τότε $\operatorname {proj} _{\mathbf {u} }(\mathbf {v} )$ ορίζεται ως το μηδενικό διάνυσμα.

Με βάση τα διανύσματα k $\mathbf {v} _{1},\ldots ,\mathbf {v} _{k}$ η μέθοδος Gram-Schmidt ορίζει τα διανύσματα $\mathbf {u} _{1},\ldots ,\mathbf {u} _{k}$ as follows: $${\begin{aligned}\mathbf {u} _{1}&=\mathbf {v} _{1},&\!\mathbf {e} _{1}&={\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}\\\mathbf {u} _{2}&=\mathbf {v} _{2}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{2}),&\!\mathbf {e} _{2}&={\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}\\\mathbf {u} _{3}&=\mathbf {v} _{3}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{3})-\operatorname {proj} _{\mathbf {u} _{2}}(\mathbf {v} _{3}),&\!\mathbf {e} _{3}&={\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\\\mathbf {u} _{4}&=\mathbf {v} _{4}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{4})-\operatorname {proj} _{\mathbf {u} _{2}}(\mathbf {v} _{4})-\operatorname {proj} _{\mathbf {u} _{3}}(\mathbf {v} _{4}),&\!\mathbf {e} _{4}&={\mathbf {u} _{4} \over \|\mathbf {u} _{4}\|}\\&{}\ \ \vdots &&{}\ \ \vdots \\\mathbf {u} _{k}&=\mathbf {v} _{k}-\sum _{j=1}^{k-1}\operatorname {proj} _{\mathbf {u} _{j}}(\mathbf {v} _{k}),&\!\mathbf {e} _{k}&={\frac {\mathbf {u} _{k}}{\|\mathbf {u} _{k}\|}}.\end{aligned}}$$

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

Για να ελεγχθεί ότι αυτοί οι τύποι δίνουν μια ορθογώνια ακολουθία, υπολογίζουμε πρώτα $\langle \mathbf {u} _{1},\mathbf {u} _{2}\rangle$ αντικαθιστώντας τον παραπάνω τύπο για το u₂:: παίρνουμε μηδέν. Στη συνέχεια χρησιμοποιούμε αυτό για να υπολογίσουμε $\langle \mathbf {u} _{1},\mathbf {u} _{3}\rangle$ πάλι αντικαθιστώντας τον τύπο για το u₃: παίρνουμε μηδέν. Η γενική απόδειξη γίνεται με μαθηματική επαγωγή.

Η μέθοδος Gram-Schmidt εφαρμόζεται επίσης σε μια γραμμικά ανεξάρτητη μετρήσιμη άπειρη ακολουθία {v_i}_i. Το αποτέλεσμα είναι μια ορθογώνια (ή ορθοκανονική) ακολουθία {u_i}_i τέτοια ώστε για φυσικό αριθμό n: το αλγεβρικό εύρος των v₁, ..., v_n είναι το ίδιο με αυτό των u₁, ..., u_n.

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

Μια παραλλαγή της μεθόδου Gram-Schmidt που χρησιμοποιεί τη διαπεραστική αναδρομή και εφαρμόζεται σε μια (ενδεχομένως μη αναρίθμητη) άπειρη ακολουθία διανυσμάτων $(v_{\alpha })_{\alpha <\lambda }$ δίνει ένα σύνολο ορθοκανονικών διανυσμάτων $(u_{\alpha })_{\alpha <\kappa }$ με $\kappa \leq \lambda$ έτσι ώστε για κάθε $\alpha \leq \lambda$, η ολοκλήρωση της έκτασης της $\{u_{\beta }:\beta <\min(\alpha ,\kappa )\}$ είναι η ίδια με εκείνη του $\{v_{\beta }:\beta <\alpha \}$.. Ειδικότερα, όταν εφαρμόζεται σε μια (αλγεβρική) βάση ενός χώρου Hilbert (ή, γενικότερα, σε μια βάση οποιουδήποτε πυκνού υποχώρου), δίνει μια (λειτουργική-αναλυτική) ορθοκανονική βάση. Σημειώστε ότι στη γενική περίπτωση συχνά ισχύει η αυστηρή ανισότητα $\kappa <\lambda$, ακόμη και αν το αρχικό σύνολο ήταν γραμμικά ανεξάρτητο, και η έκταση του $(u_{\alpha })_{\alpha <\kappa }$ δεν χρειάζεται να είναι υποχώρος της έκτασης του $(v_{\alpha })_{\alpha <\lambda }$ (μάλλον, είναι ένας υποχώρος της ολοκλήρωσής του).

Παράδειγμα

Ευκλείδειος χώρος

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

R² (με το συμβατικό εσωτερικό γινόμενο) $S=\left\{\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2\\2\end{bmatrix}}\right\}.$

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

$\mathbf {u} _{1}=\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}}$

$\mathbf {u} _{2}=\mathbf {v} _{2}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{2})={\begin{bmatrix}2\\2\end{bmatrix}}-\operatorname {proj} _{\left[{\begin{smallmatrix}3\\1\end{smallmatrix}}\right]}{\begin{bmatrix}2\\2\end{bmatrix}}={\begin{bmatrix}2\\2\end{bmatrix}}-{\frac {8}{10}}{\begin{bmatrix}3\\1\end{bmatrix}}={\begin{bmatrix}-2/5\\6/5\end{bmatrix}}.$

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

$\langle \mathbf {u} _{1},\mathbf {u} _{2}\rangle =\left\langle {\begin{bmatrix}3\\1\end{bmatrix}},{\begin{bmatrix}-2/5\\6/5\end{bmatrix}}\right\rangle =-{\frac {6}{5}}+{\frac {6}{5}}=0,$

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

$\mathbf {e} _{1}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}3\\1\end{bmatrix}}$

$\mathbf {e} _{2}={\frac {1}{\sqrt {40 \over 25}}}{\begin{bmatrix}-2/5\\6/5\end{bmatrix}}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}-1\\3\end{bmatrix}}.$

Ιδιότητες

Σημειώστε με $\operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})$ το αποτέλεσμα της εφαρμογής της διαδικασίας Gram-Schmidt σε μια συλλογή διανυσμάτων $\mathbf {v} _{1},\dots ,\mathbf {v} _{k}$. Έτσι προκύπτει ένας χάρτης GS : $\operatorname {GS} \colon (\mathbb {R} ^{n})^{k}\to (\mathbb {R} ^{n})^{k}$.

Έχει τις ακόλουθες ιδιότητες:

• Είναι συνεχής
• Διατηρεί τον προσανατολισμό με την έννοια ότι $\operatorname {or} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})=\operatorname {or} (\operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k}))$.
• Συναλλάσσεται με ορθογώνιους χάρτες:

Έστω $g\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}$ να είναι ορθογώνιο (ως προς το δεδομένο εσωτερικό γινόμενο). Τότε έχουμε

$\operatorname {GS} (g(\mathbf {v} _{1}),\dots ,g(\mathbf {v} _{k}))=\left(g(\operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})_{1}),\dots ,g(\operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})_{k})\right)$

Περαιτέρω, μια παραμετρική εκδοχή της μεθόδου Gram-Schmidt δίνει μια (ισχυρή) παραμορφωτική ανάκληση της γενικής γραμμικής ομάδας $\mathrm {GL} (\mathbb {R} ^{n})$ στην ορθογώνια ομάδα $O(\mathbb {R} ^{n})$.

Αριθμητική σταθερότητα

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

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

$\mathbf {u} _{k}=\mathbf {v} _{k}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{k})-\operatorname {proj} _{\mathbf {u} _{2}}(\mathbf {v} _{k})-\cdots -\operatorname {proj} _{\mathbf {u} _{k-1}}(\mathbf {v} _{k}),$

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

${\begin{aligned}\mathbf {u} _{k}^{(1)}&=\mathbf {v} _{k}-\operatorname {proj} _{\mathbf {u} _{1}}(\mathbf {v} _{k}),\\\mathbf {u} _{k}^{(2)}&=\mathbf {u} _{k}^{(1)}-\operatorname {proj} _{\mathbf {u} _{2}}\left(\mathbf {u} _{k}^{(1)}\right),\\&\;\;\vdots \\\mathbf {u} _{k}^{(k-2)}&=\mathbf {u} _{k}^{(k-3)}-\operatorname {proj} _{\mathbf {u} _{k-2}}\left(\mathbf {u} _{k}^{(k-3)}\right),\\\mathbf {u} _{k}^{(k-1)}&=\mathbf {u} _{k}^{(k-2)}-\operatorname {proj} _{\mathbf {u} _{k-1}}\left(\mathbf {u} _{k}^{(k-2)}\right),\\\mathbf {e} _{k}&={\frac {\mathbf {u} _{k}^{(k-1)}}{\left\|\mathbf {u} _{k}^{(k-1)}\right\|}}\end{aligned}}$

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

Ακολουθεί μια άλλη περιγραφή του τροποποιημένου αλγορίθμου. Δεδομένων των διανυσμάτων $v_{1},v_{2},\dots ,v_{n}$, στο πρώτο βήμα μας παράγουμε τα διανύσματα $v_{1},v_{2}^{(1)},\dots ,v_{n}^{(1)}$ αφαιρώντας συνιστώσες κατά μήκος της διεύθυνσης του $v_{1}$. Σε τύπους,$v_{k}^{(1)}:=v_{k}-{\frac {\langle v_{k},v_{1}\rangle }{\langle v_{1},v_{1}\rangle }}v_{1}$. Μετά από αυτό το βήμα έχουμε ήδη δύο από τα επιθυμητά ορθογώνια διανύσματα $u_{1},\dots ,u_{n}$, δηλαδή $u_{1}=v_{1},u_{2}=v_{2}^{(1)}$, αλλά κάναμε και $v_{3}^{(1)},\dots ,v_{n}^{(1)}$ ήδη ορθογώνια προς $u_{1}$. Στη συνέχεια, ορθογωνικοποιούμε αυτά τα υπόλοιπα διανύσματα κατά $u_{2}=v_{2}^{(1)}$. Αυτό σημαίνει ότι υπολογίζουμε τα $v_{3}^{(2)},v_{4}^{(2)},\dots ,v_{n}^{(2)}$ με αφαίρεση $v_{k}^{(2)}:=v_{k}^{(1)}-{\frac {\langle v_{k}^{(1)},u_{2}\rangle }{\langle u_{2},u_{2}\rangle }}u_{2}$. Τώρα έχουμε αποθηκεύσει τα διανύσματα $v_{1},v_{2}^{(1)},v_{3}^{(2)},v_{4}^{(2)},\dots ,v_{n}^{(2)}$ όπου τα τρία πρώτα διανύσματα είναι ήδη $u_{1},u_{2},u_{3}$ και τα υπόλοιπα διανύσματα είναι ήδη ορθογώνια προς τα $u_{1},u_{2}$. Όπως θα πρέπει να είναι σαφές τώρα, το επόμενο βήμα ορθογωνιοποιεί τα $v_{4}^{(2)},\dots ,v_{n}^{(2)}$ έναντι του $u_{3}=v_{3}^{(2)}$.Προχωρώντας με αυτόν τον τρόπο βρίσκουμε το πλήρες σύνολο των ορθογώνιων διανυσμάτων $u_{1},\dots ,u_{n}$. Αν επιθυμούμε ορθοκανονικά διανύσματα, τότε κανονικοποιούμε καθώς προχωράμε, έτσι ώστε οι παρονομαστές στους τύπους αφαίρεσης να μετατραπούν σε μονάδες.

Αλγόριθμος

Ο ακόλουθος αλγόριθμος MATLAB υλοποιεί την κλασική ορθοκανονικοποίηση Gram-Schmidt. Τα διανύσματα v₁, ..., v_k (στήλες του πίνακα 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

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

Μέσω απαλοιφής Γκάους

Εάν οι γραμμές {v₁, ..., v_k} γράφονται ως πίνακας $A$, τότε η εφαρμογή της απαλοιφής Γκάους στον επαυξημένο πίνακα $\left[AA^{\mathsf {T}}|A\right]$ θα παράγει τα ορθογωνιοποιημένα διανύσματα στη θέση του $A$. Ωστόσο, ο πίνακας $AA^{\mathsf {T}}$ πρέπει να μετατραπεί σε μορφή echelon γραμμής, χρησιμοποιώντας μόνο την πράξη γραμμής της πρόσθεσης ενός κλιμακωτού πολλαπλάσιου μιας γραμμής σε μια άλλη. Για παράδειγμα, λαμβάνοντας$\mathbf {v} _{1}={\begin{bmatrix}3&1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2&2\end{bmatrix}}$ όπως παραπάνω, έχουμε

$\left[AA^{\mathsf {T}}|A\right]=\left[{\begin{array}{rr|rr}10&8&3&1\\8&8&2&2\end{array}}\right]$

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

$\left[{\begin{array}{rr|rr}1&.8&.3&.1\\0&1&-.25&.75\end{array}}\right]$

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

$\mathbf {e} _{1}={\frac {1}{\sqrt {.3^{2}+.1^{2}}}}{\begin{bmatrix}.3&.1\end{bmatrix}}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}3&1\end{bmatrix}}$

$\mathbf {e} _{2}={\frac {1}{\sqrt {.25^{2}+.75^{2}}}}{\begin{bmatrix}-.25&.75\end{bmatrix}}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}-1&3\end{bmatrix}},$

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

Προσδιοριστικός τύπος

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

$\mathbf {e} _{j}={\frac {1}{\sqrt {D_{j-1}D_{j}}}}{\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j-1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j-1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\mathbf {v} _{2}&\cdots &\mathbf {v} _{j}\end{vmatrix}}$

$\mathbf {u} _{j}={\frac {1}{D_{j-1}}}{\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j-1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j-1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\mathbf {v} _{2}&\cdots &\mathbf {v} _{j}\end{vmatrix}}$

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

$D_{j}={\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j}\rangle \end{vmatrix}}.$

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

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

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

Εκφρασμένα με χρήση συμβολισμού που χρησιμοποιείται στη γεωμετρική άλγεβρα, τα μη ομαλοποιημένα αποτελέσματα της μεθόδου Gram-Schmidt εκφράζονται ως εξής $\mathbf {u} _{k}=\mathbf {v} _{k}-\sum _{j=1}^{k-1}(\mathbf {v} _{k}\cdot \mathbf {u} _{j})\mathbf {u} _{j}^{-1}\ ,$ η οποία είναι ισοδύναμη με την έκφραση που χρησιμοποιεί τον τελεστή $\operatorname {proj}$ που ορίζεται παραπάνω. Τα αποτελέσματα μπορούν ισοδύναμα να εκφραστούν ως $\mathbf {u} _{k}=\mathbf {v} _{k}\wedge \mathbf {v} _{k-1}\wedge \cdot \cdot \cdot \wedge \mathbf {v} _{1}(\mathbf {v} _{k-1}\wedge \cdot \cdot \cdot \wedge \mathbf {v} _{1})^{-1},$ η οποία είναι στενά συνδεδεμένη με την έκφραση με χρήση προσδιοριστικών παραγόντων παραπάνω.

ναλλακτικές λύσεις

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

Μια άλλη λύση έχει ως κίνητρο τη χρήση της αποσύνθεσης Τσολέσκι για την αντιστροφή του πίνακα των κανονικών εξισώσεων σε γραμμικά ελάχιστα τετράγωνα. Έστω $V$ ένας πίνακας πλήρους τάξης του οποίου οι στήλες πρέπει να είναι ορθογωνοποιημένες. Ο πίνακας $V^{*}V$ είναι ερμιτιανός και θετικά ορισμένος, οπότε μπορεί να γραφεί στη μορφή $V^{*}V=LL^{*},$ χρησιμοποιώντας την αποσύνθεση Τσολέσκι. Ο κάτω τριγωνικός πίνακας $L$ με αυστηρά θετικές διαγώνιες καταχωρήσεις είναι αντιστρέψιμος. Οι στήλες του πίνακα $U=V\left(L^{-1}\right)^{*}$ είναι τότε ορθοκανονικές και καλύπτουν τον ίδιο υποχώρο με τις στήλες του αρχικού πίνακα $V$. Η ρητή χρήση του γινομένου $V^{*}V$ καθιστά τον αλγόριθμο ασταθή, ιδιαίτερα αν ο αριθμός των όρων του γινομένου είναι μεγάλος. Παρ' όλα αυτά, ο αλγόριθμος αυτός χρησιμοποιείται στην πράξη και υλοποιείται σε ορισμένα λογισμικά λόγω της υψηλής αποδοτικότητας και απλότητας του.

Στην κβαντομηχανική υπάρχουν διάφορα σχήματα ορθογωνοποίησης με χαρακτηριστικά που είναι καλύτερα προσαρμοσμένα για ορισμένες εφαρμογές από τα αρχικά σχήματα 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.

Πηγές

• Bau III, David; Trefethen, Lloyd N. (1997), Numerical linear algebra, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 978-0-89871-361-9 .
• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd έκδοση), Johns Hopkins, ISBN 978-0-8018-5414-9 .
• Greub, Werner (1975), Linear Algebra (4th έκδοση), Springer .
• Soliverez, C. E.; Gagliano, E. (1985), «Orthonormalization on the plane: a geometric approach», Mex. J. Phys. 31 (4): 743–758, http://rmf.smf.mx/pdf/rmf/31/4/31_4_743.pdf, ανακτήθηκε στις 2024-01-24 .