Gram–Schmidt-eljárás

A főként a lineáris algebrában és a numerikus analízisben használatos Gram–Schmidt-ortogonalizálás (avagy Gram–Schmidt-eljárás, esetleg Gram–Schmidt-féle ortogonalizálási eljárás) egy skalárszorzatos tér egy véges, lineárisan független {v_j} vektorrendszerét alakítja át egy olyan {u_j} vektorrendszerré, melynek elemei páronként merőlegesek egymásra (a skalárszorzatra vonatkozóan), más szóval ortogonálisak, és a két vektorrendszer ugyanazt az alteret feszíti ki az említett skalárszorzatos térben.

A módszert Jørgen Pedersen Gram és Erhard Schmidt után nevezték el, bár korábban Laplace-nál is szerepelt az eljárás. A Gram–Schmidt-ortogonalizálás egy általánosításának tekinthető a Lie-csoportok elméletében szereplő Iwasawa-dekompozíció.

Az eljárás alkalmazható például a reguláris mátrixok QR-felbontásánál.

Lebegőpontos számításokhoz kevéssé alkalmas, mivel a felhalmozódó kerekítési hibák miatt a kapott vektorok nem lesznek ortogonálisak. Egyes módosítások kiküszöbölik ezt a hibát, így alkalmassá téve a módszert ezekre a számításokra.

A Gram–Schmidt-eljárás

Az egydimenziós altérre vetítés

Pre-Hilbert-térben (skalárszorzatos térben) az u nemnulla vektor alterébe merőlegesen vetít a

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{𝐮}𝐱=⟨𝐮,𝐱⟩\frac{𝐮}{\Vert 𝐮{\Vert }^2}$

leképezés, ahol <u, x> a két vektor skaláris szorzatát jelöli. A projekciótételből következik ugyanis, hogy pre-Hilbert-térben, ha létezik olyan y vektor az u kifeszítette altérben, hogy minden λ ∈ C(ill. R)-re

$\Vert 𝐱-𝐲\Vert \le \Vert 𝐱-\lambda .𝐮\Vert$

akkor az ilyen y-t egyértelműen jellemzi az, hogy minden λ ∈ C (illetve R)-re:

$⟨𝐱-𝐲,\lambda .𝐮⟩=0$

És valóban létezik ilyen y éspedig pont a fenti projekció, ugyanis

$⟨𝐱-⟨𝐮,𝐱⟩\frac{𝐮}{\Vert 𝐮{\Vert }^2},\lambda .𝐮⟩=⟨𝐱,\lambda .𝐮⟩-⟨𝐮,𝐱⟩\frac{\lambda .{𝐮}^2}{\Vert 𝐮{\Vert }^2}=⟨𝐱,\lambda .𝐮⟩-⟨\lambda .𝐮,𝐱⟩\cdot 1=0$

Az eljárás

A Gram–Schmidt-eljárás első lépése: vetítsük merőlegesen v₂-t v₁-re. Ekkor Span(v₁,v₂) = Span(v₁,v₂ - proj v₂) és az utóbbiak merőlegesek.

Legyen {v₁, ... , v_n } lineárisan független vektorrendszer. Azt az {u₁, ... , u_n } vektorrendszert, melynek elemei páronként merőlegesek és Span(v₁, ... , v_n) = Span(u₁, ... , u_n) (azaz ugyanazt az alteret feszítik ki, ugyanaz a generált Span(...) részalgebrájuk) a következőképpen kapjuk. Legyen u₁=v₁. Vetítsük v₂-t merőlegesen u₁-re, legyen ez w₂. Ekkor u₂ = v₂ – w₂. Tegyük ezt v₃-mal és u₁-vel illetve u₂-vel ... Ha ortonormált bázist akarunk, akkor osszuk le az u_k-kat a hosszukkal.

	${𝐮}_1={𝐯}_1,$		${𝐞}_1=\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }$
	${𝐮}_2={𝐯}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}{𝐯}_2,$		${𝐞}_2=\frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }$
	${𝐮}_3={𝐯}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}{𝐯}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}{𝐯}_3,$		${𝐞}_3=\frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }$
	${𝐮}_4={𝐯}_4-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}{𝐯}_4-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}{𝐯}_4-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_3}{𝐯}_4,$		${𝐞}_4=\frac{{𝐮}_4}{\Vert {𝐮}_4\Vert }$
	$⋮$		$⋮$
	${𝐮}_n={𝐯}_n-\sum _{k=1}^{n-1}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_k}{𝐯}_n,$		${𝐞}_n=\frac{{𝐮}_n}{\Vert {𝐮}_n\Vert }$

Helyesség

Annak az igazolása, hogy az eljárás valóban a kívánt eredményt adja a következő.

Először belátjuk, hogy az {u_k} vektorrendszer bázisa a {v_k} vektorrendszer által kifeszített L lineáris altérnek. Mivel L dimenziója a feltevés miatt éppen |{v_k}| = n, ezért elég belátni, hogy {u_k} generálja L-et. Tudjuk:

${𝐮}_1={𝐯}_1$

${𝐮}_2={𝐯}_2-{\lambda }_{21}{𝐮}_1$

${𝐮}_3={𝐯}_3-{\lambda }_{32}{𝐮}_2-{\lambda }_{31}{𝐮}_1$

$⋮$

${𝐮}_n={𝐯}_n-\sum _{k=1}^{n-1}{\lambda }_{nk}{𝐮}_k$

alkalmas λ_ij számokkal. Valójában tetszőleges λ_ij-kre generálja {u_k} az L-et, mert minden k-ra v_k előáll az u₁, ... , u_k-k lineáris kombinációjaként, azaz előállítják az összes bázisvektort, melyek viszont előállítják L összes elemét.

Másodszor belátjuk, hogy minden k = 1, ..., n-re az algoritmus által előállított {u₁,...,u_k} ortogonális, azaz

$⟨{𝐮}_i,{𝐮}_j⟩\{\begin{array}{ccc}\ne 0,& \mathrm{h}\mathrm{a}& i=j\\ =0,& \mathrm{h}\mathrm{a}& i\ne j\end{array}$

k=1 esetén az egyetlen nemnulla u teljesíti az ortogonalitási kritériumot. Ha 1, ..., k–1 már teljesíti a páronkénti ortogonalitást, akkor az u_k vektor mindegyik addigira merőleges, mert

$⟨{𝐮}_i,{𝐮}_k⟩=⟨{𝐮}_i,{𝐯}_k-\sum _{j=1}^{k-1}{\lambda }_{kj}{𝐮}_j⟩=⟨{𝐮}_i,{𝐯}_k⟩-\sum _{j=1}^{k-1}{\lambda }_{kj}⟨{𝐮}_i,{𝐮}_j⟩=$

$=⟨{𝐮}_i,{𝐯}_k⟩-{\lambda }_{ki}⟨{𝐮}_i,{𝐮}_i⟩=⟨{𝐮}_i,{𝐯}_k⟩-\frac{⟨{𝐮}_i,{𝐯}_k⟩}{\Vert {𝐮}_i{\Vert }^2}⟨{𝐮}_i,{𝐮}_i⟩=0$,

hiszen az algoritmusból kiolvasva éppen

${\lambda }_{ki}=\frac{⟨{𝐮}_i,{𝐯}_k⟩}{\Vert {𝐮}_i{\Vert }^2}$.

Megjegyzések

• Az eljárás általános k-adik lépésének formuláját így is írhatjuk:

${𝐯}_k={𝐮}_k+\sum _{i=1}^{k-1}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_i}{𝐯}_k$.

Eszerint ha már megvan az {u₁, ..., u_k–1} ortogonális rendszer, akkor a k-adik lépésben nem mást teszünk, mint vesszük a v_k vektor új, már meglévő báziselemekre eső merőleges vetületét és kiválasztjuk, hogy melyik u_k vektor az, amelyiket a vetületekhez adva v_k előáll. Míg a projekciótétel, lévén tiszta egzisztenciatétel, csak azt állítja, hogy létezik ilyen vektor, addig a Gram–Schmidt-eljárás konstruktívan adja meg a vetületet, éspedig:

${𝐦}_0={𝐯}_k-{𝐮}_k=\sum _{i=1}^{k-1}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_i}{𝐯}_k$.

A helyességi gondolatmenetben pont azt látjuk be, hogy a v_k – m₀ vektor merőleges a Span({u₁, ..., u_k–1}) altérre, hisz mindegyik bázisvektorára merőleges.

• Végtelen dimenziós altér esetén szintén alkalmazható az eljárás, azzal az eredménnyel, hogy az előállított (u₁, ..., u_k, ...) sorozatban bármely k-ig az u₁, ..., u_k vektorok páronként ortogonálisak. Itt a függetlenség azt jelenti, hogy egy elem sem fekszik a korábbiak lineáris burkában. Megszámlálható esetben (szeperábilis Hilbert-terekben) az ortogonalizáció visszavezethető véges esetre. Általában minden független rendszer a jólrendezési tétel szerint felírható egy ${\left({𝐰}_{\alpha }\right)}_{\alpha <d}$ sorozatként, ahol $d$ kardinális szám, és $\alpha$ ordinális szám. Ha a rendszer lineáris burka sűrű, akkor $d$ a Hilbert-tér dimenziója. Jelölje $H$ a teret, és legyen ${\pi }_A:H\to A$ egy ortogonális projekció az $A$ altérre, ami a teljesség miatt mindig létezik, és $\widehat{𝐱}$ legyen az $\frac{𝐱}{\Vert 𝐱\Vert }$ normált vektor. Így adódik egy ${\left({𝐯}_{\alpha }\right)}_{\alpha <d}$ ortonormált rendszer, ahol

$A_{\alpha }:=\overline{\mathrm{span}\left(\{{𝐰}_{\beta }:\beta <\alpha \}\right)}$

${𝐯}_{\alpha }:=\widehat{({𝐰}_{\alpha }-{\pi }_{A_{\alpha }}\left({𝐰}_{\alpha }\right))}$.

• Transzfinit indukcióval megmutatható, hogy $A_{\alpha }=\overline{\mathrm{span}\left(\{{𝐯}_{\beta }:\beta <\alpha \}\right)}$, továbbá $\alpha =d$. Explicit transzfinit rekurzióval:

${𝐯}_{\alpha }:=\widehat{({𝐰}_{\alpha }-\sum _{\beta <\alpha }⟨{𝐯}_{\beta },{𝐰}_{\alpha }⟩\cdot {𝐯}_{\beta })}$

A Bessel-egyenlőtlenség miatt az összeg jóldefiniált (legfeljebb megszámlálható sok elem különbözik nullától).

• Lineárisan összefüggő vektorrendszerre alkalmazva az eljárást az eredményben előbb-utóbb előáll a 0 vektor. Ha ugyanis a k-adik vektor már az előzőek által kifeszített altérben van, akkor a vektorból az altérre eső vetületét kivonva a 0-t kapjuk. A lineárisan összefüggő vektorok által kifeszített alteret is lehet azonban ortogonális vektorokkal előállítani, éspedig úgy, hogy az algoritmusban minden új bázisvektor esetén megnézzük, hogy 0-t ad-e és ha igen, a régi vektort elvetjük és folytatjuk egy másik elem előállításával. Ekkor az algoritmus eredménye annyi vektor lesz, amennyi az eredeti vektorrendszer rangja volt.

• Az eljárás alatt az addig kiszámolt ${𝐯}_1,\dots ,{𝐯}_i$ vektorok ugyanazt az alteret feszítik ki, mint az eredeti ${𝐰}_1,\dots ,{𝐰}_i$ vektorok. A ${𝐯}_1,\dots ,{𝐯}_i$ vektorok ortogonális bázist alkotnak a megfelelő altérben. Más szóval, az egyik rendszert a másik rendszer bázisában jobb felső háromszögmátrix fejezi ki. Ennek a mátrixnak pozitív a determinánsa, így az eredményként kapott ortogonális bázis irányítása megegyezik az eredetivel. Ha az ortonormált ${𝐯}_1,\dots ,{𝐯}_n$ vektorokból, mint oszlopokból megalkotjuk a Q mátrixot, és az eredeti ${𝐰}_1,\dots ,{𝐰}_n$ vektorokból az A mátrixot, akkor van egy R háromszögmátrix, úgy, hogy A=QR, tehát egy QR-felbontáshoz jutunk.

• QR-felbontás más módszerekkel is meghatározható, így Givens-forgatásokkal vagy Householder-tükrözésekkel.

• Kézzel számoláskor egyszerűbb, ha először csak ortogonalizálunk, és csak a végén normalizálunk. Így elkerüljük a kétszeres normalizációt, és gyakran egyszerűbb értékekkel kell számolni. Kifizetődő az ortogonalizáció előtt egy Gauß-eliminációt is elvégezni.

Példa

Vegyük az

$A=\left[\begin{array}{ccc}1& 2& 1\end{array}\right]$

mátrix magterét mint R³ alterét és adjunk meg benne egy ortogonális bázist!

A feladatot az

$𝐚𝐛=\sum _{i=1}^3{𝐚}_i{𝐛}_i$

sztenderd skalárszorzat szerint végezzük el!

Megoldás:

A dimenziótétel szerint a magtér kétdimenziós, ugyanis dim(R³) = dim Ker A + dim Im A, de A oszlopai skalárok, így dim Im A = 1. A kétdimenziós magtérnek kételemű a bázisa. A magtér egy alkalmas bázisa lehet az {v₁ = (2, -1, 0), v₂ = (1, 0, -1)}, mert a két vektor nyilvánvalóan lineárisan független, és mindkettő magtérbeli, mivel

$\left[\begin{array}{ccc}1& 2& 1\end{array}\right]\cdot \left[\begin{array}{cc}2& 1\\ -1& 0\\ 0& -1\end{array}\right]=\left[\begin{array}{cc}0& 0\end{array}\right]$.

Feladatunk most már a bázisvektorok oszlopmátrixának ortogonalizálása. Alkalmazzuk az eljárást {v₁, v₂}-re!

${𝐮}_1={𝐯}_1=\left[\begin{array}{c}2\\ -1\\ 0\end{array}\right]$,

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}{𝐯}_2=⟨{𝐮}_1,{𝐯}_2⟩\frac{{𝐮}_1}{\Vert {𝐮}_1{\Vert }^2}=\frac{2\cdot 1+(-1)\cdot 0+0\cdot (-1)}{2^2+(-1{)}^2+0^2}\left[\begin{array}{c}2\\ -1\\ 0\end{array}\right]=\frac{2}{5}\cdot \left[\begin{array}{c}2\\ -1\\ 0\end{array}\right]=\left[\begin{array}{c}\frac{4}{5}\\ -\frac{2}{5}\\ 0\end{array}\right]$,

${𝐮}_2={𝐯}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}{𝐯}_2=\left[\begin{array}{c}1\\ 0\\ -1\end{array}\right]-\left[\begin{array}{c}\frac{4}{5}\\ -\frac{2}{5}\\ 0\end{array}\right]=\left[\begin{array}{c}\frac{1}{5}\\ \frac{2}{5}\\ -1\end{array}\right]$.

Ellenőrizzük vektoriális szorzattal! Mivel

$\mathrm{K}\mathrm{e}\mathrm{r}A=\{(x,y,z)\in {𝐑}^3\mid x+2y+z=0\}$,

ezért nincs más feladatunk, mint a

$x+2y+z=0$

síkban lévő két merőleges vektort mondanunk. Legyen ugyanaz az első:

${𝐮}_1=\left[\begin{array}{c}2\\ -1\\ 0\end{array}\right]$,

ez valóban a síkban van. Most vegyük az (1, 2, 1) normálvektor és az előbbi vektoriális szorzatát:

${𝐮}_1=\left|\begin{array}{ccc}𝐢& 𝐣& 𝐤\\ 1& 2& 1\\ 2& -1& 0\end{array}\right|=1𝐢+2𝐣-5𝐤$,

ami valóban párhuzamos a fent kapott vektorral, éspedig az 5-szöröse. Ebből is világosan látható, hogy az ortogonális vektorrendszer nem egyértélmű (még akkor sem, ha egységvektorokat választunk bázisnak).

Ortonormalizáció

Az algoritmus egy változata nemcsak ortogonalizál, hanem normalizál is, így a ${𝐰}_1,\dots ,{𝐰}_n$ független vektorokból ortonormált rendszert kapunk, ami ugyanazt az alteret generálja, mint a kiindulási vektorok.

A ${𝐯}_1,\dots ,{𝐯}_n$ vektorok ortonormált rendszert alkotnak, hogyha az ortogonalizáció után normáljuk is őket:

${𝐯}_1=\frac{{𝐰}_1}{\Vert {𝐰}_1\Vert }$ (az első vektor normalizációja)

${𝐯}_2^{\prime }={𝐰}_2-⟨{𝐯}_1,{𝐰}_2⟩\cdot {𝐯}_1$ (a második vektor ortogonalizációja)

${𝐯}_2=\frac{{𝐯}_2^{\prime }}{\Vert {𝐯}_2^{\prime }\Vert }$ (a második vektorból kapott ${𝐯}_2^{\prime }$ vektor normalizációja)

${𝐯}_3^{\prime }={𝐰}_3-⟨{𝐯}_1,{𝐰}_3⟩\cdot {𝐯}_1-⟨{𝐯}_2,{𝐰}_3⟩\cdot {𝐯}_2$ (a harmadik vektor ortogonalizációja)

${𝐯}_3=\frac{{𝐯}_3^{\prime }}{\Vert {𝐯}_3^{\prime }\Vert }$ (a harmadik vektorból kapott ${𝐯}_3^{\prime }$ vektor normalizációja)

$⋮$

${𝐯}_n^{\prime }={𝐰}_n-\sum _{i=1}^{n-1}⟨{𝐯}_i,{𝐰}_n⟩\cdot {𝐯}_i$ (az $n$-edik vektor ortogonalizációja)

${𝐯}_n=\frac{{𝐯}_n^{\prime }}{\Vert {𝐯}_n^{\prime }\Vert }$ (a ${𝐯}_n=\frac{{𝐯}_n^{\prime }}{\Vert {𝐯}_n^{\prime }\Vert }$-edik vektorból kapott ${𝐯}_n^{\prime }$ vektor normalizációja)

Másként, a ${𝐯}_j$ és a ${𝐯}_j^{\prime }$ vektorok, ahol $j=1,2,\dots ,n$, rekurzívan is definiálhatók:

${𝐯}_j^{\prime }={𝐰}_j-\sum _{i=1}^{j-1}⟨{𝐯}_i,{𝐰}_j⟩\cdot {𝐯}_i$ és ${𝐯}_j=\frac{{𝐯}_j^{\prime }}{\Vert {𝐯}_j^{\prime }\Vert }$

Általában nem kapunk kitüntetett rendszert. A jobb- vagy balsodrású rendszerhez először rendezni kell a vektorokat.

Példa

${ℝ}^2$-ben a $⟨\cdot ,\cdot ⟩$ skalárszorzattal adva van a következő bázis:

${𝐰}_1=\left(\begin{array}{c}3\\ 1\end{array}\right),{𝐰}_2=\left(\begin{array}{c}2\\ 2\end{array}\right)$

Ezekből kiszámítunk egy ${𝐯}_1$ és ${𝐯}_2$ vektort, melyek ${ℝ}^2$ egy ortonormált bázisát alkotják.

${𝐯}_1=\frac{{𝐰}_1}{\Vert {𝐰}_1\Vert }=\frac{1}{\sqrt{10}}\cdot \left(\begin{array}{c}3\\ 1\end{array}\right)$

${𝐯}_2^{\prime }={𝐰}_2-⟨{𝐯}_1,{𝐰}_2⟩\cdot {𝐯}_1=\left(\begin{array}{c}2\\ 2\end{array}\right)-\frac{1}{\sqrt{10}}\cdot ⟨\left(\begin{array}{c}3\\ 1\end{array}\right),\left(\begin{array}{c}2\\ 2\end{array}\right)⟩\cdot \frac{1}{\sqrt{10}}\left(\begin{array}{c}3\\ 1\end{array}\right)=\frac{1}{5}\left(\begin{array}{c}-2\\ 6\end{array}\right)$

${𝐯}_2=\frac{{𝐯}_2^{\prime }}{\Vert {𝐯}_2^{\prime }\Vert }=\sqrt{\frac{25}{40}}\cdot \frac{1}{5}\left(\begin{array}{c}-2\\ 6\end{array}\right)=\frac{1}{\sqrt{10}}\cdot \left(\begin{array}{c}-1\\ 3\end{array}\right)$

Források

• Freud Róbert: Lineáris algebra (ELTE Eötvös Kiadó, 1998)
• Szörényi Miklós: Szemléletes lineáris algebra - összefoglaló I. informatikusoknak Sablon:Pdf (SZE MTK jegyzet, 2005)
• A kétdimenziós és háromdimenziós eset számítógépes animációval
• MIT Linear Algebra Lecture on Gram-Schmidt Sablon:En
• K. Kirchgessner, M. Schreck: Vektoranalysis für Dummies. Das Pocketbuch Paperback . Wiley-VCH, 2012. Sablon:ISBN