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 (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 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 Fehler nicht haben. Weitere Möglichkeiten für 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.
Algorithmus des Orthogonalisierungsverfahrens

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:
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.
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
)
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,
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).



© biancahoegel.de
Datum der letzten Änderung: Jena, den: 03.08. 2022