Gram Schmidt

Gram Schmidt

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 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. Es existieren aber Modifikationen des Verfahrens, die diesen Fehler nicht haben. Weitere Möglichkeiten für Orthogonalisierungsverfahren basieren auf Householdertransformationen oder Givens-Rotationen.


Inhaltsverzeichnis

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 Orthogonalsystems berechnen sich wie folgt:

u_1 = v_1\,
u_2 = v_2 - \frac{\langle v_2, u_1\rangle}{\langle u_1, u_1\rangle} \, u_1
u_3 = v_3 - \frac{\langle v_3, u_1\rangle}{\langle u_1, u_1\rangle} \, u_1 - \frac{\langle v_3, u_2\rangle}{\langle u_2, u_2\rangle} \, u_2
\vdots
u_n = v_n - \frac{\langle v_n, u_1\rangle}{\langle u_1, u_1\rangle} \, u_1 - \frac{\langle v_n, u_2\rangle}{\langle u_2, u_2\rangle} \, u_2 - \ldots - \frac{\langle v_n, u_{n-1}\rangle}{\langle u_{n-1}, u_{n-1}\rangle} \, u_{n-1}
= v_n - \sum_{i=1}^{n-1} \frac{\langle v_n, u_i\rangle}{\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 u1 und u2 berechnet, die denselben Untervektorraum erzeugen:

u_1 = v_1 = \begin{pmatrix} 3 \\ 1 \\ 2 \end{pmatrix}
u_2 = v_2 - \frac{\langle v_2, u_1\rangle}{\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{1}{7} \begin{pmatrix} -4 \\ 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 v1)
u_2^\prime = v_2 - \langle v_2, u_1 \rangle \cdot u_1 (Orthogonalisieren des zweiten Vektors v2)
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 v3)
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 vn)
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 \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 u1 und u2 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. Anders ausgedrückt ist die Transformationsmatrix, die die Koordinaten des einen Systems im anderen ausdrückt, eine rechtsobere Dreiecksmatrix. Fasst man die orthonormalen Vektoren u_1, \dots, u_n als Spalten einer Matrix Q zusammen, ebenso die Vektoren des Ausgangssystems v_1, \dots, v_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 u_1, \ldots, u_{k-1} bereits bestimmt, versuchen wir, von vk eine passende Linearkombination der Vektoren u_1, \ldots, 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, \ldots, 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 λi ein, so erhält man

\begin{align}\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\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.

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

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

  • Gram-Schmidt — Procédé de Gram Schmidt En algèbre linéaire, dans un espace vectoriel muni d un produit scalaire, le procédé de Gram Schmidt[1], en notant ou est un algorithme pour construire de proche en proche une base orthonormée à partir d une base donnée.… …   Wikipédia en Français

  • Gram-Schmidt — 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

  • Gram–Schmidt process — In mathematics, particularly linear algebra and numerical analysis, the Gram–Schmidt process is a method for orthogonalizing a set of vectors in an inner product space, most commonly the Euclidean space R n . The Gram–Schmidt process takes a… …   Wikipedia

  • Gram-Schmidt-Orthogonalisierung — 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

  • Gram-Schmidt-Prozess — 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

  • Gram-Schmidt-Verfahren — 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

  • Gram-Schmidt orthogonalization — /gram shmit /, Math. a process for constructing an orthogonal basis for a Euclidean space, given any basis for the space. [named after Jörgen Pedersen Gram (1850 1916), Danish mathematician, and Erhard Schmidt (1876 1959), German mathematician] * …   Universalium

  • Gram-Schmidt orthogonalization — /gram shmit /, Math. a process for constructing an orthogonal basis for a Euclidean space, given any basis for the space. [named after Jörgen Pedersen Gram (1850 1916), Danish mathematician, and Erhard Schmidt (1876 1959), German mathematician] …   Useful english dictionary

  • Procédé de Gram-Schmidt — En algèbre linéaire, dans un espace préhilbertien (c est à dire un espace vectoriel sur le corps des réels ou celui des complexes, muni d un produit scalaire), le procédé de Gram Schmidt[1] est un algorithme pour construire, à partir d une… …   Wikipédia en Français

  • Lemme d'orthonormation de Gram-Schmidt — Procédé de Gram Schmidt En algèbre linéaire, dans un espace vectoriel muni d un produit scalaire, le procédé de Gram Schmidt[1], en notant ou est un algorithme pour construire de proche en proche une base orthonormée à partir d une base donnée.… …   Wikipédia en Français

Share the article and excerpts

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