6 Pienimmän neliösumman ratkaisu

Mikäli yhtälöryhmälläAx=bei ole ratkaisua eli vektoribei kuulu matriisin Asarakeavaruuteen, niin voimme etsiä vektoria ˜x, jolleAx˜ on lähimpänä vektoriab. Etsimme siis vektoria ˜x, jolle etäisyys

kb−Ax˜k

on pienin mahdollinen. Yhtäpitävästi voimme etsiä vektoria ˜x, joka minimoi lausekkeen

kb−Ax˜k².

Tällöin vektoria ˜xkutsutaanpienimmän neliösumman ratkaisuksi. Mikäli yh-tälöryhmälläAx=bon ratkaisu, niin pienimmän neliösumman ratkaisulle x˜pätee

kb−Ax˜k²=0.

Siispä etsimällä pienimmän neliösumman ratkaisua löydämme myös yh-tälöryhmänAx= bratkaisun, mikäli se on olemassa. Tällöin voimme kes-kittyä ainoastaan pienimmän neliösumman ratkaisun löytämiseen. Vaik-ka itse yhtälöryhmän ratVaik-kaisua ei olisiVaik-kaan olemassa, niin usein olemme kiinnostuneita löytämään pienimmän neliösumman ratkaisun. Pienimmän neliösumman ratkaisemisella on merkittäviä sovelluksia esimerkiksi fysii-kassa ja tilastotieteessä. Suoran sovittaminen pistejoukkoon on yksi näistä sovelluksista. Pienimmän neliösumman ratkaisun sovelluksista löytyy esi-merkkejä kirjan [2] kappaleesta 5.3.

Pienimmän neliösumman ratkaisun löytäminen onnistuu matriisin pseudoinverssin avulla. Päästäksemme itse pienimmän neliösumman rat-kaisun löytämiseen tarvitsemme kuitenkin aluksi suoran summan määri-telmän ja tähän liittyvän apulauseen.

Määritelmä 6.1. OlkoonUjaVavaruudenRⁿaliavaruuksia. Sanotaan, että avaruusRⁿ on avaruuksien U ja V suora summa, mikäli jokainen vektori w∈Rⁿvoidaan kirjoittaa yksikäsitteisesti summana

w=u+v,

missäu∈Ujav∈V. Tällöin merkitäänRⁿ=U⊕V.

Lemma 6.2. Olkoon S avaruudenRⁿaliavaruus. Tällöin on Rⁿ=S⊕S^⊥.

Todistus. Lauseen todistuksessa on käytetty apuna kirjan [2] Lauseen 5.2.3 todistusta. Mikäli S = {0} tai S = Rⁿ, niin tapaus on selvä. Olkoon nyt

dimS = r, missä 0 < r < n. Tällöin Lauseen 2.5 nojalla jokainen vektori x∈Rⁿvoidaan kirjoittaa muodossa

x=c₁x₁+· · ·+c_rx_r+c_r+1x_r+1+· · ·+c_nx_n,

missäci ∈R,{x1, . . . ,xr}on avaruudenSortonormaali kanta ja{xr+1, . . . ,xn} on avaruudenS^⊥ortonormaali kanta. Tällöin voidaan merkitä

u=c₁x₁+· · ·+c_rx_r ja v=c_r+1x_r+1+· · ·+c_nx_n,

jolloinu ∈ S, v ∈ S^⊥ ja x = u+v. Täytyy vielä osoittaa, että tämä summa esitys on yksikäsitteinen. Oletetaan, että vektorixvoidaan kirjoittaa myös summanay+z, missäy∈Sjaz∈S^⊥. Tällöin

u+v=x=y+z, josta saadaan

u−y=z−v.

Nytu−y ∈ Sjaz−v ∈ S^⊥, joten kumpikin kuuluu leikkaukseen S∩S^⊥. KuitenkinS∩S^⊥ = {0} jos nimittäin a ∈ S∩S^⊥, niin (a|a) = 0 eli a = 0.

Täytyy siis olla

u−y=0 ja z−v=0.

Tällöin siis

u=y ja v=z.

Mikäli vektori ˜x on yhtälöryhmän Ax = b pienimmän neliösumman ratkaisu ja p = Ax, niin˜ p on matriisin A sarakeavaruuden vektori, joka on lähimpänä vektoriab. Seuraavan lauseen mukaan tällainen lähimpänä oleva vektori on aina olemassa ja lisäksi se on yksikäsitteinen.

Lause 6.3. Olkoon S avaruuden R^m aliavaruus. Jokaiselle vektorille b ∈ R^m on olemassa yksikäsitteinen vektori p∈S, joka on lähinnä vektoria b eli pätee

kb−yk>kb−pk,

kaikille y∈S, y,p. Lisäksi vektori p∈S on lähinnä vektoria b∈R^m, jos ja vain jos b−p∈S^⊥.

Todistus. Lauseen todistuksessa on käytetty apuna kirjan [2] Lauseen 5.3.1 todistusta. Lemman 6.2 mukaanR^m =S⊕S^⊥, jolloin jokainen vektorib∈R^m voidaan kirjoittaa yksikäsitteisesti summana

b=p+z,

missäp∈Sjaz∈S^⊥. Tällöin mikäli vektoriy∈Sjay,p, niin kb−yk²=k(b−p)+(p−y)k².

Nyt vektoritp−y∈Sjab−p=z∈S^⊥ovat toisiaan vastaan kohtisuorassa, jolloin Pythagoraan lauseen mukaan

kb−yk² =kb−pk²+kp−yk². Tästä seuraa, että

kb−yk>kb−pk.

Tällöin vektorinbyksikäsitteisessä summaesityksessäb=p+zoleva vektori p∈Son aina olemassa ja se on lähinnä vektoriab, sillä pätee

kb−yk>kb−pk, kaikilley∈S,y,p.

Osoitetaan vielä, että vektorip ∈ S on lähinnä vektoriab ∈ R^m, jos ja vain josb−p∈S^⊥. Olkoot vektorip∈Sjab−p∈S^⊥. Tällöin aikaisemman todistuksen nojalla vektoripon lähinnä vektoriab.

Olkoon vektori p ∈ S lähinnä vektoria b ∈ Rⁿ. Täytyy osoittaa, että b−p ∈ S^⊥. Nyt Lemman 6.2 mukaan R^m = S⊕S^⊥, jolloin vektori b∈ R^m voidaan kirjoittaa yksikäsitteisesti summanab=u+v, missäu∈Sjav∈S^⊥. Tällöin vektoreillepjaupätee

p=u+(p−u).

Tästä saadaan

kb−pk=k(b−u)+(u−p)k.

Vektoritb−u ∈ S^⊥ jau−p ∈ S ovat toisiaan vastaan kohtisuorassa, joten Pythagoraan lauseen mukaan

kb−pk² =kb−uk²+ku−pk² (13)

≥ kb−uk².

Toisaalta vektorip∈Son oletuksen mukaan lähinnä vektoriab∈R^m, joten päteekb−pk ≤ kb−ykkaikillay∈S. Tällöin erityisesti vektorilleu∈Spätee

kb−pk ≤ kb−uk. Tällöin myös normien neliöille pätee

(14) kb−pk² ≤ kb−uk².

Siispä kohdat (13) ja (14) yhdistämällä saadaan kb−uk²≥ kb−pk²

=kb−uk²+ku−pk²

≥ kb−uk². Tällöin on oltava

ku−pk²=0,

joten täytyy ollau=pja tällöin vektorilleb∈R^mpätee b=u+v=p+v.

Siispä saadaan

b−p=v∈S^⊥.

Seuraavan lauseen mukaan yhtälöryhmän Ax = b pienimmän neliö-summan ratkaisun löytäminen vastaa niin sanottujen normaaliyhtälöiden ratkaisemista. Tämän lauseen avulla pääsemme pienimmän neliösumman ratkaisun löytämiseen pseudoinverssin avulla.

Lause 6.4. Olkoon b∈R^m ja A m×n matriisi. Tällöinx˜ ∈Rⁿon yhtälöryhmän Ax=b pienimmän neliösumman ratkaisu, jos ja vain josx toteuttaa normaaliyh-˜ tälöt

A^TAx=A^Tb.

Todistus. Lauseen todistuksessa on käytetty apuna kirjan [2] kappaletta 5.3.

Vektori ˜xon yhtälöryhmänAx=bpienimmän neliösumman ratkaisu, jos ja vain josp=Ax˜on matriisinAsarakeavaruuden vektori, joka on lähimpänä vektoriab. Lisäksi Lauseen 6.3 mukaan vektori p ∈ Col (A) on lähimpänä vektoriab∈R^m, jos ja vain jos vektori

b−p=b−Ax˜

kuuluu matriisinAsarakeavaruuden ortogonaalikomplementtiin Col (A)^⊥. Toisaalta Lauseen 2.4 nojalla tiedämme, että Col (A)^⊥ = N(A^T). Siispä vek-tori ˜xon pienimmän neliösumman ratkaisu, jos ja vain jos

b−Ax˜ ∈N(A^T).

Eli yhtäpitävästi, jos ja vain jos

A^T(b−Ax)˜ =0.

Tästä seuraa, että vektori ˜xon pienimmän neliösumman ratkaisu, jos ja vain jos

A^TAx˜=A^Tb.

Nyt pääsemme yhtälöryhmänAx=bpienimmän neliösumman ratkai-sun löytämiseen matriisin A pseudoinverssin avulla. Osoitetaan kahden seuraavan lauseen avulla, että pienimmän neliösumman ratkaisu löyde-tään aina pseudoinverssin avulla. Keskitylöyde-tään yleiseenm×nmatriisiinA.

Tällöin meillä on kaksi mahdollista tapausta riippuen matriiisinAasteesta.

Käsitellään seuraavassa lauseessa ensin tapaus, jossa matriisinA aste on täysi eli rank (A)=n. Tässä tapauksessa pienimmän neliösumman ratkaisu on aina olemassa ja lisäksi se on yksikäsitteinen.

Lause 6.5. Olkoon b∈R^mja A m×n matriisi, jonka aste on r=n. Lisäksi olkoon UΣV^T matriisin A singulaariarvohajotelma. Tällöin

˜

x=A⁺b=VΣ⁺U^Tb

minimoi lausekkeen kb−Axk² yli vektorien x ∈ Rⁿ. Lisäksi tämä minimoiva vektorix on yksikäsitteinen.˜

Todistus. Lauseen todistuksessa on käytetty apuna kirjan [2] sivulta 472 löytyvää todistusta. Olkoon Aon m×n matriisi, jonka aste on n. Tällöin m×nmatriisiΣjan×mmatriisiΣ^T ovat muotoa matriisiΣ⁺on muotoa

Σ⁺=

Nyt matriisitΣ^T jaΣlohkoittain kertomalla huomataan, että Σ^TΣ =

Tästä muodosta nähdään, että matriisillaΣ^TΣonnkappaletta lineaarises-ti riippumattomia sarakevektoreita eli sen aste on n. Tällöin se on n×n matriisina kääntyvä ja

(Σ^TΣ)⁻¹=















σ112 · · · 0 ... ... ...

0 · · · ¹

σn2













 .

Tällöin matriisit lohkottain kertomalla huomataan, että (Σ^TΣ)⁻¹Σ^T = Σ⁺.

Lauseen 3.9 nojallan×n matriisinA^TAaste onn, jolloin se on kääntyvä.

Nyt singulaariarvohajotelmassaA=UΣV^T esiintyvä matriisiVon ortogo-naalinen ja matriisitV, V^T ja (Σ^TΣ)⁻¹ ovat kaikki n×n matriiseja, jolloin käänteismatriisin laskusääntöjen nojalla saadaan

(A^TA)⁻¹ =

(VΣ^TU^T)(UΣV^T)⁻1

=

V(Σ^TΣ)V^T−1

=(V^T)⁻¹(Σ^TΣ)⁻¹V⁻¹

=V(Σ^TΣ)⁻¹V^T.

Olkoonp=Ax˜ ∈Col (A) vektori, joka on lähimpänä vektoriab. Tämä vek-toripon Lauseen 6.3 nojalla olemassa. Tällöin vektori ˜xon yhtälöryhmän Ax =bpienimmän neliösumman ratkaisu ja se toteuttaa Lauseen 6.4 mu-kaan normaaliyhtälöt, jolloin siis

A^TAx˜=A^Tb.

Operoimalla puolittain matriisilla (A^TA)⁻¹saadaan

˜

x=(A^TA)⁻¹A^Tb

=(V(Σ^TΣ)⁻¹V^T)(VΣ^TU^T)b

=V(Σ^TΣ)⁻¹Σ^TU^Tb

=VΣ⁺U^Tb

=A⁺b.

Nyt olemme osoittaneet, että vektori ˜x=A⁺bminimoi lausekkeenkb−Axk². Lisäksi nähdään, että vektori ˜x=A⁺bon yksikäsitteinen.

Toinen mahdollinen tapaus on se, ettäm×nmatriisinAaste onr < n.

Tällöin lausekkeenkb−Axk²minimoivia pienimmän neliösumman ratkai-suja on äärettömän monta. Pseudoinverssi antaa tässä tapauksessa pienim-män neliösumman ratkaisun ˜x, jonka normi kx˜k on pienin mahdollinen.

Näytetään tämä seuraavassa lauseessa.

Lause 6.6. Olkoon b∈R^mja A m×n matriisi, jonka aste on r<n. Lisäksi olkoon UΣV^T matriisin A singulaariarvohajotelma. Tällöin

˜

x=A⁺b=VΣ⁺U^Tb

minimoi lausekkeen kb−Axk² yli vektorien x ∈ Rⁿ. Lisäksi mikäli jokin muu vektori z minimoi lausekkeenkb−Axk², niin tällöinkzk>kx˜k.

Todistus. Tämän lauseen todistamisessa on käytetty apuna kirjan [2]

Lauseen 7.7.1 todistusta. Olkoonx∈Rⁿja määritellään c=U^Tb= c₁

onr×rdiagonaalimatriisi.

Nyt matriisiU^Ton ortogonaalinen, jolloin Lauseen 1.7 nojalla saadaan kb−Axk²=kU^T(b−Ax)k²

Tässä vektoric₂ei ole riippuvainen vektoristax, jolloin lausekkeenkb−Axk² arvo on pienin mahdollinen, kun

kc₁−Σ1y₁k=0.

Tämä on mahdollista, jos ja vain jos Σ1y₁=c₁, missä matriisiΣ1on kääntyvä ja

Σ1−1= Tällöin operoimalla puolittain matriisillaΣ1

−1saadaan

, ja saadaan x=Vy

Huomataan siis, että vektorixminimoi lausekkeenkb−Axk², kun

(15) x=V Σ1−1c₁

minimoi lausekkeenkb−Axk². Todistetaan vielä, että vektorin ˜xnormikx˜k on pienimmän neliösumman ratkaisuista pienin mahdollinen. Nyt minkä tahansa muun vektorin z, joka minimoi lausekkeen kb−Axk² täytyy olla muotoa on ortogonaalinen, jolloin

kzk²=kV^Tzk² =kV^T(Vy)k²=kyk² =kΣ1

−1c₁k²+ky2k² >kΣ1

−1c₁k²=kx˜k². Lauseen 6.6 todistuksesta on hyvä huomata, että vektori y2 voidaan valita yhtälössä (15) äärettömän monella tavalla. Siispä tapauksessa, jossa matriisinA aste onr < n pienimmän neliösumman ratkaisuja on ääretön määrä. Lisäksi Lause 6.5 ja Lause 6.6 pätevät myös neliömatriisin tapauk-sessa eli, josm=n. YhtälöryhmänAx=bpienimmän neliösumman ratkai-su löydetään siis aina matriisinApseudoinverssin avulla. Lisäksi saadun pienimmän neliösumman ratkaisun ˜xnormikx˜kon pienin mahdollinen ta-pauksessa, jossa pienimmän neliösumman ratkaisuja on ääretön määrä.

Lasketaan seuraavaksi esimerkki yhtälönAx=bpienimmän neliösum-man ratkaisemisesta matriisinApseudoinverssin avulla. Seuraavan esimer-kin laatimiseen on käytetty apuna kirjan [3] Esimerkkiä 7.40.

Esimerkki 2. Etsi yhtälölleAx=bpienimmän neliösumman ratkaisu, kun A= 1 1

Tästä nähdään, että yhtälöllä ei ole ratkaisua. Voimme kuitenkin etsiä pie-nimmän neliösumman ratkaisun ˜x, joka minimoi lausekkeenkb−Axk². Tä-mä ratkaisu ˜xlöydetään matriisinApseudoinverssinA⁺avulla. Tarvitsem-me siis ensin matriisinAsingulaariarvohajotelman. Jätetään tässä yhteydes-sä singulaariarvohajotelman yksityiskohtainen muodostaminen tekemättä ja todetaan vain, että matriisinAsingulaariarvohajotelmaksi saadaan

A=UΣV^T =

Tällöin Määritelmän 4 mukaan matriisinApseudoinverssi on A⁺ =VΣ⁺U^T =









√1 2

√1 1 2

√ 2

−√¹ 2









1

2 0

0 0

! 







√1 2

√1 1 2

√ 2

−√¹ 2







= ¹⁴₁ ¹⁴

4 1

4

! .

MatriisinA sarakevektorit ovat lineaarisesti riippuvia, jolloin matriisinA aste on 1< 2= n. Pienimmän neliösumman ratkaisuja on siis Lauseen 6.6 mukaan ääretön määrä. Tällöin Lauseen 6.6 nojalla etäisyyden kb−Axk² minimoivaksi pienimmän neliösumman ratkaisuksi saadaan

˜

x=A⁺b= ¹⁴₁ ¹⁴

4 1

4

! 0 1

!

= ¹⁴₁

4

! .

Tämä pienimmän neliösumman ratkaisu ˜x on myös normiltaankx˜k = ¹

2

√

pienin mahdollinen. 2

In document Matriisin singulaariarvohajotelma (sivua 37-47)