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]

Egydimenziós altérre vetítés[szerkesztés]

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

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

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

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

Az eljárás[szerkesztés]

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.

Helyesség[szerkesztés]

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:

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

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

hiszen az algoritmusból kiolvasva éppen

Megjegyzések[szerkesztés]

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

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:

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 alkalmazható 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]

1. Vegyük az

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

A feladatot a

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

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

Ellenőrizzük vektoriális szorzattal! Mivel

ezért nincs más feldatunk, mint a

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

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

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]

  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ások[szerkesztés]