Ugrás a tartalomhoz

Numerikus módszerek 1.

Stoyan Gisbert (1942–), Takó Galina (195?–) (2005)

Typotex

1.3. Gauss-elimináció és LU-felbontás

1.3. Gauss-elimináció és LU-felbontás

1.3.1. A Gauss-elimináció

Írjuk le most részletesen az rendszert:

(1.24)

A kiküszöbölési módszer a következőképpen jár el: Legyen . Kivonjuk az első egyenlet -szeresét az -edik egyenletből, . Az mátrix elemeit -vel jelölve, a kivonás által -re létrehozott új elemeket pedig -vel, a következő képletekkel írhatjuk le ezt a műveletet:

(1.25)

Legyen továbbá

akkor az első lépés után az egyenletrendszer a következő lesz:

(1.26)

Ha , akkor hasonlóan járhatunk el az itt az első sor alatt álló -es egyenletrendszerrel, és így folytatva, végeredményben a következő rendszerhez jutunk (amennyiben nincs fennakadás miatt, ):

(1.27)

A tulajdonképpeni kiküszöbölést avagy eliminációt ezzel lezártuk.

Ha most az utolsó egyenletben még is érvényes, akkor fordított sorrendben könnyen megkapjuk a megoldást, egymásután kiszámítva ; ez a visszahelyettesítés.

Tisztázzuk először, hogy mit is jelentenek az feltételek, amelyek nélkül megakad a leírt folyamat, a Gauss-elimináció. Képleteink szerint pl.

A jobb oldalon az elsőrendű és másodrendű bal felső főminor hányadosa szerepel,

hányadosa. Ennek magyarázata a következő: nem változtatja a determinánsokat az (1.24) rendszer sorainak kombinációja (a (1.26) rendszer második sora így jött létre), ezért

Feltéve, hogy , az innen kifejezhető. Továbbá, ha a másodrendű főminor nem zérus, akkor nyilván sem – tehát ilyenkor folytathatjuk az eliminációt. Hasonlóan a -edik lépés után hivatkozunk arra, hogy változatlan a -adrendű bal felső főminor,

Hogy idáig jutottunk, ahhoz már az a feltétel kellett, hogy az összes -edrendű főminor ne legyen zérus. Ha most még a -adrendű bal felső főminor sem zérus, akkor és folytathatjuk az eliminációt. Így a Gauss-elimináció kiküszöbölési részéhez elegendő az, hogy . Foglaljuk össze eredményeinket!

1.3. Tétel.

A Gauss-elimináció pontosan akkor végezhető el, ha az összes bal felső főminor nemzérus:

Ebből az első feltétel biztosítja a Gauss-elimináció kiküszöbölési részének végrehajthatóságát, az utolsó pedig a visszahelyettesítés beindítását.

A tétel szerint a Gauss-elimináció – eddig tárgyalt formájában – gyakran elvégezhetetlen, amikor az (1.24) rendszernek van egyértelmű megoldása, hiszen ahhoz csak az -edik feltétel kell.

A tételben megfogalmazott szükséges és elégséges feltétel a gyakorlatban nehezen ellenőrizhető, leginkább – a kerekítési hibáktól eltekintve – úgy, hogy a számítás közben mindig teszteljük, vajon különbözik-e nullától. Ezért érdekes tudni, hogy vannak olyan mátrixosztályok, amelyekre a Gauss-elimináció mindig elvégezhető.

Mielőtt ennek vizsgálatára áttérnénk, írjuk át a Gauss-elimináció első lépését mátrixalakba, majd ebből további következtetéseket vonunk le.

1.3.2. A Schur-féle komplementer

Az (1.24)-ből (1.26)-ba való átmenet a következőképpen írható le:

Itt az (1.26) rendszerben még feldolgozásra váró (a második egyenlettől az -edik egyenletig tartó) részének a mátrixa; és -dimenziós sorvektorok, pedig -dimenziós oszlopvektor:

Ha -gyel jelöljük az eredeti mátrix azon elemeit, amelyek az helyén állnak, akkor (1.28)-ból következik az

összefüggés.

Folytatva a Gauss-eliminációt, a -adik lépésben újabb -es mátrixot, valamint az -méretű mátrixot és és vektorokat állítunk elő; a teljes analógia miatt viszont elegendő az elimináció első lépésével foglalkoznunk.

Közvetlenül ellenőrizhetjük, hogy reguláris, inverze alig különbözik -től:

(1.29)

Tehát

(1.30)

Az mátrix ezen felbontása 3 mátrix szorzatára tükrözi a Gauss-elimináció első lépését.

Annak érdekében, hogy általánosabb betekintést nyerjünk, vizsgáljuk most azt a lehetőséget, hogy az első lépésben mindjárt az első két ismeretlent elimináljuk (ez egyébként fontos szimmetrikus indefinit mátrixoknál). Ehhez kiindulunk az

blokkalakból (ahol és az mátrix, ill. a vektor megfelelő blokkrészei, mérete ). Általánosítva a fenti eljárást, az (1.24) egyenletet balról megszorozzuk az

alsó háromszög blokkmátrixszal. Tegyük fel, hogy reguláris. Akkor a szorzás eredménye

(1.31)

ha , és ekkor

Fontos észrevenni, hogy akkor is létezhet, ha , tehát, amikor az ezelőtt vázolt eljárást nem használhatjuk.

Az (1.31)-ben szereplő, az mátrixszal kapcsolatos egyenletrendszerrel tovább kell foglalkoznunk; ha erre megtaláljuk az megoldást, akkor

adja a hiányzó ismeretleneket. Az (1.31) egyenletrendszer mátrixát tovább felbonthatjuk, hasonlóan mint (1.28) alatt:

(1.32)

ahol – megint felhasználva regularitását.

Mivel közvetlenül ellenőrizhető, hogy

(1.32)-ből kapjuk az mátrixnak az alábbi felbontását:

Ennek és az (1.30) felbontásnak az általánosítása a következő:

(1.33)

ahol

Tisztázzuk, hogy mikor létezik ez a blokkfelbontás. Kiszámítjuk az elképzelt felbontás jobb oldalát:

Innen leolvashatjuk, hogy

Tegyük most fel, hogy reguláris. Akkor , , és egyértelműen meg vannak határozva:

(1.34)

A mátrix az az almátrix, amely esetleg még további feldolgozásra vár; így a Gauss-elimináció első lépése után , illetve a blokklépés ( és egyidejű eliminációja) után .

Definíció.

A mátrix az (1.33) blokkmátrix blokkjának Schur-féle komplementere.

A szokásos jelölés: .

1.4. Lemma (Schur-féle komplementer létezése, jellemzése).

Legyen az (1.33) blokkmátrix és reguláris. Akkor a Schur-féle komplementer létezik és rendelkezik az alábbi tulajdonságokkal. a)

b) A Schur-féle komplementer megtartja az mátrix következő tulajdonságait: regularitás, szimmetria, pozitív definitség.

Bizonyítás.

A létezést már (1.34)-ben beláttuk. Közvetlenül az (1.33) felbontásból következik

(1.35)

azaz a). Most legyen reguláris, akkor is az (mivel ). Ezután legyen szimmetrikus. Ekkor

Ha pozitív definit – azaz ha – akkor is az. Legyen ugyanis , az mátrix blokkalakjának megfelelően. Válasszuk -t úgy, hogy

viszont legyen tetszőleges nemzérus vektor. Ekkor

Itt -szel együtt a jobb oldal pozitív, mivel .

Megjegyzés.

Figyelmeztetünk arra, hogy itt is – mint a fogalom bevezetésénél – a pozitív definitséget attól függetlenül kezeljük, hogy a mátrix hermitikus vagy szimmetrikus. Amennyiben a valós elemű mátrixról ismeretes, hogy minden valós nemzérus vektorra igaz , akkor azt mondjuk, hogy a mátrix valósan pozitív definit. Ez a tulajdonság szimmetrikus mátrixra ekvivalens a pozitív definitséggel (amely az (1.11) skalárszorzatra vonatkozik). Általában viszont miatt igaz valós vektorra, és így valósan pozitív definitsége ekvivalens az szimmetrikus részének – az mátrixnak – a pozitív definitségével. Viszont a fenti 1.4. lemmában a pozitív definitség helyett azt is követelhetjük, hogy csupán valósan pozitív definit.

Következmény.

Ha (valósan) pozitív definit, akkor és minden főminor is pozitív.

Bizonyítás.

A második állítás következik az elsőből, mivel -val együtt minden -ra (1.33)-ban az is (valósan) pozitív definit: elegendő az blokkvektorban -nak és -nak választani, akkor . Ennek speciális esete az, hogy az -edik koordináta egységvektor. Ekkor , tehát a főátlóbeli elemek pozitívak.

Első állításunk igaz, ha . Legyen igaz az állítás minden -méretű mátrixra, legyen -méretű és . Mivel ez reguláris mátrix, így létezik és -val együtt (valósan) pozitív definit. Indukció szerint , ezért (1.35) alapján .

1.3.3. A Gauss-elimináció és az LU-felbontás viszonya

Most térjünk vissza a Gauss-elimináció első lépéséhez, az (1.30) képlethez.

1.5. Tétel.

a) Legyen , akkor a Gauss-elimináció első lépése végrehajtható, és -val együtt is reguláris, ill. szimmetrikus;

b) ha (valósan) pozitív definit, akkor a Gauss-elimináció minden lépése végrehajtható és a közbülső mátrixok, így pl.  , mind (valósan) pozitív definitek.

Bizonyítás.

Az a) rész következik (1.30), (1.33) és (1.34) összevetése után az 1.4. lemmából, hiszen ; a b) részben biztosított a lemmához tartozó következtetés szerint, a lemma miatt is (valósan) pozitív definit, így az pozitív, tehát folytatható a Gauss-elimináció stb.

Megjegyzés.

A tétel akkor is igaz, ha a vizsgált eliminációs lépés egy blokk-eliminációs lépés; ekkor az feltétel helyett a feltétel szerepel.

Most tegyük fel, hogy az 1.3. tétel feltételei teljesülnek. A Gauss-elimináció (1.27) végeredménye, ha csak változását nézzük, az

(1.36)

úgynevezett felső háromszög mátrix. Ezt -ból úgy kapjuk meg, hogy folytatva az (1.28) átmenetet, -et balról az alsó háromszög mátrixokkal szorozzuk meg,

(1.37)

A második lépés például az eliminációját szolgálja, és ez leírható az

mátrix segítségével stb., általában tehát

ahol

(1.38)

Az mátrixok inverzei az (1.29)-hez analóg módon mindig úgy képződnek, hogy csupán a főátlón kívüli elemek előjele változik meg. Azt is kiszámíthatjuk közvetlenül, hogy

(1.39)

Az mátrixot alakja szerint alsó háromszög mátrixnak hívjuk; a mátrix normált: . Most (1.37)-ből és (1.39)-ből kapjuk

(1.40)

ez az mátrix LU-felbontása. Tehát ha a Gauss-elimináció kiküszöbölési része során megőrizzük az szorzókat, akkor a végén rendelkezünk mind az , mind az mátrixszal, azaz a mátrix LU-felbontásával. Ilyen értelemben az LU-felbontással ekvivalens a Gauss-elimináció kiküszöbölési része. Ezért az LU-felbontás létezéséhez az 1.3. tétel első feltétele elegendő.

Ha reguláris, tehát a tétel utolsó feltétele teljesül, akkor lényegében csak egy LU-felbontás van (pl. akkor, ha -t normáltnak tételezzük fel), ld. a 15. feladatot.

Amennyiben az 1.3. tétel feltételei nem teljesülnek, akkor lehet, hogy nincs LU-felbontás, vagy a felbontás létezik, de az nem egyértelmű (még a normalizációtól is eltekintve). Erre egy jellemző példa a következő mátrix:

A Gauss-elimináció első lépése után kapjuk

és ez esetén már az mátrix, de máskor nem tudunk továbblépni, és ekkor nincs LU-felbontás. Viszont az esetben, közvetlenül tanulmányozva az felbontással kapcsolatos egyenleteket (feltéve azonnal, hogy normált), észrevesszük, hogy

ahol tetszőleges szám. Ekkor tehát az LU-felbontás létezik, de az nem egyértelmű.

Térjünk most vissza (1.40)-hez akkor, amikor ott és regulárisak! Az LU-felbontás birtokában két háromszög mátrixú egyenletrendszer megoldásán keresztül eljutunk az

egyenletrendszer megoldásához:

(1.41)

Ezekből a Gauss-elimináció az első rendszert már az szorzó elkészítésével párhuzamosan meg is oldja; ha több egyenletrendszert ugyanazzal a mátrixszal és különböző jobboldallal kell megoldanunk, akkor érdemes az szorzót megőriznünk, amit a Gauss-elimináció – szűkebb értelemben – nem tesz.

Mivel az mátrix főátlóbeli elemei külön szerepet játszanak (ezeket főelemeknek is hívjuk) és nullától különböznek, kivihetjük -ból: , ahol

helyett -t írva, eljutunk az mátrix LDU-felbontásához,

amelynek blokkváltozatával már (1.33)-ben találkoztunk. Ez a felbontás egyértelműen meghatározott (most ugyanis az szorzó is normált); használata különösen a szimmetrikus mátrixoknál előnyös. Ekkor lesz, ami az első sorra nézve közvetlenül a Gauss-elimináció első lépéséből következik, a többi sorra viszont az 1.4. lemmából. (A szimmetrikus mátrixok esetét részletesen az 1.3.8. pontban tárgyaljuk.)

Mielőtt két további olyan mátrixosztály tárgyalására térünk át, amelyekben az LU-felbontás létezik, megemlítjük, hogy a Schur-féle komplementer a (lépésenkénti) Gauss-eliminációval is kiszámítható (ha ez végrehajtható).

A Gauss-elimináció -adik lépése után

(1.42)

ahol

Figyelembe véve az mátrixok alakját (ld.  (1.39) is)

ahol alsó háromszög mátrix ( és pedig reguláris felső háromszög mátrixok), és így (1.42)-ből következik

Közvetlen számítással nyerjük innen

tehát valóban .

A Schur-féle komplementer (1.33), (1.34) szerinti levezetésével összehasonlítva az a következtetés adódik, hogy akármilyen (végrehajtható) blokk- vagy egyszerű lépésekkel elimináljuk az első ismeretlent és az -t az (1.42) jobb oldalán álló alakra hozzuk, az mátrix ettől függetlenül mindig marad. De vegyük észre, hogy az ehhez szükséges feltételek az mátrixról nagyon különbözőek. Pl. a lépésenkénti Gauss-eliminációhoz feltételnek kell teljesülnie ( , ), míg az (1.33) blokkfelbontáshoz csak egynek ; mindig annyi feltétel lesz, mint ahány lépés van. Tehát előfordulhat, hogy pl. a blokkfelbontás kivitelezhető, a lépésenkénti viszont nem.

1.3.4. Domináns főátlójú mátrixok, M-mátrixok

Most vizsgáljunk egy második mátrixosztályt, amelyben a Gauss-elimináció végrehajtható.

Definíció.

Azt mondjuk, hogy soronként (szigorúan) domináns főátlóval rendelkezik, ha

illetve, ha

akkor oszloponként (szigorúan) domináns a főátlója.

Gazdasági és ökológiai csererendszerek lineáris modellezésénél olyan mátrixok keletkeznek, amelyeknek főátlója oszloponként domináns (ld. a 10.1. pontot).

1.6. Tétel.

Ha az mátrix főátlója domináns, akkor végrehajtható a Gauss-elimináció.

Bizonyítás.

Azt akarjuk megmutatni, hogy a vizsgált tulajdonság megmarad a Gauss-elimináció során. Ebből következik, hogy valóban végrehajtható az elimináció, hiszen ha domináns a főátló, akkor az összes -re, így pl. az elimináció első lépése után igaz lesz , stb. Legyen és a mátrix főátlója soronként domináns. Ekkor

továbbá (az első sor dominanciájából kiindulva)

ahol a „ ” jel azért áll, mert lehetséges. Ezt kombinálva az előbbi szigorú egyenlőtlenséggel:

Innen következik a háromszög egyenlőtlenséggel

Most -val osztva megkapjuk a keresett egyenlőtlenséget.

Egészen hasonló az állítás bizonyítása, amikor oszloponként domináns főátlóval rendelkezik.

Megjegyzések. 1. Az 1.3. tétellel összevetve adódik a következtetés, hogy a domináns főátlójú mátrix minden főminora különbözik nullától; ezen eredmény része az Hadamard-tétel.

2. A domináns főátlójú mátrix elemei komplex számok is lehetnek, vagyis: megismerkedtünk egy olyan komplexelemű mátrixosztállyal, amelyre a Gauss-elimináció végrehajtható. Komplex mátrixok keletkeznek alkalmazásokban pl. azért, mert elektromágneses hullámok leírásában előnyös a komplex számok használata.

3. A domináns főátlójú mátrix inverzének maximum normájára becslést vezethetünk le közvetlenül a dominancia definíciójából (ld. az 1.5. pont mintafeladatát).

Most foglalkozunk egy harmadik olyan mátrixosztállyal, amelyre a Gauss-elimináció ugyancsak elvégezhető lesz; ezen osztályhoz tartozó mátrixok gyakran fordulnak elő az alkalmazásokban, pl. differenciálegyenletek közelítő megoldása során (az (1.5) mátrix ilyen), de a lineáris egyenletrendszerek iteratív megoldásánál is fontosak.

Definíció.

Az mátrixot M-mátrixnak hívjuk akkor, ha eleget tesz a következő feltételeknek:

a) , ;

b) létezik olyan pozitív komponensű vektor , amelyre .

A definícióban használt jelölést az alábbiakban mátrixokra is ki fogjuk terjeszteni: ha valamilyen mátrix nemnegatív elemekből áll, akkor ezt alakban írjuk fel.

Megjegyzés.

Ha M-mátrix és , és , akkor is M-mátrix. Ugyanis előjeleloszlása megfelel. Továbbá , és ha , , akkor ebből következik .

1.7. Lemma.

Legyen M-mátrix. Ekkor reguláris és inverze nemnegatív elemekből áll.

Bizonyítás.

Legyen a definícióban szereplő pozitív komponensű vektor és . Ekkor és reguláris diagonális mátrix, , ahol és . Mivel és elemeinek előjelei megegyeznek elemeiével, főátlója domináns:

és nyilván . Hadamard tétele szerint (és vele együtt is) reguláris.

Legyen . Ez megint nemnegatív, reguláris diagonális mátrix (egyébként ). Ekkor , ahol és reguláris. Mutassuk meg, hogy maximum normája kisebb mint 1! Mivel , így

de -ből következik

tehát

(1.43)

Ezért, használva az

azonosságot, azaz

esetén következik (1.43)-ból , tehát

(1.44)

Most inverze nemnegatív, így és

inverze is nemnegatív.

Megjegyzések. 1. A bizonyításhoz az Hadamard-tétel valójában nem szükséges, hiszen regularitása az 1.2. pontban bebizonyított 1.2. lemmából, valamint (1.43)-ból is következik.

2. Az (1.44)-ben szereplő sor a Neumann-sor. Mint mellékeredményt könyvelhetjük el, hogy a Neumann-sor akkor konvergál, ha van olyan norma, amelyre . (A konvergencia pontos feltételét később, az 1.6.2. pontban tisztázzuk.)

3. Ha valamilyen mátrix reguláris és inverze nemnegatív, akkor megoldása pozitív. Ugyanis ha a vektornak egy komponense nulla lenne, akkor tartalmazna egy nullasort. Ha most -nak olyan előjeleloszlása van, mint az M-mátrixoknak, akkor valóban M-mátrix. Így pl.  -val együtt is M-mátrix.

4. Amennyiben az rendszer jobboldala és egy M-mátrix, akkor következik -ból, hogy ilyenkor garantálhatjuk a megoldás nemnegativitását.

Az M-mátrixoknak további hasznos tulajdonságai vannak. Elsőnek megmutatjuk, hogy az M-mátrixok inverzének maximum normájára egy becslést lehet levezetni.

1.8. Lemma (M-mátrix inverzének becslése).

Legyen M-mátrix, olyan vektor, amelyre teljesül a definíció b) feltétele. Akkor

Bizonyítás.

Tekintsük az egyenletrendszert. Mivel az vektor pozitív, van olyan , amelyre a következő vektoregyenlőtlenség (amely komponensenként értelmezendő) igaz:

itt akár a „+” akár a „ ” jel érvényes, mégpedig akkor, ha

Ekkor viszont a fenti egyenlőtlenséget a nemnegatív mátrixszal megszorozva azt látjuk, hogy

Innen következik

tehát -t figyelembe véve kapjuk az állítást.

Megjegyzés.

Hasonló alsó és felső becslést – és ezzel hibakorlátokat – lehet az egyenletrendszer megoldására kapni, ha a jobboldalhoz ismerünk olyan és vektorokat, hogy . Ekkor ez utóbbi egyenlőtlenséget megszorozva a nemnegatív -gyel, következik , ahol , . Ez az egyszerű megjegyzés akkor értékes, ha és könnyebben kiszámítható, vagy szerencsés választásunkkal éppen elérjük, hogy .

A kétoldalú hibakorlát lehetősége miatt az M-mátrixok a 0.3. pontban említett intervallum-aritmetikában is fontos szerepet játszanak.

Következőnek azt fogjuk belátni, hogy az M-mátrixokra végrehajtható a Gauss-elimináció.

1.9. Tétel (M-mátrixok és a Gauss-elimináció).

Legyen egy M-mátrix. Akkor az alakú egyenletrendszer megoldható a Gauss-elimináció segítségével és az elimináció során az M-mátrix tulajdonság is megmarad:

-val együtt és is M-mátrix, így az összes és mátrix is az, továbbá és is M-mátrixok.

Bizonyítás.

a) Az 1.7. lemmából látjuk, hogy M-mátrix főátlóbeli elemei pozitívak. (Ez egyébként a definícióból is rögtön következik, mert ha valamilyen -re lenne, akkor .) Ezért a Gauss-elimináció első lépése végrehajtható.

b) Közvetlenül az (1.25) képletekből látható, hogy az mátrix főátlón kívüli elemei nempozitívak, azaz a definíció a) feltétele igaz.

c) Hasonlóan (1.25)-ből és (1.28)-ból következik, hogy ; ebből és (1.29)-ből látjuk, hogy M-mátrix: az előjel-elrendeződés megfelel és inverze nemnegatív.

Legyen továbbá az a vektor, amellyel a definíció b) feltétele teljesül az mátrixra nézve, . Ezt az mátrixszal megszorozva,

(1.45)

érvényes, tehát , . Ezért és is M-mátrix.

d) is M-mátrix lesz. Konkrétan, első sora lesz első sora, első sora második sora stb., tehát az előjelek megfelelnek. (1.45)-ből látjuk, hogy a Gauss-elimináció folytatásával végül is .

e) is M-mátrix. Az előjelek (1.39)-ből kivehetők, inverze (mint M-mátrixok inverzeinek szorzata) nemnegatív.

Következmény.

Ha az mátrix főátlója domináns, vagy a mátrix M-mátrix, továbbá, ha a mátrix (1.33) blokkalakjában reguláris, akkor -val együtt -nek is domináns a főátlója, ill. az is M-mátrix.

Befejezve ezt a pontot úgy foglaljuk össze, hogy ha vagy pozitív definit, ill. valósan pozitív definit, vagy főátlója domináns vagy M-mátrix, akkor az LU-felbontása létezik, és ez a Gauss-eliminációval előállítható.

1.3.5. Algoritmusok, műveletigény

Most foglalkozzunk az egyenletrendszerek megoldásának gyakorlati oldalával. Az egyik lehetőséget már bemutattuk, a Gauss-eliminációt. Ennek jellegzetessége az, hogy a -adik lépésben létrehozott és számokhoz a későbbi lépésekben már nem nyúlunk hozzá; a mátrix összes visszamaradó elemét viszont mindig használjuk.

További algoritmikus megoldásokat találhatunk, ha közvetlenül az LU-felbontást hozzuk létre, az

képletből kiindulva. Az LU-felbontás bizonyos többértelműségét figyelembe véve választhatunk akár -et (mint a Gauss-eliminációnál), akár -et minden -re (ld. a 15. feladatot). Válasszuk az első normalizálási lehetőséget. Ekkor esetén

alapján számítjuk ki -t, esetén

-ből az elemeket. Vagy felváltva számítjuk ki az mátrix sorait és az mátrix oszlopait, vagy pedig soronként járunk el.

3. ábra - LU-felbontás

LU-felbontás

Az első lehetőség hasonlít a Gauss-eliminációra abban, hogy ugyanabban a sorrendben kapjuk meg az , ill.  számokat; a mátrix visszamaradó elemeivel még nem foglalkoztunk.

Figyelemreméltó, hogy a második lehetőség esetében nincs szükség az mátrix -nél magasabb sorszámú soraira, amikor az és -edik sorát számítjuk. Ennek akkor van jelentősége, amikor a mátrix a belső tárban nem fér el és külső tárban soronként tároljuk.

Mindegyik esetben érdemes a számítás során fellépő , ill.  szorzókat külön megőrizni; az , ill.  számokat az -k helyén tárolhatjuk.

Hány műveletbe kerül az LU-felbontás, ha egy művelet alatt egy szorzást és egy összeadást értünk?

A fenti képletek ugyanazt adják, mint a Gauss-elimináció, melynek

a műveletigénye (ha már itt is eltekintünk az osztástól és az szorzók kiszámításának költségétől, ami művelet). Lényegében tehát művelet kell.

Az LU-felbontás elvégzése után az mátrix főátlóbeli elemeit összeszorozva megkaphatjuk az determinánsát (ld. az 1.5. tételt), ennek kiszámítása ezen az úton tehát már nem művelettel, hanem körülbelül művelettel kivitelezhető. (Például esetén , .)

Ha nagy, az elemek szorzásánál akár túlcsordulásra, akár alulcsordulásra is fel kell készülnünk. (  Az „Algebra” programban a determináns kiszámítása a „főelem-kiválasztás nélküli” Gauss-eliminációnál található, mint mellékeredmény. Ennek kiszámításakor csak részben igyekeztünk a determinánst olyan esetekben is előállítani, amikor bár értéke meglévő lebegőpontos szám, a közbülső szorzatok viszont hol alul-, hol túlcsordulnak.)

Célunk természetesen mindenekelőtt az egyenletrendszer megoldása (1.41) segítségével. Ebből az megoldása (ha normált) az

képlet alapján történik. Itt az -edik komponens kiszámításához művelet szükséges, ezért összesen műveletet kell végrehajtani (ennyi elem van -ben a főátló alatt).

A visszahelyettesítésnél, az megoldása során ezen túl még szorzással több kell,

ahol az számok rendelkezésünkre állnak; összesen tehát művelet szükséges (ennyi elem van felső háromszögében). A két (1.41) rendszer megoldása ezért műveletet jelent.

Egy újabb egyenletrendszer megoldása (ugyanazzal az mátrixszal, az LU-felbontás birtokában) így éppen műveletbe kerül – ugyanannyiba, mint az mátrixszal való szorzás.

Hogyan állíthatjuk elő az inverz mátrixot és milyen a műveletigénye?

Először számítsuk ki az LU-felbontást, azután sorozatosan oldjuk meg -vel, , ahol a -edik koordináta-egységvektor, a megfelelő (1.41) rendszereket. Ez lényegében műveletet igényelne, de az rendszerek megoldásánál figyelembe vehetjük az vektorok nulla komponensét. Ekkor összesen művelet elegendő, ugyanis

tehát kiszámításához csak

művelet szükséges (ennyi elem van -ben a főátló alatt, a -edik oszloptól jobbra). Az összes kiszámítása így

azaz lényegében műveletet igényel.

Az rendszerek megoldásánál már nincs lényeges egyszerűsítés. Így összesen művelet kell. Ez azt jelenti, hogy az inverz mátrix kiszámítása háromszor költségesebb, mint az LU-felbontásé.

Más szóval általában nem érdemes az inverz mátrixot kiszámítani, mert a műveletnyi többletbefektetés nem térül meg még akkor sem, ha több különböző jobboldalra kell megoldanunk ugyanazt az egyenletrendszert. Bonyolultabb -t tartalmazó kifejezést is olcsóbban kapunk meg az LU-felbontás segítségével.

Például kiszámításához először a szorzatot számítjuk ki ( művelet), aztán az rendszert oldjuk meg, ahol (ez művelet), végül is az lesz a keresett vektor ( művelet). Ehelyett az mátrix kiszámítása lényegében műveletbe kerülne.

Feltéve, hogy az rendszerre ez az eljárás alkalmazható, megadjuk a Gauss-elimináció algoritmusát az normalizáció esetében; az elemeit soronként olvassuk be, az és szorzókat soronként állítjuk elő.

1.

2. , Beolvassuk -edik sorát.

3.

4.

5. Most vihetjük ki -edik sorát külső tárolóba, kivéve -t, amit formában a tömbben helyezünk el.

6. , Az -edik sora kész, kivihetjük.

7.

8. Kezdődik a visszahelyettesítés.

9.

10.

11. stop [eredmény: ]

Ha ezt programozzuk, akkor a 6. lépésben természetesen az feltételt ellenőriznünk kell, mert akár egy inputhiba miatt esetleg mégsem végezhető el a Gauss-elimináció az mátrixra. Felhívjuk a figyelmet arra, hogy az 5., 6. és 9. lépés ciklusa üres is lehet.

További részleteket a Gauss-elimináció számítógépes megvalósításáról (pointeres technika, BLAS-routinok stb.) ld. Galántai és Jeney könyvében.

1.3.6. Az LU-felbontás általános mátrixokra, főelem-kiválasztás

Eddig mindig feltételeztük, hogy , . Ez teljesült is bizonyos mátrixosztályokban, ld.  1.3.2. és 1.3.4. pontok. Viszont az LU-felbontás – megfelelő változtatással – akkor is végrehajtható, amikor egy tetszőleges mátrix.

1.10. Tétel (általános mátrix LU-felbontása).

Legyen . Létezik egy felső háromszög mátrix, egy normált alsó háromszög mátrix és egy permutációs mátrix, úgy hogy .

Bizonyítás.

Használjuk a Gauss-eliminációt! Amikor , az elimináció első lépését változtatás nélkül megtehetjük, és biztosított. Most legyen viszont , . Ekkor már maga olyan formájú, mint :

Tehát ebben az esetben rögtön átalakítására térhetünk át (de első sorával együtt a készülő mátrix főátlójára kerül egy nulla).

Végül legyen , de , . Ekkor cseréljük fel az -edik sort az első sorral a megfelelő permutációs mátrixszal, . Így jutunk az mátrixról a mátrixhoz, majd megszokott módon elimináljuk az pozíciójú elemeket, :

Így folytatva az eliminációt, elérkezünk -hoz, amely felső háromszög mátrix. Számítsuk ki a szorzatot, ha és ha cseréli az -edik és az -edik sort :

Felépítése szerint az alsó háromszög mátrix pontosan megegyezik -val, csak az és pozíciójú elemek felcserélődtek. A permutációs mátrixokat mind jobbra cserélve, az

összefüggést kapjuk, (ahol most -ban nem egy, hanem összesen csere történt a -adik oszlopban), és ekkor az

jelölésekkel .

Megjegyzések. 1. A bizonyítás azt mutatja, hogy először összes sorait is lehet megfelelően cserélni, és utána a Gauss-eliminációt az eredeti formájában végrehajtani (a zérus oszlopokat átugorva) – az eredmény megegyezik a fentivel.

2. Ha tekintjük a egyenlet mindkét oldalán szereplő mátrixok determinánsait, akkor kiderül, hogy pontosan abban az esetben szinguláris, ha főátlóján vannak zérus elemek.

3. Amennyiben reguláris, akkor is az. Így tetszőleges reguláris rendszer a PLU-felbontás útján megoldható – mégpedig lényegében úgy, mint korábban (ld.  (1.41)). A permutációs mátrix megjelenése csak azt eredményezi, hogy helyett az első lépésben oldandó meg.

4. A tétel bizonyításában az LU-felbontást oszloponkénti főelem-kiválasztással használtuk: ha a soros elem zérus, akkor helyette főelemnek ugyanazon -adik oszlop főátló alatti részéből keresünk egy nemzérus elemet, és ha ilyen nemzérus elem nincs, akkor szinguláris. A tétel szerint mindkét esetben az így módosított LU-felbontás folytatható.

Emiatt a gyakorlatban a Gauss-eliminációt oszloponkénti (más néven részleges) főelem-kiválasztással szívesen használják, de nem akármilyen nemzérus elemet keresnek az elimináció folytatásához, hanem abszolút értékben a legnagyobbat a soron lévő -adik oszlopból. Legyen az onnan kiválasztott főelem . Akkor a -adik és az -edik sort cseréljük, és az elimináció folytatódhat.  Az „Algebra” programban így valósítottuk meg a (teljes) főelem-kiválasztást, míg a nagy mátrixokra orientált termelési programokban legtöbbször csak egy-két mutatóvektorral tartják számon az elimináció sorrendjét.

Hogy melyik módszer a gyorsabb, az a géptől és a programozási nyelvtől függ.

Befejezésül ehhez a ponthoz arra utalunk, hogy a 2.4. és 2.5. pontokban a legkisebb négyzetek feladatainak megoldása kapcsán megismerünk egy másik lehetőséget általános mátrix felbontására, a QR-felbontást. Ekkor , ahol ortogonális és egy felső trianguláris mátrix; az egyenletrendszert a -tal való szorzással lehet megoldani: .

Ennek az az előnye, hogy az ortogonális -tal való szorzás nem növeli az -ban vagy -ben tartalmazott hibákat, ld.  (1.16) 1.2-ben. Viszont ennek a felbontásnak a műveletigénye nagyobb, mint a Gauss-eliminációé (az utóbbinak duplája a legjobb esetben). Ezért egyenletrendszerek megoldására általában nem használják.

Más a helyzet, ha szinguláris az egyenletrendszer. Ilyen esetben inkább a QR-felbontást alkalmazzuk (ill. a szinguláris felbontást, ld. a 2.6. pontot). Ha csak az LU-felbontást kiszámító programmal rendelkezünk, akkor a főelemválasztás nélkülözhetetlen, és ajánlatos ezt az alábbiak szerint kiegészíteni. Amennyiben annak a (maradék-) oszlopnak, amelyből éppen főelemet akarunk kiválasztani, minden eleme abszolút értékben kisebb egy bizonyos küszöbértéknél, akkor az egész oszlopot hátracseréljük. Így a következő blokkalakra hozhatjuk a szinguláris rendszert:

Itt és négyzetesek, reguláris felső háromszög mátrix, -nek minden eleme kisebb a küszöbértéknél. Ha komponensei is kicsik, akkor megoldhatónak tekinthetjük a rendszert, komponenseinek tetszőleges értéket (pl. nullát) adhatunk, és az

egyenletből számítjuk ki az -et.

A küszöbérték megadása viszont problémás; az LU-felbontás -edik lépése során a

érték javasolható (ahol a számítógép relatív pontossága, ld.  0.2. pontot). Az komponenseire a küszöbérték

ajánlható. Ily módon gyakran használható eredményre juthatunk, de arra nincs garancia, hogy a javasolt módon egyáltalán meg tudjuk különböztetni a szinguláris rendszert a reguláristól (amelyre a következő valamint a 2.6. pont tárgyalása némely fényt derít).

1.3.7. Az LU-felbontás stabilitása, hibaanalízise

1.11. Lemma (főelem-kiválasztásos LU-felbontás stabilitása).

Ha az LU-felbontást részleges főelem-kiválasztással alkalmazzuk, akkor érvényesek a következő becslések a felbontás közbülső mátrixaira, ill. azok elemeire:

Bizonyítás.

A részleges főelem-kiválasztás azt eredményezi (ld.  (1.38)-at is), hogy , ezért (1.37)-ből következik

Az elemekkel együtt nőnek azok a hibák, amelyek a felbontás -adik lépésében keletkeznek a kerekítés miatt, ill. az elemek hozott hibái is. Legyen ezen hiba maximuma , akkor ez egy lépésben legfeljebb megduplázódik, úgyhogy végül is elemeit abszolút hibával kapjuk meg. Ez bár erőteljes növekedés, de mindenesetre megint Lipschitz-folytonos viselkedés.

Ugyanez a növekedés érvényes a Gauss-elimináció során változó jobboldalra alapján. A , mint a hibanövekedés felső határa, valóban elérhető, pl. a következő egyenlet eliminációja során (ehhez ld. a 16. feladatot is):

(1.46)

Amennyiben a felbontás -adik lépése előtt nem a -adik oszlop legnagyobb elemét határozzuk meg, hanem a még feldolgozandó teljes mátrix legnagyobb elemét, akkor ezt teljes főelem-kiválasztásnak hívjuk. (  Az „Algebra” program ezt tartalmazza.) Ilyenkor az elemek és a hibák nem a -szeresére nőnek, hanem lényegesen lassabban (de gyorsabban mint ), pl.  esetén kb. a 3552-szeresére (ekkor ).

A gyakorlatban nem használják a teljes főelem-kiválasztást. Ennek oka az, hogy ilyenkor a munkaigény megduplázódik (az szükséges összehasonlítás miatt), viszont ha csak az oszloponkénti főelem-kiválasztást használjuk, akkor a többletmunka elhanyagolható és a gyakorlatban a mátrix elemeinek ténylegesen tapasztalható hibanövekedése ritkán erőteljesebb, mint a teljes főelem-kiválasztásnál. Leggyakrabban ezek a hibák legfeljebb négyszeresére-nyolcszorosára nőnek, és különösen a rosszul kondicionált feladatoknál még ennél is kisebb a hibanövekedés.

Egyébként az is tapasztalati tény, hogy a (részleges) főelemválasztással alkalmazott Gauss-elimináció nem feltétlenül pontosabb megoldást ad, mint a sima (főelemválasztás nélküli) Gauss-elimináció.

Most legyen a Gauss-eliminációval kiszámított numerikus megoldás, legyen a pontos megoldás; az adatok hibájától eltekintünk. (Azok hatását már 1.2-ben vizsgáltuk. Megemlítjük, hogy pl. a Hilbert-mátrix esetében a rossz kondicionáltság által felerősített inputhibához képest elhanyagolható a Gauss-elimináció által elkövetett hiba.) Így a numerikus megoldást most csak az elimináció során elkövetett és később tovább felerősített hibák terhelik. Bár a Gauss-elimináció jellemző sajátsága, hogy – a mátrix elemeihez és a jobboldalhoz képest – kicsi értékre vezet, ez nem jelenti feltétlenül azt, hogy az vektor közel lesz -hez, mivel a kondíciószám nagy lehet. Ugyanis, ha

akkor (1.20)-ból következik

(1.47)

Itt az -et az maradékvektorának hívjuk. Felhívjuk a figyelmet arra, hogy a (1.47) egyenlőtlenség csak felső határt szab (relatív) hibájának. Annak igazolására nem nyújt lehetőséget, hogy amennyiben és két közelítő megoldásunk és és a hozzátartozó maradékvektorok, akkor az relációkból következne . Már a -es mátrixok között is találhatunk olyat, amelyre éppen van közelebb az megoldáshoz.

Az (1.47) becslés sajátossága az, hogy az numerikus megoldás birtokában hibabecsléshez juttat. Ezért a-posteriori becslésnek hívjuk. Ennek ellenkezője az a-priori becslés, azaz olyan egyenlőtlenség, amely a megoldás kiszámítása előtt megengedi a lehetséges hiba becslését. Az (1.20) és (1.23) becsléseket ilyeneknek tekinthetjük, a gond csak az kiszámítása. Általános mátrix esetén az Auchmuty-féle a-posteriori hibabecsléssel ez a probléma gyakran elkerülhető (ld. a 19.c feladatot). Ezenkívül – az LU-felbontás birtokában – becslése a egyenlőtlenség alapján az inverz iteráció ( 3.4.2. pont) segítségével nem túl nagy műveletigényt jelent (a túl nagy lenne). Speciális mátrixok esetén ld. pl. a 3. megjegyzést az 1.6. tételhez, valamint az 1.8. lemmát, a mintafeladatot és a 10., 16. feladatot is.

A keresett megoldásra a feladat adatainak input, ill. hozott hibáin kívül még kihatással vannak az algoritmus során fellépő hibák. A legrosszabb esetben a háromszög egyenlőtlenség szerint ezeket a hibákat össze kell adnunk.

Egy összetett direkt hibabecslés így gyakran rendkívül pesszimisztikus; lényegében azt sugallja, hogy nem is érdemes a Gauss-eliminációval foglalkozni. (Ld. a 17. feladatot, amely azt is világossá teszi, hogy eléggé körültekintően kell eljárnunk ahhoz, hogy kiderítsük, honnan ered a megoldás megfigyelt hibája; a nagy kondíciószám mindenesetre veszélyre figyelmeztet.)

Galántai A. cikkében ld. a legpontosabb eredményeket arra nézve, hogy az mátrix perturbációja ismeretében, feltételezve az és mátrixok LU-felbonthatóságát, hogyan becsülhetők az felbontás és perturbációi?

Ehelyett most használjuk a már a 0.3. pontban említett fordított hibaanalízist arra, hogy a részleges főelem-kiválasztásos LU-felbontás során fellépő hibákat megvizsgáljuk. Ehhez kiindulunk a 0.3. pont (0.4) relációjából,

(1.48)

amelyben valamelyik aritmetikai alapművelet és a gép relatív pontossága. Ezt alkalmazva az

(1.49)

képletre látjuk, hogy az elimináció végrehajtásánál fellépő kerekítési hibákat hozzászámíthatjuk az elemeinek hibáihoz, és felhalmozódva végül az eredeti mátrix elemeihez. Az így kapott perturbált rendszert pontosan (kerekítési hiba nélkül) oldottuk meg. Most nem az a kérdés, hogy mekkora a végső számítási hiba, hanem vajon a perturbált rendszer elfogadhatóan közel van-e ahhoz a feladathoz, amit tulajdonképpen meg akarunk oldani (és amely mérési hibák stb. miatt amúgy is hibás).

Tekintsük 1.49-ben a esetet; a képletben a pontos helyett a kerekítési hibák hatására kerül felhasználásra, de a főelem-kiválasztás és a lebegőpontos aritmetika monotonitást megtartó tulajdonsága miatt biztos, hogy , valamint az is, hogy az és számok lebegőpontos szorzásának eredménye alakban leírható, ahol . Most (1.48) alapján helyett az értéket kapjuk:

ahol a kivonás relatív hibája és

Itt miatt érvényes

(1.50)

Ugyanígy becsülhetjük az első oszlop elemeinek azon hibáját, amely megfelel az pontatlan kiszámításának és az mátrixba beírt nulla különbségének,

Mátrix alakban leírva az egzakt helyett keletkezik, ahol

Mivel az szorzók pontos alakja a hibákra nézve nem érdekes, hanem csak az becslés a fontos, az mátrixot tekinthetjük mint a Gauss-elimináció első lépésének pontos eredményét az mátrixból kiindulva.

Hasonlóan

helyett valóban

(1.51)

keletkezik, ahol

Legyen

ekkor mátrixformában leírva az (1.51) összefüggést, megkapjuk, hogy

ahol felhasználtuk azt, hogy . Ez alakjából következik, ld.  (1.28) 1.3.2-ben. miatt teljesül

(1.52)

Az eliminációt folytatva, az -edik lépés után adódik

tehát a Gauss-elimináció pontos eredménye, -ra alkalmazva. Itt

mivel , amikor , ill.  Az (1.50), (1.52) stb. képletekből megkapjuk, a továbbiakban az -ben másodrendű tagokat elhanyagolva, hogy

(1.53)

(1.49)-ből következik miatt (v.ö. az 1.11. lemmával)

de említettük, hogy ez a felső korlát nem tipikus a szokásos feladatoknál. Ezért a következőképpen fogalmazzuk meg az (1.53) eredményt:

1.12. Tétel (LU-felbontás és a kerekítési hibák).

Legyen

Az LU-felbontás alatt fellépő kerekítési hibák első közelítésben ekvivalensek azzal, hogy az mátrixnak hibája van és a számítás pontos; ekkor teljesül

Bizonyítás.

Ekkor , így

Megjegyzések. 1. Az inverz hibaanalízis szellemében az így kapott hibakorlátot össze kell vetni a mátrix hozott hibájával; ha ez nem nagyobb utóbbinál, akkor elfogadhatónak tekintjük a megoldást.

2. Az mátrix fent említett hibája az egyenletrendszer pontos megoldásában (ld. a 9. feladatot)

relatív hibát okoz a maximum normában.

3.  Az „Algebra” programban rendelkezésre áll a tétel száma: ehhez a Gauss-eliminációt teljes főelem-kiválasztással kell alkalmazni és a maximális főelemet feljegyezni.

4. A fentiekhez hasonlóan becsülhető az (1.41) háromszögű egyenletrendszerek megoldásának ekvivalens hibája. Ha , akkor a végső eredmény

[Itt a harmadik hatvány úgy jön létre, hogy az (1.41) rendszerek számítógépes megoldása ekvivalens az , rendszerek pontos megoldásával, ahol ( 18. feladat)

de és , .

Ez utóbbi becslések közvetlenül a részleges főelem-kiválasztással és az szám definíciójával kapcsolatosak.]

5. Kísérleti eredmények szerint a kerekítési hibák kihatása az LU-felbontásra nagyjából olyan perturbációnak felel meg, amelyre . (Ld. a 19. feladatot is.)

Akár ezt a tapasztalatot, akár a 4. megjegyzés szerinti pesszimisztikusabb becslést vesszük, a következtetés egyértelmű: minél nagyobb a feladat, a biztonságos megoldáshoz annál nagyobb kell, hogy legyen a számábrázolás hossza (ill. az ugyancsak nagyobb ráfordításokat jelentő, a 0.3. pontban említett intervallum-aritmetikai algoritmusokat kell alkalmazni).

Az (1.47) és a 19.b feladat hibabecsléseiben szerepet játszó maradékvektor segítségével javíthatunk egy már kiszámított numerikus megoldást. Ha a közelítő megoldás és , akkor az

egyenletrendszert pontosan megoldva megkapjuk az egzakt megoldást , ugyanis

Ez az észrevétel gyakorlatilag csak akkor hasznos, hogy ha a maradékvektort nagyobb pontossággal (hosszabb számábrázolás mellett) számítjuk ki, mint az LU-felbontást és az megoldást; de az egyenletrendszer ismételt megoldásához alkalmazhatjuk a rendelkezésre álló (bizonyos alappontossággal kapott) LU-felbontást. Ezután javított megoldás lesz. Ezt a folyamatot ismételve jön létre az utóiteráció (amely nem mindig és nem monoton módon javítja a megoldást).

Az kiszámításához egyébként azért szükséges a nagyobb pontosság, hogy új információt és ne csak számítási hibát hozzunk létre. Ugyanis ha a megoldás elég jó közelítése, akkor kiszámítása során az értékes számjegyek végzetes eltűnésével kell számolnunk; ez megnehezíti az (1.47) becslés gyakorlati hasznosítását is.

1.3.8. Direkt módszerek szimmetrikus mátrixokra

Először foglalkozzunk azzal a speciális esettel, amikor az mátrix szimmetrikus és pozitív definit. Ilyen mátrixok nem is ritkák az alkalmazásokban; például mechanikai feladatok vagy a legjobb approximáció meghatározása (ld. a 2.2. pontot) vezetnek szimmetrikus és pozitív definit mátrixokhoz.

1.13. Lemma (szimmetrikus és pozitív definit mátrix LDU-felbontása).

Legyen pozitív definit. Ekkor létezik az mátrixnak olyan LDU-felbontása, amelyre érvényes az egyenlőség, az alsó háromszög mátrix főátlója normált , és a diagonális mátrix főátlóbeli elemei pozitívak.

Bizonyítás.

Az 1.5. tétel szerint az LU-felbontás létezik, az 1.4. lemmához tartozó következtetés alapján az elemek (mint az -adrendű és -edrendű főminorainak hányadosai) pozitívak. Legyen , , ekkor még azt kell belátnunk, hogy . Az első sorában állnak az eredeti mátrix elemei, azaz első sorában állnak az elemek, vagyis az szorzók (1.25). Így első sora az mátrix első oszlopának transzponáltja. Ezekután az állítás abból következik, hogy a még feldolgozandó mátrix ugyancsak szimmetrikus és pozitív definit (1.4. lemma, 1.5. tétel).

Megjegyzés.

szimmetrikus mátrix LDL -felbontása akkor is létezhet, amikor nem pozitív definit. Erre még visszatérünk.

Ha a lemma feltételei teljesülnek, akkor a mátrix négyzetgyöke képezhető,

ezért az jelöléssel következik .

Ez az mátrix Cholesky-felbontása; a levezetés szerint az alsó háromszög mátrix főátlóján a számok állnak.

1.14. Tétel (Cholesky-felbontás létezése).

Az mátrix pontosan akkor bontható fel formában reguláris alsó háromszög mátrixszal, amikor szimmetrikus, pozitív definit mátrix.

Bizonyítás.

Az állítást az egyik irányban már beláttuk; ha viszont , akkor szimmetrikus és . Ez a kifejezés pozitív az regularitása miatt, ha .

Megjegyzés.

Az mátrix egyértelműen meg van határozva, ha eltekintünk a főátlóján álló elemek előjeleitől; ezeket pozitívnak választjuk.

Következmény.

szimmetrikus M-mátrixok pozitív definitek. Ugyanez igaz a domináns főátlójú mátrixok esetén, amennyiben főátlóbeli elemei pozitívak. Ugyanis a tételhez vezető úton haladva, mindkét esetben először az LU-felbontást hozzuk létre, és ekkor kiderül, hogy az -k pozitívak, ld.  1.9., ill.  1.6. tétel. (A domináns főátlójú mátrix esetén az 1.6. tétel szerint stb.)

Az -felbontás létrehozását szolgálja a Cholesky- (vagy négyzetgyök-) algoritmus. Az egyenletből következik

(1.54)

tehát az

képletek segítségével kiszámíthatjuk oszloponként az elemeket. A munkaigény összesen művelet, hiszen a Gauss-eliminációhoz képest most csak a fele elemet kell előállítani, a tárigény is csak .

Most vizsgáljuk az (1.54) képlet esetét! Ekkor

Így bár az főelem lehet kicsi, de az ő segítségével kiszámított számok mégsem nőhetnek korlátlanul, hiszen

Ilyen értelemben stabil a Cholesky-felbontás: az eljárás által kapott számok az alatt a korlát alatt maradnak, amit a kiindulási adatok (az mátrix elemei) megszabnak.

Az mátrixra kényelmesen úgy vezethetünk le egy becslést az euklideszi normában, ha az

(1.55)

összefüggésekből indulunk ki (ahol , ). Ekkor

Az főelemekre még alsó becslést is kaphatunk az (1.55) adatokból, hiszen és

és így .

Elméleti vizsgálatoknál így kényelmes a szimmetrikus, pozitív definit mátrix Cholesky-felbontása; gyakorlatilag hasznosabb a mátrix -felbontása (amelyre a fenti stabilitási eredmények – az és közötti összefüggés alapján – is vonatkoznak).

Egyrészt megtakarítjuk a négyzetgyökvonásokat, de az -felbontás előnyösebb azért is, mert szorzással kevesebbre van szükség

egyenletek megoldásánál. Ezenkívül az -felbontás még akkor is végrehajtható lehet, amikor a mátrix, bár szimmetrikus, de nem pozitív definit (ami a felbontás során kiderül, mert ekkor van olyan , amelyre ). Viszont ilyenkor nem garantált a felbontás stabilitása.

Ha szimmetrikus és valóban indefinit mátrix, akkor egy -felbontást stabilisan úgy állíthatunk elő, hogy minden lépésben egy -méretű blokkot választunk ki főelemnek, vagy . Így blokk-diagonális lesz (v.ö. 1.3.2. ponttal).

A felbontás első lépése a következőképpen írható le:

ahol permutációs mátrix,

reguláris -méretű, -méretű blokk, mérete viszont , v.ö. (1.33)-mal.

Ennek a lépésnek a döntő része a blokk megválasztása ( -et mindig megfelelően hozzáválasztjuk). Ez a következőképpen történik. Először határozzuk meg az

számot. Ha , akkor lesz a főelem ( , ). Máskülönben három lehetőség van:

ahol . Az első esetben , a másodikban , a harmadikban pedig

Ekkor próbálkozunk a ,

lehetőséggel. Számítsuk ki az megfelelő blokkalakjához Schur-féle komplementerének elemét! Ez

Innen kapjuk, hogy

(1.56)

Ebben a kifejezésben zavaró a tag, amely az szorzat becsléséből származik: ugyan becsülhetjük felülről a segítségével, de ekkor (1.56) nem vezet a keresett alakú becslésre, mert a jobb oldalon ezen maximum négyzete keletkezik. Ezért az szorzatot másképpen kell becsülnünk. Ehhez tekintsük a

számot és amennyiben , akkor (1.56) helyett

Ekkor maradt még az eset; itt újra választhatjuk -et, -et, és most megint

mivel

A megválasztásával elérjük, hogy az elemek növekedése két hagyományos, -gyel jellemzett lépés alatt (amikor is értéke ugyanakkora legyen, mint egy dupla lépés alatt ( ; a növekedés ekkor ). Az így adódó növekedés tehát legfeljebb egy hagyományos lépésre átszámítva – míg ez az érték az oszloponkénti főelem-kiválasztásos LU-felbontásnál 2 volt, ld.  1.11. lemma. Közben az aritmetikai munka maradt, az összehasonlítások száma .

Befejezésül ehhez a ponthoz megadjuk azt az algoritmust, amely az szimmetrikus egyenletrendszert az -felbontás alapján oldja meg. Ez az algoritmus az mátrix alsó háromszögbeli elemeit oszloponként állítja elő.

Legyen szimmetrikus és pozitív definit (vagy más olyan szimmetrikus mátrix, amelyre az -felbontás létezik), adott sorvektor.

1.

2. ,

3.

4.

5. Ha =0, akkor hibajelzés és kiszállás.

6.

7. Kezdődik a visszahelyettesítés.

8.

9. stop [eredmény: ]

Felhívjuk a figyelmet arra, hogy a 6. sor után, a -ciklus végén az tömb tartalmazza a mátrix főátlóbeli elemeit, míg a tömb azoknak reciprokait.

1.3.9. Ritka mátrixok

Az alkalmazásokban gyakran kevés a nemzérus elem a mátrixokban. Ez a jelenség akkor adódik, ha olyan lineáris modellel írunk le valamilyen rendszert, amelyben a globális hatás lokális kölcsönhatások összegeként jön létre, és mindegyik lokális kölcsönhatásban a rendszer csak kevés egysége vesz részt. Az 1.1-ben a lineáris egyenletrendszerekre felhozott példák mind ide tartoznak.

Legyen mátrix rendje . Ritka mátrixról beszélünk akkor, ha két tulajdonsága van -nak. Egyrészt a nemzérus elemek száma kicsi -hez képest: . Másrészt az egyenletrendszer megoldása során sikerül az össztárigényt csökkenteni azáltal, hogy az nulla elemeit nem tároljuk – a számítási idő csökkentése, ill. jelentéktelen növelése mellett. Célunk az, hogy elkerüljük az olyan műveleteket, amelyekben csak nullával szorzunk, ill. nullát hozzáadjunk valamihez.

A tapasztalatok szerint számíthatunk arra, hogy míg a mátrix elemeinek kb. 40%-a vagy több nemzérus, addig nem érdemes különbséget tenni a nulla és nemnulla elemek között (tehát „telt” mátrixként kezeljük azt). Hogy mikor érdemes, az a zérus és nemzérus elemek elhelyezkedésétől függ.

Az 1.1. pontban példaképpen szereplő gazdasági rendszer mátrixáról elmondható, hogy általában eléggé rendszertelenül helyezkednek el a nemzérus elemek, viszont telt oszlopok is előfordulnak: az alapanyagok közül pl. áram és víz mindegyik gyárnak kell.

A hálózatokat leíró mátrixoknál rendszerint nagyon kevés a nemzérus elem; a főátló foglalt, és ezenkívül arra számíthatunk, hogy még három nemzérus elem van ugyanabban a sorban (mert a tipikus áramköri vagy csőelem az elágazás, ez három csomópontot köt össze az adott csomóponttal).

A differenciálegyenletek közelítő megoldása során keletkező egyenleteknél a nemzérus elemek gyakran egy a főátlóval párhuzamos sávban helyezkednek el – mint az (1.5) mátrixnál is. Ilyen sávos (ill. szalag-) mátrixok jellemzésére vezetjük be a sávszélesség fogalmát.

Definíció.

Az mátrix fél sávszélességének hívjuk azt az számot, amelyre teljesül

és létezik olyan indexpár, hogy és .

Így pl. az (1.5) mátrix (fél) sávszélessége 1.

1.15. Lemma (a sávszélesség megmaradása).

Az mátrix (fél) sávszélessége legyen , az mátrixú rendszerek legyenek megoldhatók Gauss-elimináció segítségével. Ekkor a Gauss-elimináció során megmarad a sávszélesség: az és szorzók sávszélessége is .

Bizonyítás.

Mint mindig, itt is elég a Gauss-elimináció első lépését vizsgálni.

Amikor , akkor a sávban vagyunk, így ezt az indextartományt nem szükséges vizsgálni. Legyen . Ekkor az

képlet alapján , hiszen ekkor . Hasonlóan esetén következik miatt. Így az elimináció első lépésében -re nem történik változás a mátrixban, azaz a nullák is ott maradnak, ahol voltak.

Megjegyzés.

Nem lényeges, hogy a vizsgált esetben a főátlótól jobbra és balra ugyanolyan széles-e a sáv, és az sem, hogy párhuzamos-e a főátlóval a határvonal a zérus és nemzérus elemek között, ld. a 24. feladatot.

A sávon belül, -re előfordulhat, hogy -ból lesz. Általános mátrix esetén és az elimináció -adik lépésében

(1.57)

alapján akkor lesz -ból , ha

Ezt a jelenséget, hogy a Gauss-elimináció során olyan helyen keletkezik nemzérus elem, ahol eredetileg nulla állt, feltöltődésnek hívjuk.

Hogy ez a természetes jelenség külön nevet kapott, annak legalább két oka van. Egyrészt, amennyiben a nulla elemeket nem tároljuk, a feltöltődésre ügyelnünk kell: helyet kell szereznünk az újonnan keletkezett elemeknek. Másrészt, a feltöltődés nagymértékű is lehet; alább példát adunk arra, hogy egy eliminációs lépés alatt rögtön az egész mátrix feltöltődik. Így az eredetileg tárhely helyett (ott ) mindjárt helyre lesz szükségünk, és a ritka mátrix meghatározása szerint . Itt jegyezzük meg, hogy a Gauss-elimináció gyakorlati problémája leginkább a tárhely, kevésbé a számítási idő.

A sávos mátrixoknál arra kell számítani, hogy az elimináció előrehaladásával a sáv egész szélességében feltöltődik. Ezért, ha nem túl széles a sáv, célszerű és egyszerű az a megoldás, hogy eleve az egész sávot tároljuk (sőt annyi mátrixon kívüli elemmel többet, hogy éppen kitöltsünk egy téglalap alakú tárrészt). A sávon belüli elemeknél nem teszünk különbséget nulla és nemzérus elem között, és a Gauss-eliminációt úgy változtatjuk (megfelelő indexátszámítással), hogy a sávon kívüli elemeket ne is érintse. Így kapjuk a sávos Gauss-eliminációt.

A sávos mátrixokra nyilván nem vonatkozhat ezen pont elején említett feltétel a 40 vagy több százalék nemzérus elemről (aminél nem érdemes különbséget tenni telt és ritka mátrix között), mert itt az összes sávon kívüli zéruselem jelenlétét előnnyel tudjuk kihasználni.

A sávos Gauss-elimináció műveletigénye (ld. az 1.15. lemma bizonyítását), mivel minden lépésben legfeljebb elemet kell megváltoztatnunk, lényegében . Ez azért kevesebb, mint telt mátrixnál az , mert sávszélességű mátrixról csak esetén érdemes beszélni. Egyébként az említett téglalap alakú tárrész már -től kezdve -nél kevesebb elemet tartalmaz.

Tekintsünk egy speciális egyenletrendszert, amelynek megoldására a sávos Gauss-elimináció a legjobb választás, mert az az egyenletrendszer művelettel való megoldását lehetővé teszi:

(1.58)

ahol háromátlós avagy tridiagonális mátrix, v.ö (1.5)-tel:

Teljesüljenek a következő feltételek:

(1.59)

Ezekben a feltételekben legyen .

A mátrix előjel struktúrája tehát olyan, mint egy M-mátrixé. De főátlója általában nem szigorúan domináns.

A fél sávszélesség 1, és az 1.15. „megmaradási” lemma szerint és fél sávszélessége is 1, ha a Gauss-elimináció alkalmazható. Ilyenkor mindkét háromszög alakú mátrixnak csak két (nemzérus) átlója van, és az megoldást a következő formában kereshetjük, ami a visszahelyettesítési menetnek felel meg:

(1.60)

Itt az és mennyiségeket az (1.58) rendszer -edik sorából lehet meghatározni.

azaz

Most tegyük fel, hogy . (Majd ezután fogjuk megvizsgálni, hogy ez mikor igaz.) Ekkor

ahol

(1.61)

A rendszer legelső egyenlete, , azt mutatja, hogy a fenti formulákban kiindulhatunk az

(1.62)

értékekből. Így kezdődhet a számítás, rendre megkapjuk az összes mennyiségeket, végül -re a következő rendszert írhatjuk fel:

tehát

(1.63)

Most ebből az értékből indulhat a visszahelyettesítési menet, kiszámítjuk az számokat. Az (1.60)– (1.63) algoritmus rövidített Gauss-elimináció néven avagy mint tridiagonális algoritmus is ismert.

A fenti formulákat nyilván csak akkor használhatjuk, amikor

1.16. Tétel (rövidített Gauss-elimináció stabilitása).

Az (1.59) feltételek mellett az (1.60)– (1.63) képletek jól definiáltak ( ) és stabilak abban az értelemben, hogy

Bizonyítás.

Tudjuk, hogy -re , így . Továbbá

Legyen rögzített -re, ekkor (1.59) miatt

és így

Az indukció alapján most már az összes -re , legfeljebb a -et nem számíthatjuk ki , miatt. Viszont ez csak akkor történhet, hogyha feltételeinkben nem szerepel „ ” – és ilyenkor a tridiagonális mátrix valóban szinguláris. Ha előfordul egyszer „ ”, akkor attól fogva , és ekkor is kiszámítható. Vagy pedig az összes , de .

Megjegyzések. 1. Az (1.59) feltételek teljesülnek az (1.5) mátrix esetén.

2. Amennyiben (1.59)-ben kizárólag az egyenlőség igaz, tehát a mátrix szinguláris, az egyenletrendszer megoldható egy mellékfeltétel teljesülése esetén (ld. a 20. feladatot).

3. Más feltételek mellett is stabil a rövidített Gauss-elimináció (ld. a 22. feladatot).

4. A rövidített Gauss-elimináció műveletigénye lényegében művelet (az 1.3.5. pont értelmében) és osztás, vagyis ha nem teszünk különbséget a négy alapművelet között, aritmetikai művelet.

5. Az algoritmus általánosítása más sávszélesség esetén kézenfekvő; ebből az esetre több alkalmazott feladatban szükség van. A képletek levezetésénél, a fentiekhez hasonló gondolatmenettel, az összefüggésekből induljunk ki.

Nem megfelelő a sávos Gauss-elimináció abban az esetben, amikor a sávszélesség összemérhető -nel vagy pl.  -nel, ha ugyanakkor a sávon belül is csak kevés a nemzérus elem. Ekkor elsőnek az az ötlet segíthet, hogy a sorokat vagy oszlopokat vagy mindkettőt permutálva az eredeti sávszélesség csökkenthető. Amennyiben ez sikerül, a sávszélességgel együtt csökken a tár- és a műveletigény is a telt mátrixéhoz képest.

Mutatunk egy egyszerű példát, amelyből látszik, hogy már szimultán sor- és oszlopcserével is előnyösen változtatható a sávszélesség. Legyen „ ” egy nemzérus elem helye és

ekkor a sávszélesség . Ha erre a mátrixra alkalmazzuk balról a és jobbról a permutációs mátrixokat, akkor az eredmény

Ennek sávszélessége 1.

A sávszélesség csökkentése csak az egyik lehetőség, ugyanis a ritka mátrixok nemzérus elemeinek más elrendeződését sem változtatja meg a Gauss-elimináció, és más algoritmus is van, mint a sávos Gauss-elimináció. A 24. feladatban definiáljuk a mátrix profilját; bebizonyítandó, hogy a Gauss-elimináció ezt a profilt – amely erősen eltérhet a sáv formájától – sem hagyja el. Így igyekezhetünk az adott mátrixot olyan formába rendezni, hogy a profil szélessége, azaz a feladat jelöléseivel: , minimális legyen. A profil alakú mátrixok LU-felbontását szolgáló algoritmust sem nehéz programozni, ennek használatával is csökkentjük a tár- és műveletigényt.

Amennyiben a nemzérus elemek elhelyezkedése nagyon rendszertelen, akkor előfordulhat, hogy a sáv- vagy profilszélesség minimalizálása nem hatékony, ill. sok időt igényel. Ami viszont ettől függetlenül is befolyásolható, és a tár- és műveletigényt közvetlenül meghatározza, az a feltöltődés.

A legegyszerűbb példát arra, hogy szimultán sor- és oszlopcserével mennyire változtatható a feltöltődés – a sávszélességnek és a lépcsőzetes profilszélességnek változtatása nélkül is –, az

mátrix adja. Ha erre a Gauss-eliminációt elvégezzük, akkor már az első lépés utáni mátrix telt és ennek eredményeképpen az és az szorzók mind telt mátrixok. Most szorozzuk meg balról a és jobbról a permutációs mátrixszal, akkor az eredmény

Ezen mátrix LU-felbontása során egyáltalán nincs feltöltődés; az és a mátrixok sávszélessége .

A példa általános tanulságot is szolgáltat: mindig toljuk el a nehézségeket (a telt, ill. sok feltöltődést okozó sorokat, oszlopokat) a Gauss-elimináció végére. Ezt teszi meg automatikusan a minimális fokszám algoritmus.

Ennek leírásához feltesszük, hogy a mátrixunk a három kiemelt osztályból való és ezenkívül strukturálisan szimmetrikus, azaz minden -re és -re igaz, hogy amennyiben , akkor .

Csak a szimultán sor- és oszlopcserék segítségével próbáljuk a feltöltődést minimalizálni, ugyanis ilyen cserék által a főátlóbeli elemek a főátlóban maradnak (ld. a 25. feladatot is), stabilitási problémáktól nem kell tartanunk, viszont más cserék esetén a három kiemelt mátrixosztály előnyös tulajdonságait elveszíthetjük.

Ezután a feltöltődés minimalizálásához elegendő lenne az összes lehetséges sorrendet (avagy permutációs mátrixot) végignézni, amelyben a főátlóbeli elemeket el lehet rendezni. Ez nyilván nem célszerű; leginkább csak olyan algoritmus jöhet szóba, amelynek költsége nem nagyobb -nél. Ilyen algoritmus csak viszonylag jó sorrendet tud garantálni, nem az optimálisat az lehetőség között.

Ha az elemet választjuk főelemnek, (1.57) miatt legfeljebb

(1.64)

helyen lesz feltöltődés az elimináció -adik lépésében. Itt jelöli az mátrix ( blokkjába eső és) -edik sorában álló nemzérus elemek számát; ugyanazt jelöli az oszlopokra nézve. Az függvényt Markowitz-költségnek hívjuk. A feltételezett mátrixosztályokban a főátlón mehetünk végig, azaz (1.64)-ben , és strukturális szimmetria esetén .

A fokszámot a következőképpen definiáljuk:

a) Az index szomszédja olyan index, amelyre van nemzérus elem;

b) az index fokszáma ezen szomszédok száma, azaz . A minimális fokszám algoritmus abból áll, hogy az elimináció -adik lépésében azt a főátlóbeli elemet választjuk főelemnek, amelynek az index fokszáma minimális. Az előbbiek szerint így elérjük, hogy ebben a lépésben minimális legyen a feltöltődés. Ezzel tehát a globális minimalizálást a lokálissal váltjuk fel, ami a műveletigény csökkentését -ról -re jelenti. A fenti példamátrixra alkalmazva, a minimális fokszám algoritmus adja a sorrendet – ezzel teljesen elkerülve a feltöltődést.

A nemzérus elemek nagyon rendszertelen elhelyezésénél előnyösebb ezeket nem sávban vagy profilban tárolni, hanem a kompakt tárolással, és a hozzátartozó, módosított LU-felbontást alkalmazni. Az 1.1-ben részletezett első és második példa rendszereit ilyen módon kell kezelnünk.

A kompakt tárolás az mátrixban tartalmazott információt három tömbben írja le, sorfolytonosan végighaladva a mátrix elemein:

a nemzérus elemeket

a lebegőpontos típusú

a

tömbben,

az indexeit

a két egészszám típusú

ja, ia

tömbben.

Mégpedig

ja-ban vannak a nemzérus elemek oszlopindexei,

ia mutatóvektor: -adik eleme adja azt az indexet a-ban és ja-ban, ahol a -adik sor kezdődik.

Egyébként előnyös, ha az ia tömbnek eleme van: , ahol a nemzérus elemek száma (ami egyben a és ja hossza). Ekkor minden ciklust egyformán lehet programozni. Míg a feladat mérete nem túl nagy , előnyös a ja tömböt kétbájtosnak deklarálni.

Az 1.2. pontban szereplő -es példamátrix kompakt tárolási alakja a következő:

Más lehetőségek is vannak ritka mátrixok nemzérus elemeinek tárolására. A programozás szempontjából a legegyszerűbb az, ha ia-ban a nemzérus elemek sorindexeit tartjuk. Ekkor, ha valamely elem az a mondjuk -adik komponense, akkor az ia, ill. ja vektorok -adik komponense a hozzátartozó , ill.  . Ehhez a témához ld. Galántai és Jeney könyvét és a 26. feladatot is.

Ha ritka az mátrix, akkor legtöbbször és is ritka. Emiatt ritka mátrix esetén különösen hátrányos lenne az inverz mátrixot kiszámítani, mert tipikusan telt mátrix (ld. a 28. feladatot).

Az és elemeit ugyancsak kompakt módon tároljuk; az indexeket az il, jl, ill. iu, ju tömbök tartalmazzák, a nemzérus elemeket az l és u tömbök. (Az LU-felbontás programozásához ezen tömbök ismeretében ld. a 29. feladatot.)

A három említett mátrixosztályra ezeket a tömböket (sőt az elimináció sorrendjét is, pl. a minimális fokszám algoritmus szerint) egy szimbolikus elimináció során lehet meghatározni a tulajdonképpeni számítás előtt (mert a főelemek meghatározásánál ekkor nem kell még a stabilitási szempontokat is figyelembe venni).

Ehhez a jl, ill. ju tömbökbe eleinte beírjuk a ja tömb tartalmát (aszerint, hogy az alsó vagy a felső háromszögbe tartozik az éppen vizsgált sorindex eleme), ennek megfelelően megkapjuk az il és iu tömbök elemeit. Majd a szimbolikus elimináció során, ha a ju tömbben a -adik sornak megfelelő szakasz tartalmazza a indexet és a jl tömbben az -edik sornak megfelelő szakasza tartalmazza a indexet, akkor esetén jl-t, esetén pedig ju-t egészítjük ki a indexszel (kivéve, ha ez már ott van). Ezután megfelelően változtatjuk il-t, ill. iu-t.

Amennyiben a mátrixunk nem a három osztályból való, akkor a tényleges számítás során úgy kell a főelemet megválasztani, hogy a stabilitást is biztosítsuk és a feltöltődést is kis szinten tartsuk. Ez általában kompromisszumot tesz szükségessé, de ekkor nem hátrányos a főátlón kívül is főelemet keresni.

Ennek a kompromisszumnak a megkereséséhez használjuk az (1.64) Markowitz-költséget, amit nem nehéz kiszámítani az és szorzók jelenlegi, a -adik lépés előtti állapotot leíró jl, il, ju, iu tömbökből.

Míg eddig a részleges főelem-kiválasztás során a -adik oszlopból azt az elemet vettük, aminek abszolút értéke maximális, most ehelyett ugyanabból az oszlopból olyan elemet veszünk, amire

(1.65)

Ha ezt az elemet főelemnek választjuk, akkor

minden komponensére igaz lesz . Ennek alapján érvényes , ld.  1.11. lemma.

A tapasztalatok szerint megfelelő az említett kompromisszum szempontjából.

Így tehát lehetséges egy korlátozott elemnövekedés az egymást követő mátrixokban, v.ö. 1.11. lemmával. jelentené az eredeti részleges főelemválasztást, miatt viszont a -adik oszlopból több elem jöhet szóba (1.65)-ben főelemként, amelyek közül a minimális Markowitz-költséggel rendelkezőt választjuk ki. Ha ez a főelem a -edik sorba esik, akkor megcseréljük a -adik és a -edik sort. Ezután világos, hogy hol keletkezik feltöltődés, és ennek megfelelően változtatjuk, ill. egészítjük ki a jl, il, ju, iu tömböket; az új -adik sor elemeit beírjuk az u tömbbe, az szorzókat az l tömbbe.

A sorcseréket itt is helyettesíthetjük mutatóvektorok segítségével.

Befejezésül megadjuk a legegyszerűbb, sávos mátrixra vonatkozó algoritmust, amely az (1.60)– (1.63) képleteket valósítja meg, tehát a rövidített Gauss-elimináció algoritmusát, más néven tridiagonális algoritmust.

Adott az (1.58) rendszer, amelynek tridiagonális mátrixa teljesíti az (1.59) feltételeket; legyen .

1. , ,

2.

3.

4.

5.

6. stop [eredmény: ]

Ebben az algoritmusban az jobboldali komponenseket a segédmennyiségekkel írjuk felül és ezért előnyös az indexek eltolása; az 1., 3. és 4. lépésben kellene a nullára való osztást letesztelni.

1.3.10. A Gauss–Jordan-algoritmus

A Gauss-elimináció végeredménye az

felső háromszög alakú rendszer. Ha itt a második sor -szorosát kivonjuk az első sorból, akkor az (1,2) pozícióban nullát kapunk – míg a főátló alatti nullákat nem érintjük. Ezután a harmadik sor segítségével az (1,3) és (2,3) pozíciókban állíthatunk elő nullákat stb. Ez a Gauss–Jordan-algoritmus. Végeredménye egy diagonális mátrix a bal oldalon, egy vektor a jobb oldalon.

Ez előnyösnek tűnik az LU-felbontáshoz képest. Szekvenciális számítógépen viszont költsége további művelet (most még a felső háromszög elemeit – az eredeti elemeknek durván a felét – el kell tüntetnünk, amihez művelet szükséges). Ez a plusz költség soha nem térül meg, amikor egyenletrendszert akarunk megoldani, és a művelettöbblet a kerekítési hibák növelését is okozza.

Párhuzamos vagy vektor-számítógép esetén más a Gauss–Jordan-algoritmus értékelése. Ekkor – főelem-kiválasztással – alkalmazása előnyös, mert ugyanannyi vektor- vagy párhuzamos lépés alatt készíthetjük el vele az egyenletrendszer megoldását, mint az LU-felbontást, és visszahelyettesítésre nincs szükség.

Most pedig bemutatjuk a Gauss–Jordan-algoritmus alkalmazását mátrix invertálásra, amikor párhuzamos gép áll rendelkezésre. Minden processzor ugyanannyi sort kap az mátrixból, pl. az -edik processzor az -edik sort, -t. Ezenkívül minden processzorhoz hozzárendeljük egy további mátrixnak egy-egy sorát, -t; ez a eleinte az egységmátrix, a végén a keresett inverz mátrix. Ekkor – ha főelem-kiválasztásra nincs szükség – a sorműveletekkel dolgozó algoritmus a következő.

Adott , keresett :

1.

2.

3. tehát minden -ra hajtsuk végre a ciklust

4.

5. stop [eredmény: ]

Az algoritmus lényeges vonása az, hogy a processzorok a -adik kivételével mind ugyanazokat az utasításokat hajtják végre; ehhez a 2. lépés befejeztével szét kell küldeni az és sorokat a többi processzorhoz. Az algoritmus során az mátrix oszloponként átalakul egységmátrixszá; más szóval, minden lépéssel csökken az sorok azon hossza, amivel érdemes foglalkozni. Ha nem az inverz mátrix számítandó ki, akkor alatt nem a mátrix -edik sorát, hanem a jobboldal -edik komponensét kell érteni.

A speciális mátrixosztályoktól eltekintve általában itt is szükséges a főelem-kiválasztás. Ebben az esetben sikeresebb a soronkénti főelem-kiválasztás. A főelem kiválasztása után cseréljük meg a mindenkori oszlopot a főelem oszlopával. A többi műveletet is át lehet írni oszlopműveletre ( 31. feladat). Az így keletkező algoritmus párhuzamos és vektor-számítógépen egyaránt előnyös, mert itt a vektorok hossza nem csökken lépésenként; az inverz mátrixot helyén állíthatjuk elő.