LU-hajotelma

Matriisihajotelmat

Usein matriisiyhtälön \(\mathbf{Ax=y}\) ratkaiseminen on epäkäytännöllistä ja hidasta. Siksi numeerisessa matriisilaskennassa usein pyritään esittämään matriisi \(\mathbf{A}\) kahden tai usemman jotakin yksinkertaista muotoa olevan matriisin tulona.

Tällaista esitystä kutsutaan matriisihajotelmaksi. Useimmat suorat (ei-iteratiiviset) menetelmät perustuvat hajotelmien käyttöön.

Hajotelma helpottaa matriisiyhtälön ratkaisemista ja saattaa myös antaa käyttökelpoista tietoa itse matriisista.

Matriisihajotelmia on monia erilaisia, koska eri tilanteissa tarvitaan eri hajotelmia.

Matriisihajotelmia ei yleensä kannata laskea käsin, mutta niitä löytyy valmiiksi implementoituna eri laskentaohjelmistoista ja -kirjastoista.

LU-hajotelma

Tarkastellaan yhtälöryhmän \(\mathbf{Ax=y} \) ratkaisemista, kun \( \mathbf{A}\in \mathbb{R}^{n\times n}\) on yläkolmiomatriisi, eli \(a_{jk}= 0\), kun \(j>k\).

Tällöin siis matriisiyhtälöä \(\mathbf{Ax=y}\) vastaa yhtälöryhmä

\[ \left\{\begin{array}{rcl} a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n &=& y_1,\\ a_{22}x_2+\ldots+a_{2n}x_n &=& y_2,\\ \vdots & \vdots & \vdots\\ a_{nn}x_n &=& y_n. \end{array}\right. \]

Tällöin tuntemattomat \( x_1,\ldots,x_n\) voidaan ratkaista takaisinsijoituksella.

Esimerkki

Olkoot

\[ \mathbf{A} =\begin{pmatrix} 1 & -2 & 1 \\ 0 & 4 & 2 \\ 0 & 0 & -2 \end{pmatrix}, \quad \mathbf{y}=\begin{pmatrix} 0 \\ 16 \\ 4 \end{pmatrix} \] Tällöin \[ \mathbf{Ax=y} \quad \Leftrightarrow \quad \left\{\begin{array}{rcl} x_1 -2x_2 + x_3 &=& 0,\\ 4x_2+2x_3 &=& 16,\\ -2x_3&=&4. \end{array}\right. \] Saadaan \(x_3=-2\), eli \(x_2=\frac{1}{4}(16-2x_3)=5\), ja \(x_1=2x_2-x_3=12\).

Ratkaisu on siis \(x = (12,5,-2)\).


Edellisen esimerkin menettelyä voidaan soveltaa yleisesti:

\[ x_n = \frac{y_n}{a_{nn}},\textrm{ ja }x_j = \frac{1}{a_{jj}}\Big(y_j -\sum_{k=j+1}^n a_{jk}x_j\Big). \]

Matriisiyhtälön ratkaisemisen kannalta on siis edullista, jos matriisi \(\mathbf{A}\) saadaan muutettua yläkolmiomuotoon (tai alakolmiomuotoon).

Tästä päädytään LU-hajotelmaan : Jos \(\mathbf{A}\in \mathbb{R}^{n\times n}\), niin etsitään sellaiset matriisit \(\mathbf{L,U}\in \mathbb{R}^{n\times n}\) , että

  1. \( \mathbf{L} \) on alakolmio- ja \( \mathbf{U}\) on yläkolmiomatriisi, ja
  2. \( \mathbf{A=LU}\).

Tällöin yhtälö \(\mathbf{Ax=y}\) voidaan ratkaista ratkaisemalla kaksi kolmiomatriisiyhtälöä

\[ \left\{\begin{array}{rcl} \mathbf{Lz} &=& \mathbf{y},\\ \mathbf{Ux} &=& \mathbf{z},\end{array}\right. \textrm{ eli } \mathbf{Ax} = \mathbf{LUx} = \mathbf{Lz=y}. \]

Molemmat yhtälöt voidaan ratkaista takaisinsijoituksella: Ensin ratkaistaan \( \mathbf{z}\) yhtälöstä \(\mathbf{Lz=y} \) ja sitten \(\mathbf{x} \) yhtälöstä \(\mathbf{Ux=z} \).

Seuraavaksi tutkitaan miten hajotelma \( \mathbf{A}=\mathbf{LU}\) voidaan löytää nk. Doolittlen algoritmia käyttäen.

Selvitetään aluksi tuntemattomien määrä. Matriisit \(\mathbf{L}\) ja \(\mathbf{U}\) ovat

\[ \mathbf{L} = \begin{pmatrix} l_{11} & 0 & \cdots & 0 \\ l_{21} & l_{22} &\cdots & 0 \\ \vdots & &\ddots & \vdots \\ l_{n1} & l_{n2} & \cdots & l_{nn}, \end{pmatrix} \qquad \mathbf{U} = \begin{pmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} &\cdots & u_{2n} \\ \vdots & &\ddots & \vdots \\ 0 & 0 & \cdots & u_{nn}. \end{pmatrix} \]

Siten matriisiin \(\mathbf{L}\) liittyvien tuntemattomien määrä on \(n(n+1)/2\) ja samoin matriisiin \(\mathbf{U}\) liittyvien. Yhteensä tehtävässä siis on \(n^2+n\) tuntematonta.

Koska matriisissa \(\mathbf{A}\) on vain \(n^2\) alkiota, voidaan \(\mathbf{L}\):n tai \(\mathbf{U}\):n alkioista \(n\) kappaletta valita vapaasti.

Järkevintä on valita jomman kumman matriisin diagonaalialkiot ykkösiksi. Jos

  1. \(l_{11}=\ldots = l_{nn}=1\), niin saadaan Doolittlen algoritmi, ja jos
  2. \(u_{11}=\ldots= u_{nn}=1\), saadaan Croutin algoritmi.
Lisähuomioita*
  • Jos valitaan \(l_{11}=\ldots = l_{nn}=1\), niin \(\det(\mathbf{L})=1\), koska kolmiomatriisin determinantti saadaan diagonaalialkioiden tulosta (ks. determinantin määritelmä osiosta viisi).
  • Jos \(\mathbf{A}\) on neliömatriisi, niin silloin pätee myös \(\det(\mathbf{A}) = \det(\mathbf{LU}) = \det(\mathbf{L})\det(\mathbf{U}) = 1\cdot\det(\mathbf{U}) = \det(\mathbf{U})\).
  • Lisäksi, \(\mathbf{A}\) on kääntyvä, jos ja vain jos \(\det(\mathbf{A})\neq 0\), mistä seuraa, että \(\det(\mathbf{U})\neq 0\).
  • Siten kääntyvälle matriisille \(\mathbf{A}\) myös sen yläkolmiokomponentti \(\mathbf{U}\) on kääntyvä eli \(\mathbf{U} \):n diagonaalialkiot ovat nollasta poikkeavia (koska determinatti on diagonaalialkioiden tulo).

Esimerkki

Muodostetaan matriisin \(\mathbf{A}\) LU-hajotelma Doolittlen menetelmällä, kun

\[ \mathbf{A} = \begin{pmatrix}3 & 5 & 2\\ 0 & 8 & 2 \\ 6 & 2 & 8 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{pmatrix} \begin{pmatrix}u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23}\\ 0 & 0 & u_{33} \end{pmatrix}. \]

Ensimmäisellä rivillä saadaan heti \(u_{11} =3\), \(u_{12} = 5\) ja \(u_{13}=2\). Toisella rivillä \(l_{21}u_{11} =0\), joten \(l_{21}=0\) (koska \(u_{11}\neq 0\)). Edelleen, \(l_{21}u_{12}+ u_{22} =8\), joten \(u_{22}=8\) (koska \(l_{21}= 0\)).

Saadaan myös \(l_{21}u_{13}+ u_{23} =2\), ja siis \(u_{23}=2\) (koska \(l_{21}= 0\)). Samaan tapaan kolmannella rivillä \(l_{31}u_{11} = 6\) ja siis \(l_{31}=2\) (koska \(u_{11}=3\)).

Koska \(l_{31}=2\), \(u_{12}=5\) ja \(u_{22}=8\), saadaan yhtälöstä \(l_{31}u_{12}+l_{32}u_{22}=2\) ratkaistua \(l_{32}=-1\).

Lopuksi sijoittamalla saadut arvot yhtälöön \(l_{31}u_{13} + l_{32}u_{23}+u_{33}=8\) saadaan \(u_{33}=6\).

Saadaan siis esitys

\[ \mathbf{A} = \mathbf{L}\mathbf{U} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & -1 & 1 \end{pmatrix} \begin{pmatrix} 3 & 5 & 2\\ 0 & 8 & 2 \\ 0 & 0 & 6 \end{pmatrix}. \]

Yleinen algoritmi toimii samaan tapaan, eli ratkaistaan \(\mathbf{A}\):n alkioista muodostuvat yhtälöt järjestyksessä \(a_{11}, a_{12},\ldots,a_{1n},a_{21},\ldots,a_{nn}\).

Huomautuksia

Algoritmi katkeaa, jos \(\mathbf{U}\):n diagonaalille ilmestyy nollia.

LU-hajotelmaa voidaan käyttää myös ei-kääntyville matriiseille.

Ei-neliömatriisin \(\mathbf{A}\in \mathbb{R}^{m\times n}\) LU-hajotelmassa

\[ \mathbf{L} = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ l_{21} & 1 & \cdots & 0 \\ \vdots & & \ddots & \vdots \\ l_{m1} & l_{m2} & \cdots & 1 \end{pmatrix}\in \mathbb{R}^{m\times m} \]
on alakolmiomatriisi.

Yläkolmiomatriisi on muotoa

\[ \mathbf{U} = \begin{pmatrix} u_{11} & u_{12} & u_{13} && \cdots & u_{1n} \\ 0 & u_{22} & u_{23} & &\cdots & u_{2n} \\ 0 & 0 & \ddots & & &\vdots \\ 0 & \cdots & 0 & u_{mm} & \cdots & u_{mn} \end{pmatrix} \in \mathbb{R}^{m\times n}. \]

Esimerkki

Kaikilla matriiseilla ei ole LU-hajotelmaa. Yritetään muodostaa hajotelma matriisille:

\[ \mathbf{A} = \begin{pmatrix} 0 & 1\\ -1 & 0 \end{pmatrix} = \begin{pmatrix} a & 0 \\ b & c \end{pmatrix} \begin{pmatrix} d & e \\ 0 & f \end{pmatrix}. \]

Tällöin \(ad=0\) ja siten \(a=0\) tai \(d=0\).

Lisäksi \(ae=1\), joten \(a\neq 0\), ja \(bd=-1\), joten \(d\neq 0\).

Nämä kolme ehtoa eivät voi olla samaan aikaan voimassa.

Hajotelma voidaan kuitenkin löytää vaihtamalla rivien järjestystä (ks. \(\mathbf{PA=LU}\) -hajotelma alempaa).


Esimerkki

Ratkaise \( \mathbf{Ax=y}\) LU-hajotelmaa käyttäen, kun

\[ \mathbf{A}=\begin{pmatrix} 3 & -7 & -2 \\ -3 & 5 & 1 \\ 6 & -4 & 0 \end{pmatrix}, \quad \mathbf{b}=\begin{pmatrix} -7 \\ 5 \\ 2 \end{pmatrix}. \]

Ratkaisu:

Ratkaistaan ensin yläkolmiomatriisi:

\[ \begin{pmatrix} 3 & -7 & -2 \\ -3 & 5 & 1 \\ 6 & -4 & 0 \end{pmatrix} \] Lisätään ylin rivi keskimmäiseen riviin: \[ \begin{pmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 6 & -4 & 0 \end{pmatrix} \] Kerrotaan ylin rivi 2:lla ja vähennetään se alimmasta rivistä: \[ \begin{pmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 10 & 4 \end{pmatrix} \] Kerrotaan keskimmäinen rivi 5:llä ja lisätään se alimpaan riviin: \[ \begin{pmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 0 & -1 \end{pmatrix} \] Saatu tulos on kysytty yläkolmiomatriisi, eli \[ \mathbf{U}= \begin{pmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 0 & -1 \end{pmatrix} \] Alakolmiomatriisi saadaan kirjoittamalla yllä olevien vaiheiden kertoimet identiteettimatriisin kohtiin, joita kyseinen kerroin eliminoi vähennyslaskulla nollaksi: \[ \mathbf{L}=\begin{pmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{pmatrix} \] LU-hajotelmaksi saadaan siis \[ \mathbf{LU}=\begin{pmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{pmatrix}\begin{pmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 0 & -1 \end{pmatrix} \] Ratkaistaan yhtälö \( \mathbf{Ax=b}\) LU-hajotelmaa käyttäen:

Merkitään, että \( \mathbf{y}=\mathbf{Ux}\), eli \( \mathbf{Ax}=\mathbf{LUx}=\mathbf{Ly}=\mathbf{b}\).

Ratkaistaan ensin \( \mathbf{y}\) siten, että

\[ \mathbf{Ly}=\mathbf{b} \] \[ \begin{pmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{pmatrix}\begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix}=\begin{pmatrix} -7 \\ 5 \\ 2 \end{pmatrix} \] Ratkaistaan \( y_1,y_2,y_3\): \begin{align*} y_1 & = -7, \\ -y_1+y_2 & =5 \Rightarrow y_2=2, \\ 2y_1-5y_2+y_3 & = 2 \Rightarrow y_3=6. \end{align*} Ratkaisuksi saadaan \[ \mathbf{y}=\begin{pmatrix} -7 \\ -2 \\ 6 \end{pmatrix}. \] Sitten ratkaistaan yhtälö \( \mathbf{y}=\mathbf{Ux}\): \[ \begin{pmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 0 & -1 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}=\begin{pmatrix} -7 \\ -2 \\ 6 \end{pmatrix} \] Ratkaistaan \( x_1,x_2,x_3\): \begin{align*} x_ 3 & = -6 \\ -2x_2-x_3 & = -2 \Rightarrow x_2=4 \\ x_1-7x_2-2x_3 & = -7 \Rightarrow x_1=3 \end{align*} Ratkaisuksi saadaan \[ \mathbf{x}=\begin{pmatrix} 3 \\ 4 \\ -6 \end{pmatrix}. \] Voidaan tarkistaa laskemalla: \[ \mathbf{Ax}=\begin{pmatrix} 3 & -7 & -2 \\ -3 & 5 & 1 \\ 6 & -4 & 0 \end{pmatrix}\begin{pmatrix} 3 \\ 4 \\ -6 \end{pmatrix}=\begin{pmatrix} -7 \\ 5 \\ 2 \end{pmatrix}=\mathbf{b}. \]

Esimerkki

Etsi (jos mahdollista) matriisin

\[ \mathbf{A}=\begin{pmatrix} 1 & 2 & 4 \\ 3 & 8 & 14 \\ 6 & 6 & 13 \end{pmatrix} \] LU-hajotelma.

Ratkaisu:

Ratkaistaan ensin yläkolmiomatriisi \( \mathbf{U}\). Vähennetään ylin rivi keskimmäisestä 3:lla kerottuna ja alimmasta 6:lla kerrottuna:

\[ \begin{pmatrix} 1 & 2 & 4 \\ 0 & 2 & 2 \\ 0 & -6 & -11 \end{pmatrix} \] Vähennetään keskimmäinen rivi alemmasta -3:lla kerrottuna: \[ \mathbf{U}=\begin{pmatrix} 1 & 2 & 4 \\ 0 & 2 & 2 \\ 0 & 0 & -5 \end{pmatrix} \] Alakolmiomatriisi \( \mathbf{L}\) saadaan kirjoittamalla yllä olevien vaiheiden kertoimet identiteettimatriisin kohtiin, joita kyseinen kerroin eliminoi vähennyslaskulla nollaksi: \[ \mathbf{L}=\begin{pmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 6 & -3 & 1 \end{pmatrix}. \] Siten \[ \mathbf{A}=\mathbf{LU}=\begin{pmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 6 & -3 & 1 \end{pmatrix}\begin{pmatrix} 1 & 2 & 4 \\ 0 & 2 & 2 \\ 0 & 0 & -5 \end{pmatrix}. \]

PA=LU -hajotelma*

LU-hajotelman jatke, jossa \(\mathbf{A}\):n rivien järjestystä muutetaan eli sitä kerrotaan ensin permutaatiomatriisilla \(\mathbf{P}\) (kertaa permutaatiomatriisit tarvittaessa osiosta 2).

Esimerkki

\[ \begin{pmatrix} 0 & 1 & 1 \\ 1 & 2 & 1 \\ 2 & 7 & 9 \end{pmatrix} \] Vaihdetaan ensimmäisen ja toisen rivin paikkaa: \[ \begin{pmatrix} \underline{1} & 2 & 1 \\ 0 & \underline{1} & 1 \\ 2 & 7 & 9 \end{pmatrix} \] Kerrotaan ensimmäinen rivi 2:lla ja vähennetään se kolmannesta rivistä: \[ \begin{pmatrix} \underline{1} & 2 & 1 \\ 0 & \underline{1} & 1 \\ 0 & 3 & 7 \end{pmatrix} \] Kerrotaan toinen rivi 3:lla ja vähennetään se kolmannesta rivistä. Saadaan \[ \mathbf{LU}=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 3 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 4 \end{pmatrix}=\mathbf{PA}, \quad \mathbf{P}= \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}. \]

Hajotelma \( \mathbf{PA=LU}\) on olemassa kaikille säännöllisille matriiseille.

Last modified: Monday, 23 October 2017, 4:11 PM