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 und bezeichnet, gegebenenfalls mit Indizes wie und . Es wird sowohl auf übergesetzte Pfeile als auch auf Fettdruck verzichtet. Das Skalarprodukt wird durch spitze Klammern dargestellt: . Im komplexen Fall wird dabei die Konvention verwendet, dass das Skalarprodukt im ersten Argument semilinear, im zweiten Argument linear ist, das heißt
für alle Vektoren , und alle . 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 die Norm des Vektors .
Algorithmus des Orthogonalisierungsverfahrens
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/Gram-Schmidt_orthonormalization_process.gif/220px-Gram-Schmidt_orthonormalization_process.gif)
Der folgende Algorithmus berechnet zu den linear unabhängigen Vektoren ein Orthogonalsystem von paarweise orthogonalen Vektoren, das denselben Untervektorraum erzeugt.
Die einzelnen Vektoren des Orthogonalsystems berechnen sich wie folgt:
Anders gesagt werden die für also rekursiv durch
definiert.
Beispiel
Im versehen mit dem Standardskalarprodukt seien zwei linear unabhängige Vektoren vorgegeben, die einen Untervektorraum erzeugen:
Es werden nun zwei orthogonale Vektoren und berechnet, die denselben Untervektorraum erzeugen:
Algorithmus des Orthonormalisierungsverfahrens
Der folgende Algorithmus berechnet zu den linear unabhängigen Vektoren ein Orthonormalsystem von 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 des Orthonormalsystems erhält man, indem zuerst jeweils ein orthogonaler Vektor berechnet und anschließend normalisiert wird:
- (Normalisieren des ersten Vektors )
- (Orthogonalisieren des zweiten Vektors )
- (Normalisieren des Vektors )
- (Orthogonalisieren des dritten Vektors )
- (Normalisieren des Vektors )
- (Orthogonalisieren des -ten Vektors )
- (Normalisieren des Vektors )
- (Orthogonalisieren des zweiten Vektors )
Anders gesagt werden die und für also rekursiv durch
- und definiert.
Im Allgemeinen erhält man durch dieses Verfahren kein besonders ausgezeichnetes System. Im muss z. B. erst ein Umordnungsschritt nachgeschaltet werden, um ein Rechts- oder Linkssystem zu erhalten.
Beispiel
Im versehen mit dem Standardskalarprodukt seien zwei Basisvektoren gegeben:
Es werden nun zwei Vektoren und berechnet, die eine Orthonormalbasis des bilden.
Anmerkungen
Eine besondere Eigenschaft der beiden Verfahren ist, dass nach jedem Zwischenschritt die bisher berechneten Vektoren den gleichen Vektorraum erzeugen wie die Vektoren . Die Vektoren 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 als Spalten einer Matrix Q zusammen, ebenso die Vektoren des Ausgangssystems 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.
Prinzip des Verfahrens
Sind die orthogonalen Vektoren bereits bestimmt, versuchen wir, von eine passende Linearkombination der Vektoren abzuziehen, sodass der Differenzvektor
zu allen Vektoren orthogonal wird. Dies ist gleichbedeutend damit, dass das Skalarprodukt für alle den Wert 0 ergibt. Eine solche Linearkombination ergibt sich, wenn für jedes der Ausdruck
gewählt wird. Eine Kontrollrechnung zeigt, dass dadurch alle Skalarprodukte mit den Wert 0 annehmen:
Orthonormalisierung unendlicher Systeme von Vektoren
In einem beliebigen Hilbertraum 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 Abschluss der linearen Hülle der übrigen Vektoren liegt. Den Fall eines abzählbaren Systems (d. h. ist ein separabler Hilbertraum) kann direkt auf den oben dargestellten endlichen Fall zurückgeführt werden: Gegeben sei eine unabhängige Folge , so erhält man eine entsprechende orthonormale Folge , indem man für jedes das obige Verfahren anwendet und erhält. Allgemeiner kann jedes unabhängige System nach dem Wohlordnungssatz als Folge für eine Kardinalzahl und Ordinalzahlen angesehen werden (im Falle einer dichten linearen Hülle des unabhängigen Systems ist gerade die Dimension von ). Bezeichne nun die orthogonale Projektion auf einen abgeschlossenen Teilraum , die aufgrund der Vollständigkeit des Raumes stets existiert, und bezeichne die Normierung . So ergibt sich ein Orthonormalsystem durch
- .
Per transfiniter Induktion lässt sich dann zeigen, dass , sogar für . Expliziter lässt sich das Verfahren per transfiniter Rekursion wie folgt schreiben:
Hierbei ist die Summe aufgrund der besselschen Ungleichung 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
Auf dieser Seite verwendete Medien
The animation illustrates the Gram-Schmidt process for obtaining an orthonormal basis of vectors, in this particular case, in 3-dimensional euclidean space.
- The first of the original vectors, v1, is taken as the first vector of the orthogonal basis, u1.
- The second of the original vectors, v2, is then projected onto u1. The projection is subtracted from v2, obtaining a new vector u2, which is orthogonal to u1
- The third of the original vectors, v3, is projected onto u1. The result is subtracted from v3, obtained the intermediate vector v'3. This intermediate vector was used for illustration purposes, in order to show the orthogonalization against each individual vector one at a time. Next, this intermediate vector is projected onto u2, and the resulting vector is subtracted from v'3, resulting in the vector u3, which is orthogonal to both u1 and u2. At this point, we have an orthogonal basis, but not an orthonormal basis, as the vectors are not unit vectors.
- In the last step, the vectors are scaled by the inverse of their norms, a process called normalization. The resulting vectors, e1, e2 and e3 are mutually orthogonal, and are all unit vectors. Therefore, they form an orthonormal basis for the 3-dimensional euclidean space R3. This completes the process.