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 {vj} vektorrendszerét alakítja át egy olyan {uj} 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.[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ásSzerkesztés

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

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

 

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

 

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ásSzerkeszté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 = v2w2. 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égSzerkeszté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ésekSzerkeszté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 helyességi gondolatmenetben pont azt látjuk be, hogy a vkm0 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 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.

PéldaSzerkesztés

Vegyük az

 

mátrix magterét[6] mint R3 alterét és adjunk meg benne egy ortogonális bázist!

A feladatot az

 

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

Megoldás:

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 kétdimenziós magtérnek kételemű a bázisa. A magtér egy alkalmas bázisa lehet az {v1 = (2, -1, 0), v2 = (1, 0, -1)}, mert a két vektor nyilvánvalóan lineárisan független, és mindkettő magtérbeli, mivel

 .

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

 ,
 ,
 .

Ellenőrizzük vektoriális szorzattal! Mivel

 ,

ezért nincs más feladatunk, 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[7] é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).

JegyzetekSzerkesztés

  1. A módszer leírása például itt: Szörényi: Szemléletes lineáris algebra - összefoglaló I. informatikusoknak PDF 8. o.
  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 PDF 30. o.
  5. Lásd például: Freud Róbert: Lineáris algebra (ELTE Eötvös Kiadó, 1998) 202. o.
  6. Az 1×3-as A mátrix Ker A magtere a következőképpen van definiálva: Ker A := { vR3 | Av = 0 }. Belátható, hogy Ker A lineáris altér R3-ban.
    Az A mátrix Im A képtere a következőképpen van definiálva: Im A := { wR | ∃ vR3: Av = w }.
  7. Az A mátrix most egyetlen sorvektor, ami merőleges az A magterének vektoraira, vagyis normálvektor.

ForrásokSzerkesztés