Matriisin singulaariarvohajotelma

(1)

Matriisin singulaariarvohajotelma

Jaakko Kirsilä

Matematiikan pro gradu Jyväskylän yliopisto

Matematiikan ja tilastotieteen laitos kevät 2021

(2)

Tiivistelmä:Jaakko Kirsilä,Matriisin singulaariarvohajotelma(engl. Singular Value Decomposition), matematiikan pro gradu -tutkielma, 55 s., Jyväsky- län yliopisto, Matematiikan ja tilastotieteen laitos, syksy 2020.

Tämän tutkielman tarkoituksena on esitellä ja todistaa matriisin singulaariarvohajotelma, jonka mukaan jokainenm×nmatriisiAvoidaan esittää muodosssaA=UΣV^T, missä matriisitUjaVovat ortogonaalisia jaΣon diagonaalimatriisi. Tuloksen muotoa voidaan verrata matriisin diagonalisoi- tuvuuteen. Diagonalisoituvuudesta puhuttaessa matriisin täytyy kuitenkin olla neliömatriisi ja lisäksi kaikki neliömatriisit eivät ole diagonalisoituvia.

Singulaariarvohajotelma on olemassa kaikillem×nmatriiseille.

Tutkielmassa tarvittavia tuloksia esitellään tutkielman alussa lineaarialgebran ja matriisiteorian kannalta merkittävien neljän aliavaruuden avulla.

Lisäksi tutustutaan näiden aliavaruuksien rooliin matriisinAtoiminnassa.

Singulaariarvohajotelmaan liittyy olennaisena osana matriisinAsingulaa- riarvot, jotka ovat matriisin A^TA ominaisarvojen neliöjuuret. Ennen singulaariarvohajotelman esittelyä tutkielmassa tutustutaankin matriisinA^TA ominaisuuksiin, joita tarvitaan myöhemmin singulaariarvohajotelman todistuksessa.

Tarkoituksena on myös esitellä matriisin singulaariarvohajotelman sovelluksia. Ensimmäisenä sovelluksena on matriisin pseudoinverssi, jota voidaan pitää käänteismatriisin yleistyksenä. Pseudoinverssin avulla voidaan ratkaista lineaarisia yhtälöryhmiä, jotka ovat muotoa Ax = b. Tällä yhtälöryhmällä ei kuitenkaan aina ole ratkaisua. Tällöin voidaan kuitenkin etsiä vektoria ˜x, joka minimoi lausekkeen kb−Ax˜k². Tätä vektoria ˜x kutsutaan pienimmän neliösumman ratkaisuksi. Osoittautuu, että pseudoinverssin avulla löydetään myös pienimmän neliösumman ratkaisu. Singu- laariarvohajotelman sovelluksena on myös matriisin approksimointi alemman asteen matriisilla. Tarkoituksena on esitellä tulos, jonka mukaan matriisin singulaariarvohajotelman avulla matriisille saadaan paras alemman asteen approksimaatio Frobenius normin suhteen. Tutkielman lopuksi so- velletaan matriisin alemman asteen approksimaatiota valokuvan häviölli- sessä pakkaamisessa.

(3)

Sisältö

Johdanto 1

1 Esitietoja 3

2 Neljä aliavaruutta 5

3 MatriisinA^TAominaisuuksia 12

4 Matriisin singulaariarvohajotelma 18

5 Pseudoinverssi 28

6 Pienimmän neliösumman ratkaisu 34

7 Matriisin approksimointi 44

8 Kuvan pakkaaminen 52

Viitteet 55

(4)

Johdanto

Tämä tutkielman päätarkoituksena on esitellä ja todistaa matriisin singulaariarvohajotelma, jonka mukaan jokainenm×nmatriisiAvoidaan esit- tää muodosssa A = UΣV^T, missä matriisit U ja V ovat ortogonaalisia ja Σon diagonaalimatriisi. Lisäksi esitellään matriisin singulaariarvohajotelman sovelluksia. Tutkielman päälähteinä on käytetty Steven J. Leonin kir- jaa Linear Algerbra with Applications [2] ja Gilbert Strangin artikkelia The Fundamental Theorem of Linear Algebra[4]. Osaan tutkielmassa olevista to- distuksista on käytetty apuna lähteistä löytyviä todistuksia, jotka on mai- nittu kunkin todistuksen yhteydessä. Lähteiden todistuksia on muokattu tutkielmaan sopiviksi ja niihin on lisätty välivaiheita.

Tutkielman ensimmäisessä kappaleessa esitellään tutkielmassa myö- hemmin tarvittavia ja suurimmaksi osaksi lukijalle ennestään tunnettuksi oletettuja esitietoja. Toisen kappaleen aluksi esitellään ja todistetaan lineaarialgebran merkittäviä ja työssä myöhemmin tarvittavia tuloksia, kutendi- mensiolausejaastelause. Toisen kappaleen päätarkoituksena on kuitenkin tu- tustuttaa lukija lineaarialgebran ja singulaariarvohajotelman kannalta olen- naisiin neljään aliavaruuteen. Nämä neljä aliavaruutta ovat yleiseenm×n matriisiinAliittyvätriviavaruusRow (A),sarakeavaruusCol (A), sekäytimet N(A) jaN(A^T).

Kolmannessa kappaleessa lähdetään edellisten kappaleiden tuloksien avulla johtamaan aputuloksia, joita tarvitsemme matriisin singulaariarvohajotelman ja sen sovelluksiin liittyvien tulosten todistamisessa. Mukana on kuitenkin sellaisenaankin mielenkiintoisia aputuloksia kuten lause, jonka mukaan matriisinasteei muutu, kun sitä kerrotaan kääntyvällä matriisilla.

Kappaleessa neljä esitellään ja todistetaan tutkielman päätulos eli matriisin singulaariarvohajotelma. Lisäksi perehdytään tarkemmin aiemmin mainittujen neljän aliavaruuden ja singulaariarvohajotelman yhteyteen.

Kappaleessa viisi käsitellään ensimmäistä tutkielmassa esiintyvää singulaariarvohajotelman sovellusta. Tämä onpseudoinverssi, jota voidaan pitää käänteismatriisin yleistyksenä. Tähän liittyen kuudennessa kappaleessa kä- sitellään yhtälöryhmänAx=bratkaisemista. Riippuen matriisistaAja vek- toristabvoi kuitenkin käydä myös niin, että yhtälöryhmällä ei ole ratkaisua.

Tällöin etsitään vektoria, joka on lähimpänä. Eli vektoria ˜x, joka minimoi lausekkeen kb−Ax˜k². Tätä vektoria ˜x kutsutaan pienimmän neliösumman ratkaisuksi. Osoittautuu, että matriisin pseudoinverssin avulla löydämme pienimmän neliösumman ratkaisun tai yhtälöryhmänAx = bvarsinaisen ratkaisun, mikäli se on olemassa.

Kappaleessa seitsemän käsitellään toista matriisin singulaariarvohajoel- man sovellusta eli matriisin approksimointia alemman asteen matriisilla.

Tässä yhteydessä määritellään matriiseihin liittyväFrobenius normi. Kappa- leen päätuloksen mukaan Frobenius normin mielessä matriisia parhaiten approksimoiva alemman asteen matriisi löydetään matriisin singulaariar-

(5)

vohajotelman avulla. Kappaleessa kahdeksan käytetään matriisin approksimointia valokuvan häviölliseen pakkaamiseen. Tämä on yksi merkittä- vimpiä matriisin singulaariarvohajotelman sovelluksia. MATLAB ohjelmaa apuna käyttäen tehdään esimerkkikuvalle eri asteisia approksimaatioita.

(6)

1 Esitietoja

Esitellään aluksi tässä tutkielmassa käytettäviä merkintöjä ja määritelmiä, joista suurin osa oletetaan lukijalle jo ennestään tunnettuna.

Määritelmä 1.1. Määritellään avaruudenRⁿeuklidinen sisätulo (· | ·) :Rⁿ× Rⁿ→Rasettamalla

x| y= Xn

i=1

x_iy_i

kaikillex=(x₁, . . . ,x_n)∈Rⁿjay=(y₁, . . . ,y_n)∈Rⁿ.

Määritelmä 1.2. Olkoon S = {v₁,v₂, . . . ,v_m}avaruuden Rⁿ vektorijoukko.

Tällöin joukonSvektoreidenv₁,v₂, . . . ,v_mvirittämäaliavaruus elilineaarinen verhoon

hSi=hv₁,v₂, . . . ,v_mi={λ1v₁+λ2v₂+. . .+λmv_m |λi∈R}.

Määritelmä 1.3. Olkoon V joukon Rⁿ osajoukko ja (· | ·) avaruuden Rⁿ sisätulo. Tällöin joukonV ortogonaalikomplementti V^⊥on

V^⊥ ={x∈Rⁿ|(x|v)=0 kaikille v∈V}.

V^⊥ on siis joukko, jonka vektorit ovat kohtisuorassa jokaisen joukonV vektorin kanssa. Toistensa kanssa kohtisuorassa olevia vektoreita sanotaan ortogonaalisiksi. Lisäksi pätee (V^⊥)^⊥ =V.

Määritelmä 1.4. OlkoonRⁿeuklidinen avaruus ja (· | ·) sen sisätulo. Tällöin avaruudenRⁿvektorit{v₁, . . . ,vn}ovatortogonaalisiamikäli

v_i |v_j

=











0, i, j ,0, i= j, jaortonormaalejamikäli

v_i|v_j

=











0, i, j 1, i= j. Määritelmä 1.5. OlkoonA m×nmatriisi

A=







a₁₁ a₁₂ · · · a_1n a₂₁ a₂₂ · · · a_2n

... ... ...

a_m1 am2 · · · amn





 .

(7)

Tällöin matriisinA transpoosi A^Tonn×mmatriisi

A^T =







a11 a21 · · · am1

a₁₂ a₂₂ · · · am2

... ... ...

a_1n a_2n · · · a_mn





 .

Sanotaan, ettän×nmatriisiAonsymmetrinen, jos se ei muutu transponoi- taessa eliA^T=A.

Määritelmä 1.6. n×n matriisia Q sanotaan ortogonaaliseksi, mikäli se on kääntyvä jaQ⁻¹=Q^T.

Ortogonaalisen matriisin sarakevektorit ovat ortonormaaleja. Lisäksi ortogonaalisella matriisilla on kaksi kuvauksen kannalta olennaista omi- naisuutta, sillä se säilyttää vektorien pituudet ja niiden väliset kulmat. To- distetaan näistä kahdesta ominaisuudesta vektorien pituuksien säilyvyys seuraavassa lauseessa.

Lause 1.7. Olkoon n×n matriisi Q ortogonaalinen. Lisäksi olkoon x ja y avaruuden Rⁿvektoreita. Tällöin

Qx|Qy= x| y

ja kQxk=kxk.

Todistus. Käyttäen sisätulon, transpoosin ja ortogonaalisen matriisin ominaisuuksia saadaan

Qx|Qy=(Qx)^TQy

=x^TQ^TQy

=x^TIy

=x^Ty

= x| y. Tällöin erityisesti

kQxk²=(Qx|Qx)

=(x|x)

=kxk²,

josta seuraa, ettäkQxk=kxk.

Koska ortogonaalinen matriisi säilyttää vektoreiden pituudet ja sisätu- lot, niin se kuvaa ortonormaalit kannat ortonormaaleiksi kannoiksi. Orto- gonaalinen matriisi on siis erikoistapaus kannanvaihtomatriisista.

(8)

2 Neljä aliavaruutta

Tämän kappaleen tarkoituksena on tutustua neljäänm×nmatriisiinAliit- tyvään aliavaruuteen. Kappaleen laatimisessa on käytetty apuna Gilbert Strangin artikkelia [4]. Esitellään aluksi muutama jatkossa käytettävä mer- kintä.

Määritelmä 2.1. OlkoonA m×nmatriisi. Tällöin matriisinA sarakeavaruus Col (A) on sen sarakevektoreiden virittämä avaruus

Col (A)={Ax|x∈Rⁿ}.

MatriisinA riviavaruusRow (A) on sen rivivektoreiden virittämä avaruus Row (A)=Col (A^T).

MatriisinA ydin N(A) on

N(A)={x∈Rⁿ|Ax=0}.

MatriisinA asterank (A) on sen sarakeavaruudendimensiodim Col (A).

Avaruuden Col (A) dimensio vastaa matriisinAlineaarisesti riippumat- tomien sarakkeiden lukumäärää. Pidetään myös yleisesti tunnettuna, että n×nneliömatriisi on kääntyvä, jos ja vain jos sen aste onn. Tämän tuloksen todistuksen voi halutessaan lukea kirjan [1] sivulta 358.

Riviavaruus Row (A) ja matriisinAydin N(A) ovat avaruudenRⁿ aliavaruuksia. Sarakeavaruus Col (A) ja neljäs tarvittava aliavaruus, matriisin A^T ydin N(A^T) ovat puolestaan avaruuden R^m aliavaruuksia. Aloitetaan näiden aliavaruuksien esittely yhdellä lineaarialgebran tärkeimmistä tu- loksista eli aliavaruuksien Col (A) ja N(A) dimensioiden välille liittyvästä dimensiolauseesta. Lauseen mukaan aliavaruuksien Col (A) jaN(A) dimensioiden summa vastaa matriisinAsarakkeiden lukumäärää.

Lause 2.2. (Dimensiolause) Olkoon A m×n matriisi. Tällöin dim Col (A)+dimN(A)=n.

Todistus. Olkoon dimN(A)=kja{u₁, . . . ,u_k}avaruudenN(A) kanta. Koska N(A) on avaruuden Rⁿ aliavaruus, niin voimme laajentaa tämän kannan avaruudenRⁿkannaksi{u₁, . . . ,u_k,v₁, . . . ,v_l}. Tällöinn=k+l=dimN(A)+l.

Riittää siis näyttää, että dim Col (A)=l.

Osoitetaan, että vektorit Av₁, . . . ,Av_l muodostavat avaruuden Col (A) kannan. Tästä seuraa, että dim Col (A) = l, sillä vektoreita on l kap- paletta. Näytetään aluksi, että vektorit Av₁, . . . ,Av_l virittävät avaruuden Col (A). Matriisitulon lineaarisuuden nojalla lineaariselle verholle

(9)

hAu₁, . . . ,Au_k,Av₁, . . . ,Av_lipätee

hAu₁, . . . ,Au_k,Av₁, . . . ,Av_li

=Ahu₁, . . . ,u_k,v₁, . . . ,v_li

=A(Rⁿ)

=Col (A).

Kuitenkin Au₁ = . . . = Au_k = 0, sillä u₁, . . . ,u_k ∈ N(A). Siispä vektorit Av₁, . . . ,Av_l virittävät avaruuden Col (A). Tämä ei kuitenkaan vielä riitä näyttämään, että dim Col (A)=l. Näiden virittäjävektoreiden joukossa voi nimittäin olla myös lineaarisesti riippuvia vektoreita, jolloin todellisuudes- sa voisi olla dim Col (A) <l. Osoitetaan siis, että vektoritAv₁, . . . ,Av_l ovat lineaarisesti riippumattomia ja siten muodostavat avaruuden Col (A) kannan. Olkoon siis

Xl

i=1

αiAv_i =0,

joillekinα1, . . . , αl ∈R. Matriisitulon lineaarisuuden nojalla saadaan A





 Xl

i=1

αiv_i





=0. TällöinPl

i=1αiv_i ∈N(A). Eli on olemassa esitys Xl

i=1

αivi= Xk

i=1

βiui,

joillekinβ1, . . . , βk ∈R. Vektoritu₁, . . . ,u_k,v₁, . . . ,v_lovat lineaarisesti riippumattomia, jolloin yhtäsuurus on mahdollista vain, josα1 =. . . =αl =β1 = . . . = βk = 0. Erityisesti siisα1 = . . . = αl = 0, jolloin vektoritAv₁, . . . ,Av_l

ovat lineaarisesti riippumattomia.

Dimensiolauseen yhteydessä esille tulee usein myös seuraava lineaarialgebran merkittävä tulos, jonka mukaan matriisinAsarakeavaruudella ja riviavaruudella on sama dimensio. Vastaavasti jos tulos muotoillaan käyt- täen matriisin asteen määritelmää, niin matriisillaAja sen transpoosillaA^T on sama aste.

Lause 2.3. (Astelause) Olkoon A m×n matriisi. Tällöin on dim Col (A)=dim Row (A).

Yhtäpitävästi matriisin asteen ja transpoosin määritelmien nojalla rank (A) = rank (A^T).

(10)

Todistus. Olkoon matriisin Apaikallai j oleva alkioa_{i j} ja matriisinArivi- vektoritr₁,r₂, . . . ,r_m. Olkoon lisäksi dim Row (A) =kja{u₁,u₂, . . . ,u_k}avaruuden Row (A) kanta. Tällöin voimme kirjoittaa jokaisen matriisinArivin avaruuden Row (A) kantavektoreiden avulla lineaarikombinaatioina

(1)











r₁=α11u₁+α12u₂+· · ·+α1ku_k r₂=α21u₁+α22u₂+· · ·+α2ku_k ...

rm =αm1u₁+αm2u2+· · ·+αmku_k,

joillekin αi j ∈ R. Merkitään paikalla i olevaa kantavektoria u_i = (u_i1,u_i2, . . . ,u_in). Tällöin yhtälöt (1) voidaan kirjoittaa muotoon











r₁=α11(u₁₁,u₁₂, . . . ,u_1n)+α12(u₂₁,u₂₂, . . . ,u_2n)+· · ·+α1k(u_k1,u_k2, . . . ,u_kn) r2=α21(u₁₁,u₁₂, . . . ,u1n)+α22(u₂₁,u22, . . . ,u2n)+· · ·+α2k(u_k1,u_k2, . . . ,u_kn) ...

r_m=αm1(u₁₁,u₁₂, . . . ,u_1n)+αm2(u₂₁,u₂₂, . . . ,u_2n)+· · ·+αmk(u_k1,u_k2, . . . ,u_kn). Nyt rivivektorin ri paikalla joleva komponentti on matriisin A alkio ai j. Jos poimimme ylempien yhtälöiden molemmilta puolilta paikalla jolevat komponentit, niin saadaan yhtälöt











a_1j=α11u₁_j+α12u₂_j+· · ·+α1ku_{k j} a_2j=α21u₁_j+α22u₂_j+· · ·+α2ku_{k j} ...

a_{m j}=αm1u_1j+αm2u₂_j+· · ·+αmku_{k j}. Nämä voidaan kirjoittaa muotoon





 a_1j a_2j ...

a_{m j}







=u_1j





 α11

α21

...

αm1





 +u_2j





 α12

α22

...

αm2







+· · ·+u_{k j}





 α1k

α2k

...

αmk





 .

Merkitään vektoriaαi =





 α1i

α2i

α...mi







, jolloin ylempi yhtälö voidaan kirjoittaa muotoon





 a_1j a2j

...

a_{m j}







=u_1jα1+u_2jα2+· · ·+u_{k j}αk.

(11)

Tästä huomataan, että yhtälön vasen puoli on matriisinApaikalla joleva sarake. Siispä jokainen matriisinAsarake voidaan kirjoittaa lineaarikom- binaationa vektoreiden α1, α2, . . . , αk avulla. Tällöin vektorit α1, α2, . . . , αk

virittävät avaruuden Col (A), jolloin

(2) dim Col (A)≤k=dim Row (A).

Toisaalta epäyhtälö (2) pätee mille tahansa matriisilleA, joten se pätee erityisesti myös matriisilleA^T. Siispä saadaan dim Col (A^T) ≤ dim Row (A^T).

Tästä seuraa, että

(3) dim Row (A)≤dim Col (A).

Tällöin epäyhtälöistä (2) ja (3) saadaan, että dim Row (A)=dim Col (A).

Seuraavan neljää aliavaruutta koskevan tuloksen mukaan ydinN(A) ja riviavaruus ovat toisiaan vasten kohtisuorassa. Lisäksi ydin N(A^T) ja sarakeavaruus ovat toisiaan vasten kohtisuorassa. Tämä kohtisuoruus antaa osaltaan myös selityksen sille, miksi ydin N(A^T) on juuri tarvitsevamme neljäs aliavaruus.

Lause 2.4. Olkoon A m×n matriisi. Tällöin N(A) = Row (A)^⊥ ja N(A^T) = Col (A)^⊥.

Todistus. Näytetään aluksi, ettäN(A)=Row (A)^⊥. Osoitetaan, ettäN(A) on kohtisuorassa avaruuden Row (A) kanssa. Täytyy siis näyttää, että jokainen avaruuden N(A) vektori on ortogonaalinen jokaisen avaruuden Row (A) vektorin kanssa. Olkoon siisx ∈N(A) ja y∈ Row (A). Tällöin vektoreillex jayon voimassa









 Ax=0

y=A^Tz,jollekinz∈R^m . Saadaan siis

x| y=x^Ty

=x^TA^Tz

=(Ax)^Tz

=0^Tz

=0.

Tästä seuraa, että N(A) ⊆ Row (A)^⊥. Toisaalta jos vektori v ∈ Row (A)^⊥, niinv on ortogonaalinen jokaisen matriisinA^T sarakevektorin kanssa eli Av = 0. Siispä v ∈ N(A) ja siten Row (A)^⊥ ⊆ N(A). Tällöin täytyy olla N(A)=Row (A)^⊥. TulosN(A^T)=Col (A)^⊥seuraa tästä, sillä

N(A^T)=Row (A^T)^⊥ =Col (A)^⊥.

(12)

Tiedämme nyt, että ydinN(A) ja riviavaruus ovat toistensa ortogonaalikomplementteja. Vastaavasti ydinN(A^T) ja sarakeavaruus ovat toistensa ortogonaalikomplementteja. Seuraava ortogonaalikomplementtien dimensioita ja niiden ortonormaaleja kantoja koskeva tulos luo lisää ymmärrystä näiden neljän aliavaruuden merkityksestä.

Lause 2.5. Olkoon V avaruudenRⁿaliavaruus. Tällöin dimV+dimV^⊥ = n.

Lisäksi jos{v₁, . . . ,vr}on aliavaruuden V ortonormaali kanta ja{v_r+1, . . . ,vn}on aliavaruuden V^⊥ortonormaali kanta, niin{v₁, . . . ,v_r,v_r+1, . . . ,v_n}on avaruuden Rⁿortonormaali kanta.

Todistus. JosV={0}, niinV^⊥=Rⁿ. Tällöin dimV+dimV^⊥=0+n=n. Jos V,{0}, niin olkoon{v₁, . . . ,v_r}avaruudenVkanta. OlkoonQ n×rmatriisi, jolle Q =

v₁ v₂ · · · v_r

. Sarakevektorit v₁, . . . ,v_r ovat kantavektoreina lineaarisesti riippumattomia, jolloin dim Col (Q) =rja lisäksi Col (Q) =V.

Tällöin Lauseen 2.4 mukaanV^⊥ = Col (Q)^⊥ = N(Q^T). Nyt dimensiolause 2.2 sovellettunar×nmatriisilleQ^Tantaa

dim Col (Q^T)+dimN(Q^T)=n.

Astelauseen 2.3 nojalla dim Col (Q^T) = dim Col (Q), jolloin dim Col (Q)+ dimN(Q^T)=n. KoskaV=Col (Q) jaV^⊥=N(Q^T), niin

dimV+dimV^⊥=n.

Näytetään vielä, että{v₁, . . . ,v_r,v_r₊₁, . . . ,v_n}on avaruudenRⁿortonormaali kanta. Osoitetaan aluksi, että vektoritv₁, . . . ,vr,v_r+1, . . . ,vnovat lineaarisesti riippumattomia. Olkoon

α1v₁+. . .+αrv_r+αr+1v_r+1+. . .+αnv_n=0,

joillekinα1, . . . , αr, αr+1, . . . , αn ∈ R. Merkitään x = α1v1+. . .+αrvrja y = α_r+1v_r+1+. . .+αnv_n. Nyt siisx+y=0 elix=−y. Lisäksix∈Vjay∈V^⊥, joten x| y = 0. Tästä seuraa, että (x|x) = x| −y = − x| y= 0 ja vastaavasti y| y= y| −x=− y|x=0. Tämä on mahdollista vain, josx=0 jay=0.

Siispä saadaan











α1v₁+. . .+αrv_r=0

αr+1vr+1+. . .+αnvn=0 .

Nyt v₁, . . . ,v_r ovat avaruuden V kantavektoreina lineaarisesti riippumattomia. Vastaavasti vektorit v_r₊₁, . . . ,v_n ovat avaruuden V^⊥ kantavektoreina lineaarisesti riippumattomia, jolloin täytyy olla α1 = · · · = αr = 0 ja α_r+1 = · · ·=αn =0. Tällöin vektoritv₁, . . . ,v_r,v_r+1, . . . ,v_novat lineaarisesti riippumattomia ja niitä onnkappaletta, jolloin ne muodostavat avaruuden Rⁿkannan. Osoitetaan vielä, että tämä kanta on ortonormaali. Nyt vektorit

(13)

v₁, . . . ,vr∈Vovat oletuksen nojalla ortonormaaleja ja vastaavasti myös vek- toritv_r+1, . . . ,v_n∈V^⊥ovat ortonormaaleja. Lisäksi avaruudetVjaV^⊥ovat toisiaan vastaan kohtisuorassa. Tällöin kaikki vektoritv₁, . . . ,v_r,v_r₊₁, . . . ,v_n ovat keskenään ortonormaaleja ja muodostavat avaruudenRⁿortonormaa-

lin kannan.

Jos yhdistämme Lauseen 2.4 ja edellisen Lauseen 2.5 dimensioita koskevan tuloksen, niin saamme kaksi tärkeää näiden aliavaruuksien dimensioita koskevaa tulosta:

(4) dim Row (A)+dimN(A)=n ja dim Col (A)+dimN(A^T)=m. Tämä dimensioita koskeva tulos on selityksenä sille, miksiN(A^T) on neljäs tarvitsemamme aliavaruus. Lisäksi aliavaruuksien Row (A) ja N(A) ortonormaalien kantojen yhdiste muodostaa ortonormaalin kannan avaruudel- leRⁿ. Vastaavasti aliavaruuksien Col (A) jaN(A^T) ortonormaalien kantojen yhdiste muodostaa ortonormaalin kannan avaruudelleR^m. Näiden neljän aliavaruuden ortonormaalit kannat ovat merkittävässä roolissa myöhem- min esiteltävässä matriisin singulaariarvohajotelmassa.

Ymmärtääksemme paremmin näiden neljän aliavaruuden yhteyttä mat- riisiinAtarkastellaan lineaarista yhtälöryhmääAx=bja sen ratkaisun löy- tämistä. YhtälöryhmänAx=bratkaiseminen vastaa kaikkien niiden kertoi- mienx₁,x₂, . . . ,x_nlöytämistä, jotka yhdessä matriisinAsarakkeiden kanssa muodostavat vektorinbsarakeavaruudessa Col (A):

Ax=

· · ·

!

| {z }

matriisinAsarakkeet





 x₁ x2

...

x_n







=x₁(1.sarake)+· · ·+x_n(n.sarake)=b.

Ydin N(A) puolestaan sisältää kaikki ratkaisut homogeeniseen yhtälöön Ax = 0. Mikäli vektori b kuuluu sarakeavaruuteen Col (A), niin yhtälöllä Ax = b on olemassa ratkaisu. Yksittäinen ratkaisu xr on riviavaruudessa Row (A) ja homogeenisen yhtälön ratkaisu x₀ on ytimessä N(A). Näistä muodostuu yleinen ratkaisux= x_r+x₀. Tilanteen hahmottamiseen auttaa Kuva 1. Kuva on lainattu samasta artikkelista [4], mutta sen merkintöjä on hieman muutettu vastaamaan tässä tutkielmassa käytettäviä merkintöjä.

Kuvasta 1 nähdään kuinka matriisiAvie vektorinx_rsarakeavaruuteen ja ytimestäN(A) olevan vektorinx0 nollavektoriksi. Vektori xr on ortogonaalinen vektorinx₀kanssa. Tämä seuraa siitä, että aliavaruudet Row (A) ja N(A) ovat Lauseen 2.4 mukaan toistensa ortogoonalikomplementteja. Vas- taavasti aliavaruudet Col (A) ja N(A^T) ovat toistensa ortogonaalikomplementteja. Tämä ilmenee myös kuvasta, sillä vastaavat aliavaruudet ovat kohtisuorassa keskenään.

(14)

Kuvasta 1 näkyy myös Lauseen 2.3 tulos, sillä riviavaruudella ja sara- keavaruudella on sama dimensior. Lisäksi ytimienN(A) jaN(A^T) dimensiot on laskettu yhtälöiden (4) avulla ja merkitty kuvaan.

Kuva 1: YhtälöAx=bja siihen liittyvät neljä aliavaruutta.

(15)

3 Matriisin A

^T

A ominaisuuksia

Tämän kappaleen tarkoituksena on edellisen kappaleen tuloksia apuna käyttäen edetä kohden seuraavassa kappaleessa esiteltävää matriisin singu- laariarvohajotelmaa. Erityisesti matriisiA^TAtulee olemaan singulaariarvohajotelman kannalta olennainen ja tarkoituksena on esitellä tähän matriisiin liittyviä myöhemmin tarvittavia tuloksia.

Määritelmä 3.1. OlkoonA n×nmatriisi. Jos vektorillev∈Rⁿ\ {0}ja luvulle λ∈Rpätee

Av=λv,

niin lukuλon matriisinA ominaisarvoja vektorivsiihen liittyväominaisvek- tori.

Yhtäpitävästi matriisinAominaisarvot saadaan yhtälöstä det (A−λI)=0,

jossa det (A−λI) on niin sanottu matriisinA karakteristinen polynomi. Karak- teristisen polynomin juuren monikertaa sanotaan ominaisarvonalgebralli- seksi kertaluvuksi.

Esitellään seuraavaksi matriisin ominaisarvojen yhteydessä diagonaalimatriisin ominaisarvoja koskeva aputulos, sekä similaaristen matriisien määritelmä ja siihen liittyvä aputulos, joita tarvitsemme myöhemmin kappaleessa 7.

Lemma 3.2. Olkoon D n× n diagonaalimatriisi, jonka diagonaalialkiot ovat λ1, . . . , λn. Tällöin matriisin D diagonaalialkiot ovat sen ominaisarvot algebralliset kertaluvut huomioiden.

Todistus. Nyt matriisinDkarakteristinen polynomi on

det (D−λI)=det







λ1−λ · · · 0

... ... ...

0 · · · λn−λ







=(λ1−λ)· · ·(λn−λ).

Tästä muodosta nähdään, että matriisinDdiagonaalialkiotλ1, . . . , λnovat karakteristisen polynomin juuret, jolloin ne ovat matriisinDominaisarvot

algebralliset kertaluvut huomioiden.

Määritelmä 3.3. OlkoonAjaB n×nmatriiseja. MatriisitAjaBovatsimi- laariset, jos on olemassa kääntyvän×nmatriisiCsiten, että

B=C⁻¹AC. Tällöin merkitäänA∼B.

(16)

Lemma 3.4. Olkoon A, B ja D n×n matriiseja. Lisäksi olkoon A ∼B ja A ∼D.

Tällöin (i) B∼D,

(ii) matriiseilla A ja B on samat karakteristiset polynomit,

(iii) matriiseilla A ja B on algebralliset kertaluvut huomioiden samat ominaisarvot.

Todistus. Lauseen todistuksessa on käytetty apuna kirjan [1] kappaleen 6.3 Lauseen 1 todistusta.

(i) MatriisitAjaBovat similaariset, joten on olemassa kääntyvä matriisi C, jolleB =C⁻¹AC. LisäksiA ∼D, joten on olemassa kääntyvä matriisi P, jolleA=P⁻¹DP. Tällöin saadaan

B=C⁻¹AC

=C⁻¹(P⁻¹DP)C

=(PC)⁻¹D(PC) SiispäB∼D.

(ii) MatriisitAjaBovat similaariset, jolloin on olemassa kääntyvä mat- riisiC, jolleB=C⁻¹AC. Tällöin determinantin laskusääntöjä käyttäen mat- riisinBkarakteristiselle polynomille saadaan

det (B−λI)=det (C⁻¹AC−λI)

=det (C⁻¹AC−λC⁻¹IC)

=det (C⁻¹AC−C⁻¹(λI)C)

=det (C⁻¹(A−λI)C)

=det (C⁻¹) det (A−λI) det (C)

=det (C⁻¹) det (C) det (A−λI)

=det (C⁻¹C) det (A−λI)

=det (I) det (A−λI)

=det (A−λI).

Siispä matriiseillaAjaBon samat karakteristiset polynomit.

(iii) MatriisienAjaBkarakteristiset polynomit ovat kohdan (ii) nojalla samat, joten näiden karakterististen polynomien juuret ovat myös samat.

Nämä juuret ovat matriisien A ja B ominaisarvot ja niiden algebralliset

kertaluvut ovat samat.

(17)

Ennen matriisiinA^TAliittyvien tuloksien esittelyä tarvitsemmeortogo- naalisesti diagonalisoituvanmatriisin määritelmän ja kaksi apulausetta. Näis- tä ensimmäisen mukaan symmetrinen matriisi on ortogonaalisesti diagonalisoituva ja toisen mukaan matriisin aste ei muutu mikäli sitä kerrotaan kääntyvällä matriisilla.

Määritelmä 3.5. n×nmatriisiAonortogonaalisesti diagonalisoituva, jos on olemassa ortogonaalinen matriisiQsiten että

Q^TAQ=D,

missä D on diagonaalimatriisi ja sen diagonaalialkiot λ1, λ2, . . . , λn ovat matriisinAominaisarvot algebralliset kertaluvut huomioiden.

Lemma 3.6. Olkoon A n×n symmetrinen matriisi. Tällöin A on ortogonaalisesti diagonalisoituva.

Todistus. Tämän lauseen todistus sivuutetaan tässä työssä. Todistuksen voi

halutessaan lukea teoksen [1] kappaleesta 6.4.

Lemma 3.7. Olkoon A m×n matriisi. Lisäksi olkoon B n×n kääntyvä matriisi ja C m×m kääntyvä matriisi. Tällöinrank (A)=rank (AB)=rank (CA).

Todistus. Lauseen todistus on tehty teoksessa [5] olevien Seurauksen 5.4.3 ja Lemman 5.4.3 todistuksien ideoita yhdistämällä. Näytetään aluksi, että Col (AB) = Col (A). Olkoon matriisi A muotoa A =

a₁ a₂ · · · a_n ja matriisiBmuotoaB =

b₁ b2 · · · bn

. Merkitään matriisin Bpaikalla j olevaa sarakevektoriab_j = (β1, β2, . . . , βn). Tällöin matriisin AB paikalla j oleva sarakevektori on muotoa

Ab_j =β1a₁+β2a₂+. . .+βna_n,

missäa₁,a₂, . . . ,a_n ∈ Col (A) ja β1, β2, . . . , βn ∈ R. Koska Col (A) on aliavaruus, niin edelleenAbj ∈Col (A). Siispä tästä seuraa, että Col (AB)⊆Col (A).

Toisaalta Col (A) = Col (ABB⁻¹) = Col

(AB)B⁻¹

⊆ Col (AB) aiemman kohdan nojalla, sillä matriisi B⁻¹ on kääntyvä. Tällöin siis on Col (AB) = Col (A) ja siispä rank (AB)=rank (A).

Näytetään seuraavaksi, että Row (CA)=Row (A). Nyt pätee Row (CA)=Col ((CA)^T)

=Col (A^TC^T)

⊆Col (A^T)

=Row (A),

(18)

sillä matriisiC^T on kääntyvä. Matriisin C^T kääntyvyys seuraa matriisinC kääntyvyydestä, silläC^T(C⁻¹)^T =(C⁻¹C)^T =I^T =I. Toisaalta myös

Row (A)=Row (C⁻¹CA)

=Col

(C⁻¹CA)^T

=Col

(CA)^T(C⁻¹)^T

⊆Col (CA)^T

=Row (CA),

sillä matriisi (C⁻¹)^T on matriisin C^T käänteismatriisina kääntyvä ja matriisi (CA)^T on n × m matriisi. Tällöin siis Row (CA) = Row (A), jolloin dim Row (CA) = dim Row (A). Tästä seuraa astelauseen 2.3 nojalla, että dim Col (CA)=dim Col (A) ja siispä rank (CA)=rank (A).

Esitellään seuraavaksi kaksi matriisiinA^TAliittyvää tulosta, joita tarvitsemme myöhemmin matriisin singulaariarvohajotelman todistuksessa.

Lause 3.8. Olkoon A m×n matriisi. Tällöin n×n matriisilla A^TA on seuraavat ominaisuudet

(i) matriisi A^TA on symmetrinen,

(ii) matriisin A^TA ominaisarvot ovat ei-negatiivisia, (iii) matriisi A^TA on ortogonaalisesti diagonalisoituva,

(iv) matriisin A^TA aste vastaa sen positiivisten ominaisarvojen lukumäärää algebralliset kertaluvut huomioiden.

Todistus. (i) Symmetrisyyden näyttäminen onnistuu suoralla laskulla transpoosin laskusääntöjä käyttäen

(A^TA)^T =A^T(A^T)^T =A^TA.

(ii) OlkoonλmatriisinA^TAominaisarvo javsitä vastaava ominaisvek- tori. Tällöin

kAvk²=(Av)^T(Av)

=v^TA^T(Av)

=v^T(A^TA)v

=v^T(λv)

=λv^Tv

=λkvk².

(19)

Tästä saadaan

λ= kAvk² kvk²

≥0.

Tällöin nähdään, että matriisinA^TAominaisarvoλon ei-negatiivinen.

(iii) Kohdan (i) mukaan matriisi A^TA on symmetrinen, jolloin Lem- man 3.6 nojalla matriisiA^TAon ortogonaalisesti diagonalisoituva.

(iv) Kohdan (iii) nojalla matriisiA^TAon ortogonaalisesti diagonalisoituva, joten on olemassa ortogonaalinen matriisiQsiten että

(5) Q^T(A^TA)Q=D,

missä D on diagonaalimatriisi ja sen diagonaalialkiot λ1, λ2, . . . , λn ovat matriisin A^TA ominaisarvot. Nyt matriisi Q on ortogonaalinen eli se on kääntyvä ja Q⁻¹ = Q^T. Tällöin kun operoidaan yhtälöä (5) vasemmalta matriisillaQja oikealta matriisillaQ^T, niin saadaan

A^TA=QDQ^T.

Tällöin rank (A^TA) = rank (QDQ^T). Lisäksi Lauseen 3.7 nojalla rank (QDQ^T) =rank (D), sillä matriisitQjaQ^T ovat kääntyviä. Siispä saadaan, että rank (A^TA)=rank (D). DiagonaalimatriisiDon muotoa

D=







λ1 0 . . . 0

0 λ2 . . . 0

... ... ... ...

0 0 . . . λn





 ,

missä luvutλ1, λ2, . . . , λn ovat matriisinA^TAominaisarvot. Nyt matriisin Dmuodosta nähdään, että kaikki matriisinDsarakkeet, joilla on nollasta poikkeava ominaisarvo ovat lineaarisesti riippumattomia. Nämä nollasta poikkeavat ominaisarvot ovat kohdan (ii) nojalla positiivisia. Tällöin mat- riisinDaste vastaa matriisinA^TApositiivisten ominaisarvojen lukumäärää algebralliset kertaluvut huomioiden. Nyt kuitenkin rank (A^TA)=rank (D),

joten väite on todistettu.

Seuraavan tuloksen mukaan matriiseillaAjaA^TAon sama aste. Lisäksi niillä on sama ydin.

Lause 3.9. Olkoon m×n matriisin A asterank (A)= r. Tällöin myös matriisin A^TA aste onrank (A^TA)=r. Lisäksi N(A)=N(A^TA).

Todistus. Osoitetaan aluksi, että N(A) =N(A^TA). Olkoonx ∈N(A). Tällöin Ax = 0, josta saadaan A^TAx = 0. Tästä seuraa, että x ∈ N(A^TA). Siispä N(A)⊆N(A^TA).

(20)

Toisaalta olkoon x ∈ N(A^TA), jolloin (A^TA)x = 0. Tästä saadaan x^T(A^TA)x = 0, joka on transpoosin laskusääntöjen nojalla sama kuin (Ax)^T(Ax) = kAxk² = 0. Täytyy siis olla Ax = 0, joten x ∈ N(A). Näin ollen N(A^TA) ⊆ N(A). Siispä täytyy olla N(A) = N(A^TA). Nyt A on m×n matriisi jaA^TAonn×nmatriisi, jolloin dimensiolauseen nojalla











rank (A)+dimN(A)=n

rank (A^TA)+dimN(A^TA)=n , joten

rank (A)+dimN(A)=rank (A^TA)+dimN(A^TA), ja tästä saadaan

rank (A)=rank (A^TA).

(21)

4 Matriisin singulaariarvohajotelma

Tässä kappaleessa esitellään tämän työn päätulos, eli matriisin singulaariarvohajotelma. Hajotelman avulla jokainenm×nmatriisiAvoidaan esittää muodossaA=UΣV^T, missä matriisitUjaVovat ortogonaalisia jaΣon diagonaalimatriisi. Lisäksi todistetaan tämä tulos ja lasketaan esimerkki hajo- telma konkreettiselle matriisille. Kappaleen lopuksi tutustutaan hajotelman toimintaan.

Määritelmä 4.1. Olkoon A m × n matriisi. Matriisin A singulaariarvot σ1, . . . , σn ovat matriisin A^TA ominaisarvojen λ1, . . . , λn neliöjuuret σi =

√λi ≥0.

Tässä on hyvä huomata, että Lemman 3.8 mukaan matriisinA^TAomi- naisarvot ovat ei-negatiivisia, jolloin niiden neliöjuuret eli matriisinAsin- gulaariarvot ovat hyvin määriteltyjä.

Lause 4.2. Jokainen m×n matriisi A voidaan esittää muodossa

A=UΣV^T =

u₁ u₂ · · · u_m







σ1 · · · 0 ... ... ...

0 · · · σr

0r×(n−r)

0(m−r)×r 0(m−r)×(n−r)











 v1T

v₂^T ...

v_n^T





 ,

missä matriisin U sarakevektorit u_iovat matriisin AA^Tominaisvektoreita. Lisäksi m×n diagonaalimatriisinΣjärjestyksessäσ1≥. . .≥σr>0olevat diagonaalialkiot ovat matriisin A positiiviset singulaariarvot ja matriisi täydennetään tarvittaessa riittävän suurilla nollamatriiseilla. Matriisin V sarakevektorit v_i ovat matriisin A^TA ominaisvektoreita. Lisäksi matriisit U ja V ovat molemmat ortogonaalisia.

Todistus. Tämän lauseen todistuksessa on käytetty apuna teoksen [2]

Lauseen 6.5.1 todistusta. Lemman 3.8 nojalla kaikki matriisinA^TAominai- sarvot ovat reaalisia ja ei-negatiivisia. Lisäksi matriisilleA^TAon olemassa sen ortogonaalisesti diagonalisoiva matriisiV.

Nyt siis Lauseen 4.2 matriisit A^TAja V ovat hyvin määriteltyjä. Näin ollen voidaan matriisinVsarakevektorit eli matriisinA^TAominaisvektorit järjestää niihin liittyvien ominaisarvojen

λ1≥λ2≥. . .≥λn≥0

määräämään järjestykseen. Koska nämä ominaisarvot ovat reaalisia ja ei- negatiivisia, niin matriisinAsingulaariarvot ovat

σj = q

λj j=1, . . . ,n.

(22)

Olkoon matriisinAaster. Tällöin Lemman 3.9 mukaan matriisinA^TAaste on myös r. Toisaalta Lauseen 3.8 kohdan (iv) nojalla matriisin A^TA aste vastaa sen positiivisten ominaisarvojen lukumäärää algebralliset kertaluvut huomioiden eli ominaisarvoille pätee

λ1≥λ2≥. . .≥λr>0 ja λr+1=λr+2=. . .=λn=0. Vastaavasti singulaariarvoille pätee

σ1 ≥σ2≥. . .≥σr>0 ja σr+1 =σr+2=. . .=σn=0. Esitetään matriisiV=

V₁ V₂

näihin ominaisarvoihin liittyvien ominaisvektorien avulla siten, että

V₁=

v₁ · · · v_r

ja V₂=

v_r+1 · · · v_n . Lisäksi olkoon

Σ1 =







σ1 0 . . . 0

0 σ2 . . . 0

... ... ... ...

0 0 . . . σr







r×r diagonaalimatriisi, jonka diagonaalialkiot ovat positiiviset singulaa- riarvotσ1, . . . , σr. Tällöin hajotelman varsinainenm×nmatriisiΣvoidaan muodostaa matriisistaΣ1täydentämällä se sopivan kokoisilla nollamatriiseilla, jolloin

Σ = Σ1

0 0 0

! .

Nyt olemme muodostaneet singulaariarvohajotelman matriisitVjaΣ. Teh- tävänä on siis vielä muodostaa ortogonaalinen matriisiU =

u₁ · · · u_m siten, että

A=UΣV^T tai yhtä pitävästi

(6) AV=UΣ.

Tarkastelemalla muotoa (6) sarakkeeseenrasti huomataan, että Avj =σjuj, j=1, . . . ,r.

Määritellään tämän avulla

(7) u_j = 1

σj

Av_j, j=1, . . . ,r

(23)

ja

U1=

u₁ · · · u_r . Tällöin näillä merkinnöillä pätee

(8) AV1 =U1Σ1.

Osoitetaan seuraavaksi, että matriisin U₁ sarakevektorit ovat keskenään ortonormaaleja. Nyt kaikille 1≤i≤rja 1≤ j≤rpätee

u_i |u_j

=u_i^Tu_j

=1 σi

Avi

T 1 σj

Avj

!

=1 σi

v_i^TA^T 1

σj

Av_j

!

= 1 σiσj

v_i^T(A^TAv_j)

= 1 σiσj

v_i^T(λjv_j) (v_jon matriisinA^TAominaisvektori eli (A^TA)v_j =λjv_j)

= 1 σiσj

viT(σj2vj)

= σj

σi

v_i^Tv_j

=











0 i, j 1 i= j,

sillä ortogonaalisen matriisinV₁sarakevektoritv₁, . . . ,vrovat ortonormaaleja. Siispä myös matriisinU₁sarakevektoritu₁, . . . ,u_rovat ortonormaaleja.

Lausekkeesta (7) nähdään sarakeavaruuden määritelmän mukaan, et- tä ortonormaalit vektoritu₁, . . . ,urkuuluvat matriisinAsarakeavaruuteen Col (A). Tämän sarakeavaruuden dimensio onr, jolloin{u₁, . . . ,u_r}muodostaa avaruuden Col (A) ortonormaalin kannan. Avaruuden Col (A) ortogonaalikomplementin Col (A)^⊥dimensio on Lauseen 2.5 mukaanm−r. Olkoon

(24)

siis{u_r+1, . . . ,um}avaruuden Col (A)^⊥ortonormaali kanta. Määritellään U₂=

ur+1 · · · um

, ja

U=

U₁ U₂ .

Edelleen Lauseen 2.5 mukaan {u₁, . . . ,u_r,u_r+1, . . . ,u_m} muodostaa avaruu- denR^mortonormaalin kannan. Tällöin matriisiUon ortogonaalinen.

Meidän täytyy vielä näyttää, että todella A=UΣV^T.

Tätä varten tarvitsemme aputuloksen, jonka mukaan A=AV₁V₁^T.

Näytetään tämä seuraavaksi. Nyt matriisin V2 sarakevektorit v_r+1, . . . ,vn

ovat ominaisarvoaλ=0 vastaavia ominaisvektoreita, jolloin A^TAvj=0 j=r+1, . . . ,n.

Tästä nähdään, että vektoritv_r+1, . . . ,v_nkuuluvat ytimeenN(A^TA). Toisaalta Lemman 3.9 nojallaN(A^TA) =N(A), jolloin samat vektorit kuuluvat myös ytimeenN(A). Tällöin

AV₂=0.

Lisäksi matriisiVon ortogonaalinen, joten

I=VV^T =V₁V₁^T+V₂V₂^T. Tällöin saadaan haluamamme aputulos

A=AI (9)

=A(V₁V₁^T+V₂V₂^T)

=AV₁V₁^T+AV₂V₂^T

=AV₁V₁^T+0V₂^T

=AV₁V₁^T.

Tämän jälkeen yhdistämällä kohdat (8) ja (9) saadaan UΣV^T =

U₁ U₂ Σ1

0 0 0

! V₁^T V₂^T

!

=U₁Σ1V₁^T

=AV₁V₁^T

=A.

(25)

Tällöin

A=UΣV^T.

Näytetään vielä lopuksi, että matriisinUsarakevektoritu_iovat matriisin AA^T ominaisvektoreita. Käyttämällä tietoa, että matriisiVon ortogonaalinen eli V^TV = I ja matriisille A todistamaamme hajotelmaa A = UΣV^T saadaan

AA^T =UΣV^T

UΣV^TT

(10)

=UΣV^T

(V^T)^TΣ^TU^T

=UΣV^T(VΣ^TU^T)

=UΣIΣ^TU^T

=UΣΣ^TU^T.

Tässä matriisiΣΣ^T on edelleen diagonaalimatriisi, jonka diagonaalialkiot ovatβ1, β2, . . . , βm. Tällöin matriisiUdiagonalisoi matriisinAA^Tortogonaa- lisesti. Yllä oleva yhtälöAA^T =UΣΣ^TU^Tvoidaan kirjoittaa myös muodossa

AA^TU=UΣΣ^T, josta saadaan

(AA^T)u_i=βiu_i i=1, . . . ,m.

Nyt nähdään, että matriisinΣΣ^T diagonaalialkiotβ1, β2, . . . , βmovat matrii- sinAA^T ominaisarvoja ja vektorit u_i ovat matriisin AA^T ominaisvektorei-

ta.

Muodostetaan seuraavaksi esimerkkinä singulaariarvohajotelma sopivan yksinkertaiselle matriisille, jotta hajotelman idea on helpompi hahmot- taa. Seuraava esimerkki on lainattu teoksen [3] sivulta 616.

Esimerkki 1. Muodosta singulaariarvohajotelma matriisilleA= 1 1 0 0 0 1

! . Tarvitsemme aluksi matriisinA^TAominaisarvot. Laskemalla saadaan mat- riisiksi

A^TA=







1 1 0 1 1 0 0 0 1





 . MatriisinA^TAkarakteristinen polynomi on

det (A^TA−λI)=−λ³+3λ²−2λ,

(26)

jolloin tämän polynomin juuret eli matriisinA^TAominaisarvot ovatλ1=2, λ2 =1 ja λ3 = 0. Näitä ominaisarvoja vastaavien ominaisvektorien selvit- täminen on melko mekaanista, mutta työlästä. Tämän vuoksi sivuutetaan näiden laskeminen tässä yhteydessä ja todetaan, että ominaisarvoja vastaavat ominaisvektorit ovat

w₁ =





 1 1 0







, w2=





 0 0 1







ja w3 =







−1 1 0





 .

Näistä ominaisvektoreista huomataan, että (w₁ |w₂) = 0, (w₁|w₃) = 0 ja (w₂|w₃) = 0. Siispä ne ovat ortogonaalisia. Matriisin V muodostamista varten nämä ominaisvektorit täytyy vielä normeerata. Saadaan siis ortonormaalit vektorit

v₁ =







√1 12

√ 2

0







, v₂=





 0 0 1







ja v₃=







−√¹ 12

√ 2

0





 .

Matriisin Asingulaariarvot saadaan matriisinA^TAominaisarvojen neliö- juurinaσ1= √

2,σ2= √

1=1 jaσ3 = √

0=0. MatriisinΣmuodostamisessa on tärkeää huomata, että hajotelman mukaan vain positiiviset singulaariarvot otetaan mukaan. Siispä singulaariarvoa σ3 = 0 ei oteta mukaan matriisiinΣ. Nyt voimme muodostaa matriisitVjaΣ. Saadaan

V=







√1

2 0 −^√¹

1 2

√

2 0 ^√¹

2

0 1 0







ja Σ =

√

2 0 0

0 1 0

! .

Meidän täytyy vielä muodostaa matriisiU. Lasketaan matriisin Usarake- vektorit yhtälön (7) avulla. Saadaan

u₁ = 1 σ1

Av₁ = 1

√ 2

1 1 0 0 0 1

!







√1 12

√ 2

0







= 1 0

!

ja

u₂ = 1 σ2

Av₂ = 1 1

1 1 0 0 0 1

!



 0 0 1







= 0 1

! .

Tässä on hyvä huomata, että sarakevektoriau3ei voida laskea, silläσ3=0.

Tämä ei kuitenkaan ole tarpeenkaan, sillä vektoritu₁jau₂ovat valmiiksi ortonormaaleja ja muodostavat avaruudenR²ortonormaalin kannan. Tällöin matriisiksiUsaadaan

U= 1 0 0 1

! .

(27)

MatriisinAsingulaariarvohajotelma on siis

A=UΣV^T = 1 0 0 1

! √

2 0 0

0 1 0

!







√1 2

√1

2 0

0 0 1

−^√¹

2

√1

2 0





 .

Halutessaan voi laskemalla varmistaa, että näin todella on.

Tarkastellaan vielä singulaariarvohajotelman muodostamista ja toimin- taa. Lauseessa 4.2 esiintyvät ortonormaalit kannat{v₁, . . . ,vr},{vr+1, . . . ,vn}, {u₁, . . . ,u_r}ja{u_r+1, . . . ,u_m}ovat merkittävässä roolissa singulaariarvohajotelman muodostamisessa. Nämä neljä kantaa ovat aiemmin kappaleessa 2 mainittujen neljän aliavaruuden Row (A),N(A), Col (A) jaN(A^T) ortonormaaleja kantoja. Todistetaan tämä seuraavassa lauseessa.

Lause 4.3. Olkoon A m×n matriisi ja A=UΣV^Tmatriisin A singulaariarvohajotelma, missä matriisit

V=

v₁ · · · v_r v_r+1 · · · v_n ja

U=

u₁ · · · u_r u_r+1 · · · u_m .

ovat ortogonaalisia. Lisäksi olkoonσ1, . . . , σrmatriisin A nollasta poikkeavat singulaariarvot. Tällöin

(i) matriisin A aste on r,

(ii) {v₁, . . . ,v_r}on aliavaruudenRow (A)ortonormaali kanta, (iii) {v_r+1, . . . ,v_n}on aliavaruuden N(A)ortonormaali kanta, (iv) {u₁, . . . ,u_r}on aliavaruudenCol (A)ortonormaali kanta, (v) {ur+1, . . . ,um}on aliavaruuden N(A^T)ortonormaali kanta.

Todistus. Lauseen todistuksessa on käytetty apuna kirjan [3] Lauseen 5.17 todistusta.

(i) Koska matriisit U ja V^T ovat ortogonaalisina kääntyviä, niin Lem- man 3.7 nojalla

rank (A)=rank (UΣV^T)

=rank (ΣV^T)

=rank (Σ)

=r.

(28)

(iii) Todistetaan tämä kohta ensin, sillä kohta (ii) seuraa tästä. Tiedäm- me Lauseen 4.2 todistuksesta, että vektoritv_r+1, . . . ,v_nkuuluvat matriisinA ytimeenN(A). Nämä vektorit ovat ortogonaalisen matriisinVsarakevekto- reina ortonormaaleja ja niitä onn−rkappaletta. Lisäksi dimensiolauseen 2.2 nojalla dimN(A)=n−r, jolloin{v_r+1, . . . ,v_n}muodostaa aliavaruudenN(A) ortonormaalin kannan.

(ii) Tiedämme, että vektorit {v₁, . . . ,vr,v_r+1, . . . ,vn} muodostavat ava- ruudenRⁿ ortonormaalin kannan. Tästä seuraa, että jokainen vektoreista v₁, . . . ,v_ron kohtisuorassa jokaisen vektorinv_r+1, . . . ,v_n∈N(A) kanssa. Täl- löin sisätulon lineaarisuuden nojalla vektoritv₁, . . . ,vr ovat kohtisuorassa kaikkien vektoreista v_r+1, . . . ,v_n muodostettujen lineaarikombinaatioiden kanssa. Nyt kuitenkin kohdan (iii) nojalla vektorit v_r+1, . . . ,v_n muodostavat aliavaruuden N(A) ortonormaalin kannan, jolloin vektorit v₁, . . . ,vr

ovat kohtisuorassa kaikkien aliavaruudenN(A) vektoreiden kanssa. Lisäk- si Lauseen 2.4 nojallaN(A)^⊥=Row (A), joten vektoritv₁, . . . ,v_r∈ Row (A).

Tällöin Lauseen 2.5 mukaan

dim Row (A)=dimRⁿ−dimN(A)

=n−(n−r)

=r.

Nyt vektoritv₁, . . . ,vr ∈ Row (A) ovat ortonormaaleja eli ne ovat lineaarisesti riippumattomia. Lisäksi niitä onrkappaletta, jolloin ne muodostavat avaruuden Row (A) ortonormaalin kannan.

(iv) Tämä kohta on todistettu Lauseen 4.2 todistuksen yhteydessä.

(v) Lauseen 4.2 todistuksessa määrittelimme, että {u_r+1, . . . ,u_m} on aliavaruuden Col (A) ortogonaalikomplementin ortonormaali kanta. Nyt kuitenkin Lauseen 2.4 nojalla Col (A)^⊥=N(A^T). Siispä{ur+1, . . . ,um}on aliava-

ruudenN(A^T) ortonormaali kanta.

Artikkelista [4] lainatusta Kuvasta 2 nähdään kuinka riviavaruuden kantavektoreillev₁, . . . ,v_rja sarakeavaruuden kantavektoreilleu₁, . . . ,u_ron voimassa yhtälöAv_i =σiu_i.