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.A módszer leírása például itt: Szörényi: Szemléletes lineáris algebra - összefoglaló I. informatikusoknak 8. o.
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.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. A Gram–Schmidt-ortogonalizálás egy általánosításának tekinthető a Lie-csoportok elméletében szereplő Iwasawa-dekompozíció.Orthogonalization process in Encyclopaedia of Mathematics
Az eljárás alkalmazható például a reguláris mátrixok QR-felbontásánál.Szörényi: Szemléletes lineáris algebra - összefoglaló I. informatikusoknak 30. o.
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
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 bélyegkép|jobbra|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 Annak az igazolása, hogy az eljárás valóban a kívánt eredményt adja a következő.Lásd például: Freud Róbert: Lineáris algebra (ELTE Eötvös Kiadó, 1998) 202. o.
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 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 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. 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 sorozatként, ahol kardinális szám, és ordinális szám. Ha a rendszer lineáris burka sűrű, akkor a Hilbert-tér dimenziója. Jelölje a teret, és legyen egy ortogonális projekció az altérre, ami a teljesség miatt mindig létezik, és legyen az normált vektor. Így adódik egy ortonormált rendszer, ahol
.
Transzfinit indukcióval megmutatható, hogy , továbbá . Explicit transzfinit rekurzióval:
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 vektorok ugyanazt az alteret feszítik ki, mint az eredeti vektorok. A 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 vektorokból, mint oszlopokból megalkotjuk a Q mátrixot, és az eredeti 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
mátrix magterétAz 1×3-as A mátrix Ker A magtere a következőképpen van definiálva: Ker A := { v ∈ R3 | 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 := { w ∈ R | ∃ v ∈ R3: Av = w }. 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álvektorAz A mátrix most egyetlen sorvektor, ami merőleges az A magterének vektoraira, vagyis 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).
Ortonormalizáció Az algoritmus egy változata nemcsak ortogonalizál, hanem normalizál is, így a független vektorokból ortonormált rendszert kapunk, ami ugyanazt az alteret generálja, mint a kiindulási vektorok.
A vektorok ortonormált rendszert alkotnak, hogyha az ortogonalizáció után normáljuk is őket: (az első vektor normalizációja) (a második vektor ortogonalizációja) (a második vektorból kapott vektor normalizációja) (a harmadik vektor ortogonalizációja) (a harmadik vektorból kapott vektor normalizációja)
(az -edik vektor ortogonalizációja) (a -edik vektorból kapott vektor normalizációja)
Másként, a és a vektorok, ahol , rekurzívan is definiálhatók: és
Általában nem kapunk kitüntetett rendszert. A jobb- vagy balsodrású rendszerhez először rendezni kell a vektorokat. Példa -ben a skalárszorzattal adva van a következő bázis:
Ezekből kiszámítunk egy és vektort, melyek egy ortonormált bázisát alkotják.
Jegyzetek
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 (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 K. Kirchgessner, M. Schreck: Vektoranalysis für Dummies. Das Pocketbuch Paperback . Wiley-VCH, 2012. Fordítás
Kategória:Lineáris algebra