Lineaarinen yhtälöryhmä

Wikipedia
Loikkaa: valikkoon, hakuun
Kolmen muuttujan lineaarinen yhtälöryhmä määrittää joukon tasoja, joiden leikkauspiste on ryhmän ratkaisu.

Lineaarinen yhtälöryhmä on nimensä mukaisesti yhtälöryhmä, joka koostuu tietystä määrästä lineaarisia yhtälöitä. N:n muuttujan lineaarinen yhtälö on muotoa:

 a_{1} x_{1} + a_{2} x_{2} + \cdots + a_{n}x_{n} = b

Siis m:n yhtälön n:n muuttujan lineaarinen yhtälöryhmä on muotoa:

 \left\{\begin{matrix} a_{11} \cdot x_{1} + a_{12} \cdot x_{2} + & \cdots & + a_{1n}\cdot x_{n} = b_1 \\ \vdots \\ a_{m1} \cdot x_{1} + a_{m2} \cdot x_{2} + & \cdots & + a_{mn}\cdot x_{n} = b_m \end{matrix}\right.

Lineaarinen yhtälöryhmä voidaan esittää matriisimuodossa:

 A\mathbf{x} = \mathbf{b} ,

jossa matriisi A on n\times m'-kerroinmatriisi, x on ratkaistava sarakevektori ja b yhtälöryhmän ratkaisuvektori.

Lineaarista yhtälöryhmää kutsutaan homogeeniseksi, jos ratkaisuvektori on nollavektori eli \mathbf{b}=\mathbf{0}.

Voimme tulkita lineaarisen yhtälöryhmän myös m:n (n-1)-ulotteisen hypertason, jotka määräytyvät yhtälöistä, leikkaukseksi n-ulotteisessa avaruudessa. Siis kolmen muuttujan kolmen yhtälön ratkaisu on kolmiulotteisessa avaruudessa sijaitseva kolmen tason leikkaus. Olettaen, että ratkaisuja on olemassa, on olemassa leikkaus ja samoin, jos on olemassa leikkaus, on olemassa ratkaisuja.

Ratkaisujen määrä[muokkaa | muokkaa wikitekstiä]

Lineaarisella yhtälöryhmällä voi olla:

  1. ei yhtään ratkaisua
  2. yksi ratkaisu
  3. äärettömän monta ratkaisua

Jos lineaarisella yhtälöryhmällä ei ole yhtään ratkaisua, sitä kutsutaan inkonsistentiksi tai ristiriitaiseksi. Lineaarisen yhtälöryhmän ratkaisujen määrä voidaan aina luokitella johonkin näistä kolmesta ryhmästä, koska jos yhtälöllä on ratkaisuvektorit a ja b, voidaan näistä muodostaa kolmas vektori, joka toteuttaa yhtälöt. Siis jos ratkaisuja on enemmän kuin yksi, niitä on äärettömän monta.

Ratkaisujen määrää voi myös ennustaa tiedosta, mikä on muuttujien määrän ja yhtälöiden määrän välinen ero:

  1. Jos lineaarisessa yhtälöryhmässä on enemmän muuttujia kuin yhtälöitä, on yhtälöryhmän ratkaisuja joko ääretön määrä tai ei yhtään
  2. Jos lineaarisessa yhtälöryhmässä on enemmän yhtälöitä kuin muuttujia, emme voi sanoa tilanteesta mitään, mutta yleisesti ottaen ei silloin yhtälöryhmällä ole ratkaisuja.

Tämä perustuu siihen, että kun yhtälöitä on vähemmän kuin muuttujia, ovat yhtälöt inkonsistentteja tai yhtälön ratkaisussa joudutaan ilmaisemaan ratkaisut vapaiden muuttujien avulla, jolloin saadaan ääretön määrä ratkaisuja. Mutta jos yhtälöitä on enemmän kuin muuttujia, ratkaisujen lukumäärästä ei voi tehdä päätelmiä, koska osa yhtälöistä voi olla yhtäpitäviä keskenään.

Yhtälöryhmän ratkaiseminen[muokkaa | muokkaa wikitekstiä]

Yhtälöryhmän ratkaiseminen tapahtuu tavallisesti matriisimuodossa, koska se on helpommin implementoitavissa tietokonelaskentaan ja koska se on tiiviimpi ja kätevämpi kuin yhtälöryhmän standardi muoto.

Saamme yhtälöryhmää vastaavan matriisimuodon (täydennetty matriisi) lisäämällä kerroinmatriisiin yhden sarakkeen perään, eli:

\begin{bmatrix} a_{11} & \cdots & a_{1m} & b_1 \\ \vdots & \ddots & \vdots & \vdots \\ a_{n1} & \cdots & a_{nm} & b_1\end{bmatrix}.

Tämän matriisin ratkaisut ovat alkuperäisen lineaarisen yhtälöryhmän ratkaisut, ja kaikki laskutoimitukset, mitä voidaan tehdä lineaariselle yhtälöryhmälle, voidaan käsitellä matriisin alkeisrivitoimitusten avulla, joita ovat:

  1. Summata yksi rivi kerrottuna vakiolla c\ne0 toiseen riviin
  2. Kertoa yksi rivi nollasta eroavalla vakiolla
  3. Vaihtaa matriisin kahden rivin paikkaa keskenään

Kun matriisille toimitetaan jokin yllä olevista operaatioista, sanotaan tulokseksi saadun matriisin olevan riviekvivalentti alkuperäisen matriisin kanssa ja sitä merkitään ~-merkillä. Merkkiä käytetään myös merkitsemään rivioperaatioita tehtäessä välivaiheita. Silloin sen yläpuolelle lisätään tehdyt rivioperaatioiden merkit. Rivioperaatioita merkitään kahdella tavalla, joista kumpikin on pätevä:

  1. c\cdot R_i+ R_j\Rightarrow R_j
  2. E_{i,j}(c)\,

Molemmat ilmaisevat: "Lisää rivi i kerrottuna vakiolla c riviin j ja laita se j-riville". Samoin:

  1. c\cdot R_i \Rightarrow R_i
  2. E_{i}(c)\,

merkitsee: "kerro rivi i vakiolla c". Mainittakoot, että rivioperaatio voidaan aina kääntää, jolloin, jos matriisi A on riviekvivalentti B:n kanssa, pätee sama toisin päin. Eli myös B on riviekvivalentti A:n kanssa.

Tulee havaita, että rivioperaatiot eivät muuta matriisin ratkaisuja ja siten voisi herätä ajatus pyrkiä saamaan matriisi muotoon:

\begin{bmatrix} a_{11} & a_{11} & \cdots & a_{1m-1} & b_{1m}
\\0 & a_{21} & \cdots & a_{2m-1} & b_{2m} \\ \vdots & \vdots & \ddots & \vdots & \vdots
\\0 & 0 & \cdots & a_{nm-1} & b_{nm} \end{bmatrix}

Tätä muotoa kutsutaan matriisin porrasmuodoksi (engl. row echelon form). Porrasmuotoisen matriisin jokaisen rivin ensimmäisen nollasta eroavan alkion alla on vain nollia, ja nollarivit ovat pohjalla. Tästä saadaan suoraan ratkaisut alkuperäiselle lineaariselle yhtälöryhmälle, koska tämän matriisin ratkaisujoukko on sama kuin alkuperäisellä matriisilla. Algoritmia, jolla matriisi saatetaan tähän muotoon, kutsutaan Gaussin eliminoinniksi. Sen perusideana on poistaa ensin ensimmäisestä sarakkeesta kaikki muut alkiot ja tehdä sama kaikille muille.

Huomaa, että jos eliminoinnin aikana päädymme riviin \begin{matrix}[0\;0\; 0\; 0\; ...\; 0\; k]\end{matrix}, jossa  k \ne 0 , tulisi yhtälöryhmästä tuloksena 0=k, mikä on mahdotonta. Tällöin yhtälöryhmällä ei ole ollenkaan ratkaisuja eli yhtälöryhmä on inkonsistentti.

Toisaalta voimme saada eliminoinnin aikana kokonaisen nollarivin, mikä ei tuota ristiriitaa, mutta yhtälöryhmälle emme saa yksikäsitteistä ratkaisua, koska emme saa viimeisestä yhtälöstä ensimmäistä viimeistä muuttujaa. Silloin joudumme ottamaan vapaan muuttujan ja päädymme äärettömään määrään ratkaisuja. Tästä muodosta on helpointa saada ratkaisut ja tehdä analyysiä ratkaisujen lukumäärästä, mutta joskus voidaan halutessa jatkaa matriisille toimitettuja rivioperaatioita niin, että päädytään muotoon:

\begin{bmatrix} 1 & 0 & \cdots & 0 & b_{1m}
\\0 & 1 & \cdots & 0 & b_{2m} \\ \vdots & \vdots & \ddots & \vdots & \vdots
\\0 & 0 & \cdots & 1 & b_{nm} \end{bmatrix},

mistä saamme suoraan ratkaisut. Tätä muotoa matriisista kutsutaan sen rref-muodoksi. Matriisin rref-muodossa jokaisen rivin ensimmäinen nollasta eroava alkio on yksi, ja sen sarakkeessa kaikki muut arvot ovat nollia, ja nollarivit ovat pohjalla. Algoritmia, jolla pääsemme tähän muotoon ref-muodosta kutsutaan Jordanin eliminoinniksi, ja siten eliminointia, jolla pääsemme tähän muotoon alkuperäisestä matriisista, kutsutaan Gaussin–Jordanin -eliminoinniksi. Tämä eliminointi on kuitenkin useimmiten tarpeetonta, koska ratkaisujen määrä näkyy suoraan ja nopeammin ref-muodosta. Lisäksi rref-muodon rakentamiseen tarvitaan yleensä vähintään saman verran rivioperaatioita kuin porrasmuotoon pääsemiseksi, mikä tekee siitä tehottoman varsinkin tietokonelaskennassa.

Teoreettisesti voimme kuitenkin todeta, että matriisin rref-muoto on yksilöllinen. Matriisin ref-muodosta on hyötyä myös determinantin määrityksessä, koska kolmiomatriisin, eli yhtä hyvin ref-muotoisen matriisin diagonaali-alkioiden tulo kertaa elementaarimatriisioperaatioiden vastaavien kerroinmatriisien determinantit, mikä on helppo määrittää.

Muita ratkaisumenetelmiä[muokkaa | muokkaa wikitekstiä]

Teoreettiselta merkitykseltänsä mielenkiintoisia ratkaisumenetelmiä on muutamia, jotka alla:

Matriisin kääntäminen[muokkaa | muokkaa wikitekstiä]

Algebrasta tutulla tavalla voimme ratkaista ax=b kertomalla yhtälön puolittain a-1. Samalla tavalla voimme ratkaista lineaarisen yhtälön matriisimuodosta Ax=b. Kertomalla yhtälön puolittain (vasemmalta, matriiseista puhuttaessa on puoli määriteltävä) matriisin A käänteismatriisilla (olettaen tietysti, että se on olemassa) saamme:

A\mathbf{x}=\mathbf{b} \Rightarrow A^{-1}A\mathbf{x}=I_n\mathbf{x}=\mathbf{x}=A^{-1}\mathbf{b}.

Tämä näyttää ihan kätevältä menetelmältä, jos unohdamme hetkeksi, että matriisi on kääntyvä, jos ja vain jos se ei ole singulaarinen ja kun se on neliömatriisi. Tätä ratkaisua voimme käyttää, jos A on neliömatriisi ja sen determinantti on nollasta eroava. Käänteismatriisin laskeminen on kuitenkin hidasta ja numeerisesti epätarkkaa. Käänteismatriisi on teoreettisesti hyödyllinen, helppo toteuttaa tietokoneella, ja sillä voi tarkistaa yhtälöryhmän ratkaisun.

Cramerin sääntö[muokkaa | muokkaa wikitekstiä]

Laskemalla käänteismatriisi voidaan todistaa, että kun matriisi A on neliömatriisi ja ei-singulaarinen, ratkaisu saadaan kaavalla:

x_i=\det \left( A_i \right) / \det \left( A \right),

missä matriisi A_i saadaan vaihtamalla i:s sarake ratkaisuvektorilla b. Tämä sääntö kärsii samoista puutteista kuin matriisin kääntämiseen perustuva laskukaava, joten se on tehoton ottaen huomioon, että A:n determinantti vaatii jo itsessään matriisin saattamista porrasmuotoon, jolloin yhtälöryhmä voitaisiin ratkaista takaisinsijoitusten avulla.