Yfirlit

• Margföldun fylkja og vigra
• Línuleg jöfnuhneppi
• Línuleg föll
• Margföldun fylkja
• QR-þáttun

Margföldun fylkja og vigra

Fyrir \(m\times n\) fylki \(A\) og \(n\)-vigur \(x\) skilgreinum við fylkjamargföldunina \(y=Ax\) sem

\[y_i = A_{i,1}x_1 + \ldots + A_{i,n}x_n, \quad i=1,\ldots,m\]

• Ef \(A\) hefur raðirnar \(b_1^T,\ldots,b_m^T\) þá er \[y_i = b_i^Tx\]

• \(y=Ax\) er í raun mörg innfeldi á milli raða \(A\) og vigursins \(x\)

Dálktúlkun

\(y=Ax\) má skrifa sem

\[ y = x_1a_1 + x_2a_2 + \ldots + x_na_n \] þar sem \(a_1,\ldots,a_n\) eru dálkar \(A\).

• \(y=Ax\) er línuleg samantekt af dálkum \(A\) með stuðlana \(x_1,\ldots,x_n\).
• mikilvægt dæmi: \(Ae_j = a_j\)
• dálkar \(A\) eru línulega óháðir ef \(Ax=0\) leiðir til þess að \(x=0\).

Varpanir

• Margar varpanir í tví- og þrívídd er hægt að setja fram sem margföldun \(y = Ax\)
• Snúningur um hornið \(\theta\) \[ y = \begin{bmatrix}\cos(\theta) & -\sin(\theta) \\ \sin(\theta) & -\cos(\theta)\end{bmatrix} x \]
• snúningur í þrívídd um vigur er mun flóknari

Línuleg föll

Útvíkkum skilgreininguna á línulegum föllum til að leyfa niðurstöðunni að vera vigur

\(f: \mathbf{R}^n \to \mathbf{R}^m\) er vörpun/fall frá \(n\)-vigrum til \(m\)-vigra.

• skrifum \(f(x) = (f_1(x),\ldots,f_m(x))\) til að lýsa stökunum í útkomunni \(f(x)\)
• skrifum \(f(x_1,\ldots,x_n)\) til að lýsa stökunum í inntakinu \(x\)
• fallið \(f\) er línulegt ef fyrir öll \(x,y,\alpha,\beta\) gildir \[ f(\alpha x + \beta y) = \alpha f(x) + \beta f(y) \]
• jafngildir því að öll föllin \(f_1,\ldots,f_m\) eru línuleg

Ef \(A\) er \(m\times n\) fylki skilgreinum við \(f\) sem \(f(x) = Ax\)

• Öll slík föll, \(f\), eru línuleg
• Ef \(f\) er eitthvert línulegt fall \(f: \mathbf{R}^n \to \mathbf{R}^m\), þá er til \(m\times n\) fylki \(A\) þ.a. \(f(x) = Ax\)

• \(f(x) = x_1f(e_1) + \ldots + x_nf(e_n)\) svo að \[ A = \begin{bmatrix}f(e_1) & f(e_2) & \cdots & f(e_n)\end{bmatrix} \]

• þ.e. dálkur \(i\) í \(A\) er fenginn með því að reikna út \(f(e_1)\)

Línuleg jöfnuhneppi

mengi af \(m\) línulegum jöfnum í \(n\) breytum \(x_1,\ldots,x_n\)

\[ \begin{aligned} A_{11} x_1 + A_{12}x_2 + \ldots + A_{1n}x_n &= b_1\\ A_{21} x_1 + A_{22}x_2 + \ldots + A_{2n}x_n &= b_2\\ &\vdots\\ A_{m1} x_1 + A_{m2}x_2 + \ldots + A_{mn}x_n &= b_m\\ \end{aligned} \]

• \(n\)-vigurinn \(x\) eru óþekktu stærðirnar
• \(A_{i,j}\) eru stuðlarnir og \(A\) er stuðlafylkið
• \(b\), \(m\)-vigurinn er kallaður "hægri hliðin"
• Táknað sem \(Ax=b\)

Línuleg jöfnuhneppi

Línulega jöfnuhneppið \(Ax=b\) þar sem \(A\) er \(m\times n\) fylki, \(b\) er \(m\)-vigur og \(x\) er \(n\)-vigur er kallað

• vanákvarðað ef \(m < n\) (A er breitt)
• ferningslaga ef \(m=n\) (A ferningslaga)
• ofákvarðað ef \(m > n\) (A er mjótt)
• \(x\) er kallað lausn ef það uppfyllir \(Ax=b\)

• Það er háð \(A\) og \(b\) hvort til sé

  • engin lausn
  • nákvæmlega ein lausn
  • óendanlega margar lausnir

Hvert erum við að fara?

• Fylkjamargföldun gefur okkur knappan rithátt til að tala um línuleg jöfnuhneppi og margar aðrar aðgerðir
• Þurfum að geta sett fram og leyst línuleg jöfnuhneppi
• Aðhvarfsgreining er leyst með línulegum jöfnuhneppum
• Aðferði minnstu fervika er notuð til að aðlaga gögn að ferlum

Fylkjamargföldun

Ef \(A\) er \(m\times p\) fylki og \(B\) er \(p\times n\) fylki þá er margfeldið \(C=AB\) skilgreint sem \(m\times n\) fylkið

\[ C_{i,j} = \sum_{k=1}^p A_{i,k}B_{k,j} = A_{i,1}B_{1,j} + A_{i,2}B_{2,j} + \ldots + A_{i,p}B_{p,j} \]

Til að fá \(C_{i,j}\) notum við \(i\)-tu röðina í \(A\) og \(j\)-ta dálk í \(B\)

Sértilfelli

• tala sinnum vektor, vektor er \(n\times 1\) fylki og tala er \(1\times 1\) fylki
• innfeldi af \(n\)-vigrum, \(a^Tb\), \(a^T\) er \(1\times n\) fylki og \(b\) er \(n\times 1\) fylki, niðurstaðan er \(1\times 1\) fylki eða tala
• Fylki sinnum vigur, \(Ax\)
• Ytra margfeldi fyrir vigra

\[ ab^T = \begin{bmatrix}a_1b_1 & a_1b_2 & \cdots & a_1b_n\\ a_2b_1 & a_2b_2 & \cdots & a_2b_n\\ \vdots & \vdots & & \vdots\\ a_nb_1 & a_nb_2 & \cdots & a_nb_n\\ \end{bmatrix} \]

Eiginleikar

• \((AB)C = A(BC)\), skrifum því bara \(ABC\)
• \(A(B+C) = AB + AC\)
• \((AB)^T = B^TA^T\)
• \(AI = A\) og \(IA = A\), munið að \(I\) er einingafylkið með \(1\) á hornalínunni
• \(AB = BA\) gildir ekki nema í undantekningartilvikum!

Dálkaframsetning

Skrifum \(B = \begin{bmatrix}b_1 & b_2 & \cdots & b_n\end{bmatrix}\), þ.e. \(b_i\) er \(i\)-ti dálkur \(B\).

Þá gildir

\[ AB = A \begin{bmatrix}b_1 & b_2 & \cdots & b_n\end{bmatrix} = \begin{bmatrix}Ab_1 & Ab_2 & \cdots & Ab_n\end{bmatrix} \]

Dálkarnir í \(AB\) fást með því að margfalda A með dálkunum í \(B\).

Innfeldisframsetning

Ef \(a_i^T\) eru raðirnar í \(A\) og \(b_j\) eru dálkarnir í \(B\) þá getum við skrifað

\[ AB = \begin{bmatrix} a_1^Tb_1 & a_1^Tb_2 & \cdots & a_1^Tb_n\\ a_2^Tb_1 & a_2^Tb_2 & \cdots & a_2^Tb_n\\ \vdots & \vdots & & \vdots\\ a_m^Tb_1 & a_m^Tb_2 & \cdots & a_m^Tb_n \end{bmatrix} \]

Flækjustig

Til að reikna út fylkjamargfeldið þarf ca. \(mnp\) aðgerðir

• \(C_{i,j} = AB_{i,j}\) er innfeldi af tveimur \(p\)-dálkum
• Þarf \((mn)2p = 2nmp\) reikniaðgerðir
• Margföldun tveggja \(1000\times 1000\) fylkja þarf ca \(2\cdot10^9\) aðgerðir
• tekur ca. 1 sekúndu á nútímatölvum.

Samskeyting línulegra falla

• \(A\) er \(m\times p\) og \(B\) er \(p\times n\) fylki
• Skilgreinum \(f(y) = Ay\) og \(g(x) = Bx\)
• \(f\) og \(g\) eru línuleg föll
• samskeytingin \(h(x) = f(g(x))\) er líka línuleg
• við höfum \[ h(x) = f(g(x)) = A(Bx) = (AB)x \]
• svo fylkið fyrir samskeytinguna er margfeldið af fylkjunum

Veldi af fylkjum

Fyrir ferningslaga fylki \(A\) skilgreinum við \(A^2 = AA\) og svipað fyrir hærri veldi

• \(A^0 = I\) skv. skilgreiningu og
• \(A^{k+1} = A^{k}A\) fyrir \(k\ge 0\)
• \(A^{k}A^l = A^{k+l}\)
• Neikvæð veldi koma seinna (ef þau eru til)

Hornréttir dálkar

Ef \(Q\) er \(n\times n\) fylki með innbyrðis hornrétta dálka \(q_i\), þá er

\[ \begin{aligned} Q^TQ &= \begin{bmatrix} q_1^Tq_1 & q_1^Tq_2 & \cdots & q_1^Tq_n\\ q_2^Tq_1 & q_2^Tq_2 & \cdots & q_2^Tq_n\\ \vdots & \vdots & & \vdots\\ q_n^Tq_1 & q_n^Tq_2 & \cdots & q_n^Tq_n \end{bmatrix}\\ &= diag(||q_1||^2,||q_2||^2,\ldots,||q_n||^2) \end{aligned} \]

Ef dálkarnir eru staðlaðir \(||q_i||=1\) þá verður þetta einingafylkið.

Gram-fylki

Fyrir \(m\times n\) fylki \(A\) skilgreinum við Gram-fylkið

\[ G = A^TA = \begin{bmatrix} a_1^Ta_1 & a_1^Ta_2 & \cdots & a_1^Ta_n\\ a_2^Ta_1 & a_2^Ta_2 & \cdots & a_2^Ta_n\\ \vdots & \vdots & & \vdots\\ a_n^Ta_1 & a_n^Ta_2 & \cdots & a_n^Ta_n \end{bmatrix} \]

• Gram fylkið gefur öll innfeldi af pörum af dálkum í \(A\)
• \(A^TA = I\) þýðir að dálkarnir eru þverstaðlaðir
• Dálkarnir í Hadamard fylkjunum eru þverstæðir.

QR þáttun

Látum \(A\) vera \(n\times k\) fylki með dálkana \(a_{i}\). Keyrum Gram-Schmidt reikniritið

• ef dálkarnir eru óháðir þá fáum við \(q_{1},\ldots,q_k\) þverstaðlaða dálka
• skilgreinum \(n\times k\) fylkið \(Q\) með dálka \(q_1,\ldots,q_k\)
• \(Q^TQ = I\)
• Úr Gram-Schmidt reikniritinu fæst

\[ \begin{aligned} a_i &= (q_1^Ta_i)q_i + \ldots + (q_{i-1}^Ta_i)q_{i-1} + ||\tilde{q_i}|| q_i\\ &= R_{1,i}q_1 + \ldots R_{i-1,i}q_{i-1} + R_{i,i}q_i \end{aligned} \]

þar sem \(R_{i,j} = q_i^Ta_j\) fyrir \(i < j\), \(R_{i,i} = ||\tilde{q_i}||\) og \(R_{i,j} = 0\) fyrir \(i > j\).

QR þáttun

• Ef dálkarnir í \(A\) eru línulega óháðir
• Getum skrifað \(A = QR\)
• \(Q\) er með þverstaðlaða dálka
• \(R\) er efra þríhyrningsfylki með jákvæð gildi á hornalínunni.
• \(A=QR\) er kallað QR-þáttun á fylkinu \(A\)
• Hægt að útvíkka fyrir dálka sem eru ekki línulega óháðir.

Andhverfur

• Tala \(x\) sem uppfyllir jöfnuna \(xa = 1\) er kölluð (margföldunar)andhverfa \(a\)
• andhverfan er bara til ef \(a\neq 0\) og þá er hún einstök
• Fylki \(X\) sem uppfyllir \(XA = I\) er kallað vinstri andhverfa \(A\) (og \(A\) er sagt vinstra andhverfanlegt)
• Fylkið \[ A = \begin{bmatrix} -3 & -4 \\ 4 & 6 \\ 1 & 1 \end{bmatrix} \] hefur tvær ólíkar vinstri andhverfur \[ B = \frac{1}{9}\begin{bmatrix} -11 & -10 & 16 \\ 7 & 8 & -11 \end{bmatrix} \] og \[ C = \frac{1}{2}\begin{bmatrix} 0 & -1 & 6\\ 0 & 1 & -4\end{bmatrix} \]

Ef fylkið \(A\) hefur vinstri andhverfu \(C\) þá eru dálkar \(A\) óháðir

• Ef \(Ax = 0\) og \(CA = I\) þá er

\[ 0 = C0 = C(Ax) = (CA)x = Ix = x \]

• hin áttin er líka sönn, ef \(A\) hefur línulega óháða dálka þá hefur það vinstri andhverfu.

• Vinstra andhverfanleg fylki eru ferningslaga eða mjó (þ.e. fjöldi raða \(\ge\) fjöldi dálka)

Skoðum jöfnuna \(Ax = b\) og \(A\) hefur vinstri andhverfuna \(C\). Ef jafnan hefur lausn \(x\) þá er \[ Cb = C(Ax) = (CA)x = Ix = x \] lausn á jöfnunni.

Lausnin fæst með því að margfalda báðar hliðar vinstra megin og athuga hvort hún sé lausn með því að stinga inn í jöfnuna.

Þar sem \(A\) er mjótt fylki gæti verið að engin lausn sé til.

Hægri andhverfur

Eru skilgreindar á sama hátt

• Fylki \(X\) sem uppfyllir \(AX=I\) er hægri andhverfa \(A\)
• \(A\) er hægra andhverfanlegt þþaa \(A^T\) er vinstra andhverfanlegt

\[ AX=I \iff (AX)^T = I^T \iff X^TA^T = I \]

• Fylki \(A\) er hægra andhverfanlegt þþaa raðirnar eru línulega óháðar

Lausn jöfnuhneppa

Ef \(A\) hefur hægri andhverfu \(B\) og skoðum jöfnuna \(Ax=b\). Þar sem \(A\) hefur hægri andhverfu þá er alltaf til lausn og ein slík lausn er \(x = Bb\). Stingum þessu inn og sjáum

\[ A(Bb) = (AB)b = Ib = b \]

Andhverfur

• Ef \(A\) hefur hægri og vinstri andhverfu þá eru þær einstakar og jafnar og við segjum að \(A\) er andhverfanlegt fylki
• \(A\) verður að vera ferningsfylki
• Ef \(X\) er hægri andhverfa og \(Y\) vinstri þá gildir \(AX = I\), \(YA = I\) og \[ X = IX = (YA)X = Y(AX) = YI = Y \]
• Andhverfan, ef hún er til, er táknuð með \(A^{-1}\), \(A^{-1}A = AA^{-1} = I\)
• \((A^{-1})^{-1} = A\)

Lausn ferningslaga jöfnuhneppa

Ef \(A\) er andhverfanlegt og við skoðum jöfnuna \(Ax=b\)

• Þá er lausnin \(x = A^{-1}b\)
• Það er bara ein lausn til
• útvíkkuna á einföldu jöfnunni \(ax=b\) með tölum (\(1\times 1\) fylki) með lausnina \(x = a^{-1}b\)

Andhverfanleg fylki

Eftirfarandi skilyrði eru jafngild fyrir ferningslaga fylki \(A\)

• \(A\) er andhverfanlegt
• dálkar \(A\) eru óháðir
• raðir \(A\) eru óháðar
• \(A\) hefur vinstri andhverfu
• \(A\) hefur hægri andhverfu

Dæmi

• \(I^{-1} = I\)
• ef \(Q\) er þverstaðlað, þ.e. \(Q^TQ = I\) þá er \(Q^{-1} = Q^T\)
• \(2\times 2\) fylki \(A\) hefur andhverfu þþaa \(A_{1,1}A_{2,2} \neq A_{1,2}A_{2,1}\) og \[ A^{-1} = \frac{1}{A_{1,1}A_{2,2} - A_{1,2}A_{2,1}} \begin{bmatrix}A_{2,2} & -A_{1,2} \\ -A_{2,1} & A_11\end{bmatrix} \]
• góð formúla til að muna
• svipaðar formúlur fyrir stærri fylki en mun flóknari

Eiginleikar

Ef \(A\) og \(B\) eru \(n\times n\) andhverfanleg fylki þá gildir

• \((AB)^{-1} = B^{-1}A^{-1}\)
• \((A^T)^{-1} = (A^{-1})^T\), stundum táknað \(A^{-T}\)
• neikvæð veldi, \((A^{-1})^k\) er táknað \(A^{-k}\)
• með \(A^0 = I\) þá gildir \(A^{k}A^{l} = A^{k+l}\) fyrir allar heiltölur

Þríhyrningsfylki

Efri þríhyrningsfylki eru andhverfanleg þþaa það er ekki \(0\) á hornalínunni. Þurfum bara að sýna að dálkarnir eru línulega óháðir, þ.e. jafnan \(Rx=0\) hefur bara lausnina \(x=0\).

\[ \begin{aligned} R_{1,1}x_1 + R_{1,2}x_2 + \ldots + R_{1,n}x_n &= 0\\ &\vdots\\ R_{n-1,n-1}x_{n-1}+ R_{n-1,n}x_n &= 0\\ R_{n,n}x_n = 0 \end{aligned} \]

Síðasta jafnan \(R_{n,n}x_n = 0\) gefur \(x_n =0\), því \(R_{n,n} \neq 0\). Stingum inn í jöfnuna og fáum eins, minna þríhyrningalaga fylki. Eina lausnin verður \(x_n = x_{n-1} = \ldots x_1 = 0\)

Fyrir næstu viku

Lesa kafla 11.3-5 (lausn jöfnuhneppa og gerviandhverfur) og kafla 12 um aðferð minnstu fervika