Gram-Schmidtsches Orthogonalisierungsverfahren

Das Gram-Schmidtsche Orthogonalisierungsverfahren ist ein Algorithmus aus dem mathematischen Teilgebiet der linearen Algebra, mit dem man in einem endlichdimensionalen Prähilbertraum zu einem System linear unabhängiger Vektoren ein Orthogonalsystem berechnen kann, das denselben Untervektorraum erzeugt. Eine Erweiterung stellt das Gram-Schmidtsche Orthonormalisierungsverfahren dar: statt eines Orthogonalsystems berechnet es ein Orthonormalsystem. Verwendet man die Basisvektoren des Prähilbertraums als Eingabe für die Algorithmen, so berechnen sie eine Orthogonal- bzw. Orthonormalbasis.

Die beiden Verfahren sind nach Jørgen Pedersen Gram und Erhard Schmidt benannt. Sie wurden allerdings bereits früher in den Werken von Pierre-Simon Laplace und Augustin Louis Cauchy verwendet.

Für die numerische Berechnung durch einen Computer sind die Gram-Schmidt-Verfahren nicht geeignet. Durch akkumulierte Rundungsfehler sind die berechneten Vektoren nicht mehr orthogonal. Daher sind für numerische Zwecke Verfahren, wie die QR-Zerlegung, die auf der Householdertransformation oder Givens-Rotation basieren, besser geeignet.

Algorithmus des Orthogonalisierungsverfahrens

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

Die einzelnen Vektoren $u_{1},\dots ,u_{n}$ des Orthogonalsystem berechnen sich wie folgt:

$u_{1}=v_{1}\,$

$u_{2}=v_{2}-{\langle v_{2},u_{1}\rangle \over \langle u_{1},u_{1}\rangle }\,u_{1}$

$u_{3}=v_{3}-{\langle v_{3},u_{1}\rangle \over \langle u_{1},u_{1}\rangle }\,u_{1}-{\langle v_{3},u_{2}\rangle \over \langle u_{2},u_{2}\rangle }\,u_{2}$

$\vdots$

$u_{n}=v_{n}-{\langle v_{n},u_{1}\rangle \over \langle u_{1},u_{1}\rangle }\,u_{1}-{\langle v_{n},u_{2}\rangle \over \langle u_{2},u_{2}\rangle }\,u_{2}-...-{\langle v_{n},u_{n-1}\rangle \over \langle u_{n-1},u_{n-1}\rangle }\,u_{n-1}=v_{n}-\sum _{i=1}^{n-1}{\langle v_{n},u_{i}\rangle \over \langle u_{i},u_{i}\rangle }\,u_{i}$

Beispiel

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

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

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

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

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

Algorithmus des Orthonormalisierungsverfahrens

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

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

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

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

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

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

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

$\vdots$

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

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

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

Beispiel

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

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

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

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

$u_{2}^{\prime }=v_{2}-\langle v_{2},u_{1}\rangle \cdot u_{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}}$

$u_{2}={\frac {u_{2}^{\prime }}{\left\|u_{2}^{\prime }\right\|}}={\frac {1}{\sqrt {40/25}}}\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 $u_{1},\dots ,u_{i}$ den gleichen Vektorraum erzeugen wie die Vektoren $v_{1},\dots ,v_{i}$. Die Vektoren $u_{1},\dots ,u_{i}$ bilden also eine Orthogonal- bzw. Orthonormalbasis der entsprechenden Untervektorräume.

Berechnet man ein Orthonormalsystem von Hand, ist es oftmals einfacher, zunächst ein Orthogonalsystem auszurechnen und dann die einzelnen Vektoren zu normieren. Dadurch erspart man sich das zweifache Normieren und kann oftmals mit einfacheren Werten rechnen. Gegebenenfalls lohnt es sich, vor dem Erstellen des Orthogonalsystems/Orthonormalsystems das Gaußsche Eliminationsverfahren durchzuführen.

Funktionsprinzip der Verfahren

Sind die orthogonalen Vektoren $u_{1},...,u_{k-1}$ bereits bestimmt, versuchen wir, von $v_{k}$ eine passende Linearkombination der Vektoren $u_{1},...,u_{k-1}$ abzuziehen, so dass der Differenzvektor

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

zu allen Vektoren $u_{1},...,u_{k-1}$ orthogonal wird, d.h. jedes der Skalarprodukte

$\langle u_{k},u_{j}\rangle =\langle v_{k},u_{j}\rangle -\sum _{i=1}^{k-1}\lambda _{i}\langle u_{i},u_{j}\rangle$

mit $j=1,\ldots ,k-1$ muss den Wert 0 ergeben. Hierfür ist die Wahl

$\lambda _{i}={\frac {\langle v_{k},u_{i}\rangle }{\langle u_{i},u_{i}\rangle }}$ passend.

Setzte man dieses $\lambda _{i}$ ein, so erhält man

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

$=\langle v_{k},u_{j}\rangle -\langle v_{k},u_{j}\rangle$

$=0$