2.2 LU-hajotelman muodostaminen ja olemassaolo neliömatriisille

Gaussin matriisi. Olkoon x n -vektori. Etsitään sellainen neliömatriisi L , että kuvauksessa

vektorin x k ensimmäistä komponenttia säilyvät ja loput muuttuvat nolliksi. Gaussin matriisilla

on haluttu vaikutus. Huomaa, että valittu Gaussin matriisi riippuu vektorista x, eikä välttämättä nollaa muita vektoreita halutulla tavalla.

Harjoitus 2.2.1 Tarkista, että L x=[x ,...,x ,0,...,0] .

Gaussin matriisi on helppo kääntää. Sen inverssi on (tarkista)

joten sillä kertominen ei muuta lineaarisen yhtälöryhmän ratkaisua.

Harjoitus 2.2.2 Tarkista, että Gaussin matriisilla on edellä esitetty inverssi ja että

L e = e , kun i > k.

Tarkastellaan seuraavaksi matriisia A sarakevektorimuodossa

Tarkoituksena on muuttaa A yläkolmiomuotoon kertomalla sitä vasemmalta sopivilla Gaussin matriiseilla. Tämä saadaan aikaan kertomalla matriisi sopivasti valitulla L :llä, siten että ensimmäinen sarake muuttuu yläkolmiomuotoon. Sitten matriisi kerrotaan L :lla jolla toinen sarake muutetaan yläkolmiomuotoon muuttamatta ensimmäistä saraketta. Näin jatkamalla lopussa seisoo kiitos yläkolmiomatriisin muodossa.

1. sarake: Olettaen, että a 0, valitaan Gaussin matriisi L siten, että se muuttaa A:n ensimmäisen sarakevektorin e :n suuntaiseksi. Kerrotaan yhtälö vasemmalta matriisilla

Harjoituksen 1.4.1 perusteella matriisitulo on

komponenteittain kirjoitettuna

missä

ovat muuttuneita kertoimia. Ensimmäinen sarake on oikeaa muotoa. Pidetään siitä kiinni ja käydään muiden kimppuun.

2. sarake: jos

voidaan menoa jatkaa kertomalla yhtälö Gaussin matriisilla, joka jättää edellisen matriisin toisen sarakkeen kaksi ensimmäistä alkiota ennalleen ja nollaa muut.

missä

eli komponenttimuodossa

Tulo on

ts.

Huomaa, että ensimmäisen vaakarivin alkiot eivät muutu harjoituksen 2.2.2 perusteella.

k. sarake: Teemme kuvauksen yleisestä askeleesta. k-1 askelta on jo otettu. Jos

niin voimme muodostaa Gaussin matriisin, joka jättää k:nnen sarakkeen k ensimmäistä komponenttia ennalleen ja nollaa loput.

toisin kirjoittaen

Lopulta k=n-1, ja sarakkeet loppuvat. Käsillä on tulos

missä U on etsitty yläkolmiomatriisi.

Alakolmiomatriisien, joiden diagonaalialkiot ovat ykkösiä, tulo

on alakolmiomatriisi, jonka diagonaalialkiot ovat ykkösen suuruisia. (harjoitustehtävä 7) Sen avulla tulos voidaan kirjoittaa seuraavasti

missä U on eo. yläkolmiomatriisi. Koska alakolmiomatriisin, jonka diagonaalialkiot ovat ykkösiä, inverssi on alakolmiomatriisi, jonka diagonaalialkiot ovat myös ykkösiä, (Harjoitus 1.6.7) niin saadaan lopullinen hajotelma.

Harjoitus 2.2.3 Alakolmiomatriisin L lauseke on helposti muodostettavissa jo olemassaolevien Gaussin matriisien avulla, sillä (osoita)

Esimerkki 2.2.1 Muodostetaan matriisin A

LU-hajotelma. Ensin muodostetaan L .

ja

Seuraavaksi L

ja lopulta saadaan yläkolmiomatriisi U

Etsitty LU-hajotelma on

LU-hajotelman olemassaolo

Siirrytään nyt tarkastelemaan milloin LU-hajotelma voidaan muodostaa neliömatriisille. Ainoa ehto edellisen perusteella on se, että laskennan kuluessa joudutaan jakamaan alkioilla

Näitä yhdessä : n kanssa kutsutaan pivot-alkioiksi. Edellisen perusteella on selvää, että jos n-1 ensimmäistä pivot-alkiota ovat nollasta eroavia, niin matriisin A LU-hajotelma on olemassa.

Seuraava yksinkertainen ehto takaa LU-hajotelman olemassaolon.

Lause 2.2.1. Jos nxn matriisin A k ensimmäistä pääalideterminanttia ovat nollasta eroavia, niin k ensimmäistä pivot-alkiota eivät mene nolliksi ja kääntäen. Jos merkitään A:n pääalideterminantteja

niin

Todistus. L matriiseilla kertominen merkitsee sitä, että joistakin matriisin A vaakariveistä vähennetään k:s vaakarivi vakiolla kerrottuna. Tunnetusti matriisin determinantin arvo ei muutu. Jos tarkastellaan mitä tahansa A:n pääalimatriisia, niin sille tehdään täsmälleen samat operaatiot,ts. sen vaakarivistä vähennetään toinen, joten pääalideterminanttikaan ei muutu. Laskemalla ne sekä alkuperäisestä matriisista A että -matriisista saadaan väite todistetuksi.

Mikäli n-1:stä ensimmäisestä pivot-alkioista jokin menee nollaksi, ei toivoa tarvitse vielä menettää, sillä pienellä muunnoksella selvitään eteenpäin. Matriisin vaakarivejä vaihtamalla saatetaan jatkaa.

Lause 2.2.2. Jos det(A)   0, niin matriisin A:n vaakarivejä vaihtamalla pivot-alkiot voidaan valita siten, että ne eivät mene Gaussin eliminaatiossa nolliksi.

Todistus. Jos eliminaation 1. kierroksella a  = 0, valitaan ko. sarakkeen jokin muu alkio a    0. Jos ko. alkiota ei löydy, on

mikä on ristiriita, sillä det(A)  0. Vaihdetaan 1. ja k:s vaakarivi keskenään permutaatiomatriisilla P . Näin a saadaan vasempaan yläkulmaan. Sitten kerrotaan yhtälö L :llä.

k:s kierros: Jos

niin etsitään samalta sarakkeelta pivot-alkion alapuolinen alkio, jolle pätee

Ellei sellaista löydy niin

joten det(A) = 0 mikä on ristiriita. Vaihdetaan k:s ja i:s vaakarivi keskenään permutaatiomatriisilla P . Kerrotaan vasemmalta matriisilla L .

Jos matriisin vaakarivit pannaan jo aluksi oikeaan järjestykseen kertomalla se permutaatiomatriisilla P, niin olemme saaneet todistetuksi LU-hajotelman olemassaololauseen.

Lause 2.2.3. (LU-hajotelma nxnmatriiseille.) Olkoon A ei-singulaarinen nxn- matriisi. Tällöin on olemassa permutaatiomatriisi P s.e.

PA = LU,

missä L on alakolmiomatriisi, jonka diagonaalialkiot ovat ykkösiä ja U yläkolmiomatriisi.

LU-hajotelman numeerisia ominaisuuksia voidaan parantaa valitsemalla kussakin eliminaatiovaiheessa pivot-alkioksi

itseisarvoltaan mahdollisimman suuri luku vaihtamalla vaakarivien tai/ja sarakkeiden järjestystä matriisissa. Jos tyydytään etsimään pivot-alkiota alkuperäisen

lisäksi sen alapuolisesta sarakkeesta, puhutaan osittaispivotoinnista (partial pivoting). Jos pivot-alkiota etsitään alimatriisin, jossa indeksit i k ja jk, alkioiden joukosta, puhutaan täydellisestä pivotoinnista. Täydellisessä pivotoinnissa voidaan siis vaihtaa paitsi yhtälöiden, myös tuntemattomien järjestystä.

LU-hajotelman pääasiallinen käyttö on lineaaristen yhtälöryhmien Ax=b ratkaisemisessa. Aluksi muodostetaan matriisin A LU-hajotelma. Jos sitä muodostettaessa joudutaan suorittamaan osittaispivotointia, niin se vain vastaa lineaarisen yhtälöryhmän yhtälöiden järjestyksen vaihtoa, eikä siten vaikuta itse ratkaisuun. Täydellinen pivotointi muuttaa sekin lisäksi vain tuntemattomien muuttujien x järjestystä. Saatu yhtälö

on helppo ratkaista. P on permutaatiomatriisina ortonormaali, joten P =P , ja siten päästään yhtälöön

Tämä jaetaan kahteen osaan.

Ly=Pb Ux=y.

Ensimmäisellä yhtälöllä on yksikäsitteinen ratkaisu y=L Pb, sillä L on invertoituva. U on yläkolmiomatriisi, jonka diagonaalialkiot ovat A:n pivot-alkioita. Jälkimmäisen yhtälön ratkaisu on olemassa ja yksikäsitteinen, edellyttäen, että kaikki pivot-alkiot, myös viimeinen, ovat nollasta poikkeavia.

Kootaan yllä olevat tulokset seuraavaan lauseeseen.

Lause 2.2.4. Olkoon A nxn- matriisi ja b n- vektori. Jos det(A 0, on yhtälöllä Ab yksikäsitteinen ratkaisu jokaisella vektorilla b .

Harjoitus 2.2.4. Olkoon det(A 0 ja PA = LU. Osoita, että L ja U matriisit ovat yksikäsitteiset.

Esimerkki 2.2.2. Ratkaistaan LU-hajotelman avulla yhtälö Ab,

kun A on esimerkin 2.2.1 matriisi ja b = [1,1,1] Matriisin A LU-hajotelma on

Jos merkitään

Ly=b ja Ux=y,

niin yhtälö ratkeaa ratkeaa mukavasti, sillä alakolmioyhtälö

on helppo ratkaista kun aloitetaan ylemmästä yhtälöstä. Ratkaisu on

y= [1,0,0] .

Tämän jälkeen ratkaistaan yhtälö Ux=y. Senkin ratkaisu on helppo, sillä U on yläkolmiomatriisi.

Ratkaisu on

Interaktiivinen harjoitus 2.2.1. LU-hajotelma.