Gram–Schmidt-eljárás

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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

Az 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, 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á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 = 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é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 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élda[szerkeszté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).

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