Gram-Schmidtsches Orthogonalisierungsverfahren

Das Gram-Schmidtsche Orthogonalisierungsverfahren i​st ein Algorithmus a​us dem mathematischen Teilgebiet d​er linearen Algebra. Er erzeugt z​u jedem System linear unabhängiger Vektoren a​us einem Prähilbertraum (einem Vektorraum m​it Skalarprodukt) e​in Orthogonalsystem, d​as denselben Untervektorraum erzeugt. Eine Erweiterung stellt d​as Gram-Schmidtsche Orthonormalisierungsverfahren dar: Statt e​ines Orthogonalsystems berechnet e​s ein Orthonormalsystem. Verwendet m​an ein System v​on Basisvektoren a​ls Eingabe für d​ie Algorithmen, s​o berechnen s​ie eine Orthogonal- bzw. Orthonormalbasis.

Die beiden Verfahren s​ind nach Jørgen Pedersen Gram u​nd Erhard Schmidt benannt. Sie wurden allerdings bereits früher i​n den Werken v​on Pierre-Simon Laplace u​nd Augustin-Louis Cauchy verwendet.

Für d​ie numerische Berechnung d​urch einen Computer m​it Gleitpunktarithmetik s​ind die Gram-Schmidt-Verfahren schlecht geeignet. Durch akkumulierte Rundungsfehler s​ind die berechneten Vektoren n​icht mehr orthogonal. Es existieren a​ber Modifikationen d​es Verfahrens, d​ie diesen Nachteil n​icht haben. Andere Orthogonalisierungsverfahren basieren a​uf Householdertransformationen o​der Givens-Rotationen.

Vorbemerkung

Im Folgenden werden Elemente des betrachteten Vektorraums (Vektoren) mit einfachen lateinischen Buchstaben wie ${\displaystyle v}$ und ${\displaystyle w}$ bezeichnet, gegebenenfalls mit Indizes wie ${\displaystyle v_{i}}$ und ${\displaystyle w_{j}}$. Es wird sowohl auf übergesetzte Pfeile als auch auf Fettdruck verzichtet. Das Skalarprodukt wird durch spitze Klammern dargestellt: ${\displaystyle \langle v,w\rangle }$. Im komplexen Fall wird dabei die Konvention verwendet, dass das Skalarprodukt im ersten Argument semilinear, im zweiten Argument linear ist, das heißt

${\displaystyle \langle \lambda v,w\rangle ={\overline {\lambda }}\langle v,w\rangle ,\quad \langle v,\lambda w\rangle =\lambda \langle v,w\rangle }$

für alle Vektoren ${\displaystyle v}$, ${\displaystyle w}$ und alle ${\displaystyle \lambda \in \mathbb {C} }$. Im komplexen Fall kommt es deshalb bei den unten dargestellten Formeln auf die Reihenfolge der Faktoren im Skalarprodukt an, im reellen Fall jedoch nicht.

Zudem bezeichnet ${\displaystyle \|v\|={\sqrt {\langle v,v\rangle }}}$ die Norm des Vektors ${\displaystyle v}$.

Algorithmus des Orthogonalisierungsverfahrens

Illustration des Gram-Schmidt-Verfahrens an einem Beispiel mit drei Vektoren

Der folgende Algorithmus berechnet zu den linear unabhängigen Vektoren ${\displaystyle w_{1},\dots ,w_{n}}$ ein Orthogonalsystem von ${\displaystyle n}$ paarweise orthogonalen Vektoren, das denselben Untervektorraum erzeugt.

Die einzelnen Vektoren ${\displaystyle v_{1},\dots ,v_{n}}$ des Orthogonalsystems berechnen sich wie folgt:

${\displaystyle v_{1}=w_{1}\,}$

${\displaystyle v_{2}=w_{2}-{\frac {\langle v_{1},w_{2}\rangle }{\langle v_{1},v_{1}\rangle }}\,v_{1}}$

${\displaystyle v_{3}=w_{3}-{\frac {\langle v_{1},w_{3}\rangle }{\langle v_{1},v_{1}\rangle }}\,v_{1}-{\frac {\langle v_{2},w_{3}\rangle }{\langle v_{2},v_{2}\rangle }}\,v_{2}}$

${\displaystyle \vdots }$

${\displaystyle v_{n}=w_{n}-{\frac {\langle v_{1},w_{n}\rangle }{\langle v_{1},v_{1}\rangle }}\,v_{1}-{\frac {\langle v_{2},w_{n}\rangle }{\langle v_{2},v_{2}\rangle }}\,v_{2}-\dotsb -{\frac {\langle v_{n-1},w_{n}\rangle }{\langle v_{n-1},v_{n-1}\rangle }}\,v_{n-1}=w_{n}-\sum _{i=1}^{n-1}{\frac {\langle v_{i},w_{n}\rangle }{\langle v_{i},v_{i}\rangle }}\,v_{i}}$

Anders gesagt werden die ${\displaystyle v_{j}}$ für ${\displaystyle j=1,2,\dots ,n}$ also rekursiv durch

${\displaystyle v_{j}=w_{j}-\sum _{i=1}^{j-1}{\frac {\langle v_{i},w_{j}\rangle }{\langle v_{i},v_{i}\rangle }}\,v_{i}}$

definiert.

Beispiel

Im ${\displaystyle \mathbb {R} ^{3}}$ versehen mit dem Standardskalarprodukt ${\displaystyle \langle \cdot ,\cdot \rangle }$ seien zwei linear unabhängige Vektoren vorgegeben, die einen Untervektorraum erzeugen:

${\displaystyle w_{1}={\begin{pmatrix}3\\1\\2\end{pmatrix}},\quad w_{2}={\begin{pmatrix}2\\2\\2\end{pmatrix}}}$

Es werden nun zwei orthogonale Vektoren ${\displaystyle v_{1}}$ und ${\displaystyle v_{2}}$ berechnet, die denselben Untervektorraum erzeugen:

${\displaystyle v_{1}=w_{1}={\begin{pmatrix}3\\1\\2\end{pmatrix}}}$

${\displaystyle v_{2}=w_{2}-{\frac {\langle v_{1},w_{2}\rangle }{\langle v_{1},v_{1}\rangle }}\cdot v_{1}={\begin{pmatrix}2\\2\\2\end{pmatrix}}-{\frac {12}{14}}\cdot {\begin{pmatrix}3\\1\\2\end{pmatrix}}={\frac {1}{7}}{\begin{pmatrix}-4\\8\\2\end{pmatrix}}}$

Algorithmus des Orthonormalisierungsverfahrens

Der folgende Algorithmus berechnet zu den linear unabhängigen Vektoren ${\displaystyle w_{1},\dots ,w_{n}}$ ein Orthonormalsystem von ${\displaystyle n}$ normierten, paarweise orthogonalen Vektoren, das denselben Untervektorraum erzeugt. Er ist identisch mit einer Normierung der orthogonalen Vektoren, welche durch den obigen Algorithmus bestimmt wurden.

Die einzelnen Vektoren ${\displaystyle v_{1},\dots ,v_{n}}$ des Orthonormalsystems erhält man, indem zuerst jeweils ein orthogonaler Vektor berechnet und anschließend normalisiert wird:

${\displaystyle v_{1}={\frac {w_{1}}{\left\|w_{1}\right\|}}}$ (Normalisieren des ersten Vektors ${\displaystyle w_{1}}$)

${\displaystyle v_{2}^{\prime }=w_{2}-\langle v_{1},w_{2}\rangle \cdot v_{1}}$ (Orthogonalisieren des zweiten Vektors ${\displaystyle w_{2}}$)

${\displaystyle v_{2}={\frac {v_{2}^{\prime }}{\left\|v_{2}^{\prime }\right\|}}}$ (Normalisieren des Vektors ${\displaystyle v_{2}^{\prime }}$)

${\displaystyle v_{3}^{\prime }=w_{3}-\langle v_{1},w_{3}\rangle \cdot v_{1}-\langle v_{2},w_{3}\rangle \cdot v_{2}}$ (Orthogonalisieren des dritten Vektors ${\displaystyle w_{3}}$)

${\displaystyle v_{3}={\frac {v_{3}^{\prime }}{\left\|v_{3}^{\prime }\right\|}}}$ (Normalisieren des Vektors ${\displaystyle v_{3}^{\prime }}$)

${\displaystyle \vdots }$

${\displaystyle v_{n}^{\prime }=w_{n}-\sum _{i=1}^{n-1}\langle v_{i},w_{n}\rangle \cdot v_{i}}$ (Orthogonalisieren des ${\displaystyle n}$-ten Vektors ${\displaystyle w_{n}}$)

${\displaystyle v_{n}={\frac {v_{n}^{\prime }}{\left\|v_{n}^{\prime }\right\|}}}$ (Normalisieren des Vektors ${\displaystyle v_{n}^{\prime }}$)

Anders gesagt werden die ${\displaystyle v_{j}}$ und ${\displaystyle v_{j}^{\prime }}$ für ${\displaystyle j=1,2,\dots ,n}$ also rekursiv durch

${\displaystyle v_{j}^{\prime }=w_{j}-\sum _{i=1}^{j-1}\langle v_{i},w_{j}\rangle \cdot v_{i}}$ und ${\displaystyle v_{j}={\frac {v_{j}^{\prime }}{\left\|v_{j}^{\prime }\right\|}}}$ definiert.

Im Allgemeinen erhält man durch dieses Verfahren kein besonders ausgezeichnetes System. Im ${\displaystyle \mathbb {R} ^{3}}$ muss z. B. erst ein Umordnungsschritt nachgeschaltet werden, um ein Rechts- oder Linkssystem zu erhalten.

Beispiel

Im ${\displaystyle \mathbb {R} ^{2}}$ versehen mit dem Standardskalarprodukt ${\displaystyle \langle \cdot ,\cdot \rangle }$ seien zwei Basisvektoren gegeben:

${\displaystyle w_{1}={\begin{pmatrix}3\\1\end{pmatrix}},\quad w_{2}={\begin{pmatrix}2\\2\end{pmatrix}}}$

Es werden nun zwei Vektoren ${\displaystyle v_{1}}$ und ${\displaystyle v_{2}}$ berechnet, die eine Orthonormalbasis des ${\displaystyle \mathbb {R} ^{2}}$ bilden.

${\displaystyle v_{1}={\frac {w_{1}}{\left\|w_{1}\right\|}}={\frac {1}{\sqrt {10}}}\cdot {\begin{pmatrix}3\\1\end{pmatrix}}}$

${\displaystyle v_{2}^{\prime }=w_{2}-\langle v_{1},w_{2}\rangle \cdot v_{1}={\begin{pmatrix}2\\2\end{pmatrix}}-{\frac {1}{\sqrt {10}}}\cdot \left\langle {\begin{pmatrix}3\\1\end{pmatrix}},{\begin{pmatrix}2\\2\end{pmatrix}}\right\rangle \cdot {\frac {1}{\sqrt {10}}}{\begin{pmatrix}3\\1\end{pmatrix}}={\frac {1}{5}}{\begin{pmatrix}-2\\6\end{pmatrix}}}$

${\displaystyle v_{2}={\frac {v_{2}^{\prime }}{\left\|v_{2}^{\prime }\right\|}}={\sqrt {\frac {25}{40}}}\cdot {\frac {1}{5}}{\begin{pmatrix}-2\\6\end{pmatrix}}={\frac {1}{\sqrt {10}}}\cdot {\begin{pmatrix}-1\\3\end{pmatrix}}}$

Anmerkungen

Eine besondere Eigenschaft der beiden Verfahren ist, dass nach jedem Zwischenschritt die bisher berechneten Vektoren ${\displaystyle v_{1},\dots ,v_{i}}$ den gleichen Vektorraum erzeugen wie die Vektoren ${\displaystyle w_{1},\dots ,w_{i}}$. Die Vektoren ${\displaystyle v_{1},\dots ,v_{i}}$ bilden also eine Orthogonal- bzw. Orthonormalbasis der entsprechenden Untervektorräume. Anders ausgedrückt ist die Transformationsmatrix, die die Koordinaten des einen Systems im anderen ausdrückt, eine rechtsobere Dreiecksmatrix. Diese hat außerdem eine positive Determinante, daher hat die resultierende Orthogonal- bzw. Orthonormalbasis die gleiche Orientierung wie die Ausgangsbasis. Fasst man die orthonormalen Vektoren ${\displaystyle v_{1},\dots ,v_{n}}$ als Spalten einer Matrix Q zusammen, ebenso die Vektoren des Ausgangssystems ${\displaystyle w_{1},\dots ,w_{n}}$ zu einer Matrix A, so gibt es eine Dreiecksmatrix R mit A=QR, es wird also eine QR-Zerlegung bestimmt. Dementsprechend kann das Ergebnis der Gram-Schmidt-Orthonormalisierung auch mit anderen Methoden zur QR-Zerlegung bestimmt werden, die mit Givens-Rotationen oder Householder-Spiegelungen arbeiten.

Berechnet m​an ein Orthonormalsystem v​on Hand, i​st es oftmals einfacher, zunächst e​in Orthogonalsystem auszurechnen u​nd dann d​ie einzelnen Vektoren z​u normieren. Dadurch erspart m​an sich d​as zweifache Normieren u​nd kann oftmals m​it einfacheren Werten rechnen. Gegebenenfalls l​ohnt es sich, v​or dem Erstellen d​es Orthogonalsystems/Orthonormalsystems d​as Gaußsche Eliminationsverfahren durchzuführen.

Prinzip des Verfahrens

Sind die orthogonalen Vektoren ${\displaystyle v_{1},\ldots ,v_{k-1}}$ bereits bestimmt, versuchen wir, von ${\displaystyle w_{k}}$ eine passende Linearkombination der Vektoren ${\displaystyle v_{1},\ldots ,v_{k-1}}$ abzuziehen, sodass der Differenzvektor

${\displaystyle v_{k}=w_{k}-\sum _{i=1}^{k-1}\lambda _{i}v_{i}}$

zu allen Vektoren ${\displaystyle v_{1},\ldots ,v_{k-1}}$ orthogonal wird. Dies ist gleichbedeutend damit, dass das Skalarprodukt ${\displaystyle \langle v_{j},v_{k}\rangle }$ für alle ${\displaystyle j=1,\ldots ,k-1}$ den Wert 0 ergibt. Eine solche Linearkombination ergibt sich, wenn für jedes ${\displaystyle i}$ der Ausdruck

${\displaystyle \lambda _{i}={\frac {\langle v_{i},w_{k}\rangle }{\langle v_{i},v_{i}\rangle }}}$

gewählt wird. Eine Kontrollrechnung zeigt, dass dadurch alle Skalarprodukte ${\displaystyle \langle v_{j},v_{k}\rangle }$ mit ${\displaystyle j\neq k}$ den Wert 0 annehmen:

${\displaystyle {\begin{aligned}\langle v_{j},v_{k}\rangle &=\left\langle v_{j},w_{k}-\sum _{i=1}^{k-1}\lambda _{i}v_{i}\right\rangle \\&=\langle v_{j},w_{k}\rangle -\sum _{i=1}^{k-1}{\frac {\langle v_{i},w_{k}\rangle }{\langle v_{i},v_{i}\rangle }}\langle v_{j},v_{i}\rangle \\&=\langle v_{j},w_{k}\rangle -\langle v_{j},w_{k}\rangle \\&=0\end{aligned}}}$

Orthonormalisierung unendlicher Systeme von Vektoren

In einem beliebigen Hilbertraum ${\displaystyle H}$ lässt sich das Verfahren auch auf unendliche Systeme unabhängiger Vektoren anwenden, wobei die Unabhängigkeit in dem Sinne zu verstehen ist, dass kein Element im Abschluss der linearen Hülle der übrigen Vektoren liegt. Den Fall eines abzählbaren Systems (d. h. ${\displaystyle H}$ ist ein separabler Hilbertraum) kann direkt auf den oben dargestellten endlichen Fall zurückgeführt werden: Gegeben sei eine unabhängige Folge ${\displaystyle \left(w_{n}\right)_{n\in \mathbb {N} }}$, so erhält man eine entsprechende orthonormale Folge ${\displaystyle \left(v_{n}\right)_{n\in \mathbb {N} }}$, indem man für jedes ${\displaystyle n\in \mathbb {N} }$ das obige Verfahren anwendet und ${\displaystyle v_{n}}$ erhält. Allgemeiner kann jedes unabhängige System nach dem Wohlordnungssatz als Folge ${\displaystyle \left(w_{\alpha }\right)_{\alpha <d}}$ für eine Kardinalzahl ${\displaystyle d}$ und Ordinalzahlen ${\displaystyle \alpha }$ angesehen werden (im Falle einer dichten linearen Hülle des unabhängigen Systems ist ${\displaystyle d}$ gerade die Dimension von ${\displaystyle H}$). Bezeichne nun ${\displaystyle \pi _{A}\colon H\to A}$ die orthogonale Projektion auf einen abgeschlossenen Teilraum ${\displaystyle A}$, die aufgrund der Vollständigkeit des Raumes stets existiert, ${\displaystyle {\hat {x}}}$ bezeichne die Normierung ${\displaystyle \textstyle {\frac {x}{\left\|x\right\|}}}$. So ergibt sich ein Orthonormalsystem ${\displaystyle \left(v_{\alpha }\right)_{\alpha <d}}$ durch

${\displaystyle A_{\alpha }:={\overline {\operatorname {span} \left(\left\{w_{\beta }\colon \beta <\alpha \right\}\right)}}}$

${\displaystyle v_{\alpha }:={\widehat {\left(w_{\alpha }-\pi _{A_{\alpha }}\left(w_{\alpha }\right)\right)}}}$.

Per transfiniter Induktion lässt sich dann zeigen, dass ${\displaystyle A_{\alpha }={\overline {\operatorname {span} \left(\left\{v_{\beta }\colon \beta <\alpha \right\}\right)}}}$, sogar für ${\displaystyle \alpha =d}$. Expliziter lässt sich das Verfahren per transfiniter Rekursion wie folgt schreiben:

${\displaystyle v_{\alpha }:={\widehat {\left(w_{\alpha }-\sum _{\beta <\alpha }\langle v_{\beta },w_{\alpha }\rangle \cdot v_{\beta }\right)}}}$

Hierbei i​st die Summe aufgrund d​er besselschen Ungleichung wohldefiniert (insbesondere s​ind stets n​ur abzählbar v​iele Summanden ungleich Null).

Literatur

• K. Kirchgessner, M. Schreck: Vektoranalysis für Dummies. Das Pocketbuch Paperback . Wiley-VCH, 2012. ISBN 978-3-527-70742-3