Yfirlit

• QR þáttun
• andhverfur
• lausnir línulegra jöfnuhneppa

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

Endurinnsetning

Aðferðin við að leysa efri þríhyrningsfylki er kölluð endurinnsetning (e. back substitution) og framinnsetning fyrir neðri þríhyrningsfylki.

• Reiknar lausnina \(x = R^{-1}b\)
• Flækjustig ca. \(n^2\) skref.

Lausn með QR þáttun

Gerum ráð fyrir að \(A\) er andhverfanlegt. Við leysum \(Ax=b\), þ.e. reiknum \(x=A^{-1}b\).

• dálkarnir eru línulega óháðir svo QR-þáttun er til
• \(A = QR\)
• \(Q\) er þverstaðlað svo \(Q^{-1} = Q^T\)
• \(R\) er efra þríhyrningsfylki með jákvæðar tölur á hornalínu og er því andhverfanlegt
• þá er \(A^{-1} = (QR)^{-1} = R^{-1}Q^T\)
• Reiknum því \(x=R^{-1}(Q^Tb)\) með endurinnsetningu.

Flækjustig

Gefið \(n\times n\) andhverfanlegt fylki \(A\) og \(n\)-vigur \(b\)

1. Finnum QR-þáttun \(A = QR\)
2. Reiknum \(Q^Tb\)
3. Leysum jöfnuna \(Rx=Q^Tb\) með endurinnsetningu

• Flækjustig er \(2n^3 + 2n^2 + n^2 ~ 2n^3\)
• QR-þáttunin er allsráðandi
• Fyrir margar jöfnur með sama \(A\) fylki en mismunandi \(b\) vigra getum við endurnýtt QR-þáttunina og sparað tíma.

Margliðubrúun

Finnum þriðja stigs margliðu \[p(x) = c_1 + c_2x + c_3x^2 + c_4x^3\]

sem uppfyllir

\[ p(-1.1) = b_1,\quad p(-0.4) = b_2,\quad p(0.1) = b_3,\quad p(0.8) = b_4\]

Skrifum sem \(Ac = b\) með

\[ A = \begin{bmatrix} 1 & -1.1 & (-1.1)^2 & (-1.1)^3\\ 1 & -0.4 & (-0.4)^2 & (-0.4)^3\\ 1 & 0.1 & (0.1)^2 & (-0.1)^3\\ 1 & 0.8 & (0.8)^2 & (-0.8)^3 \end{bmatrix} \]

Andhverfanleiki Gram Fylkja

Látum \(A\) vera \(m\times n\) fylki. Rifjum upp að Gram fylki \(A\) er \(n\times n\) fylkið \(A^TA\).

\(A\) hefur óháða dálka þþaa \(A^TA\) er andhverfanlegt

Til að sýna þetta er nóg að sýna að \(Ax=0 \iff A^TAx=0\)

• Ef \(Ax=0\) þá er \((A^TA)x = A^T(Ax) = A^T0 = 0\)
• Ef \((A^TA)x = 0\) þá er \[ 0 = x^T0 = x^T(A^TA)x = (x^TA^T)(Ax) = (Ax)^T(Ax) = ||Ax||^2 \]

en þar sem normið er núll þá gildir \(Ax=0\).

Gerviandhverfur

Látum \(A\) vera fylki með óháða dálka. Þá er \(m \ge n\), þ.e. fylkið er mjótt. Gerfiandhverfa \(A\) er þá

\[ A^\dagger = (A^TA)^{-1}A^T \]

• \(A^\dagger\) er vinstri andhverfa \(A\)

\[ A^\dagger A = (A^TA)^{-1}A^TA = (A^TA)^{-1}(A^TA) = I \]

• Ef \(A\) er ferningslaga þá er \(A^\dagger = A^{-1}\), því vinstri andhverfa er andhverfan.

Gerviandhverfur og QR þáttun

Ef \(A\) hefur óháða dálka og \(A=QR\). Þá er

\[ A^TA = (QR)^T(QR) = R^TQ^TQR = R^TIR = R^TR \]

Þá verður

\[ \begin{aligned} A^\dagger &= (A^TA)^{-1}A^T = (R^TR)^{-1}(QR)^T \\ &= R^{-1}R^{-T}R^TQ^T \\ &= R^{-1}Q^T \end{aligned} \]

Minnstu fervikavandamál

Látum \(A\) vera \(m\times n\) fylki, mjótt með \(m > n\), svo jafnan \(Ax=b\) er ofákvörðuð.

Fyrir flest gildi á \(b\) hefur jafnan enga lausn, t.d.

\[ \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 2 & 1 \\ \end{bmatrix}x = \begin{bmatrix} 4 \\ 2 \\ 6 \end{bmatrix} \]

Fyrir hvert \(x\) skilgreinum við aðhvarfsfrávikið \(r = Ax-b\). Ef \(x\) er lausn þá er \(r=0\).

Minnsta fervikavandamál er að finna það \(x\) sem lágmarkar \(||Ax-b||^2\).

Næsta vika Lesa kafla 12, 13,