Tämän luennon video ei valitettavasti ole saatavilla ainakaan toistaiseksi.

Gaussin eliminaatio

Kyseessä on algoritmi matriisimuodossa olevan lineaarisen yhtälöryhmän ratkaisemiseen niin kutsutuilla rivioperaatioilla. Yhtälöryhmä voidaan esittää matriisimuodossa seuraavasti:
\[ \left\{ \begin{array}{ll} x-2y & = 1 \\ 3x+2y & = 11 \end{array} \right. \quad \Leftrightarrow \quad \begin{pmatrix} 1 & -2 \\ 3 & 2 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}= \begin{pmatrix} 1 \\ 11 \end{pmatrix} \]
Yhtälöryhmän ratkaisemisesta tiedetään:
  1. Yhtälöiden järjestyksellä ei ole väliä.
  2. Yhtälöt voidaan kertoa puolittain skalaarilla.
  3. Yhtälöt voidaan laskea puolittain yhteen (yhteenlaskumenetelmä).

Gaussin eliminaation rivioperaatiot perustuvat näihin havaintoihin. Niiden tavoitteena on saattaa alkuperäinen matriisiyhtälö yläkolmiomuotoon, joka on helppo ratkaista.

Rivioperaatio

Kerrotaan eliminoitavan tuntemattoman riviä skalaarilla ja lasketaan kaksi yhtälöä yhteen. Skalaari valitaan siten, että summeeratussa yhtälössä eliminoitavan tuntemattoman kerroin on nolla.

\[ \begin{pmatrix} \underline{1} & -2 & & 1 \\ 3 & 2 & & 11 \end{pmatrix} \]
Kerrotaan ensimmäinen rivi \(-3\):lla ja summataan se toiseen riviin:
\[ \begin{pmatrix} \underline{1} & -2 & \ & 1 \\ 0 & 8 & & 8 \end{pmatrix} \]
Toiselta riviltä saadaan yhtälö:
\[ 8y=8 \quad \Leftrightarrow \quad y=1 \]
Ensimmäinen tuntematon \( x\) ei ole enää mukana yhtälössä, eli se on eliminoitu.

Luku \( \underline{1}\) on ns. tukialkio (englanniksi pivot). Tukialkiolla tarkoitetaan rivin ensimmäistä nollasta poikkeavaa alkiota ja sitä käytetään käsiteltävän rivin valitsemiseen. Haluamme korvata luvun 3 nollalla, joten skalaariksi valitaan \( -\frac{3}{1}\).


Tarkastellaan seuraavaksi kolmen muuttujan yhtälöryhmää:

\[ \begin{pmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix}= \begin{pmatrix} 2 \\ 8 \\ 10 \end{pmatrix} \]
\[ \begin{pmatrix} \underline{2} & 4 & -2 & & 2 \\ 4 & 9 & -3 & & 8 \\ -2 & -3 & 7 & & 10 \end{pmatrix} \]
Kerrotaan ensimmäinen rivi 2:lla ja vähennetään se toisesta rivistä. Lisätään ensimmäinen rivi kolmanteen riviin:
\[ \begin{pmatrix} \underline{2} & 4 & -2 & & 2 \\ 0 & \underline{1} & 1 & & 4 \\ 0 & 1 & 5 & & 12 \end{pmatrix} \]
Vähennetään toinen rivi kolmannesta rivistä:
\[ \begin{pmatrix} \underline{2} & 4 & -2 & & 2 \\ 0 & \underline{1} & 1 & & 4 \\ 0 & 0 & \underline{4} & & 8 \end{pmatrix} \quad \Rightarrow \quad \left\{ \begin{array}{ll} x & = -1 \\ y & = 2 \\ z & = 2 \end{array} \right. \]

Alkuperäinen tehtävä \( \mathbf{Ax=b}\) on saatettu Gaussin algoritmilla muotoon \( \mathbf{Ux=c} \). Tämän jälkeen yhtälöryhmä on ratkaistu takaisinsijoittamalla (ks. aiempi esimerkkivideo).

Riviporrasmuoto

Vaihtoehtona takaisinsijoittamiselle on ratkaista yhtälöryhmä kokonaan matriisimuodossa eli saattaa se ns. riviporrasmuotoon. Jaetaan aikaisemman yhtälöryhmän alin rivi puolittain neljällä ja ylin rivi kahdella, jolloin saadaan:

\[ \begin{pmatrix} 1 & 2 & -1 & & 1 \\ 0 & 1 & 1 & & 4 \\ 0 & 0 & 1 & & 2 \end{pmatrix}. \]

Summataan seuraavaksi alin rivi kahteen ylepään riviin sopivilla kertoimilla (\(-1\) ja \(1\)) kerrottuna ja saadaan:

\[ \begin{pmatrix} 1 & 2 & 0 & & 3 \\ 0 & 1 & 0 & & 2 \\ 0 & 0 & 1 & & 2 \end{pmatrix}. \]

Kerrotaan vielä keskimmäinen rivi \(-2\):lla ja summataan se ylinpään riviin ja saadaan:

\[ \begin{pmatrix} 1 & 0 & 0 & & -1 \\ 0 & 1 & 0 & & 2 \\ 0 & 0 & 1 & & 2 \end{pmatrix} \quad \Leftrightarrow \quad \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} -1 \\ 2 \\ 2 \end{pmatrix} = \begin{pmatrix} -1 \\ 2 \\ 2 \end{pmatrix}. \]

Tämä on niin kutsuttu riviporrasmuoto yhtälöryhmälle eli se on saatettu muotoon \(\mathbf{Ix = x}\), jolloin yhtälöryhmän ratkaisut voidaan siis suoraan lukea täydennetyn matriisin oikealta puolelta.

Yleinen tapaus: Yhdensuuntaiset suorat
\[ \begin{pmatrix} 1 & -2 & & 1 \\ 3 & -6 & & 11 \end{pmatrix} \]
Kerrotaan ensimmäinen rivi 3:lla ja vähennetään toisesta rivistä:
\[ \begin{pmatrix} \underline{1} & -2 & & 1 \\ 0 & 0 & & 8 \end{pmatrix} \]
Huom! 0 ei voi olla tukialkio.

Viimeinen yhtälö on epätosi, yhtälöryhmällä ei ole ratkaisua.

Yleinen tapaus: Päällekkäiset suorat
\[ \begin{pmatrix} 1 & -2 & & 1 \\ 3 & -6 & & 3 \end{pmatrix} \]
Kerrotaan ensimmäinen rivi 3:lla ja vähennetään toisesta rivistä:
\[ \begin{pmatrix} \underline{1} & -2 & & 1 \\ 0 & 0 & & 0 \end{pmatrix} \]

Viimeinen yhtälö on tosi, \( y\):n voi valita vapaasti.

Yleinen tapaus: Järjestyksen vaihto
\[ \begin{pmatrix} 0 & 2 & & 4 \\ 3 & -2 & & 5 \end{pmatrix} \]
Vaihdetaan ensimmäisen ja toisen rivin paikkaa:
\[ \begin{pmatrix} \underline{3} & -2 & & 5 \\ 0 & \underline{2} & & 4 \end{pmatrix} \]

Esimerkki

Etsi lineaarisen yhtälöryhmän

\[ \left\{ \begin{array}{ll} x_1+x_2+3x_3 & = 3,\\ -x_1+x_2+x_3 & = -1, \\ 2x_1+3x_2+8x_3 & = 4. \end{array} \right. \] kaikki ratkaisut tai osoita, että ratkaisuja ei ole.

Ratkaisu

Muutetaan yhtälöryhmä matriisimuotoon \( \mathbf{Ax=b}\):

\[ \begin{pmatrix} 1 & 1 & 3 \\ -1 & 1 & 1 \\ 2 & 3 & 8 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}=\begin{pmatrix} 3 \\ -1 \\ 4 \end{pmatrix} \] Ratkaistaan yhtälö Gaussin eliminaatiolla: \[ \begin{pmatrix} 1 & 1 & 3 & 3 \\ -1 & 1 & 1 & -1 \\ 2 & 3 & 8 & 4 \end{pmatrix} \] Lisätään ensimmäinen rivi toiseen ja vähennetään ensimmäinen rivi viimeisestä kahdella kerrottuna: \[ \begin{pmatrix} \underline{1} & 1 & 3 & 3 \\ 0 & \underline{2} & 4 & 2 \\ 0 & 1 & 2 & -2 \end{pmatrix} \] Jaetaan toinen rivi kahdella ja vähennetään se alimmasta rivistä: \[ \begin{pmatrix} \underline{1} & 1 & 3 & 3 \\ 0 & \underline{1} & 2 & 1 \\ 0 & 0 & 0 & -3 \end{pmatrix} \] Yhtälöryhmällä ei ole ratkaisua, koska alin yhtälö on nyt epätosi: \[ 0x_1+0x_2+0x_3\neq -3 \Rightarrow 0\neq -3. \]

Matriisivektoritulon vaihtoehtoiset esitystavat

Matriisi \(\mathbf{A}\) voidaan esittää joukkona indeksoituja alkioita

\[ \underset{m\times n}{\mathbf{A}}= (\alpha_{ij}), \]

missä \( m\) on rivien ja \( n\) sarakkeiden lukumäärä. \( \alpha_{ij}\) on alkio matriisin \(\mathbf{A}\) rivillä \( i\), sarakkeessa \( j\).

Lisäksi \(\mathbf{A}\) voidaan esittää sarakevektoriensa avulla

\[ \underset{m\times n}{\mathbf{A}}=(\mathbf{a}_1 \ \mathbf{a}_2 \ \ldots \ \mathbf{a}_n), \quad \mathbf{a}_i \in \mathbb{R}^m, \quad \forall i \in [1,n], \]

missä \( \mathbf{a}_i\) on \(\mathbf{A}\):n \(i\):s sarakevektori.

Matriisivektoritulo \(\mathbf{Ax=b}\) saa kaksi muotoa:

\[ \text{1.} \quad \underset{m\times 1}{\mathbf{b}}=\sum_{i=1}^{n}x_i \mathbf{a}_i \ \ \text{(Sarakkeiden lineaariyhdistely)} \]

Esimerkki

\[ \begin{align*} \underline{2\times 2}: \begin{pmatrix} \alpha_{11} & \alpha_{12} \\ \alpha_{21} & \alpha_{22} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} & = \begin{pmatrix} \alpha_{11}x_1+\alpha_{12}x_2 \\ \alpha_{21}x_1+\alpha_{22}x_2 \end{pmatrix} \\ & =x_1 \begin{pmatrix} \alpha_{11} \\ \alpha_{21} \end{pmatrix}+x_2 \begin{pmatrix} \alpha_{12} \\ \alpha_{22} \end{pmatrix} =\begin{pmatrix} b_{1} \\ b_{2} \end{pmatrix}. \end{align*} \]
\[ \text{2.} \quad b_i=\sum_{j=1}^{n}\alpha_{ij}x_j, \quad i=1,...,m \quad \text{(rivin } i \text{ ja vektorin } \mathbf{x} \text{ sisätulo)} \]

Esimerkki

\[ \begin{align*} b_1 &= \alpha_{11} x_1 + \alpha_{12} x_2 \\ b_2 &= \alpha_{21} x_1 + \alpha_{22} x_2 \end{align*} \]

Matriisien tulo

Matriisille \(\mathbf{A}\), jolla on \(n\) saraketta, ja matriisille \(\mathbf{B}\), jolla on \(n\) riviä, on määritelty kertolasku seuraavalla tavalla:

\[ \underset{m\times n}{\mathbf{A}} \ \underset{n\times p}{\mathbf{B}}=(\mathbf{Ab}_1 \ \mathbf{Ab}_2 \ldots \mathbf{Ab}_p)=\underset{m\times p}{\mathbf{C}} \]

eli tulosmatriisin \(\mathbf{C}\) sarakkeet muodostuvat matriisivektorikertolaskuista \(\mathbf{Ab}_i \), missä \(\mathbf{b}_i\) on matriisin \(\mathbf{B} \ i\):s sarake, \(i=1,2,...,p\).

Vaihtoehtoisesti voidaan merkitä:

\[ \underset{m\times n}{\mathbf{A}}=(\alpha_{ij}), \quad \underset{n\times p}{\mathbf{B}}=(\beta_{ij}), \quad \underset{m\times p}{\mathbf{C}}=(\gamma_{ij}). \]

Tällöin voidaan matriisikertolasku myös määritellä alkioittain seuraavasti:

\[ \gamma_{ij}=\sum_{k=1}^{n}\alpha_{ik}\beta_{kj}, \quad i \in [1,m], \ j \in [1,p]. \]

Lause: Matriisien tulo on assosiatiivinen \( \mathbf{A(BC)=(AB)C} \), mutta ei vaihdannainen \( \mathbf{AB}\neq \mathbf{BA} \) (yleisesti).

Huomaa! \( (\mathbf{A+B})^2\neq \mathbf{A}^2+2\mathbf{AB}+\mathbf{B}^2\) (yleisesti).

Esimerkki

Olkoot \(\mathbf{A} = \begin{pmatrix} 1 & 2 & 3 & 4 \end{pmatrix}\) ja \(\mathbf{B} = \begin{pmatrix} 1 \\ 2 \\ 3 \\ 4 \end{pmatrix}\). Laske \(\mathbf{AB}\) ja \(\mathbf{BA}\).

Ratkaisu:

\[ \mathbf{AB}=\begin{pmatrix}1 & 2 & 3 & 4 \end{pmatrix}\begin{pmatrix} 1 \\ 2 \\ 3 \\ 4 \end{pmatrix}=30. \]

(Tämän tyyppinen matriisitulo voidaan tulkita vektoreiden \(\mathbf{A}\) ja \(\mathbf{B}\) sisätulona)

\[ \mathbf{BA}=\begin{pmatrix} 1 \\ 2 \\ 3 \\ 4 \end{pmatrix}\begin{pmatrix}1 & 2 & 3 & 4 \end{pmatrix}=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 9 & 12 \\ 4 & 8 & 12 & 16 \end{pmatrix}. \]

(Tämä matriisitulo taasen vastaa vektoreiden \(\mathbf{A}\) ja \(\mathbf{B}\) ulkotuloa)


Permutaatiomatriisi

Permutaatiomatriisi on \(\mathbf{I}\), jossa rivit ovat toisessa järjestyksessä. Permutaatiomatriisilla kertomalla voidaan vaihtaa vektorin komponenttien ja matriisien rivien järjestystä.

Esimerkki

\[ \mathbf{P}_{23}=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix};\quad \mathbf{P}_{23}\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}=\begin{pmatrix} 1 \\ 3 \\ 2 \end{pmatrix} \]

Jos \( \mathbf{P_{23}}\):lla kerrotaan jotain matriisia \(\mathbf{A}\), niin tulomatriisissa \( \mathbf{P}_{23}\mathbf{A}\) rivit 2 ja 3 ovat vaihtaneet paikkaa.

Rotaatiomatriisi

Esimerkki

Etsi rotaatiomatriisi \(\mathbf{R} \in \mathbb{R}^{2\times 2}\), joka kiertää jokaista vektoria \(45^\circ\).

Vihje: Rotaatiomatriisi \(\mathbf{R}\) kuvaa vektorin \(\begin{pmatrix} 1 \\ 0 \end{pmatrix}\) vektorille \(\begin{pmatrix} \frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} \end{pmatrix}\), ja vektorin \(\begin{pmatrix} 0 \\ 1 \end{pmatrix}\) vektorille \(\begin{pmatrix} -\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} \end{pmatrix}\). Näiden avulla saat muodostettua yhtälöt \(\mathbf{R}\):n alkioille.

Ratkaisu:

Olkoon \(\mathbf{R} = \begin{pmatrix} r_{11} & r_{12} \\ r_{21} & r_{22} \end{pmatrix}\). Tällöin annetusta vihjeestä saadaan \[ \mathbf{R} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} r_{11} & r_{12} \\ r_{21} & r_{22} \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} r_{11} \\ r_{21} \end{pmatrix} = \begin{pmatrix} \frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} \end{pmatrix}, \] ja \[ \mathbf{R} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} r_{11} & r_{12} \\ r_{21} & r_{22} \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} r_{12} \\ r_{22} \end{pmatrix} = \begin{pmatrix} -\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} \end{pmatrix}. \]

Siispä saadaan rotaatiomatriisi \[ \mathbf{R} = \begin{pmatrix} \frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{pmatrix}. \]

Senast redigerad: måndag, 9 september 2019, 11:04