Gram-Schmidtsches Orthogonalisierungsverfahren

Gram-Schmidtsches Orthogonalisierungsverfahren

Das Gram-Schmidtsche Orthogonalisierungsverfahren ist ein Algorithmus aus dem mathematischen Teilgebiet der linearen Algebra. Er erzeugt zu jedem System linear unabhängiger Vektoren aus einem Prähilbertraum, d. h. einem Vektorraum mit Skalarprodukt, ein Orthogonalsystem, das denselben Untervektorraum erzeugt. Eine Erweiterung stellt das Gram-Schmidtsche 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 sind die Gram-Schmidt-Verfahren nicht geeignet. Durch akkumulierte Rundungsfehler sind die berechneten Vektoren nicht mehr orthogonal. Es existieren aber Modifikationen des Verfahrens, die diesen Fehler nicht haben. Weitere Möglichkeiten für Orthogonalisierungsverfahren basieren auf Householdertransformationen oder Givens-Rotationen.

Inhaltsverzeichnis

Vorbemerkung

Im Folgenden werden Elemente des betrachteten Vektorraums (Vektoren) mit einfachen lateinischen Buchstaben wie v und w bezeichnet, gegebenenfalls mit Indizes wie vi und w2. 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 \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.

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 - \dots - \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

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 v1 und v2 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.

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 w1)
v_2^\prime = w_2 - \langle v_1, w_2 \rangle \cdot v_1 (Orthogonalisieren des zweiten Vektors w2)
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 w3)
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 wn)
v_n = \frac{v_n^\prime}{\left\|v_n^\prime\right\|} (Normalisieren des Vektors v_n^\prime)

Im Allgemeinen erhält man durch dieses Verfahren kein besonders ausgezeichnetes System. Im \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 v1 und v2 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}

Anmerkungen

Eine besondere Eigenschaft der beiden Verfahren ist, dass nach jedem Zwischenschritt die bisher berechneten Vektoren v_1, \dots, v_i den gleichen Vektorraum erzeugen wie die Vektoren w_1, \dots, w_i. Die Vektoren 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. Fasst man die orthonormalen Vektoren v_1, \dots, v_n als Spalten einer Matrix Q zusammen, ebenso die Vektoren des Ausgangssystems 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 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 v_1, \ldots, v_{k-1} bereits bestimmt, versuchen wir, von wk eine passende Linearkombination der Vektoren v_1, \ldots, v_{k-1} abzuziehen, sodass der Differenzvektor

v_k = w_k - \sum_{i=1}^{k-1} \lambda_i v_i

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

\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 \langle v_j,v_k \rangle den Wert 0 annehmen:

\begin{align}\langle v_k,v_j \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{align}

Literatur

  • Andrzej Kielbasiński, Hubert Schwetlick: Numerische lineare Algebra. Eine computerorientierte Einführung. Deutscher Verlag der Wissenschaften, Berlin 1988, ISBN 3-326-00194-0.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Gram-Schmidtsches Orthonormalisierungsverfahren — Das Gram Schmidtsche Orthogonalisierungsverfahren ist ein Algorithmus aus dem mathematischen Teilgebiet der linearen Algebra. Er erzeugt zu jedem System linear unabhängiger Vektoren aus einem Prähilbertraum, d. h. einem Vektorraum mit… …   Deutsch Wikipedia

  • Schmidtsches Orthonormalisierungsverfahren — Das Gram Schmidtsche Orthogonalisierungsverfahren ist ein Algorithmus aus dem mathematischen Teilgebiet der linearen Algebra. Er erzeugt zu jedem System linear unabhängiger Vektoren aus einem Prähilbertraum, d. h. einem Vektorraum mit… …   Deutsch Wikipedia

  • Numerische Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration 4 Approximation und Interpolation …   Deutsch Wikipedia

  • ONB — Eine Orthonormalbasis eines Prähilbertraums ist in der linearen Algebra und der Funktionalanalysis eine Basis dieses Vektorraums, deren Elemente normiert (also Einheitsvektoren) und paarweise orthogonal (daher auch Orthonormalbasis) zueinander… …   Deutsch Wikipedia

  • Orthogonalbasis — Eine Orthonormalbasis eines Prähilbertraums ist in der linearen Algebra und der Funktionalanalysis eine Basis dieses Vektorraums, deren Elemente normiert (also Einheitsvektoren) und paarweise orthogonal (daher auch Orthonormalbasis) zueinander… …   Deutsch Wikipedia

  • Q-R-Zerlegung — Die QR Zerlegung oder QR Faktorisierung ist ein Begriff aus den mathematischen Teilgebieten der linearen Algebra und Numerik. Man bezeichnet damit die Zerlegung einer Matrix A in das Produkt zweier anderer Matrizen, wobei Q eine orthogonale (QQT …   Deutsch Wikipedia

  • QR-Faktorisierung — Die QR Zerlegung oder QR Faktorisierung ist ein Begriff aus den mathematischen Teilgebieten der linearen Algebra und Numerik. Man bezeichnet damit die Zerlegung einer Matrix A in das Produkt zweier anderer Matrizen, wobei Q eine orthogonale (QQT …   Deutsch Wikipedia

  • Orthogonalisierung — Mit Orthogonalisierungsverfahren bezeichnet man in der Mathematik Algorithmen, die aus einem System linear unabhängiger Vektoren ein Orthogonalsystem erzeugen, das den gleichen Untervektorraum aufspannt. Das bekannteste Verfahren dieser Art ist… …   Deutsch Wikipedia

  • Legendre-Polynome — Die Legendre Polynome, auch zonale Kugelfunktionen genannt, sind die partikulären Lösungen der legendreschen Differentialgleichung. Sie sind spezielle reelle oder komplexe Polynome, die ein orthogonales Funktionensystem bilden. Benannt sind sie… …   Deutsch Wikipedia

  • Legendrepolynom — Die Legendre Polynome, auch zonale Kugelfunktionen genannt, sind die partikulären Lösungen der legendreschen Differentialgleichung. Sie sind spezielle reelle oder komplexe Polynome, die ein orthogonales Funktionensystem bilden. Benannt sind sie… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”