Gram-Schmidtsches Orthogonalisierungsverfahren

In der linearen Algebra dient das Gram-Schmidtsche Orthogonalisierungsverfahren dazu, zu einer vorgegebenen Menge linear unabhängiger Vektoren v1,…,vnv_1,\dots,v_n eines Prähilbertraums VV ein Orthogonalsystem zu berechnen, dass den gleichen Untervektorraum erzeugt.
Eine Erweiterung stellt das Gram-Schmidtsche Orthonormalisierungsverfahren dar: statt eines Orthogonalsystems berechnet es ein Orthonormalsystem. Bilden die Eingangsvektoren eine Basis, so berechnet das Verfahren eine Orthogonal- bzw. Orthonormalbasis.
 
 

Algorithmus des Orthogonalisierungsverfahrens

Sei VV ein Prähilbertraum und die Vektoren v1,…,vn∈Vv_1, \dots, v_n\in V seien linear unabhängig.
Die einzelnen Vektoren u1,…,unu_1, \dots, u_n des Orthogonalsystem berechnen sich wie folgt:
u1=v1 u_1 = v_1 \,
u2=v2−(⟨v2,u1⟩⟨u1,u1⟩) u1u_2 = v_2 -\over{\langle v_2, u_1\rangle }{ \langle u_1, u_1\rangle} \, u_1
u3=v3−(⟨v3,u1⟩⟨u1,u1⟩) u1−(⟨v3,u2⟩⟨u2,u2⟩) u2u_3 = v_3 -\over{\langle v_3, u_1\rangle }{ \langle u_1, u_1\rangle} \, u_1 -\over{\langle v_3, u_2\rangle }{ \langle u_2, u_2\rangle} \, u_2
⋮\vdots
un=vn−(⟨vn,u1⟩⟨u1,u1⟩) u1−(⟨vn,u2⟩⟨u2,u2⟩) u2−⋯−(⟨vn,un−1⟩⟨un−1,un−1⟩) un−1=vn−∑i=1n−1(⟨vn,ui⟩⟨ui,ui⟩) uiu_n = v_n -\over{\langle v_n, u_1\rangle }{ \langle u_1, u_1\rangle} \, u_1 -\over{\langle v_n, u_2\rangle }{ \langle u_2, u_2\rangle} \, u_2 - \dots -\over{\langle v_n, u_{n-1}\rangle }{ \langle u_{n-1}, u_{n-1}\rangle} \, u_{n-1} = v_n - \sum\limits_{i=1}^{n-1}\over{\langle v_n, u_i\rangle }{ \langle u_i, u_i\rangle} \, u_i

Beispiel

Im R3\mathbb{R}^3 versehen mit dem Standardskalarprodukt ⟨⋅,⋅⟩\langle\cdot,\cdot \rangle seien zwei linear unabhängige Vektoren vorgegeben, die einen Untervektorraum erzeugen:
v1=(312) v_1 = \begin{pmatrix} 3 \\ 1 \\ 2 \end{pmatrix} und v2=(222) v_2 = \begin{pmatrix} 2 \\ 2 \\ 2 \end{pmatrix}
Es werden nun zwei orthogonale Vektoren u1u_1 und u2u_2 berechnet, die denselben Untervektorraum erzeugen:
u1=v1=(312)u_1 = v_1 = \begin{pmatrix} 3 \\ 1 \\ 2 \end{pmatrix}
u2=v2−(⟨v2,u1⟩⟨u1,u1⟩)⋅u1=(222)−1214⋅(312)=27(−241)u_2 = v_2 -\over{\langle v_2, u_1\rangle }{ \langle u_1, u_1\rangle} \cdot u_1 = \begin{pmatrix} 2 \\ 2 \\ 2 \end{pmatrix} - \dfrac{12}{14} \cdot \begin{pmatrix} 3 \\ 1 \\ 2 \end{pmatrix} = \dfrac{2}{7} \begin{pmatrix} -2 \\ 4\\ 1 \end{pmatrix}

Algorithmus des Orthonormalisierungsverfahrens

Sei VV ein Prähilbertraum und die Vektoren v1,…,vn∈Vv_1, \dots, v_n\in V seien linear unabhängig.
Die einzelnen Vektoren u1,…,unu_1, \dots, u_n des Orthonormalsystems erhält man, indem zuerst jeweils ein orthogonaler Vektor berechnet und anschließend normalisiert wird:
u1=v1∥v1∥u_1 = \dfrac{v_1}{\left\|v_1\right\|} (Normalisieren des ersten Vektors v1v_1)
u2′=v2−⟨v2,u1⟩⋅u1u_2^\prime = v_2 - \langle v_2, u_1 \rangle \cdot u_1 (Orthogonalisieren des zweiten Vektors v2v_2)
u2=u2′∥u2′∥u_2 = \dfrac{u_2^\prime}{\left\|u_2^\prime\right\|} (Normalisieren des Vektors u2′u_2^\prime)
u3′=v3−⟨v3,u1⟩⋅u1−⟨v3,u2⟩⋅u2u_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 v3v_3)
u3=u3′∥u3′∥u_3 = \dfrac{u_3^\prime}{\left\|u_3^\prime\right\|} (Normalisieren des Vektors u3′u_3^\prime)
⋮\vdots
un′=vn−∑i=1n−1⟨vn,ui⟩⋅uiu_n^\prime = v_n - \sum\limits_{i=1}^{n-1} \langle v_n, u_i \rangle \cdot u_i (Orthogonalisieren des nn-ten Vektors vnv_n)
un=un′∥un′∥u_n = \dfrac{u_n^\prime}{\left\|u_n^\prime\right\|} (Normalisieren des Vektors un′u_n^\prime)
Im Allgemeinen erhält man durch dieses Verfahren kein besonders ausgezeichnetes System. Im R3\R^3 muss z.B. erst ein Umordnungsschritt nachgeschaltet werden, um ein Rechts- oder Linkssystem zu erhalten.

Beispiel

Im R2\mathbb{R}^2 versehen mit dem Standardskalarprodukt ⟨⋅,⋅⟩\langle\cdot,\cdot \rangle seien zwei Basisvektoren gegeben:
v1=(31),v2=(22) v_1 = \begin{pmatrix} 3 \\ 1 \end{pmatrix},\quad v_2 = \begin{pmatrix} 2 \\ 2 \end{pmatrix}
Es werden nun zwei Vektoren u1u_1 und u2u_2 berechnet, die eine Orthonormalbasis des R2\mathbb{R}^2 bilden.
u1=v1∥v1∥=110⋅(31)u_1 = \dfrac {v_1} {\left\|v_1\right\|} = \dfrac {1} {\sqrt{10}} \cdot \begin{pmatrix} 3 \\ 1 \end{pmatrix}
u2′=v2−⟨v2,u1⟩⋅u1=(22)−110⋅⟨(31),(22)⟩⋅110(31)=15(−26)u_2^\prime = v_2 - \langle v_2, u_1 \rangle \cdot u_1 = \begin{pmatrix} 2 \\ 2 \end{pmatrix} - \dfrac{1}{\sqrt{10}}\cdot \left\langle \begin{pmatrix} 3 \\ 1 \end{pmatrix},\begin{pmatrix} 2 \\ 2 \end{pmatrix} \right\rangle \cdot \dfrac{1}{\sqrt{10}} \begin{pmatrix} 3 \\ 1 \end{pmatrix} = \dfrac{1}{5} \begin{pmatrix} -2 \\ 6 \end{pmatrix}
u2=u2′∥u2′∥=140/25⋅15(−26)=110⋅(−13)u_2 = \dfrac{u_2^\prime}{\left\|u_2^\prime\right\|} = \dfrac{1}{\sqrt{40/25}} \cdot \dfrac{1}{5} \begin{pmatrix} -2 \\ 6 \end{pmatrix} = \dfrac{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 u1,…,uiu_1, \dots, u_i den gleichen Vektorraum erzeugen wie die Vektoren v1,…,viv_1, \dots, v_i. Die Vektoren u1,…,uiu_1, \dots, u_i bilden also eine Orthogonal- bzw. Orthonormalbasis der entsprechenden Untervektorräume.
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 u1,…,uk−1u_1, \dots , u_{k-1} bereits bestimmt, versuchen wir, von vkv_k eine passende Linearkombination der Vektoren u1,…,uk−1u_1, \dots , u_{k-1} abzuziehen, so dass der Differenzvektor
uk=vk−∑i=1k−1λiuiu_k = v_k - \sum\limits_{i=1}^{k-1} \lambda_i u_i
zu allen Vektoren u1,…,uk−1u_1, \dots , u_{k-1} orthogonal wird, d.h. jedes der Skalarprodukte
⟨uk,uj⟩=⟨vk,uj⟩−∑i=1k−1λi⟨ui,uj⟩\langle u_k,u_j \rangle = \langle v_k,u_j \rangle - \sum\limits_{i=1}^{k-1} \lambda_i \langle u_i,u_j \rangle
mit j=1,…,k−1j=1,\ldots,k-1 muss den Wert 0 ergeben. Hierfür ist die Wahl
λi=⟨vk,ui⟩⟨ui,ui⟩\lambda_i = \dfrac {\langle v_k,u_i \rangle}{\langle u_i,u_i \rangle} passend.
Setzte man dieses λi\lambda_i ein, so erhält man
⟨uk,uj⟩=⟨vk,uj⟩−∑i=1k−1⟨vk,ui⟩⟨ui,ui⟩⟨ui,uj⟩\langle u_k,u_j \rangle = \langle v_k,u_j \rangle - \sum\limits_{i=1}^{k-1} \dfrac {\langle v_k,u_i \rangle}{\langle u_i,u_i \rangle} \langle u_i,u_j \rangle
=⟨vk,uj⟩−⟨vk,uj⟩= \langle v_k,u_j \rangle - \langle v_k,u_j \rangle
=0= 0

Die Mathematik ist eine Art Spielzeug, welches die Natur uns zuwarf zum Troste und zur Unterhaltung in der Finsternis.

Jean-Baptist le Rond d'Alembert

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Gram-Schmidtsches Orthogonalisierungsverfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Banach-Raum