Huomaa, että kaikille linalg-funktioille ei ole LinearAlgebra-vastinetta. Siksi on syytä yleenä ladata molemmat.
Matlab jää valitettavasti taka-alalle tällä kertaa, mutta otetaan silti joitakin Matlab-perusasoita vastaisenkin varalle.
>> A=[1,2,3,4;5,6,7,8;9,10,11,12] % Pilkun sijasta käy erottimena väli >> B=A' >> C=A*BMatlab:ssa ei tarvita loppumerkkiä. Jos tulostus halutaan estää, lopetetaan puolipisteeseen (;) Matlab käsittelee vain numeerisia matriiseja, mutta niitä sitten tehokkaasti.
Symbolisessa muodossa operointi ei ole mahdollista (symbolic toolbox laajentaa tähän suuntaan, mutta sitä emme tässä käsittele). Rationaaliaritmetiikkaa voidaan käyttää komennolla
format rational
A x =b, missä A on kerroinmatriisi (m x n) (m yhtälöä, n tuntematonta) x on tuntemattomien muodostama sarakevektori (n x 1) b on annettujen lukujen muodostama sarakevektori (m x 1)Ratkaisujen lukumäärä voi olla 0, 1 tai ääretön, kuten jo 2 x 2 systeemeistä tiedetään (yhdensuunt. suorat, leikkaavat suorat, yhtyvät suorat).
Riviajattelu: Suorien leikkauspiste
Sarakeajattelu: Etsitään annetun vektorin (b) koordinaatit
matriisin sarakevektorien avulla esitettynä.
Gaussin eliminaatio, s. 321
Alkeisrivioperaatiot (s. 326)
1. rivi[i] <--> rivi[k] (rivien vaihto) 2. rivi[i] <-- c*rivi[i] , c ei ole 0 3. rivi[i] <-- rivi[i]+c*rivi[k] , c ei ole 0Rivioperaatioissa yhtälösysteemi säilyy ekvivalenttina (samat ratkaisut). Tähän perustuu ratkaisu Gaussin menettelyllä. Muunnetaan systeemi yläkolmiomuotoon. Rivioperaatiot voidaan helpoimmin kohdistaa suoraan matriisiin, jossa A:n perään liitetään b-sarake. Tätä sanotaan liitännäismatriisiksi, "augmented matrix"
Matlab Rivioperaatiot:
A([i k],:)=A([k i],:) A(i,:)=c*A(i,:) A(i,:)=A(i,:)+c*A(k,:)
Maple-esim.
> with(linalg): with(LinearAlgebra): > A := <<1,2,3>|<2,4,6>|<3,8,11>|<4,10,14>>: > Ab:=< A | <1,1,1>>; > Ab; [1 2 3 4 1] [ ] Ab := [2 4 8 10 1] [ ] [3 6 11 14 1] > Ab[2,1..-1]:=Ab[2,1..-1]-2*Ab[1,1..-1]: # rivi[2] <-- rivi[2] - 2 rivi[1] > Ab; [1 2 3 4 1] [ ] [0 0 2 2 -1] [ ] [3 6 11 14 1]Kannattaa verrata Matlab-syntaksiin, vaikka ei tällä kertaa Matlabia käytettäisikään. Matlab:lla rivioperaatiot ovat syntaksiltaan hieman lyhyempiä. Maplen uusi matriisisyntaksi sallii hengeltään aivan samanlaiset rivien päivitykset (ilman muuta mallia on otettu Matlabista).
>> A=[1 2 3 4;2 4 8 10; 3 6 11 14];b=[1;1;1];Ab=[A b] Ab = 1 2 3 4 1 2 4 8 10 1 3 6 11 14 1 >> Ab(2,:)=Ab(2,:)-2*Ab(1,:) Ab = 1 2 3 4 1 0 0 2 2 -1 3 6 11 14 1Seuraava itse opiskeltavaksi, ei katsota luennolla. (Älä suotta opettele Maple-syntaksia tästä, vaan lopussa olevasta esimerkistä.)
Askel 2:
- Jos a[1,1]=0 ja kaikki sen alapuoliset alkiot ovat = 0, niin 1. sarake on 0-sarake. Jatketaan oikealle, kunnes tulee nollasta erillinen sarake vastaan tai ollaan lopussa ja meillä on 0-matriisi, jolloin lopetetaan.
Edellisessä tapauksessa vaihdetaan tämä sarake ensimmäiseksi ja siirrytään kohtaan 2. (Sarakkeen vaihdot tehdään teoreettisessa algoritmissamme, käytännössä ei.)- a[1,1] tai jokin sen alapuolinen alkio on # 0, suoritetaan rivinvaihto. (Jos on valinnanvaraa, vaihdetaan ensimmäiseksi se, jossa on suurin "PIVOT".) Valitaan kertoimet c[2]=-a[2,1]/a[1,1],...,c[m]=-a[m,1]/a[1,1] ja suoritetaan rivioperaatiot:
rivi[2] <-- c[2]*rivi[1] + rivi[2]
...
rivi[m] <-- c[m]*r[1] + r[m]Näin saadaan alkion a[1,1]#0 alle 0-sarake.
Näin jatketaan niin kauan, kunnes tullaan riville r, jonka alapuolella kaikki on nollaa tai tullaan riville m, eli r=m.
- Jos a[2,2]=0 ja kaikki sen alapuoliset alkiot ovat = 0, niin kaikki on hyvin. Tällöin syntyy "pitkä porras" ja siirrytään katsomaan samalla silmällä a[2,3]:a ja sen alapuolista saraketta.
Jos tämän suhteen käy samoin, siirrytään taas eteenpäin.
Jos ajaudutaan loppuun (sarakkeeseen n) samoin tuloksin, on kaikki alapuolinen 0:aa ja olemme lopussa.
Ellei ajauduta loppuun, löytyy nollasta poikkeava "ala"sarake. Teoreettisessa algoritmissamme vaihdamme tämän sarakkeen 2. sarakkeeksi, käytännössä emme vaihda sarakkeita, vaan annamme syntyä pitkiä portaita.- a[2,2] tai joku sen alapuolella #0, vaihdetaan (tarvittaessa) rivit, niin, että uusi a[2,2] # 0. (Numeerisessa käytännössä vaihdetaan itseisarvoltaan mahdollisimman suuri.) Sitten jatketaan kohdasta [2,2] alkavalle alimatriisille samoin kuin Askel 1:ssä.
Gaussin algoritmi johtaa aina muotoon: (Merkinnät KRE-kirjan mukaiset) KRE 8 s. 329.
a[1,1] a[1,2] ... a[1,n] b[1] 0 c[2,2] ... c[2,n] bmato[2] 0 0 0 0 0 0 0.. 0 k[r,r] ... k[r,n] bmato[r] 0 0 .... 0 ... 0 bmato[r+1] 0 0 .... 0 ... 0 bmato[m]Tässä "päälävistäjän" alkiot a[1,1], c[2,2], ..., k[r,r] ovat nollasta poikkeavia.
Tämä muoto saadaan siis aikaan sarakevaihtojen avulla.
Edellä saadusta muodosta on helppo lukea kaikki mahdolliset tapaukset. Itse ratkaisun kannalta sarakevaihdot aiheuttavat ylimääräisen komplikaation, sillä tuntemattomien järjestyksestä täytyy silloin pitää kirjaa. Niinpä käytännössä niitä ei tehdä, vaan annetaan päälävistäjän porrastua tarpeen mukaan pitempiin askelmiin.
Olennaista on, että siirryttäessä seuraavalle riville alaspäin, 1. nollasta poikkeva alkio siirtyy oikealle ainakin 1. askeleen.
Ratkaisujen olemassaolo ja lukumääräkysymykset ovat kaikki luettavissa tästä kaaviosta. Saamme peruslauseen
(a) r < m ja jokin bmato[i] # 0, r+1 <= i <= m Ei ratk. Esimerkki (b) r=n ja bmato[i]=0, i=r+1 .. m (tai nämä (i > r)bmadot puuttuvat (tap. m=n)) yksikäs. ratk. Esimerkki (c) r < n ja bmato[i]=0, i=r+1 .. m (tai "kriittiset" bmadot puuttuvat (tap. m < n ja r = m) ) äärettömän monta ratkaisua Esimerkki (Myös (a)-kohdassa oli jo yksi.)
Havainnollistus
Tapaus a) r < m ja B2 # 0
a) r < m ja B2 # 0 n n ------------------ ---------- | | | | | | | | | B1 | | | B1 | | | | | | | | | | r ------------------ r ---------- | 0 ... 0 | | B2 | 0..0 | | B2 | 0 ... 0 | | | 0..0 | | m ------------------ m ----------Saadaan ristiriitainen yhtälö 0=B2(i) jollain i. Ei ratkaisuja
Tapaus b) r = n ja (B2 = 0 tai puuttuu)
(B2 puuttuu <==> r=m, joten tässä puutostilanteessa r=n=m)
n ------------------- | | | | | | | | | B1 | | | | | | | | | r ------------------ | 0 ... 0 | 0 B2 Tämä siis voi puuttua, | 0 ... 0 | 0 jolloin m=r=n m ------------------Yksikäsitteinen ratkaisu. Tällöin porrasmuoto on joka kohdassa "yksiaskelinen". Takaisinsijoitusvaiheessa jokaisessa yhtälössä yksi uusi tuntematon. Siis todellakin yksikäs. ratkaisu.
Tapaus c) r < n ja (B2 = 0 tai puuttuu)
(B2 puuttuu <==> r=m)
r n ---------------------- | | | | | | | | B1 | Er x r | P | | Er x r | | | | on yläkolmiomatriisi, jonka | | | | päälävistäjän alkiot # 0 r --------------------- | 0 ... 0| 0 | 0 B2 Tämä voi puuttua. | 0 ... 0| 0 | 0 m --------------------Ääretön määrä ratkaisuja, n-r vapaata parametria.
Tärkeä seurauslause homogeenisille systeemeille Ax=0
Lause (Hsys) Jos homogeeniyhtälössä (b=0) on m < n , niin aina on äärettömän monta ratkaisua. |
Käytännössä emme siis suorita sarakepermutaatioita. Määritellään nyt tarkemmin, mitä tarkoitamme ref:llä ja rref:llä.
Takaisinsijoitus voidaan myös toteuttaa rivioperaatioina, jolloin päädytään muotoon, josta ratkaisut ovat luettavissa vielä suoremmin kuin alakolmiomuodosta. Siitä käytetään nimitystä redusoitu porrasmuoto, "reduced row echelon form" (siitä lyhenne rref, jota mekin käytämme). Tässä nollataan myös yläkolmio johtavien sarakkeiden (tuki- eli pivot-) sarakkeiden) osalta. Ei-singulaarisen neliösysteemin tapauksessa päädytään diagonaalimatriisiin.
Prosessia, jolla rref-muoto saadaan aikaan, kutsutaan Gauss-Jordanin menetelmäksi. (ref-muotohan syntyy Gaussin eliminaatiomenettelyllä.)
Tämä on erityisen hyödyllinen tapa silloin, kun on laskettava annetun neliömatriisin käänteismatriisi. (Tätä siis KRE käsittelee.)
Sanonta: Nollasta poikkeavan rivin 1. nollasta poikkeava alkio on nimeltään johtava alkio ("leading entry"). Johtavan alkion määräämää saraketta sanotaan johtavaksi sarakkeeksi .
Määritelmä: ref ja rref
Matriisi on ref-muodossa, jos
Redusoitua porrasmuoto, rref on sellainen ref-muoto, jossa lisäksi
Esim: Kaikki nämä matriisit ovat rref-muodossa, johtavat sarakkeet on merkitty *:llä.
* * * * * * * [1 0 0] [1 0 2] [1 5 0 0] [ ] [ ] [ ] [0 1 0] [0 1 6] [0 0 1 2] [ ] [ ] [0 0 1] [0 0 0] [0 0 0 0] [0 0 0 0] * * * * [1 1 0 0 0 6] [ ] [0 0 1 0 0 -1] [ ] [0 0 0 1 0 3] [ ] [0 0 0 0 1 1]Tämä kuuluu osata, vaikka ei olekaan KRE:ssä.
ref vai rref ?
Käytännön laskennassa on edullisempaa käyttää ref-muotoa (siis yläkolmiota), sillä takaisinsijoitus on halvempaa kuin rivioperaatiot. Teoreettisesti rref-muoto on kauniimpi, sitä on siten sopivaa käyttää johtopäätösten tekoon (Johtopäätökset voidaan lukea hyvin myös ref-muodosta.)
Erityisen kaunista on, että rref-muoto voidaan osoittaa 1-käsitteiseksi, mitä ref-muoto ei ole.
Myös yhtälösysteemin muoto, josta ratkaisujen olemassaolo- ja lukumäärätieto sadaan luetuksi, on vielä pelkistetympi muodossa: ([AG] s. 60 ..)
| Ir P | b1| | O1 O2| b2|Tässä Ir on r x r-yksikkömatriisi, P on n x (n-r) - matriisi (Tällä matriisilla ei ole mitään erityistä rakennetta nollien/ei-nollien suhteen.), O1 on (m-r) x r nollamatriisi, O2 on (m-r) x (n-r) nollamatriisi, ja b1 ja b2 ovat vastaavat bmato-vektorin osat. (Vrt. yllä ref-muotokaavioita.)
(Tähän muotoon pääsemiseksi pitää ajatella tarvittaessa tehdyksi sarakepermutaatiot.)
Huom! Sarakepermutaatioiden suorittaminen ei kuulu sallittuihin operaatioihin, kun yhtälösysteemiä ratkaistaan. Tällöinhän yhtälösysteemi muuttuu toiseksi. Ne ovat sallittuja vain yleisten johtopäätösten teon tasolla, kun kysytään ratkaisujen olemassolo- ja lukumääräasioita.
Määritelmä, pivot- eli tukisarake: Matriisin A pivot- eli tukisarake on sellainen sarake, joka vastaa rref-muodon johtavaa saraketta.
Siten "pivot"-kohdat ovat samat kaikissa ref-muodoissa ja saadaan siis selville pelkillä Gaussin eliminaatioaskelilla.