Gram–Schmidt-eljárás

A Wikipédiából, a szabad enciklopédiából

A matematikában, főként a lineáris algebrában és a numerikus analízisben a Gram–Schmidt-ortogonalizálás (vagy Gram–Schmidt-eljárás) egy skalárszorzatos tér véges, lineárisan független {vj} vektorrendszerét alakítja át olyan {uj} vektorrendszerré, mely elemei páronként merőlegesek (a skalárszorzatra vonatkozóan) és {vj} illetve {uj} ugyanazt az alteret feszíti ki.[1]

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.[2] A Gram–Schmidt-ortogonalizálás egy általánosításának tekinthető a Lie-csoportok elméletében szereplő Iwasawa-dekompozíció.[3]

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

A Gram–Schmidt-eljárás[szerkesztés | forrásszöveg szerkesztése]

Egydimenziós altérre vetítés[szerkesztés | forrásszöveg szerkesztése]

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

\mathrm{proj}_{\mathbf{u}}\,\mathbf{x} =\langle \mathbf{u}, \mathbf{x}\rangle\frac{\mathbf{u}}{\|\mathbf{u}\|^2}

leképezés. 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

\|\mathbf{x}-\mathbf{y}\|\leq\|\mathbf{x}-\lambda.\mathbf{u}\|\,

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

\langle\mathbf{x}-\mathbf{y},\lambda.\mathbf{u}\rangle=0

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

\left\langle \mathbf{x}-\langle \mathbf{u}, \mathbf{x}\rangle\frac{\mathbf{u}}{\|\mathbf{u}\|^2},\lambda.\mathbf{u}\right\rangle=
\langle \mathbf{x},\lambda.\mathbf{u}\rangle-\langle\mathbf{u},\mathbf{x}\rangle\frac{\lambda.\mathbf{u}^2}{\|\mathbf{u}\|^2}=\langle \mathbf{x},\lambda.\mathbf{u}\rangle-\langle\lambda.\mathbf{u},\mathbf{x}\rangle\cdot 1=0

Az eljárás[szerkesztés | forrásszöveg szerkesztése]

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

Legyen {v1, ... , vn } lineárisan független vektorrendszer. Azt az {u1, ... , un } vektorrendszert, melynek elemei páronként merőlegesek és Span(v1, ... , vn) = Span(u1, ... , un) (azaz ugyanazt az alteret feszítik ki, ugyanaz a generált Span(...) részalgebrájuk) a következőképpen kapjuk. Legyen u1=v1. Vetítsük v2-t merőlegesen u1-re, legyen ez w2. Ekkor u2 = v2 - w2. Tegyük ezt v3-mal és u1-vel illetve u2-vel ... Ha ortonormált bázist akarunk, akkor osszuk le az uk-kat a hosszukkal.

\mathbf{u}_1 = \mathbf{v}_1, \mathbf{e}_1 = {\mathbf{u}_1 \over \|\mathbf{u}_1\|}
\mathbf{u}_2 = \mathbf{v}_2-\mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_2, \mathbf{e}_2 = {\mathbf{u}_2 \over \|\mathbf{u}_2\|}
\mathbf{u}_3 = \mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_2}\,\mathbf{v}_3, \mathbf{e}_3 = {\mathbf{u}_3 \over \|\mathbf{u}_3\|}
\mathbf{u}_4 = \mathbf{v}_4-\mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_4-\mathrm{proj}_{\mathbf{u}_2}\,\mathbf{v}_4-\mathrm{proj}_{\mathbf{u}_3}\,\mathbf{v}_4, \mathbf{e}_4 = {\mathbf{u}_4 \over \|\mathbf{u}_4\|}
\vdots \vdots
\mathbf{u}_n = \mathbf{v}_n-\sum_{k=1}^{n-1}\mathrm{proj}_{\mathbf{u}_k}\,\mathbf{v}_n, \mathbf{e}_n = {\mathbf{u}_n\over \|\mathbf{u}_n \|}

Helyesség[szerkesztés | forrásszöveg szerkesztése]

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

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

\mathbf{u}_1 = \mathbf{v}_1
\mathbf{u}_2 = \mathbf{v}_2-\lambda_{21}\mathbf{u}_1
\mathbf{u}_3 = \mathbf{v}_3-\lambda_{32}\mathbf{u}_2-\lambda_{31}\mathbf{u}_1
\vdots
\mathbf{u}_n = \mathbf{v}_n-\sum_{k=1}^{n-1}\lambda_{nk}{\mathbf{u}_k}

alkalmas λij számokkal. Valójában tetszőleges λij-kre generálja {uk} az L-et, mert minden k-ra vk előáll az u1, ... , uk-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 {u1,...,uk} ortogonális, azaz

\langle \mathbf{u}_i, \mathbf{u}_j \rangle\left\{\begin{matrix}\ne 0, & \mathrm{ha} & i=j\\ = 0, & \mathrm{ha} & i\ne j\end{matrix}\right.

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 uk vektor mindegyik addigira merőleges, mert

\langle\mathbf{u}_i,\mathbf{u}_k \rangle= \langle\mathbf{u}_i,\mathbf{v}_k-\sum_{j=1}^{k-1}\lambda_{kj}{\mathbf{u}_j} \rangle=\langle\mathbf{u}_i,\mathbf{v}_k\rangle - \sum_{j=1}^{k-1}\lambda_{kj}\langle\mathbf{u}_i,\mathbf{u}_j \rangle=
=\langle\mathbf{u}_i,\mathbf{v}_k\rangle - \lambda_{ki}\langle\mathbf{u}_i,\mathbf{u}_i \rangle=\langle\mathbf{u}_i,\mathbf{v}_k\rangle - \frac{\langle \mathbf{u}_i,\mathbf{v}_k\rangle}{\|\mathbf{u}_i\|^2}\langle\mathbf{u}_i,\mathbf{u}_i \rangle=0

hiszen az algoritmusból kiolvasva éppen

\lambda_{ki}=\frac{\langle \mathbf{u}_i,\mathbf{v}_k\rangle}{\|\mathbf{u}_i\|^2}\,

Megjegyzések[szerkesztés | forrásszöveg szerkesztése]

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

\mathbf{v}_k=\mathbf{u}_k +\sum_{i=1}^{k-1}\mathrm{proj}_{\mathbf{u}_i}\,\mathbf{v}_k,

Eszerint ha már megvan az {u1,...,uk-1} ortogonális rendszer, akkor a k-adik lépésben nem mást teszünk, mint vesszük a vk vektor új, már meglévő báziselemekre eső merőleges vetületét és kiválasztjuk, hogy melyik uk vektor az, amelyiket a vetületekhez adva vk 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:

\mathbf{m}_0=\mathbf{v}_k-\mathbf{u}_k=\sum_{i=1}^{k-1}\mathrm{proj}_{\mathbf{u}_i}\,\mathbf{v}_k,

A helyeségi gondolatmenetben pont azt látjuk be, hogy a vk - m0 vektor merőleges a Span({u1,...,uk-1}) altérre, hisz mindegyik bázisvektorára merőleges.

Végtelen dimenziós altér esetén szintén alakalmazható az eljárás, azzal az eredménnyel, hogy az előállított (u1,...,uk,...) sorozatban bármely k-ig az u1,...,uk vektorok páronként ortogonálisak.

Nemfüggetlen 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 nemfüggetlen vektorok által kifeszített alteret is lehet azonban ortogonális vekrotokkal előállItani, é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.

Példák[szerkesztés | forrásszöveg szerkesztése]

1. Vegyük az

A=\begin{bmatrix}1 & 2 & 1\end{bmatrix}\,

mátrix magterét, mint R3 alterét és adjunk meg benne ortogonális bázist!

A feladatot a

\mathbf{a}\mathbf{b}=\sum\limits_{i=1}^3\mathbf{a}_i\mathbf{b}_i

sztenderd skalárszorzat szerint végezük el. A dimenziótétel szerint a magtér kétdimenziós, ugyanis dim(R3) = dim Ker A + dim Im A, de A oszlopai skalárok, így dim Im A = 1. A magtér alkalmas bázisa (2,-1,0), (1,0,-1), mert ekkor

\begin{bmatrix}1 & 2 & 1\end{bmatrix}\cdot\begin{bmatrix} 2 & 1 \\ -1 & 0 \\ 0 & -1\end{bmatrix}=\begin{bmatrix}0 & 0\end{bmatrix}

Feladatunk most már a bázisvektorok oszlopmátrixának ortogonalizálása.

\mathbf{u}_1=\begin{bmatrix} 2 \\ -1 \\ 0 \end{bmatrix}
\mathrm{proj}_{\mathbf{u}_1}\begin{bmatrix} 1 \\ 0 \\ -1\end{bmatrix}=\frac{\mathbf{u}_1}{\|\mathbf{u}_1\|^2}.\mathbf{u}_1\cdot\begin{bmatrix} 1 \\ 0 \\ -1\end{bmatrix}=\frac{2}{5}\begin{bmatrix} 2 \\ -1 \\ 0 \end{bmatrix}=\begin{bmatrix} \frac{4}{5} \\ -\frac{2}{5} \\ 0 \end{bmatrix}
\mathbf{u}_2=\begin{bmatrix} 1 \\ 0 \\ -1\end{bmatrix}-\mathrm{proj}_{\mathbf{u}_1}\begin{bmatrix} 1 \\ 0 \\ -1\end{bmatrix}=\begin{bmatrix} \frac{1}{5} \\ \frac{2}{5} \\ -1 \end{bmatrix}

Ellenőrizzük vektoriális szorzattal! Mivel

\mathrm{Ker}\,A=\{(x,y,z)\in\mathbf{R}^3\mid x+2y+z=0\}\,

ezért nincs más feldatunk, mint a

 x+2y+z=0\,

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

\mathbf{u}_1=\begin{bmatrix} 2 \\ -1 \\ 0 \end{bmatrix}

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

\mathbf{u}_1=\begin{vmatrix}\mathbf{i} & \mathbf{j} & \mathbf{k}\\
1 & 2 & 1\\
2 & -1 & 0\end{vmatrix}=1\mathbf{i} + 2\mathbf{j}-5 \mathbf{k}

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


Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. A módszer leírása például itt: Szörényi, Szemléletes lineáris algebra - összefoglaló I. informatikusoknak p. 8.
  2. Earliest known uses of some of the words of mathematics: G. A bejegyzésben hivatkoznak Gram és Schmidt eredeti cikkére és a Laplace könyvre.
  3. Orthogonalization process in Encyclopaedia of Mathematics
  4. Szörényi, Szemléletes lineáris algebra - összefoglaló I. informatikusoknak p. 30.
  5. Lásd például: Freud Róbert, Lineáris algebra, ELTE Eötvös Kiadó, 1998. p. 202.

Felhasznált irodalom[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]