Gram-Schmidtsches Orthogonalisierungsverfahren
# Gram-Schmidtsches Orthogonalisierungsverfahren

Das Gram-Schmidt’sche Orthogonalisierungsverfahren ist ein Algorithmus aus dem mathematischen Teilgebiet der linearen Algebra. Er erzeugt zu jedem System linear unabhängiger Vektoren aus einem Prähilbertraum (einem Vektorraum mit Skalarprodukt) ein Orthogonalsystem, das denselben Untervektorraum erzeugt. Eine Erweiterung stellt das Gram-Schmidt’sche Orthonormalisierungsverfahren dar: Statt eines Orthogonalsystems berechnet es ein Orthonormalsystem. Verwendet man ein System von Basisvektoren 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 mit Gleitpunktarithmetik sind die Gram-Schmidt-Verfahren schlecht geeignet. Durch akkumulierte Rundungsfehler sind die berechneten Vektoren nicht mehr orthogonal. Es existieren aber Modifikationen des Verfahrens, die diesen Nachteil nicht haben. Andere Orthogonalisierungsverfahren basieren auf Householdertransformationen oder Givens-Rotationen.

## Vorbemerkung

Im Folgenden werden Elemente des betrachteten Vektorraums (Vektoren) mit einfachen lateinischen Buchstaben wie $v$ und $w$ bezeichnet, gegebenenfalls mit Indizes wie $v_{i}$ und $w_{j}$. Es wird sowohl auf übergesetzte Pfeile als auch auf Fettdruck verzichtet. Das Skalarprodukt wird durch spitze Klammern dargestellt: $\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

    $\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 $v$, $w$ und alle $\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 $\|v\|={\sqrt {\langle v,v\rangle }}$ die Norm des Vektors $v$.

## Algorithmus des Orthogonalisierungsverfahrens

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

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

    $v_{1}=w_{1}\,$
    $v_{2}=w_{2}-{\frac {\langle v_{1},w_{2}\rangle }{\langle v_{1},v_{1}\rangle }}\,v_{1}$
    $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}$
       $\vdots$
    $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 $v_{j}$ für $j=1,2,\dots ,n$ also rekursiv durch

    $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 $\mathbb {R} ^{3}$ versehen mit dem Standardskalarprodukt $\langle \cdot ,\cdot \rangle$ seien zwei linear unabhängige Vektoren vorgegeben, die einen Untervektorraum erzeugen:

    $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 $v_{1}$ und $v_{2}$ berechnet, die denselben Untervektorraum erzeugen:

    $v_{1}=w_{1}={\begin{pmatrix}3\\1\\2\end{pmatrix}}$
    $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 $w_{1},\dots ,w_{n}$ ein Orthonormalsystem von $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 $v_{1},\dots ,v_{n}$ des Orthonormalsystems erhält man, indem zuerst jeweils ein orthogonaler Vektor berechnet und anschließend normalisiert wird:

    $v_{1}={\frac {w_{1}}{\left\|w_{1}\right\|}}$ (Normalisieren des ersten Vektors $w_{1}$)
    $v_{2}^{\prime }=w_{2}-\langle v_{1},w_{2}\rangle \cdot v_{1}$ (Orthogonalisieren des zweiten Vektors $w_{2}$)
    $v_{2}={\frac {v_{2}^{\prime }}{\left\|v_{2}^{\prime }\right\|}}$ (Normalisieren des Vektors $v_{2}^{\prime }$)
    $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 $w_{3}$)
    $v_{3}={\frac {v_{3}^{\prime }}{\left\|v_{3}^{\prime }\right\|}}$ (Normalisieren des Vektors $v_{3}^{\prime }$)
       $\vdots$
    $v_{n}^{\prime }=w_{n}-\sum _{i=1}^{n-1}\langle v_{i},w_{n}\rangle \cdot v_{i}$ (Orthogonalisieren des $n$-ten Vektors $w_{n}$)
    $v_{n}={\frac {v_{n}^{\prime }}{\left\|v_{n}^{\prime }\right\|}}$ (Normalisieren des Vektors $v_{n}^{\prime }$)

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

    $v_{j}^{\prime }=w_{j}-\sum _{i=1}^{j-1}\langle v_{i},w_{j}\rangle \cdot v_{i}$ und $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 $\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:

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

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

    $v_{1}={\frac {w_{1}}{\left\|w_{1}\right\|}}={\frac {1}{\sqrt {10}}}\cdot {\begin{pmatrix}3\\1\end{pmatrix}}$
    $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}}$
    $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}}$
