Gram-schmidtmethode

Eerste twee stappen van de gram-schmidtmethode

De gram-schmidtmethode is een algoritme waarmee in een vectorruimte voorzien van een inproduct van gegeven vectoren, die lineair onafhankelijk zijn, een orthogonaal stelsel wordt gemaakt dat dezelfde deelruimte opspant als de oorspronkelijke vectoren. De methode bepaalt achter elkaar van elke volgende vector de component die orthogonaal is met alle vorige. Die component wordt gevonden door het verschil te bepalen met de projectie op de deelruimte die door de vorige vectoren wordt opgespannen. Door de gevonden vectoren te normeren ontstaat een orthonormaal stelsel.

De methode is naar Jørgen Pedersen Gram en Erhard Schmidt genoemd, maar is van oudere datum en werd al gevonden door Laplace en Cauchy. De methode is in de theorie van lie-groepen gegeneraliseerd door Kenkichi Iwasawa.

Methode

In een vectorruimte met inproduct ⟨ ⋅ , ⋅ ⟩ {\displaystyle \langle \cdot ,\cdot \rangle } zijn de lineair onafhankelijke vectoren x 1 , x 2 , … , x n {\displaystyle \mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n}} gegeven. Er staat hieronder beschreven hoe de gram-schmidtmethode de orthogonale vectoren y 1 , y 2 , … , y n {\displaystyle \mathbf {y} _{1},\mathbf {y} _{2},\ldots ,\mathbf {y} _{n}} berekent met dezelfde span als deze vectoren x {\displaystyle \mathbf {x} } . De vectoren y {\displaystyle \mathbf {y} } worden in deze beschrijving niet genormeerd:

y 1 = x 1 {\displaystyle \mathbf {y} _{1}=\mathbf {x} _{1}}

Vervolgens geldt voor i = 2 , … , n {\displaystyle i=2,\ldots ,n} :

y i = x i − ∑ j = 1 i − 1 ⟨ y j , x i ⟩ ⟨ y j , y j ⟩ y j {\displaystyle \mathbf {y} _{i}=\mathbf {x} _{i}-\sum _{j=1}^{i-1}{\frac {\langle \mathbf {y} _{j},\mathbf {x} _{i}\rangle }{\langle \mathbf {y} _{j},\mathbf {y} _{j}\rangle }}\mathbf {y} _{j}}

De vector y i {\displaystyle \mathbf {y} _{i}} is dus gelijk aan x i {\displaystyle \mathbf {x} _{i}} waarvan eerst alle componenten zijn afgetrokken die al in de deelruimte liggen, die door de geconstrueerde orthogonale vectoren wordt opgespannen. De formule toont zo ook dat de projectie van x i {\displaystyle \mathbf {x} _{i}} op de ruimte opgespannen door die vectoren y 1 , y 2 , … , y i − 1 {\displaystyle \mathbf {y} _{1},\mathbf {y} _{2},\ldots ,\mathbf {y} _{i-1}} de som is van de afzonderlijke projecties

⟨ y j , x i ⟩ ⟨ y j , y j ⟩ y j {\displaystyle {\frac {\langle \mathbf {y} _{j},\mathbf {x} _{i}\rangle }{\langle \mathbf {y} _{j},\mathbf {y} _{j}\rangle }}\mathbf {y} _{j}}

Dat is alleen correct als y 1 , y 2 , … , y i − 1 {\displaystyle \mathbf {y} _{1},\mathbf {y} _{2},\ldots ,\mathbf {y} _{i-1}} onderling orthogonaal zijn, omdat de projecties anders met elkaar interfereren en er te veel van x i {\displaystyle \mathbf {x} _{i}} wordt afgetrokken.

Voorbeeld 1

De drie vectoren

x 1 = ( 3 , 1 , 2 , 1 ) , x 2 = ( 2 , 2 , 2 , 3 ) , x 3 = ( 2 , 1 , 3 , 2 ) {\displaystyle \mathbf {x} _{1}=(3,1,2,1),\quad \mathbf {x} _{2}=(2,2,2,3),\quad \mathbf {x} _{3}=(2,1,3,2)} ,

in R 4 {\displaystyle \mathbb {R} ^{4}} met het gewone inproduct, zijn lineair onafhankelijk en spannen een driedimensionale deelruimte op. In deze deelruimte kan met de gram-schmidtmethode uit de drie gegeven vectoren een orthogonale basis { b 1 , b 2 , b 3 } {\displaystyle \{\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\}} worden bepaald.

b 1 = x 1 = ( 3 , 1 , 2 , 1 ) {\displaystyle \mathbf {b} _{1}=\mathbf {x} _{1}=(3,1,2,1)}
b 2 = x 2 − ⟨ b 1 , x 2 ⟩ ⟨ b 1 , b 1 ⟩ b 1 = ( 2 , 2 , 2 , 3 ) − 15 15 ( 3 , 1 , 2 , 1 ) = ( − 1 , 1 , 0 , 2 ) {\displaystyle \mathbf {b} _{2}=\mathbf {x} _{2}-{\frac {\langle \mathbf {b} _{1},\mathbf {x} _{2}\rangle }{\langle \mathbf {b} _{1},\mathbf {b} _{1}\rangle }}\mathbf {b} _{1}=(2,2,2,3)-{\tfrac {15}{15}}(3,1,2,1)=(-1,1,0,2)}
b 3 = x 3 − ⟨ b 1 , x 3 ⟩ ⟨ b 1 , b 1 ⟩ b 1 − ⟨ b 2 , x 3 ⟩ ⟨ b 2 , b 2 ⟩ b 2 = {\displaystyle \mathbf {b} _{3}=\mathbf {x} _{3}-{\frac {\langle \mathbf {b} _{1},\mathbf {x} _{3}\rangle }{\langle \mathbf {b} _{1},\mathbf {b} _{1}\rangle }}\mathbf {b} _{1}-{\frac {\langle \mathbf {b} _{2},\mathbf {x} _{3}\rangle }{\langle \mathbf {b} _{2},\mathbf {b} _{2}\rangle }}\mathbf {b} _{2}=}
= ( 2 , 1 , 3 , 2 ) − 15 15 ( 3 , 1 , 2 , 1 ) − 3 6 ( − 1 , 1 , 0 , 2 ) = 1 2 ( − 1 , − 1 , 2 , 0 ) {\displaystyle =(2,1,3,2)-{\tfrac {15}{15}}(3,1,2,1)-{\tfrac {3}{6}}(-1,1,0,2)={\tfrac {1}{2}}(-1,-1,2,0)}

Het is na te gaan dat:

⟨ b 1 , b 2 ⟩ = ⟨ b 1 , b 3 ⟩ = ⟨ b 2 , b 3 ⟩ = 0 {\displaystyle \langle \mathbf {b} _{1},\mathbf {b} _{2}\rangle =\langle \mathbf {b} _{1},\mathbf {b} _{3}\rangle =\langle \mathbf {b} _{2},\mathbf {b} _{3}\rangle =0}

Voorbeeld 2

In de tweedimensionale reële vectorruimte van lineaire functies f ( t ) = p + q t {\displaystyle f(t)=p+qt} op het interval [   0 , 1   ] {\displaystyle [\ 0,1\ ]} , met inwendig product, zie het voorbeeld van een tweedimensionale functieruimte

⟨ f 1 , f 2 ⟩ = ∫ 0 1 f 1 ( t ) f 2 ( t )   d t {\displaystyle \langle f_{1},f_{2}\rangle =\int _{0}^{1}{f_{1}(t)f_{2}(t)\ \mathrm {d} t}}

wordt de basis die uit e 1 ( t ) = 1 {\displaystyle e_{1}(t)=1} en e 2 ( t ) = t {\displaystyle e_{2}(t)=t} bestaat met de gram-schmidtmethode in een orthonormaal stelsel b 1 , b 2 {\displaystyle b_{1},b_{2}} omgezet. Om te beginnen is

b 1 ( t ) = e 1 ( t ) = 1 {\displaystyle b_{1}(t)=e_{1}(t)=1} .

De component b {\displaystyle b} van e 2 {\displaystyle e_{2}} loodrecht op b 1 {\displaystyle b_{1}} is

b = e 2 − ⟨ b 1 , e 2 ⟩ ⟨ b 1 , b 1 ⟩ b 1 = e 2 − 1 2 b 1 = t − 1 2 {\displaystyle b=e_{2}-{\frac {\langle b_{1},e_{2}\rangle }{\langle b_{1},b_{1}\rangle }}b_{1}=e_{2}-{\tfrac {1}{2}}b_{1}=t-{\tfrac {1}{2}}}

Normering van b {\displaystyle b} geeft

b 2 ( t ) = b ‖ b ‖ = 2 3   ( t − 1 2 ) {\displaystyle b_{2}(t)={\frac {b}{\|b\|}}=2{\sqrt {3\ }}(t-{\tfrac {1}{2}})}