imported>314artemis: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-05-23T05:03:08Z

growthexperiments-addlink-summary-summary:2|0|0

Neue Seite

Das '''Gram-Schmidt’sche Orthogonalisierungsverfahren''' ist ein [[Algorithmus]] aus dem [[Teilgebiete der Mathematik|mathematischen Teilgebiet]] der [[Lineare Algebra|linearen Algebra]]. Er erzeugt zu jedem System [[linear unabhängig]]er Vektoren aus einem [[Prähilbertraum]] (einem [[Vektorraum]] mit [[Skalarprodukt]]) ein [[Orthogonalsystem]], das denselben [[Untervektorraum]] [[Erzeugendensystem|erzeugt]]. Eine Erweiterung stellt das '''Gram-Schmidt’sche Orthonormalisierungsverfahren''' dar: Statt eines Orthogonalsystems berechnet es ein [[Orthonormalsystem]]. Verwendet man ein System von [[Basisvektor]]en 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 (Mathematiker)|Erhard Schmidt]] benannt. Sie wurden allerdings bereits früher in den Werken von [[Pierre-Simon Laplace]] und [[Augustin-Louis Cauchy]] verwendet.

Für die [[Numerik|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 [[Arnoldi-Verfahren|Modifikationen des Verfahrens]], die diesen Nachteil nicht haben. Andere [[Orthogonalisierungsverfahren]] basieren auf [[Householdertransformation]]en oder [[Givens-Rotation]]en.

== Vorbemerkung ==
Im Folgenden werden Elemente des betrachteten Vektorraums (Vektoren) mit einfachen lateinischen Buchstaben wie <math>v</math> und <math>w</math> bezeichnet, gegebenenfalls mit Indizes wie <math>v_i</math> und <math>w_j</math>. Es wird sowohl auf übergesetzte Pfeile als auch auf Fettdruck verzichtet.
Das Skalarprodukt wird durch spitze Klammern dargestellt: <math>\langle v, w \rangle</math>. Im komplexen Fall wird dabei die Konvention verwendet, dass das [[Skalarprodukt]] im ersten Argument semilinear, im zweiten Argument linear ist, das heißt
:<math>\langle \lambda v, w \rangle = \overline \lambda \langle v, w \rangle,\quad \langle v, \lambda w \rangle = \lambda \langle v, w \rangle</math>
für alle Vektoren <math>v</math>, <math>w </math> und alle <math>\lambda \in \Complex</math>. 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 <math>\|v\|=\sqrt{\langle v, v\rangle}</math> die [[Norm (Mathematik)|Norm]] des Vektors <math>v</math>.

== Algorithmus des Orthogonalisierungsverfahrens ==
[[File:Gram-Schmidt orthonormalization process.gif|miniatur|Illustration des Gram-Schmidt-Verfahrens an einem Beispiel mit drei Vektoren]]

Der folgende Algorithmus berechnet zu den linear unabhängigen Vektoren <math>w_1, \dots, w_n</math> ein [[Orthogonalsystem]] von <math>n</math> paarweise orthogonalen Vektoren, das denselben Untervektorraum erzeugt.

Die einzelnen Vektoren <math>v_1, \dots, v_n</math> des Orthogonalsystems berechnen sich wie folgt:
:<math>v_1 = w_1\,</math>
:<math>v_2 = w_2 - \frac{\langle v_1, w_2\rangle}{\langle v_1, v_1\rangle} \, v_1</math>
:<math>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</math>
::<math>\vdots</math>
:<math>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</math>

Anders gesagt werden die <math>v_j</math> für <math>j=1,2,\dots,n</math> also rekursiv durch
:<math>v_j = w_j - \sum_{i=1}^{j-1} \frac{\langle v_i, w_j\rangle}{\langle v_i, v_i\rangle} \, v_i</math>
definiert.

=== Beispiel ===
Im <math>\mathbb{R}^3</math> versehen mit dem [[Standardskalarprodukt]] <math>\langle\cdot,\cdot \rangle</math> seien zwei linear unabhängige Vektoren vorgegeben, die einen Untervektorraum erzeugen:
:<math> w_1 = \begin{pmatrix} 3 \\ 1 \\ 2 \end{pmatrix},\quad w_2 = \begin{pmatrix} 2 \\ 2 \\ 2 \end{pmatrix}</math>
Es werden nun zwei orthogonale Vektoren <math>v_1</math> und <math>v_2</math> berechnet, die denselben Untervektorraum erzeugen:
:<math>v_1 = w_1 = \begin{pmatrix} 3 \\ 1 \\ 2 \end{pmatrix}</math>
:<math>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}</math>

== Algorithmus des Orthonormalisierungsverfahrens ==

Der folgende Algorithmus berechnet zu den linear unabhängigen Vektoren <math>w_1, \dots, w_n</math> ein [[Orthonormalsystem]] von <math>n</math> 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 <math>v_1, \dots, v_n</math> des Orthonormalsystems erhält man, indem zuerst jeweils ein orthogonaler Vektor berechnet und anschließend normalisiert wird:
:<math>v_1 = \frac{w_1}{\left\|w_1\right\|}</math> (Normalisieren des ersten Vektors <math>w_1</math>)
:<math>v_2^\prime = w_2 - \langle v_1, w_2 \rangle \cdot v_1</math> (Orthogonalisieren des zweiten Vektors <math>w_2</math>)
:<math>v_2 = \frac{v_2^\prime}{\left\|v_2^\prime\right\|}</math> (Normalisieren des Vektors <math>v_2^\prime</math>)
:<math>v_3^\prime = w_3 - \langle v_1, w_3 \rangle \cdot v_1 - \langle v_2, w_3 \rangle \cdot v_2</math> (Orthogonalisieren des dritten Vektors <math>w_3</math>)
:<math>v_3 = \frac{v_3^\prime}{\left\|v_3^\prime\right\|}</math> (Normalisieren des Vektors <math>v_3^\prime</math>)
::<math>\vdots</math>
:<math>v_n^\prime = w_n - \sum_{i=1}^{n-1} \langle v_i, w_n \rangle \cdot v_i</math> (Orthogonalisieren des <math>n</math>-ten Vektors <math>w_n</math>)
:<math>v_n = \frac{v_n^\prime}{\left\|v_n^\prime\right\|}</math> (Normalisieren des Vektors <math>v_n^\prime</math>)

Anders gesagt werden die <math>v_j</math> und <math>v_j^\prime</math> für <math>j=1,2,\dots,n</math> also rekursiv durch
:<math>v_j^\prime = w_j - \sum_{i=1}^{j-1} \langle v_i, w_j \rangle \cdot v_i</math> und <math>v_j = \frac{v_j^\prime}{\left\|v_j^\prime\right\|}</math> definiert.

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

=== Beispiel ===

Im <math>\mathbb{R}^2</math> versehen mit dem [[Standardskalarprodukt]] <math>\langle\cdot,\cdot \rangle</math> seien zwei Basisvektoren gegeben:
:<math> w_1 = \begin{pmatrix} 3 \\ 1 \end{pmatrix},\quad w_2 = \begin{pmatrix} 2 \\ 2 \end{pmatrix}</math>

Es werden nun zwei Vektoren <math>v_1</math> und <math>v_2</math> berechnet, die eine Orthonormalbasis des <math>\mathbb{R}^2</math> bilden.
:<math>v_1 = \frac {w_1} {\left\|w_1\right\|} = \frac {1} {\sqrt{10}} \cdot \begin{pmatrix} 3 \\ 1 \end{pmatrix}</math>
:<math>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}</math>
:<math>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}</math>

== Anmerkungen ==

Eine besondere Eigenschaft der beiden Verfahren ist, dass nach jedem Zwischenschritt die bisher berechneten Vektoren <math>v_1, \dots, v_i</math> den gleichen Vektorraum erzeugen wie die Vektoren <math>w_1, \dots, w_i</math>. Die Vektoren <math>v_1, \dots, v_i</math> 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 <math>v_1, \dots, v_n</math> als Spalten einer Matrix ''Q'' zusammen, ebenso die Vektoren des Ausgangssystems <math>w_1, \dots, w_n</math> 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-Rotation]]en oder [[Householdertransformation|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ßsches Eliminationsverfahren|Gauß’sche Eliminationsverfahren]] durchzuführen.

== Prinzip des Verfahrens ==

Sind die orthogonalen Vektoren <math>v_1, \ldots, v_{k-1}</math> bereits bestimmt, versuchen wir, von <math>w_k</math> eine passende [[Linearkombination]] der Vektoren <math>v_1, \ldots, v_{k-1}</math> abzuziehen,
sodass der Differenzvektor
:<math>v_k = w_k - \sum_{i=1}^{k-1} \lambda_i v_i</math>
zu allen Vektoren <math>v_1, \ldots, v_{k-1}</math> orthogonal wird. Dies ist gleichbedeutend damit, dass das Skalarprodukt
<math>\langle v_j,v_k \rangle</math>
für alle <math>j=1,\ldots,k-1</math> den Wert 0 ergibt. Eine solche Linearkombination ergibt sich, wenn für jedes <math>i</math> der Ausdruck
:<math>\lambda_i = \frac {\langle v_i,w_k \rangle}{\langle v_i,v_i \rangle}</math>
gewählt wird. Eine Kontrollrechnung zeigt, dass dadurch alle Skalarprodukte <math>\langle v_j,v_k \rangle</math> mit <math>j \neq k</math> den Wert 0 annehmen:
:<math>\begin{align}\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{align}</math>

== Orthonormalisierung unendlicher Systeme von Vektoren ==
In einem beliebigen [[Hilbertraum]] <math>H</math> 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 [[Abgeschlossene Hülle|Abschluss]] der [[lineare Hülle|linearen Hülle]] der übrigen Vektoren liegt. Den Fall eines [[Abzählbare Menge|abzählbaren]] Systems (d. h. <math>H</math> ist ein [[separabler Hilbertraum]]) kann direkt auf den oben dargestellten endlichen Fall zurückgeführt werden: Gegeben sei eine unabhängige Folge <math>\left(w_n\right)_{n\in \N}</math>, so erhält man eine entsprechende orthonormale Folge <math>\left(v_n\right)_{n\in \N}</math>, indem man für jedes <math>n\in \N</math> das obige Verfahren anwendet und <math>v_n</math> erhält. Allgemeiner kann jedes unabhängige System nach dem [[Wohlordnungssatz]] als Folge <math>\left(w_\alpha\right)_{\alpha<d}</math> für eine [[Kardinalzahl (Mathematik)|Kardinalzahl]] <math>d</math> und [[Ordinalzahl]]en <math>\alpha</math> angesehen werden (im Falle einer [[Dichte Teilmenge|dichten]] linearen Hülle des unabhängigen Systems ist <math>d</math> gerade die [[Dimension (Mathematik)|Dimension]] von <math>H</math>). Bezeichne nun <math>\pi_A\colon H \to A</math> die [[Orthogonalprojektion|orthogonale Projektion]] auf einen abgeschlossenen Teilraum <math>A</math>, die aufgrund der Vollständigkeit des Raumes stets existiert, und <math>\hat{x}</math> bezeichne die Normierung <math>\textstyle \frac{x}{\left\|x\right\|}</math>. So ergibt sich ein Orthonormalsystem <math>\left(v_\alpha\right)_{\alpha<d}</math> durch
:<math>A_\alpha := \overline{\operatorname{span}\left(\left\{w_\beta \colon \beta < \alpha\right\}\right)}</math>
:<math>v_\alpha := \widehat{\left(w_\alpha - \pi_{A_\alpha}\left(w_\alpha\right)\right)}</math>.

Per [[transfinite Induktion|transfiniter Induktion]] lässt sich dann zeigen, dass <math>A_\alpha = \overline{\operatorname{span}\left(\left\{v_\beta \colon \beta < \alpha\right\}\right)}</math>, sogar für <math>\alpha=d</math>. Expliziter lässt sich das Verfahren per [[transfinite Rekursion|transfiniter Rekursion]] wie folgt schreiben:
:<math>v_\alpha := \widehat{\left(w_\alpha - \sum_{\beta < \alpha}\langle v_\beta, w_\alpha\rangle \cdot v_\beta\right)}</math>
Hierbei ist die Summe aufgrund der [[besselsche Ungleichung|besselschen Ungleichung]] [[Wohldefiniertheit|wohldefiniert]] (insbesondere sind stets nur abzählbar viele Summanden ungleich Null).

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

[[Kategorie:Lineare Algebra]]

Gram-Schmidtsches Orthogonalisierungsverfahren - Versionsgeschichte

imported>314artemis: /* growthexperiments-addlink-summary-summary:2|0|0 */