http://www.math.hut.fi/teaching/v/3/02/L/L1.html Päivitetty 11.9.02 HA

Luento 1 (osittain vanhan kertausta)

ti-ke 10-11.9.2002

Yleisiä asioita

Kurssin sisällöstä
Opetustavasta, palautteita V2:lta
Ohjelmistot: Vain Maple. Jos joku haluaa, voi vaikka tehdä harjoitustyön Matlabilla. Neuvontaa annetaan pyydettäessä.
Prujut ja prujutoimittaja
Harjoitukset alkavat viikolla 38.

Matriisit ja lineaariset yhtälösysteemit,Maple ja Matlab-perusteita

Kreyszig 8 : Luvun 6 alkupykälät
Lay
Simo Kivelä Algebra ja Geometria luku 4

1. Matriisialgebraa

Kertaa KRE⁸ 6.1 - 6.2 Matriisitulo, Transpoosi A^T, Yksikkömatriisi Id:=diag(1,1,...1),

Matriisien käsittely Maple:lla

Tässä uudempi LinearAlgebra-tyyli, jota ensisijaisesti suosimme. Kts. myös lyhyt Maple-esimerkki tässä alla. Vanhempi linalg-tyyli toimii myös, kts. [HAM] s. 147 ...;

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.

Matriisien käsittely Matlab:lla

>> A=[1,2,3,4;5,6,7,8;9,10,11,12]  % Pilkun sijasta käy erottimena väli
>> B=A'
>> C=A*B

Matlab: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

2. Lineeriset yhtälösysteemit, Gaussin eliminaatio

KRE 6.3 s. 321 ...

   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 0

Rivioperaatioissa 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).

Matlab-esim.

>> 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     1

Seuraava itse opiskeltavaksi, ei katsota luennolla. (Älä suotta opettele Maple-syntaksia tästä, vaan lopussa olevasta esimerkistä.)

Esimerkki rivioperaatioista Maplella tehtynä (linalg-tyyli).

Voit harjoituksen vuoksi tehdä Maple-ws:n, jossa vanha tyyli vaihdetaan uudeksi.

Gaussin algoritmi

Kun olet hiukan harjoitellut Gaussin eliminaatiota, huomaat, että algoritmi voidaan yleisesti kuvata tähän tapaan. Askel 1:

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.

Askel 2:

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ä.

Näin jatketaan niin kauan, kunnes tullaan riville r, jonka alapuolella kaikki on nollaa tai tullaan riville m, eli r=m.

Porrasmuoto, Echelon form

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

Lause (linsys)

 (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         
     |    E_{r x r}      | P  |  |           E_{r 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.

Tod:Tällöinhän bmato=0 ja r <=m < n .

3. Gauss/Gauss-Jordan, ref/rref

AG s. 60, KRE s. 350 (KRE:ssä vain neliömatr., käänteismatriisin laskemisen yhteydessä.)

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

Nollarivit ovat pohjalla. (Kaikki nollasta poikkeavat rivit ovat jokaisen nollarivin yläpuolella.)
Jokaisen ei-nollarivin johtava alkio on yläpuolella olevan rivin johtavan alkion oikealla puolella (aidosti).
Johtavan alkion määräämän sarakkeen alaosa (johtavan alkion alapuoli) koostuu nollista.
Redusoitua porrasmuoto, rref on sellainen ref-muoto, jossa lisäksi
Johtavat alkiot ovat ykkösiä,

Johtavat sarakkeet ovat nollia myös johtavan alkion yläpoliselta osalta. (Ts. johtavat sarakkeet ovat yksikkömatriisin sarakkeita.)

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 ..)


    | I_r  P | b₁| 
    | O₁  O₂| b₂|

Tässä I_r 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.), O₁ on (m-r) x r nollamatriisi, O₂ on (m-r) x (n-r) nollamatriisi, ja b₁ ja b₂ 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.

Pivot- eli tukisarakkeet

Ref-muoto ei ole yksikäsitteinen, mutta voidaan osoittaa, että rref-muoto on. (Kts. vaikka Lay). Emme todistusta kuitenkaan käy läpi. Koska ref:stä rref:iin mentäessä johtavat sarakkeet pysyvät samoina, niin kaikissa ref-muodoissa täytyy olla samat johtavat sarakkeet. (Huomaa taas, permutaatioita ei tietenkään sallita.)

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.

Vapaat muuttujat, kantamuuttujat

Matriisin A tukisarakkeita vastaavat muuttujat ovat kantamuuttujia , kaikki muut ovat vapaita muuttujia . Vapaat muuttujat ovat vapaasti valittavia parametreja. Jos rengastat "pivotit", niin kaikki kerroinmatriisin muiden sarakkeiden indeksit ilmaisevat vapaita muuttujia. Jos ristiriitaisia yhtälöitä ei ole, niin siis vapaiden muuttujien lkm = vapaasti valittavien parametrien lkm. (kuullostaa hieman itsestäänselvyydeltä).

Linsys-lause toisin ilmaistuna

Koska kyseessä on tärkeä lause, kannattaa harjoitella sen lausumista eri tavoilla.

Lause: Olemassaolo-ja yksikäs./monikäs. (linsys, "pivot-muoto")

Systeemillä A x = b on ratkaisu(ja) (eli se on "konsistentti"),
jos ja vain jos
liitännäismatriisin
viimeinen sarake ei ole pivot-sarake, ts. ref-muodossa ei esiinny riviä
```
     [0,0, ...,0,c],  c#0
```
Jos systeemi on konsistentti, sillä on
- yksikäsitteinen ratkaisu, jos ja vain jos jokainen A:n sarake on tukisarake (pivot-sarake).
- Muussa tapauksessa sillä on äärettömän monta ratkaisua, tarkemmin sanottuna vapaita parametrejä on yksi kutakin ei-pivot-saraketta kohti.

ref- ja rref-muodot Maplella

This page created by mailto:Heikki.Apiola@hut.fi