Gram-Schmidt-Prozess

In der Mathematik , insbesondere in der linearen Algebra und der numerischen Analysis , ist das Gram-Schmidt-Verfahren oder der Gram-Schmidt-Algorithmus eine Methode, um ein Paar oder mehrere Vektoren zu finden, die senkrecht zueinander stehen.

Technisch gesehen ist es ein Verfahren zur Konstruktion einer Orthonormalbasis aus einer Menge von Vektoren in einem Skalarproduktraum , üblicherweise dem euklidischen Raum mit dem Standard-Skalarprodukt . Das Gram-Schmidt-Verfahren nimmt eine endliche , linear unabhängige Menge von Vektoren für k ≤ n und erzeugt eine orthogonale Menge , die denselben -dimensionalen Unterraum von aufspannt wie . ${\displaystyle \mathbb {R} ^{n}}$${\displaystyle S=\{\mathbf {v} _{1},\ldots ,\mathbf {v} _{k}\}}$${\displaystyle S'=\{\mathbf {u} _{1},\ldots ,\mathbf {u} _{k}\}}$${\displaystyle k}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle S}$

Die Methode ist nach Jørgen Pedersen Gram und Erhard Schmidt benannt , aber Pierre-Simon Laplace kannte sie bereits vor Gram und Schmidt. ^{[ 1 ]} In der Theorie der Lie-Gruppenzerlegungen wird sie durch die Iwasawa-Zerlegung verallgemeinert .

Die Anwendung des Gram-Schmidt-Verfahrens auf die Spaltenvektoren einer Matrix mit vollem Spaltenrang liefert die QR-Zerlegung (sie wird in eine orthogonale und eine Dreiecksmatrix zerlegt ).

Die Vektorprojektion eines Vektors auf einen von Null verschiedenen Vektor ist definiert als ^{[ Anmerkung 1 ]} , wobei das Skalarprodukt der Vektoren und bezeichnet . Dies bedeutet, dass die orthogonale Projektion von auf die von aufgespannte Gerade ist . Ist der Nullvektor, so ist auch der Nullvektor. ${\displaystyle \mathbf {v} }$${\displaystyle \mathbf {u} }$$${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )={\frac {\langle \mathbf {v} ,\mathbf {u} \rangle }{\langle \mathbf {u} ,\mathbf {u} \rangle }}\,\mathbf {u} ,}$$${\displaystyle \langle \mathbf {v} ,\mathbf {u} \rangle }$${\displaystyle \mathbf {u} }$${\displaystyle \mathbf {v} }$${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )}$${\displaystyle \mathbf {v} }$${\displaystyle \mathbf {u} }$${\displaystyle \mathbf {u} }$${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )}$

Bei gegebenen linear unabhängigen Vektoren ungleich Null definiert das Gram-Schmidt-Verfahren die Vektoren wie folgt: ${\displaystyle k}$${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{k}}$${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$$${\displaystyle {\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}}}$$

Die Folge ist das gesuchte System orthogonaler Vektoren, und die normierten Vektoren bilden ein Orthonormalsystem . Die Berechnung der Folge wird als Gram-Schmidt -Orthogonalisierung bezeichnet , und die Berechnung der Folge wird als Gram-Schmidt -Orthonormalisierung bezeichnet . ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$${\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{k}}$${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$${\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{k}}$

Um zu überprüfen, ob diese Formeln eine orthogonale Folge ergeben, berechnet man zunächst , indem man die obige Formel für einsetzt : Man erhält null. Anschließend berechnet man erneut , indem man die Formel für einsetzt : Man erhält wieder null. Für beliebiges erfolgt der Beweis durch vollständige Induktion . ${\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{2}\rangle }$${\displaystyle \mathbf {u} _{2}}$${\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{3}\rangle }$${\displaystyle \mathbf {u} _{3}}$${\displaystyle k}$

Geometrisch verläuft diese Methode wie folgt: Zur Berechnung von wird orthogonal auf den von erzeugten Unterraum projiziert , der mit dem von erzeugten Unterraum identisch ist . Der Vektor wird dann als Differenz zwischen und dieser Projektion definiert und ist garantiert orthogonal zu allen Vektoren im Unterraum . ${\displaystyle \mathbf {u} _{i}}$${\displaystyle \mathbf {v} _{i}}$${\displaystyle U}$${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{i-1}}$${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{i-1}}$${\displaystyle \mathbf {u} _{i}}$${\displaystyle \mathbf {v} _{i}}$${\displaystyle U}$

Das Gram-Schmidt-Verfahren ist auch auf eine linear unabhängige, abzählbar unendliche Folge { v _i } _i anwendbar . Das Ergebnis ist eine orthogonale (oder orthonormale) Folge { u _i } _i, sodass für natürliche Zahlen n gilt : Der algebraische Spann von ist derselbe wie der von . ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}}$${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{n}}$

Wird das Gram-Schmidt-Verfahren auf eine linear abhängige Folge angewendet, gibt es im i-ten Schritt den Nullvektor aus, vorausgesetzt, dieser ist eine Linearkombination der i-ten Folge. Soll eine orthonormale Basis erzeugt werden, muss der Algorithmus die Ausgabe auf Nullvektoren prüfen und diese verwerfen, da kein Vielfaches eines Nullvektors die Länge 1 haben kann. Die Anzahl der vom Algorithmus ausgegebenen Vektoren entspricht dann der Dimension des von den ursprünglichen Eingaben aufgespannten Raums. ${\displaystyle i}$${\displaystyle \mathbf {v} _{i}}$${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{i-1}}$

Eine Variante des Gram-Schmidt-Verfahrens mittels transfiniter Rekursion, angewendet auf eine (möglicherweise überabzählbar) unendliche Folge von Vektoren, liefert eine Menge orthonormaler Vektoren, sodass für jedes die Vervollständigung des linearen Spanns von mit der Vervollständigung von übereinstimmt . Insbesondere liefert die Anwendung auf eine (algebraische) Basis eines Hilbertraums (oder allgemeiner auf eine Basis eines beliebigen dichten Unterraums) eine (funktionalanalytische) Orthonormalbasis. Im allgemeinen Fall gilt oft die strikte Ungleichung , selbst wenn die Ausgangsmenge linear unabhängig war, und der lineare Spann von muss kein Unterraum des linearen Spanns von sein (sondern ein Unterraum seiner Vervollständigung). ${\displaystyle (v_{\alpha })_{\alpha <\lambda }}$${\displaystyle (u_{\alpha })_{\alpha <\kappa }}$${\displaystyle \kappa \leq \lambda }$${\displaystyle \alpha \leq \lambda }$${\displaystyle \{u_{\beta }:\beta <\min(\alpha ,\kappa )\}}$${\displaystyle \{v_{\beta }:\beta <\alpha \}}$${\displaystyle \kappa <\lambda }$${\displaystyle (u_{\alpha })_{\alpha <\kappa }}$${\displaystyle (v_{\alpha })_{\alpha <\lambda }}$

Betrachten Sie die folgende Menge von Vektoren in (mit dem üblichen Skalarprodukt ) ${\displaystyle \mathbb {R} ^{2}}$$${\displaystyle S=\left\{\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2\\2\end{bmatrix}}\right\}.}$$

Führe nun das Gram-Schmidt-Verfahren durch, um einen orthogonalen Vektorsatz zu erhalten: $${\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}}}$$$${\displaystyle \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}}.}$$

Wir überprüfen, ob die Vektoren und tatsächlich orthogonal sind: Wir beachten, dass zwei Vektoren orthogonal sind, wenn ihr Skalarprodukt gleich 0 ist.${\displaystyle \mathbf {u} _{1}}$${\displaystyle \mathbf {u} _{2}}$$${\displaystyle \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,}$$

Bei Vektoren ungleich Null können wir die Vektoren dann normalisieren, indem wir ihre Längen durcheinander teilen, wie oben gezeigt: $${\displaystyle \mathbf {e} _{1}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}3\\1\end{bmatrix}}}$$$${\displaystyle \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}}.}$$

Bezeichne mit das Ergebnis der Anwendung des Gram-Schmidt-Verfahrens auf eine Menge von Vektoren . Dies ergibt eine Abbildung . ${\displaystyle \operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})}$${\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{k}}$${\displaystyle \operatorname {GS} \colon (\mathbb {R} ^{n})^{k}\to (\mathbb {R} ^{n})^{k}}$

Es besitzt folgende Eigenschaften:

• Es ist kontinuierlich
• Es ist orientierungserhaltend in dem Sinne, dass .${\displaystyle \operatorname {or} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})=\operatorname {or} (\operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k}))}$
• Es pendelt mit orthogonalen Karten:

Seien die Vektoren orthogonal (bezüglich des gegebenen Skalarprodukts). Dann gilt: ${\displaystyle g\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$$${\displaystyle \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)}$$

Darüber hinaus liefert eine parametrisierte Version des Gram-Schmidt-Verfahrens eine (starke) Deformationsretraktion der allgemeinen linearen Gruppe auf die orthogonale Gruppe . ${\displaystyle \mathrm {GL} (\mathbb {R} ^{n})}$${\displaystyle O(\mathbb {R} ^{n})}$

Bei der Implementierung dieses Verfahrens auf einem Computer sind die Vektoren aufgrund von Rundungsfehlern oft nicht exakt orthogonal . Beim oben beschriebenen Gram-Schmidt-Verfahren (manchmal auch als „klassisches Gram-Schmidt-Verfahren“ bezeichnet) ist dieser Verlust der Orthogonalität besonders gravierend; daher gilt das (klassische) Gram-Schmidt-Verfahren als numerisch instabil . ${\displaystyle \mathbf {u} _{k}}$

Das Gram-Schmidt-Verfahren lässt sich durch eine kleine Modifikation stabilisieren; diese Version wird mitunter als modifiziertes Gram-Schmidt -Verfahren (MGS) bezeichnet . Dieser Ansatz liefert in exakter Arithmetik dasselbe Ergebnis wie die ursprüngliche Formel und führt in Arithmetik mit endlicher Genauigkeit zu geringeren Fehlern.

Anstatt den Vektor u _k so zu berechnen, wie er berechnet wird als $${\displaystyle \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}),}$$$${\displaystyle {\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}}}$$

Diese Methode wird in der vorherigen Animation verwendet, wenn der Zwischenvektor bei der Orthogonalisierung des blauen Vektors verwendet wird . ${\displaystyle \mathbf {v} '_{3}}$${\displaystyle \mathbf {v} _{3}}$

Hier ist eine weitere Beschreibung des modifizierten Algorithmus. Gegeben die Vektoren , erzeugen wir im ersten Schritt Vektoren, indem wir Komponenten entlang der Richtung von entfernen . In Formeln gilt . Nach diesem Schritt haben wir bereits zwei der gewünschten orthogonalen Vektoren , nämlich , und haben außerdem bereits orthogonal zu gemacht . Als Nächstes orthogonalisieren wir die verbleibenden Vektoren gegen . Das bedeutet, wir berechnen durch Subtraktion . Nun haben wir die Vektoren gespeichert, wobei die ersten drei Vektoren bereits orthogonal sind und die restlichen Vektoren bereits orthogonal zu sind . Wie nun klar sein sollte, orthogonalisiert der nächste Schritt gegen . Auf diese Weise erhalten wir die vollständige Menge der orthogonalen Vektoren . Wenn orthonormale Vektoren gewünscht sind, normalisieren wir die Vektoren im Verlauf der Berechnung, sodass die Nenner in den Subtraktionsformeln zu Einsen werden. ${\displaystyle \mathbf {v} _{1},\mathbf {v} _{2},\dots ,\mathbf {v} _{n}}$${\displaystyle \mathbf {v} _{1},\mathbf {v} _{2}^{(1)},\dots ,\mathbf {v} _{n}^{(1)}}$${\displaystyle \mathbf {v} _{1}}$${\displaystyle \mathbf {v} _{k}^{(1)}:=\mathbf {v} _{k}-{\frac {\langle \mathbf {v} _{k},\mathbf {v} _{1}\rangle }{\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle }}\mathbf {v} _{1}}$${\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{n}}$${\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1},\mathbf {u} _{2}=\mathbf {v} _{2}^{(1)}}$${\displaystyle \mathbf {v} _{3}^{(1)},\dots ,\mathbf {v} _{n}^{(1)}}$${\displaystyle \mathbf {u} _{1}}$${\displaystyle \mathbf {u} _{2}=\mathbf {v} _{2}^{(1)}}$${\displaystyle \mathbf {v} _{3}^{(2)},\mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}}$${\displaystyle \mathbf {v} _{k}^{(2)}:=\mathbf {v} _{k}^{(1)}-{\frac {\langle \mathbf {v} _{k}^{(1)},\mathbf {u} _{2}\rangle }{\langle \mathbf {u} _{2},\mathbf {u} _{2}\rangle }}\mathbf {u} _{2}}$${\displaystyle \mathbf {v} _{1},\mathbf {v} _{2}^{(1)},\mathbf {v} _{3}^{(2)},\mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}}$${\displaystyle \mathbf {u} _{1},\mathbf {u} _{2},\mathbf {u} _{3}}$${\displaystyle \mathbf {u} _{1},\mathbf {u} _{2}}$${\displaystyle \mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}}$${\displaystyle \mathbf {u} _{3}=\mathbf {v} _{3}^{(2)}}$${\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{n}}$

Der folgende MATLAB- Algorithmus implementiert die klassische Gram-Schmidt-Orthonormalisierung. Die Vektoren v₁ , ..., vₖ (Spalten der Matrix A _,V sodass vₖ V(:,j)der -te Vektor ist ) werden durch orthonormale Vektoren (Spalten von A) ersetzt, _die denselben Unterraum aufspannen. ${\displaystyle j}$U

Funktion U = Grammschmidt ( V )[ n , k ] = size ( V );U = zeros ( n , k );U (:, 1 ) = V (:, 1 ) / Norm ( V (:, 1 ));für i = 2 : kU (:, i ) = V (:, i );für j = 1 : i - 1U (:, i ) = U (:, i ) - ( U (:, j ) '* U (:, i )) * U (:, j );EndeU (:, i ) = U (:, i ) / norm ( U (:, i ));EndeEnde

Die Kosten dieses Algorithmus betragen asymptotisch O( nk² ⁾ Gleitkommaoperationen, wobei n die Dimensionalität der Vektoren ist ^{. [ 2} ]

Wenn die Zeilen { v₁ _, ..., vₖ } als Matrix geschrieben werden , liefert die Anwendung des Gaußschen Eliminationsverfahrens auf die erweiterte Matrix die orthogonalisierten Vektoren anstelle von _. Die Matrix muss jedoch in Zeilenstufenform gebracht werden, indem man ausschließlich die Zeilenoperation der Addition eines skalaren Vielfachen einer Zeile zu einer anderen verwendet . ^{[ 3 ]} Zum Beispiel erhalten wir, wie oben gezeigt:${\displaystyle A}$${\displaystyle \left[AA^{\mathsf {T}}|A\right]}$${\displaystyle A}$${\displaystyle AA^{\mathsf {T}}}$${\displaystyle \mathbf {v} _{1}={\begin{bmatrix}3&1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2&2\end{bmatrix}}}$$${\displaystyle \left[AA^{\mathsf {T}}|A\right]=\left[{\begin{array}{rr|rr}10&8&3&1\\8&8&2&2\end{array}}\right]}$$

Und die Reduzierung auf die Zeilenstufenform ergibt $${\displaystyle \left[{\begin{array}{rr|rr}1&.8&.3&.1\\0&1&-.25&.75\end{array}}\right]}$$

Die normalisierten Vektoren sind dann wie im obigen Beispiel. $${\displaystyle \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}}}$$$${\displaystyle \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}},}$$

Das Ergebnis des Gram-Schmidt-Verfahrens kann mithilfe von Determinanten in einer nicht-rekursiven Formel ausgedrückt werden .

$${\displaystyle \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}}}$$

$${\displaystyle \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}}}$$

wobei und für die Gram -Determinante ist${\displaystyle D_{0}=1}$${\displaystyle j\geq 1}$${\displaystyle D_{j}}$

$${\displaystyle 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}}.}$$

Beachten Sie, dass der Ausdruck für eine "formale" Determinante ist, d. h. die Matrix enthält sowohl Skalare als auch Vektoren; die Bedeutung dieses Ausdrucks ist als Ergebnis einer Kofaktorentwicklung entlang der Vektorzeile definiert. ${\displaystyle \mathbf {u} _{k}}$

Die Determinantenformel für das Gram-Schmidt-Verfahren ist rechentechnisch (exponentiell) langsamer als die oben beschriebenen rekursiven Algorithmen; sie ist hauptsächlich von theoretischem Interesse.

Die unnormierten Ergebnisse des Gram-Schmidt-Verfahrens lassen sich, ausgedrückt in der Notation der geometrischen Algebra , wie folgt darstellen : Dies entspricht dem Ausdruck mit dem oben definierten Operator. Die Ergebnisse können äquivalent auch wie folgt ausgedrückt werden ^{[ 4 ]} , was eng mit dem obigen Ausdruck mit Determinanten verwandt ist. $${\displaystyle \mathbf {u} _{k}=\mathbf {v} _{k}-\sum _{j=1}^{k-1}(\mathbf {v} _{k}\cdot \mathbf {u} _{j})\mathbf {u} _{j}^{-1}\ ,}$$${\displaystyle \operatorname {proj} }$$${\displaystyle \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},}$$

Andere Orthogonalisierungsalgorithmen verwenden Householder-Transformationen oder Givens-Rotationen . Die Algorithmen mit Householder-Transformationen sind stabiler als das stabilisierte Gram-Schmidt-Verfahren. Andererseits liefert das Gram-Schmidt-Verfahren den i-ten orthogonalisierten Vektor nach der i-ten Iteration, während die Orthogonalisierung mittels Householder-Spiegelungen alle Vektoren erst am Ende erzeugt. Daher ist nur das Gram-Schmidt-Verfahren für iterative Methoden wie die Arnoldi-Iteration anwendbar . ${\displaystyle j}$${\displaystyle j}$

Eine weitere Alternative basiert auf der Verwendung der Cholesky-Zerlegung zur Invertierung der Matrix der Normalgleichungen in der linearen Ausgleichsrechnung . Sei eine Matrix mit vollem Spaltenrang , deren Spalten orthogonalisiert werden müssen. Die Matrix ist hermitesch und positiv definit und lässt sich daher mithilfe der Cholesky-Zerlegung als darstellen . Die untere Dreiecksmatrix mit strikt positiven Diagonalelementen ist invertierbar . Die Spalten der Matrix sind dann orthonormal und spannen denselben Unterraum auf wie die Spalten der ursprünglichen Matrix . Die explizite Verwendung des Produkts macht den Algorithmus instabil, insbesondere bei großen Konditionszahlen . Dennoch findet dieser Algorithmus aufgrund seiner hohen Effizienz und Einfachheit Anwendung in der Praxis und ist in einigen Softwarepaketen implementiert. ${\displaystyle V}$${\displaystyle V^{*}V}$${\displaystyle V^{*}V=LL^{*},}$${\displaystyle L}$${\displaystyle U=V\left(L^{-1}\right)^{*}}$${\displaystyle V}$${\displaystyle V^{*}V}$

In der Quantenmechanik existieren mehrere Orthogonalisierungsverfahren mit Eigenschaften, die für bestimmte Anwendungen besser geeignet sind als das ursprüngliche Gram-Schmidt-Verfahren. Dennoch bleibt es ein beliebter und effektiver Algorithmus, selbst für die umfangreichsten elektronischen Strukturrechnungen. ^{[ 5 ]}

Die Gram-Schmidt-Orthogonalisierung kann in stark polynomieller Zeit durchgeführt werden . Die Laufzeitanalyse ähnelt derjenigen der Gaußschen Elimination . ^{[ 6 ] : 40}

• Lineare Algebra
• Rekursion
• Orthogonalität (Mathematik)

• Bau III, David; Trefethen, Lloyd N. (1997), Numerische lineare Algebra , Philadelphia: Society for Industrial and Applied Mathematics, ISBN 978-0-89871-361-9Die
• Golub, Gene H.; Van Loan, Charles F. (1996), Matrixberechnungen (3. Aufl.), Johns Hopkins, ISBN 978-0-8018-5414-9Die
• Greub, Werner (1975), Lineare Algebra (4. Aufl.), SpringerDie
• Soliverez, CE; Gagliano, E. (1985), „Orthonormalisierung in der Ebene: ein geometrischer Ansatz“ (PDF) , Mex. J. Phys. , 31 (4): 743–758 , archiviert vom Original (PDF) am 07.03.2014 , abgerufen am 22.06.2013.Die

• „Orthogonalisierung“ , Enzyklopädie der Mathematik , EMS Press , 2001 [1994]
• Harvey Mudd College Mathematik-Tutorial zum Gram-Schmidt-Algorithmus
• Früheste bekannte Verwendungen einiger mathematischer Begriffe: G Der Eintrag „Gram-Schmidt-Orthogonalisierung“ enthält einige Informationen und Verweise auf die Ursprünge der Methode.
• Demonstrationen: Gram-Schmidt-Verfahren in der Ebene und Gram-Schmidt-Verfahren im Raum
• Gram-Schmidt-Orthogonalisierungs-Applet
• NAG Gram-Schmidt-Orthogonalisierung von n Vektoren der Ordnung m Routine
• Beweis: Raymond Puzio, Keenan Kidwell. „Beweis des Gram-Schmidt-Orthogonalisierungsalgorithmus“ (Version 8). PlanetMath.org.