8. Jöfnuhneppi

Why do you go away? So that you can come back. So that you can see the place you came from with new eyes and extra colors. And the people there see you differently, too. Coming back to where you started is not the same as never leaving. – Terry Pratchett

8.1. Línuleg jöfnuhneppi

8.1.1. Verkefnið

Verkefnið í þessum kafla er eftirfarandi. Gefið \(n\times n\) fylki \(A\) og \(n\)-vigur \(\mbox{${\bf b}$}\) þá leitum við að vigri \(\mbox{${\bf x}$}\) þannig að

\[A\mbox{${\bf x}$}= \mbox{${\bf b}$}.\]

8.1.2. Lausnir

Við höfum almennt tvær leiðir til þess að leysa línuleg jöfnuhneppi:

• Gauss-eyðing og innsetning.

• Reikna andhverfu \(A\), \(A^{-1}\), en þá er

  \[\mbox{${\bf x}$}= A^{-1}\mbox{${\bf b}$}.\]

8.1.3. Fjöldi aðgerða

• Gauss-eyðing fyrir \(n\times n\) fylki krefst um það bil \(\frac 23n^3\) reikniaðgerða. Innsetningin krefst svo \(n^2\) aðgerða til viðbótar. Samanlagður fjöldi aðgerða er því

  \[\frac 23n^3+\frac 32n^2 -\frac 76n.\]

• Það að reikna \(A^{-1}\) krefst hins vegar \(2n^3-2n^2+n\) aðgerða og margföldunin \(A^{-1}b\), krefst \(2n^2-n\) aðgerða til viðbótar. Samanlagður fjöldi aðgerða er því

  \[2n^3.\]

Hér er greinilega gáfulegra að nota Gauss-eyðingu. Auk þess er ekki skynsamlegt að ætla að reikna andhverfuna ef ákveða fylkisins er 0 eða nálægt 0. Almennt þá forðumst við eins og mögulegt er að reikna \(A^{-1}\).

8.1.4. Vandamál með stöðugleika

Skoðum jöfnuhneppið

\[\begin{split}\left[\begin{array}{ll} \varepsilon& 1\\ 1 & 1 \end{array}\right] \left[\begin{array}{l} x_1\\ x_2 \end{array}\right] =\left[\begin{array}{l} 1\\ 2 \end{array}\right]\end{split}\]

Nákvæm lausn er \(x_1=1+\frac{\varepsilon}{1-\varepsilon}, x_2=1-\frac{\varepsilon}{1-\varepsilon}\).

Ef hins vegar \(\varepsilon\) er minna en nákvæmnin í tölvunni sem erum að vinna á, þá gefur Gauss-eyðing í tölvu, þar sem eytt er með 1. línu, svarið \(x_1 = 0, x_2 = 1\).

Ef línunum væri víxlað, þá gæfi tölvan hins vegar \(x_1=1, x_2=1\) sem er miklu nær réttu svari.

Aðvörun

Það er alveg ljóst að megum ekki framkvæma Gauss-eyðingu blindandi því þá geta magnast upp styttingarskekkjur sem skemma lausnina okkar.

8.2. Vending (e. pivoting)

8.2.1. Inngangur

Það sem olli vandræðum í dæminu hér á undan var það að forystustuðull fyrstu línunnar var hlutfallslega miklu minni en forystustuðull annarrar línu.

Lausnin felst í því að víxla á línum þannig að við þurfum ekki að notast við litla forystustuðla.

8.2.2. Hlutvending (e. partial pivoting)

Í grófum dráttum: Í umferð \(i\) í Gauss-eyðingunni þá athugum við hvort tölugildi forystustuðla línanna fyrir neðan línu \(i\) eru stærri en forystustuðull línu \(i\), ef svo er þá víxlum við á þeirri línu og línu \(i\).

Það er, í \(i\)-tu ítrun Gauss-eyðingar þá látum við \(M_i = \max_{i\leq j \leq n} |a_{ji}|\). Ef \(|a_{ii}| < M_i\) þá víxlum við á línu \(i\) og fyrstu línunni fyrir neðan sem hefur forystustuðul með tölugildi jafnt og \(M_i\). Það er, ef \(j_0 = \min\{ j ; i \leq j\leq n \text{ og } a_{ji} = M_i \}\) þá víxlum við á línu \(i\) og \(j_0\).

8.2.3. Vankantar

Hlutvending virkar oft vel en getur búið til skekkju þar sem hún tekur bara tillit til forystustuðlanna í hverri línu.

Dæmi þar sem hlutvending virkar illa

Ef jöfnuhneppið

\[\begin{split}\begin{aligned} 0.7 x_1 + 1725 x_2 &= 1739\\ 0.4352 x_1 - 5.433 x_2 = 3.271 \end{aligned}\end{split}\]

er leyst með fjögra stafa nákvæmni og hlutvendingu þá fæst \(x_2=1.001\) og \(x_1=17.14\) en rétt svar er \(x_2=1\) og \(x_1=20\). Það er því ljóst að hlutvending tekst ekki alltaf til að halda skekkju í skefjum.

8.2.4. Sköluð hlutvending (e. scaled partial pivoting)

Ein leið til að koma í veg fyrir þessi vandræði er sköluð hlutvending.

Skilgreinum vigurinn \(\mbox{${\bf s}$}\) sem heldur utan um ,,stærð‘‘ línanna í \(A\),

\[s_i = \max_{1\leq j \leq n} |a_{ij}|.\]

Látum dálkvigurinn \(\mbox{${\bf r}$}\) halda utan um það hvernig við umröðum línunum í \(A\). Byrjum með

\[\mbox{${\bf r}$}= [1\ 2\ 3\ 4\ \ldots\ n]^T.\]

8.2.5. Athugasemd

Við munum uppfæra \(\mbox{${\bf r}$}\) eftir þörfum en breytum ekki \(\mbox{${\bf s}$}\) (of dýrt ef \(n\) er stórt).

Í ítrun \(i\) þá látum við

\[M_i = \max_{i \leq j \leq n} \frac{|a_{{r_j}i}|}{s_{r_j}},\]

og látum \(j_0\) vera minnsta \(j\) þannig að hámarkinu er náð,

\[\frac{ |a_{r_{j_0}i}|}{s_{r_{j_0}}} = M_i.\]

Ef \(i < j_0\) þá skiptum við á línum \(i\) og \(j_0\), þ.e.

\[\mbox{${\bf r}$}= [\ldots\ i\ \ldots\ j_0\ \ldots]^T \text{ breytist í } \mbox{${\bf r}$}= [\ldots\ j_0\ \ldots\ i\ \ldots]^T.\]

Þannig að í ítrun \(i\) þá segir \(i\)-ta stakið í \(\bf r\) okkur hvaða línu við eigum að eyða með.

Aðvörun

Athugið að hér umröðum við ekki línunum í fylkinu því það er miklu ódýrara að nota vigurinn \(\bf r\) til þess að halda utanum í hvaða röð á að framkvæma Gauss-eyðinguna.

8.3. Fylkjastaðall

8.3.1. Að mæla fjarlægð milli hluta

Á rauntalnalínunni þá mælum við fjarlægð með tölugildinu, þannig að fjarlægðin á milli \(x\) og \(y\) er gefin með \(d(x,y)=|x-y|\).

Í \(\mathbb R^n\) þá finnst okkur evklíðski staðallinn náttúrulegur, enda svarar hann til þess að mæla fjarlægð milli punkta með reglustiku;

\[d(\mbox{${\bf x}$},\mbox{${\bf y}$}) = \sqrt{ (x_1-y_1)^2 + \ldots + (x_n-y_n)^2 }.\]

Þetta er hins vegar ekki eina leiðin til þess mæla fjarlægð í \({\mathbb R}^n\) og, eins og við sjáum fljótlega, ekki endilega réttari en aðrar aðferðir.

Almennt viljum við geta mælt ,,fjarlægð‘‘ á milli allra þeirra hluta sem við erum skoða, hvort sem það eru margliður, föll eða fylki. Tilgangurinn er að geta metið hversu langt nálgunin okkar er frá réttu gildi og hversu stór skekkjan er í samanburði við stærð hlutarins sem við erum að vinna með.

8.3.2. Vigurstaðall

Fall \(\| \cdot\|:{\mathbb R}^n \to {\mathbb R}\) kallast vigurstaðall (e. vector norm) ef fyrir öll \(\mbox{${\bf x}$},\mbox{${\bf y}$}\in {\mathbb R}^n\) og \(\alpha \in {\mathbb R}\) gildir eftirfarandi:

1. \(\|\mbox{${\bf x}$}\| \geq 0\)

2. \(\|\mbox{${\bf x}$}\| = 0\) ef og aðeins ef \(\mbox{${\bf x}$}= 0\)

3. \(\|\alpha\mbox{${\bf x}$}\| = |\alpha|\|\mbox{${\bf x}$}\|\)

4. \(\|\mbox{${\bf x}$}+\mbox{${\bf y}$}\| \leq \|\mbox{${\bf x}$}\| + \|\mbox{${\bf y}$}\|\)

Athugasemd

Tölugildisfallið á \({\mathbb R}\) er greinilega staðall.

8.3.3. Dæmi um staðla

• \(\ell_2\) staðallinn: Einnig kallaður evklíðska fjarlægðin, er gefinn með

  \[\|\mbox{${\bf x}$}\|_2 = \left( \sum_{j=1}^n x_j^2 \right)^{\frac 12} = \sqrt{\mbox {${\bf x}$}\cdot \mbox{${\bf x}$}}.\]

• \(\ell_\infty\) staðallinn:

  \[\|\mbox{${\bf x}$}\|_\infty = \max_{1\leq j \leq n} |x_j|.\]

• \(\ell_p\) staðlar: Almennt ef \(1\leq p < \infty\) þá skilgreinum við

  \[\|\mbox{${\bf x}$}\|_p = \left( \sum_{j=1}^n |x_j|^p \right)^{\frac 1p}.\]

8.3.4. Fylkjastaðall

Fylkjastaðall (e. matrix norm) er fall \(\|\cdot\|:{\mathbb R}^{n\times n} \to {\mathbb R}\), þannig að fyrir öll \(A,B \in {\mathbb R}^{n\times n}\) og \(\alpha \in {\mathbb R}\) gildir

1. \(\|A\| \geq 0\)

2. \(\|A\| = 0\) ef og aðeins ef \(A=0\)

3. \(\| \alpha A\| = |\alpha|\|A\|\)

4. \(\|A+B\| \leq \|A\| + \|B\|\)

5. \(\|AB\| \leq \|A\|\|B\|\)

Athugasemd

Ef þessi skilgreining er borin saman við skilgreininguna á vigurstaðli fyrir vigurrúm þá sjáum við að eini raunverulegi munurinn er skilyrði 5.

8.3.5. Fylkjastaðall skilgreindur út frá vigurstaðli

Látum \(\|\cdot\|\) vera vigurstaðal. Fallið \(\|\cdot\|:{\mathbb R}^{n\times n} \to {\mathbb R}\) sem skilgreint er með

\[\|A\| = \max_{\|\mbox{${\bf x}$}\| \neq 0} \frac{\|A\mbox{${\bf x}$}\|}{\|\mbox{${\bf x}$}\|},\]

kallast náttúrulegi fylkjastaðallinn sem \(\|\cdot\|\) gefur af sér.

Athugasemd

Það þarf að sýna, og er ekki mjög erfitt, að þessi fylkjastaðall uppfyllir öll skilyrðin í skilgreiningu hér á undan og er því sannarlega fylkjastaðall.

Athugasemd

Ef \(\|\cdot\|\) er náttúrulegur fylkjastaðall þá gildir að fyrir öll fylki \(A\) og alla vigra \(\mbox{${\bf x}$}\) að

\[\underbrace{\|A\mbox{${\bf x}$}\|}_{\text{vigurstaðll}} \leq \underbrace{\|A\|}_{\text{fylkjastaðall}} \ \cdot \ \underbrace{\|\mbox{${\bf x}$}\|}_{\text{vigurstaðall}}\]

8.3.6. Dæmi um fylkjastaðal

Fyrir sérhvern \(\ell_p\) staðal fáum við fylkjastaðal \(\|\cdot\|_p\).

\(\|\cdot\|_\infty\): Einfaldastur er staðallinn sem tilheyrir \(\ell_\infty\), en hann uppfyllir

\[\|A\|_\infty = \max_{1\leq i \leq n} \sum_{j=1}^n |a_{ij}|.\]

8.3.7. Eigingildi

Látum \(A\) vera fylki. Ef tala \(\lambda\) (hugsanlega tvinntala) og vigur \(\mbox{${\bf x}$}\) uppfylla

\[A\mbox{${\bf x}$}= \lambda \mbox{${\bf x}$},\]

þá kallast \(\lambda\) eigingildi \(A\), og \(\mbox{${\bf x}$}\) eiginvigur \(A\).

Athugið að eigingildi \(A\) eru nákvæmlega rætur kennimargliðu \(A\), \(t \mapsto \det(A-It)\).

8.3.8. Róf og rófgeisli

Mengi allra eigingilda \(A\) er kallað róf \(A\) (e. spectrum) og er táknað með \(\sigma(A)\).

Rófgeisli (e. spectral radius) fylkisins \(A\) er talan

\[\rho(A) = \max_{\lambda \in \sigma(A)} |\lambda|.\]

8.3.9. Setning um rófgeisla

Látum \(A\) vera fylki, þá gildir eftirfarandi

• \(\|A\|_2 = \sqrt{\rho(A^T A)}\)

• \(\rho(A) \leq \|A\|\) fyrir sérhvern náttúrulegan fylkjastaðal \(\|\cdot\|\)

• Fyrir sérhvert \(\varepsilon>0\) þá er til náttúrulegur fylkjastaðall \(\|\cdot\|\) þannig að \(\|A\| \leq \rho(A) + \varepsilon\).

8.4. Skekkjumat og ástandstala

8.4.1. Hvernig á að mæla skekkju

Gerum ráð fyrir að \(A\) sé andhverfanlegt fylki, \(\mbox{${\bf b}$}\) vigur og að við séum að leita að lausn \(\mbox{${\bf x}$}\) á

\[A{\bf x}= {\bf b}.\]

Ef við höfum nálgun \(\tilde {\bf x}\) þannig að leifin (e. residual) \({\bf r} = A\tilde {\bf x}- {\bf b}\) er lítil, hvað getum við þá sagt um skekkjuna (e. error) \({\bf e}= {\bf x}-\tilde {\bf x}\)? Er hún endilega lítil?

Sjáum að svo er ekki, skekkjan getur verið hlutfallslega miklu meiri heldur en leifin.

Dæmi

Skoðum jöfnuhneppið

\[\begin{split}\left[\begin{matrix} 1& 2 \\ 0.99 & 1.99 \end{matrix}\right] \mathbf{x} = \left[\begin{matrix} 1 \\ 1 \end{matrix}\right]\end{split}\]

Sjáum að rétt lausn er \([-1 \ 1]^T\). Ef við skilgreinum \(\tilde x = [1 \ 0]^T\) þá er

\[\mathbf{e} = [-2 \ 1]^T \qquad \|\mathbf{e}\|_\infty = 2.\]

Hins vegar þá er leifin

\[\begin{split}\mathbf{r} = A\mathbf{\tilde x} -\mathbf{b} = \left[\begin{matrix} 1& 2 \\ 0.99 & 1.99 \end{matrix}\right] \left[\begin{matrix} 1\\ 0 \end{matrix}\right] - \left[\begin{matrix} 1 \\ 1 \end{matrix}\right] \left[\begin{matrix} 0 \\ -0.01 \end{matrix}\right]\end{split}\]

þannig að \(\|\mathbf{e}\|_\infty = 0.01\). Hér er skekkjan 200 sinnum stærri en leifin sem sýnir að lítil leif þarf ekki endilega að hafa í för með sér litla skekkju.

8.4.2. Skekkjumat

Við höfum fjórar jöfnur

\[\mbox{${\bf b}$}=A\mbox{${\bf x}$}, \quad \mbox{${\bf x}$}=A^{-1}\mbox{${\bf b}$}, \quad \mbox{${\bf r}$}=A(\mathbf{\tilde x}-\mbox{${\bf x}$})=A\mbox{${\bf e}$}, \quad \text{ og } \quad \mbox{${\bf e}$}=A^{-1}\mbox{${\bf r}$}\]

og þær gefa okkur fjórar ójöfnur fyrir tilsvarandi staðal:

\[\|\mbox{${\bf b}$}\|\leq \|A\|\|\mbox{${\bf x}$}\|, \quad \|\mbox{${\bf x}$}\|\leq \|A^{-1}\|\|\mbox{${\bf b}$}\|, \quad \|\mbox{${\bf r}$}\|\leq \|A\|\|\mbox{${\bf e}$}\|, \quad \|\mbox{${\bf e}$}\|\leq \|A^{-1}\|\|\mbox{${\bf r}$}\|\]

Við getum tengt tvær síðustu ójöfnurnar saman í mat á skekkjunni

\[\dfrac 1{\|A\|}\cdot \|\mbox{${\bf r}$}\| \leq \|\mbox{${\bf e}$}\| \leq \|A^{-1}\| \|\mbox{${\bf r}$}\|\]

og með því að nota fyrstu tvær ójöfnurnar fæst mat á hlutfallslegri skekkju

\[\dfrac 1{\|A\|\|A^{-1}\|}\dfrac{ \|\mbox{${\bf r}$}\|}{\|\mbox{${\bf b}$}\|} \leq \dfrac{\|\mbox{${\bf e}$}\|}{\|\mbox{${\bf x}$}\|} \leq \|A\|\|A^{-1}\|\dfrac{\|\mbox{${\bf r}$}\|}{\|\mbox{${\bf b}$}\|}\]

Nú skilgreinum við ástandstölu fylkisins \(A\) með

\[\kappa(A)=\|A\|\|A^{-1}\|.\]

8.4.3. Ástandstala fylkis og mat á hlutfallslegri skekkju

Með ástandstölunni verður mat okkar á hlutfallslegu skekkjunum að

\[\dfrac 1{\kappa(A)}\cdot \dfrac{ \|\mbox{${\bf r}$}\|}{\|\mbox{${\bf b}$}\|} \leq \dfrac{\|\mbox{${\bf e}$}\|}{\|\mbox{${\bf x}$}\|} \leq \kappa(A)\cdot \dfrac{\|\mbox{${\bf r}$}\|}{\|\mbox{${\bf b}$}\|}\]

Þetta segir okkur að ef ástandstala fylkisins er stór er mögulegt að skekkjan verði miklu stærri en leifin, samanber dæmið hér á undan þar sem ástandstalan er 1197.

Aðvörun

Athugið að skilgreiningin

\[\kappa(A)=\|A\|\|A^{-1}\|.\]

er mjög háð því hvaða staðal við veljum. Þó höfum við að fyrir alla fylkjastaðla gildir

\[1=\|I\|=\|AA^{-1}\|\leq \|A\|\|A^{-1}\|=\kappa(A)\]

8.4.4. Áhrif gagnaskekkju

Hugsum okkur nú að við viljum leysa jöfnuhneppi \(A\mbox{${\bf x}$}=\mbox{${\bf b}$}\), en vegna skekkju í stuðlum jöfnuhneppisins leysum við annað hneppi \(\tilde A\mathbf {\tilde x}=\mathbf{\tilde b}\).

Við skilgreinum gagnaskekkjur \(\delta A=\tilde A-A\) og \(\delta\mbox{${\bf b}$}=\mathbf{\tilde b}-\mbox{${\bf b}$}\) og ætlum að nota þær til þess að meta skekkjuna \(\mbox{${\bf e}$}=\delta\mbox{${\bf x}$}=\mathbf{\tilde x}-\mbox{${\bf x}$}\).

Við verðum að gera ráð fyrir að \(\|\delta A\|\leq 1/\|A^{-1}\|\) sem tryggir að fylkið \(\tilde A\) sé andhverfanlegt.

Nú stillum við upp jöfnuhneppinu \(\tilde A\mathbf{\tilde x}=\mathbf{\tilde b}\) á forminu

\[(A+\delta A)(\mbox{${\bf x}$}+\delta \mbox{${\bf x}$})=(\mbox{${\bf b}$}+\delta\mbox{${\bf b}$})\]

sem jafngildir

\[\delta\mbox{${\bf x}$}=A^{-1}\big(\delta\mbox{${\bf b}$}-(\delta A)\mbox{${\bf x}$}-(\delta A)(\delta x)\big)\]

Af þessari jöfnu leiðir ójafnan

\[\|\delta\mbox{${\bf x}$}\|\leq \|A^{-1}\|\big(\|\delta\mbox{${\bf b}$}\|+\|\delta A\|\|\mbox{${\bf x}$}\|+\|\delta A\|\|\delta \mbox{${\bf x}$}\|\big)\]

Einangrum nú \(\|\delta \mbox{${\bf x}$}\|\),

\[\|\delta\mbox{${\bf x}$}\|\leq \dfrac{\|A^{-1}\|}{1-\|A^{-1}\|\|\delta A\|}\cdot \big(\|\delta\mbox{${\bf b}$}\|+\|\delta A\|\|\mbox{${\bf x}$}\|\big)\]

deilum með \(\|\mbox{${\bf x}$}\|\) báðum megin, margföldum síðan með \(\|A\|\) í teljara og nefnara í hægri hliðinni,

\[\dfrac{\|\delta\mbox{${\bf x}$}\|} {\|\mbox{${\bf x}$}\|}\leq \dfrac{\|A\|\|A^{-1}\|}{1-\|A^{-1}\|\|\delta A\|}\cdot \bigg(\dfrac{\|\delta\mbox{${\bf b}$}\|}{\|A\|\|\mbox{${\bf x}$}\|}+ \dfrac{\|\delta A\|}{\|A\|}\bigg)\]

Samkvæmt skilgreiningu er \(\kappa(A)=\|A\|\|A^{-1}\|\) og við höfum auk þess ójöfnuna \(\|\mbox{${\bf b}$}\|\leq \|A\|\|\mbox{${\bf x}$}\|\), en það gefur matið á hlutfallslegu skekkjunni sem við sækjumst eftir

\[\dfrac{\|\delta\mbox{${\bf x}$}\|} {\|\mbox{${\bf x}$}\|}\leq \dfrac{\kappa(A)}{1-\kappa(A)\cdot(\|\delta A\|/\|A\|)}\cdot \bigg(\dfrac{\|\delta\mbox{${\bf b}$}\|}{\|\mbox{${\bf b}$}\|}+ \dfrac{\|\delta A\|}{\|A\|}\bigg).\]

8.5. LU-þáttun

8.5.1. Nokkrar skilgreiningar

1. Fylkið \(A\) nefnist neðra þríhyrningsfylki ef öll stök fyrir ofan hornalínuna í \(A\) eru \(0\), þ.e. \(a_{ij}=0\) ef \(i<j\).

2. Fylkið \(A\) nefnist efra þríhyrningsfylki ef öll stökin neðan við hornalínuna eru \(0\), þ.e. \(a_{ij}=0\) ef \(i>j\).

3. Fylkið \(A\) nefnist bandfylki (e. striped matrix) ef til er \(\beta \leq n-2\) þannig að \(a_{ij}=0\) ef \(|i-j|>\beta\). Minnsta talan \(\beta\) sem uppfyllir þetta skilyrði kallst á bandvídd fylkisins \(A\).

4. Ef \(A\) er bandfylki með bandvíddina \(1\), þá nefnist \(A\) þríhornalínufylki.

5. Fylkið \(A\) er sagt vera samhverft ef \(a_{ij}=a_{ji}\) fyrir öll \(i\) og \(j\).

6. Fylkið \(A\) er sagt vera jákvætt ákvarðað ef \(\mbox{${\bf x}$}^TA\mbox{${\bf x}$}>0\) gildir fyrir alla vigra \(\mbox{${\bf x}$}\neq 0\) í \({\mathbb R}^n\).

8.5.2. Úrlausn á jöfnuhneppi með neðra þríhyrningsfylki

Ef \(A\) er neðra þríhyrningsfylki, þá er úrlausn jöfnuhneppisins \(A\mbox{${\bf x}$}= \mbox{${\bf b}$}\) auðveld, því hneppið er þá af gerðinni

\[\begin{split}\begin{aligned} &a_{11}x_1&&=b_1,\\ &a_{21}x_1+a_{22}x_2&&=b_2,\\ &a_{31}x_1+a_{32}x_2+a_{33}x_3&&=b_3,\\ &\vdots \qquad \qquad \vdots \qquad \qquad \vdots& \qquad& \vdots\\ &a_{n1}x_1+a_{n2}x_2+a_{n3}x_3\cdots+a_{nn}x_n&&=b_n,\end{aligned}\end{split}\]

Við getum rakið okkur niður línurnar og leyst út stærðirnar \(x_1,\dots,x_n\) hverja á eftir annarri

\[\begin{split}\begin{aligned} x_1& = b_1/a_{11},\\ x_2& = (b_2-a_{21}x_1)/a_{22},\\ x_3& = (b_3-a_{31}x_1-a_{32}x_2)/a_{33}\\ &\vdots \qquad \qquad \vdots \qquad \qquad \vdots\\ x_n& = (b_n-a_{n1}x_1-a_{n2}x_2-\cdots -a_{n,n-1}x_{n-1})/a_{nn}.\end{aligned}\end{split}\]

8.5.3. Fjöldi aðgerða

Nú skulum við telja saman fjölda reikningsaðgerða sem þarf til þess að framkvæma þessa útreikninga.

Við lítum á samlagningu og frádrátt sem sömu aðgerðina. Við þurfum enga samlagningu til að reikna út \(x_1\), eina til þess að reikna út \(x_2\), tvær til þess að reikna \(x_3\) og þannig áfram upp í \(n-1\) samlagningu til þess að reikna út \(x_n\).

Heildarfjöldinn er því

\[1 + 2 + \cdots + n-1 = \tfrac 12 n(n-1) = \tfrac 12n^2-\tfrac 12 n.\]

Fjöldi margfaldana er sá sami.

Við þurfum hins vegar aðeins eina deilingu til þess að reikna út hverja af stærðunum \(x_1,\dots,x_n\).

Heildarfjöldi reikniaðgerða við úrlausn á línulegu jöfnuhneppi \(Ax=b\), þar sem \(A\) er neðra þríhyrningsfylki er því

\[\tfrac 12 n^2 - \tfrac 12 n + \tfrac 12 n^2 - \tfrac 12 n +n = n^2.\]

8.5.4. Úrlausn á jöfnuhneppi með efra þríhyrningsfylki

Hugsum okkur nú að \(A\) sé efra þríhyrningsfylki. Þá verður jöfnuhneppið

\[\begin{split}\begin{aligned} a_{11}x_1+a_{12}x_2+a_{13}x_3+\cdots+a_{1n}x_n& = b_1,\\ a_{22}x_2+a_{23}x_3+\cdots+a_{2n}x_n& = b_2,\\ a_{33}x_3+\cdots+a_{3n}x_n& = b_3,\\ \vdots\quad& \quad \vdots\\ a_{nn}x_n& = b_n,\end{aligned}\end{split}\]

Við getum rakið okkur upp línurnar og fundið \(x_n,x_{n-1},\dots,x_1\) hverja af annarri

\[\begin{split}\begin{aligned} x_n& = b_n/a_{nn},\\ x_{n-1}& = (b_{n-1}-a_{n-1,n}x_n)/a_{n-1,n-1},\\ \vdots&\qquad \vdots\qquad \qquad \vdots\\ x_1& = (b_1-a_{12}x_2-a_{13}x_3-\cdots -a_{1,n}x_{n})/a_{11}.\end{aligned}\end{split}\]

Aðgerðafjöldinn er sá sami og í úrlausn neðra þríhyrningshneppisins.

8.5.5. Línuaðgerðir

Gerum ráð fyrir að við séum að ryðja \(4\times 4\) fylki með Gauss-eyðingu og að við séum búin með fyrsta dálkinn. Næsta skref er að nota línu 2 til þess að losna við stökin í sætum (3,2) og (4,2).

\[\begin{split}A= \left[\begin{array}{llll} 1 & \cdot & \cdot & \cdot\\ 0 & a & \cdot & \cdot\\ 0 & b & \cdot & \cdot\\ 0 & c & \cdot & \cdot \end{array}\right]\end{split}\]

Lína 3, \(l_3\), verður þá að \(l_3 - \frac ba l_2\), og lína 4, \(l_4\), verður að \(l_4 - \frac ca l_2\).

Þessar tvær aðgerðir má einnig framkvæma með því að margfalda fylkið að ofan frá vinstri með fylkinu

\[\begin{split}M_2 = \left[ \begin{array}{llll} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & -\frac ba & 1 & 0\\ 0 & -\frac ca & 0 & 1 \end{array} \right]\end{split}\]

8.5.6. Ný sýn á Gauss-eyðingu

Það að ryðja fylkið eins og hér á undan, felst því í því að margfalda \(A\) frá vinstri með þremur fylkjum \(M_1, M_2\) og \(M_3\) sem eru þannig að \(M_i\) er einingafylkið nema í sætum \((i+1,i),\ldots,(n,i)\) eru tölur sem eru hugsanlega frábrugðnar 0. Fylkið \(M_i\) sér þá um að eyða í dálk \(i\).

Athugum að Gauss-eyðing skilar fylki \(U\) á efra þríhyrningsformi.

Við getum því skrifað

\[M_3 M_2 M_1 A = U\]

Almennt, fyrir \(n \times n\) fylki þá getum við skrifað

\[M_{n-1}\cdots M_2 M_1 A = U,\]

þar sem \(M_i\) eru fylki eins og lýst er hér að ofan.

8.5.7. Nánar um \(M_i\)

Við sjáum að ef

\[\begin{split}M_i = \left[ \begin{array}{ccccccc} 1 & & & & & & \\ & . & & & & & \\ & & 1 & & & & \\ & & m_{i+1,i} & 1 & & & \\ & & . & & . & & \\ & & . & & & . & \\ & & m_{n,i} & & & & 1 \end{array}\right],\end{split}\]

þá er

\[\begin{split}M_i^{-1} = \left[ \begin{array}{ccccccc} 1 & & & & & & \\ & . & & & & & \\ & & 1 & & & & \\ & & -m_{i+1,i} & 1 & & & \\ & & . & & . & & \\ & & . & & & . & \\ & & -m_{n,i} & & & & 1 \end{array}\right].\end{split}\]

Eins þá er auðvelt að sjá að

\[\begin{split}M_i^{-1} M_j^{-1} = \left[ \begin{array}{cccccccc} 1 & & & & & & & \\ & . & & & & & & \\ & & 1 & & & & & \\ & & -m_{i+1,i} & . & & & & \\ & & . & & 1 & & & \\ & & . & & -m_{j+1,j} & . & & \\ & & . & & . & & . & \\ & & -m_{n,i} & & -m_{n,j} & & & 1 \end{array} \right]\end{split}\]

Það er

\[\begin{split}M_1^{-1} M_2^{-1} \cdots M_{n-1}^{-1} = \left[ \begin{array}{cccccc} 1 & & & & & \\ -m_{2,1} & 1 & & & & \\ -m_{3,1} & -m_{3,2} & 1 & & & \\ & -m_{4,2} & -m_{4,3} & 1 & & \\ & . & & & . & \\ -m_{n,1} & -m_{n,2} & -m_{n,3} & . & -m_{n,n-1} & 1 \end{array} \right]\end{split}\]

8.5.8. LU-þáttun

Þetta hefur í för með sér að ef við skilgreinum \(L = M_1^{-1} M_2^{-1} \cdots M_{n-1}^{-1}\) þá er

\[A = LU\]

eða

\[\begin{split}A = \left[\begin{array}{cccccccc} 1 & & & & & & & \\ -m_{2,1} & 1 & & & & & & \\ -m_{3,1} & -m_{3,2} & 1 & & & & & \\ & -m_{4,2} & -m_{4,3} & 1 & & & & \\ & . & & & . & & & \\ & . & & & & . & & \\ & . & & & & & . & \\ -m_{n,1} & -m_{n,2} & -m_{n,3} & . & . & . & -m_{n,n-1} & 1 \end{array}\right] U\end{split}\]

Þannig að með því að framkvæma Gauss-eyðingu á \(A\) og halda utanum aðgerðirnar (\(M_i\)’in) og niðurstöðuna \(U\) þá fæst \(LU\)-þáttun á \(A\).

8.5.9. \(LU\)-þáttun og sköluð hlutvending

Aðferðin hér að framan gerði ráð fyrir að stak \(a_{i,i}\) yrði aldrei 0 (þá getum við ekki notað þá línu til þess að eyða). Eins hugsuðum við ekkert út í styttingarskekkjur sem við búum til.

Ef við framkvæmum Gauss-eyðinguna með skalaðri hlutvendingu þá ráðum við bót á báðum þessum atriðum, því þá veljum við aldrei línu með forystustuðul 0 og við minnkum skekkjuna eins og hefur komið fram áður.

Aðvörun

Þegar við notum skalaða hlutvendingu þá uppfylla fylkin \(L\) og \(U\) ekki endilega \(LU=A\). Þess í stað fæst

\[LU =PA\]

þar sem fylkið \(P\) umraðar línunum í \(A\) í samræmi við umröðunarvigrinn \(\mbox{${\bf r}$}\). Það er, stökin í \(P\) eru 0, nema \(p_{i,r_i} = 1\).

8.5.10. Jöfnuhneppi leyst með LU-þáttun

Við skiptum nú úrlausnarferlinu á \(A\mbox{${\bf x}$}=\mbox{${\bf b}$}\) í þrjú skref

(i) \(LU\) -þáttun: Reiknum út neðra þríhyrningsfylki \(L\) og efra þríhyrningsfylki \(U\) með skalaðri hlutvendingu. Höldum utanum \(\mbox{${\bf r}$}\) (og þar með \(P\)). Þá er

\[LU=PA.\]

(ii) Forinnsetning: Leysum \(L\mbox{${\bf y}$}=P\mbox{${\bf b}$}\).

(iii) Endurinnsetning: Leysum \(U\mbox{${\bf x}$}=\mbox{${\bf y}$}\).

Lausnin sem við leitum að er þá \(\mbox{${\bf x}$}\), því

\[P\mbox{${\bf b}$}= L\mbox{${\bf y}$}= UL\mbox{${\bf x}$}= PA\mbox{${\bf x}$},\]

sem er jafngilt því að \(\mbox{${\bf b}$}=A\mbox{${\bf x}$}\)

8.5.11. Fjöldi reikniaðgerða fyrir \(LU\)-þáttun

Heildarfjöldi reikningsaðgerða til þess að framkvæma \(LU\)-þáttunina er

\[\frac 23n^3-\frac 12n^2-\frac 76 n.\]

Liðir (ii) og (iii) krefjast svo \(n^2 + n^2 = 2n^2\) aðgerða til viðbótar. Samanlagður fjöldi aðgerða er því

\[\frac 23n^3+\frac 32n^2-\frac 76 n.\]

Ef \(n\) er stór tala, segjum \(n=1000\), þá er fyrsti liðurinn lang stærstur og við getum slegið á aðgerðafjöldann með \(\tfrac 23n^3\).

Þetta er töluvert betra heldur en að reikna \(A^{-1}\) og svo \(\mbox{${\bf x}$}=A^{-1}\mbox{${\bf b}$}\), en þá er heildafjöldi aðgerða \(2n^3\).

8.5.12. Mörg jöfnuhneppi

Ef við þurfum að leysa mörg jöfnuhneppi með sama stuðlafylkið þá koma kostir \(LU\)-þáttunar vel í ljós.

Gefið \(A\) og \(\mbox{${\bf b}$}_1,\ldots,\mbox{${\bf b}$}_m\) þá leitum við að vigrum \(\mbox{${\bf x}$}_1,\ldots,\mbox{${\bf x}$}_m\) þannig að

\[A\mbox{${\bf x}$}_i = \mbox{${\bf b}$}_i, \qquad \text{fyrir } i = 1,\ldots,m.\]

Við þurfum bara að framkvæma \(LU\)-þáttunina einu sinni, en innsetningarnar í lið (ii) og (iii) framkvæmum við \(m\)-sinnum. Heildar fjöldi aðgerða er þá

\[\frac 23n^3+(2m-\frac 12)n^2- (m-\frac 16) n.\]

8.6. Fastapunktsaðferðir fyrir línuleg jöfnuhneppi

8.6.1. Ítrekunaraðferðir til þess að leysa línuleg jöfnuhneppi

Munum að samanlagður fjöldi reikniaðgerða sem þarf til þess að leysa \(n\times n\) línulegt jöfnuhneppi \(A\mbox{${\bf x}$}=\mbox{${\bf b}$}\) með Gauss-eyðingu, for- og endurinnsetningu er \(\sim \tfrac 23 n^3\).

Ef jöfnuhneppið er jafngilt hneppinu

\[\mbox{${\bf x}$}=T\mbox{${\bf x}$}+\mbox{${\bf c}$}\]

þá getum við sett upp fastapunktsferð til þess að leysa þetta hneppi með því að giska á eitthvert nálgunargildi \(\mbox{${\bf x}$}^{(0)}\) fyrir lausnina og ítra síðan með formúlunni

\[\mbox{${\bf x}$}^{(k+1)}=T\mbox{${\bf x}$}^{(k)}+\mbox{${\bf c}$}, \qquad k=0,1,2,\dots,\]

í þeirri von að runan \((\mbox{${\bf x}$}^{(k)})\) stefni á réttu lausnina \(\mbox{${\bf x}$}\) á upprunalega jöfnuhneppinu.

Það þarf \(n^2-n\) aðgerðir til þess að reikna út margfeldið \(T\mbox{${\bf v}$}\) fyrir vigur \(\mbox{${\bf v}$}\in {\mathbb R}^n\) og því getum við komist upp með að taka \(\approx \tfrac 23 n\) ítrekanir áður en heildaraðgerðafjöldinn er kominn upp fyrir aðgerðafjöldann í Gauss-eyðingu, ásamt for- og endurinnsetningu.

8.6.2. Fastapunktsítrekun til þess að leysa línuleg jöfnuhneppi

Við ætlum nú að gera ráð fyrir að jafnan \(A\mbox{${\bf x}$}=\mbox{${\bf b}$}\) sé jafngild

\[\mbox{${\bf x}$}=T\mbox{${\bf x}$}+\mbox{${\bf c}$}\]

giskum á eitthvert nálgunargildi \(\mbox{${\bf x}$}^{(0)}\) fyrir lausnina \(\mbox{${\bf x}$}\) og skilgreinum síðan rununa

\[\mbox{${\bf x}$}^{(k+1)}=T\mbox{${\bf x}$}^{(k)}+\mbox{${\bf c}$}, \qquad k=0,1,2,\dots,\]

Allt er nú undir því komið að \(n\times n\) fylkið \(T\) sé vel valið.

8.6.3. Fastapunktsítrekun - skekkjumat

Við skilgreinum nú skekkjuna í \(k\)-ta ítrekunarskrefinu \(\mbox{${\bf e}$}^{(k)}=\mbox{${\bf x}$}-\mbox{${\bf x}$}^{(k)}\). Þá gildir formúlan

\[\mbox{${\bf e}$}^{(k)}=T\mbox{${\bf e}$}^{(k-1)}=T^2\mbox{${\bf e}$}^{(k-2)}=\cdots=T^{k}\mbox{${\bf e}$}^{(0)}\]

sem við höfum áður séð í athugun okkar á fastapunktsaðferðinni.

Nú beitum við

\[\|\mbox{${\bf e}$}^{(k)}\| \leq \|T^{k}\|\|\mbox{${\bf e}$}^{(0)}\|\leq \|T\|^{k}\|\mbox{${\bf e}$}^{(0)}\|\]

Við höfum \(\mbox{${\bf x}$}^{(1)}-\mbox{${\bf x}$}^{(0)}=T\mbox{${\bf x}$}^{(0)}+\mbox{${\bf c}$}-\mbox{${\bf x}$}^{(0)}\) og \(\mbox{${\bf c}$}=\mbox{${\bf x}$}-T\mbox{${\bf x}$}\) og þar með

\[\mbox{${\bf x}$}^{(1)}-\mbox{${\bf x}$}^{(0)}=T(\mbox{${\bf x}$}^{(0)}-\mbox{${\bf x}$})-(\mbox{${\bf x}$}^{(0)}-\mbox{${\bf x}$})= -(\mbox{${\bf e}$}^{(0)}-T\mbox{${\bf e}$}^{(0)})=-(I-T)\mbox{${\bf e}$}^{(0)}.\]

Þetta gefur jöfnuna

\[\mbox{${\bf e}$}^{(0)}=-(I-T)^{-1} \big(\mbox{${\bf x}$}^{(1)}-\mbox{${\bf x}$}^{(0)}\big).\]

Með smá útreikningi má sýna fram á að ef \(\|T\|<1\), þá er

\[\|(I-T)^{-1}\|\leq \dfrac 1{1-\|T\|}.\]

Við vorum komin með ójöfnurnar

\[\|\mbox{${\bf e}$}^{(k)}\| \leq \|T\|^{k}\|\mbox{${\bf e}$}^{(0)}\|\]

og niðurstaðan verður því

\[\|\mbox{${\bf e}$}^{(k)}\| \leq \dfrac{\|T\|^{k}}{1-\|T\|} \|\mbox{${\bf x}$}^{(1)}-\mbox{${\bf x}$}^{(0)}\|\]

Sem þýðir að fastapunktsaðferðin er samleitin þegar \(\|T\|<1\).

8.6.4. Skilyrði fyrir samleitni

Munum nú að \(\rho(T)\) er rófgeisli fylkisins \(T\) sem er samkvæmt skilgreiningu tölugildi á stærsta eigingildi fylkisins \(T\).

Rifjum líka upp að samkvæmt setningu um rófgeisla gildir fyrir sérhvern náttúrlegan fylkjastaðal \(\|\cdot\|\) að \(\rho(T) \leq \|T\|\) og að fyrir sérhvert \(\varepsilon>0\) gildir að hægt er að finna náttúrlegan fylkjastaðal þannig að

\[\|T\|\leq \rho(T)+\varepsilon.\]

Sérstaklega gildir í tilfellinu \(\rho(T)<1\) að til er náttúrlegur fylkjastaðall \(\|\cdot\|\) þannig að \(\|T\|<1\).

Þetta þýðir að fastapunktsaðferðin er samleitin ef \(\rho(T) < 1\).

8.6.5. Skiptingaraðferð (e. splitting method)

Við viljum setja upp fastapunktsaðferð til þess að leysa línulega jöfnuhneppið \(A\mbox{${\bf x}$}=\mbox{${\bf b}$}\) með því að umrita jöfnuna yfir í jafngilda línulega jöfnu

\[\mbox{${\bf x}$}=T\mbox{${\bf x}$}+\mbox{${\bf c}$}.\]

Gerum ráð fyrir að \(A=M-N\) þar sem \(M\) er andhverfanlegt fylki. Þá jafngildir \(A\mbox{${\bf x}$}=\mbox{${\bf b}$}\) jöfnunni \(M\mbox{${\bf x}$}=N\mbox{${\bf x}$}+\mbox{${\bf b}$}\) og fastapunktsjafnan er

\[\mbox{${\bf x}$}=M^{-1}N\mbox{${\bf x}$}+M^{-1}\mbox{${\bf b}$},\]

þar sem \(T = M^{-1}N\) og \(\mbox{${\bf c}$}= M^{-1}\mbox{${\bf b}$}\).

Þessi leið til þess að umrita línulega jöfnuhneppið \(A\mbox{${\bf x}$}=\mbox{${\bf b}$}\) yfir í jafngilda hneppið \(\mbox{${\bf x}$}=T\mbox{${\bf x}$}+\mbox{${\bf c}$}\) nefnist skiptingaraðferð fyrir línulega jöfnuhneppið \(A\mbox{${\bf x}$}=\mbox{${\bf b}$}\).

8.6.6. Jacobi-aðferð

Við skrifum \(A=D-L-U\), þar sem \(D\) er hornalínufylkið með hornalínu \(A\), \(L\) er neðra þríhyrningsfylki og \(U\) er efra þríhyrningsfylki

Við tökum \(M=D\) og \(N=L+U\) og fáum þá \(T=D^{-1}(L+U)\) og \(\mbox{${\bf c}$}=D^{-1}\mbox{${\bf b}$}\).

Þessi skiptingaraðferð er nefnd Jacobi-aðferð.

Rakningarformúlan er

\[\mbox{${\bf x}$}^{(k+1)}=D^{-1}(L+U)\mbox{${\bf x}$}^{(k)}+D^{-1}\mbox{${\bf b}$}.\]

Ef við skrifum hana hnit fyrir hnit, þá fáum við fyrir \(i=1,2,\dots,n\),

\[x_i^{(k+1)}=\dfrac 1{a_{i,i}}\bigg( b_i-\sum_{j=1}^{i-1}a_{i,j}x_j^{(k)}-\sum_{j=i+1}^n a_{i,j}x_j^{(k)}\bigg)\]

8.6.7. Gauss-Seidel-aðferð

Augljós endurbót á Jacobi-aðferðinni er að nota gildið \(x_i^{(k+1)}\) fyrir \(i<j\) um leið og það hefur verið reiknað.

Við það breytist rakningarformúlan í Jacobi-aðferð í

\[x_i^{(k+1)}=\dfrac 1{a_{i,i}}\bigg( b_i-\sum_{j=1}^{i-1}a_{i,j}x_j^{(k+1)}-\sum_{j=i+1}^n a_{i,j}x_j^{(k)}\bigg)\]

Þetta svarar til þess að við veljum skiptingu á \(A\) með \(M=D-L\) og \(N=U\) og þar með að

\[T=(D-L)^{-1}U \qquad \text{ og } \qquad \mbox{${\bf c}$}=(D-L)^{-1} \mbox{${\bf b}$}\]

8.6.8. SOR-aðferð (e. successive over-relaxation)

Það er hægt að hraða samleitni í Gauss-Seidel-aðferð með því að taka vegið meðaltal af gildinu \(x_i^{(k+1)}\) sem kemur út úr Gauss-Seidel reikniritinu og næsta gildi á undan með vægisstuðli sem við táknum með \(\omega\).

Formúlan verður

\[x_i^{(k+1)}=(1-\omega)x_i^{(k)}+\dfrac \omega{a_{i,i}}\bigg( b_i-\sum_{j=1}^{i-1}a_{i,j}x_j^{(k+1)}-\sum_{j=i+1}^n a_{i,j}x_j^{(k)}\bigg)\]

Þetta svarar til þess að við veljum

\[M=\dfrac 1\omega D-L \quad { og } \quad N=\bigg(\dfrac 1\omega -1\bigg) D+U\]

og þar með að

\[T=\bigg(\dfrac 1\omega D-L\bigg)^{-1} \bigg(\bigg(\dfrac 1\omega-1\bigg)D+ U\bigg) \quad \text{ og } \quad \mbox{${\bf c}$}=\bigg(\dfrac 1\omega D-L\bigg)^{-1} \mbox{${\bf b}$}\]

8.6.9. Setning um samleitni Gauss-Seidel-aðferðarinnar

• Gerum ráð fyrir að \(A\) sé samhverft rauntölufylki með öll hornalínustökin jákvæð. Þá er Gauss-Seidel aðferðin samleitin ef og aðeins ef \(A\) er jákvætt ákvarðað.

• Ef fylkið \(A\) er jákvætt ákvarðað, þá er Gauss-Seidel-aðferð samleitin fyrir sérhvert val á upphafságiskun \(\mbox{${\bf x}$}^{(0)}\).

8.7. Newton-aðferð fyrir jöfnuhneppi

Að lokum þá skulum við skoða aðeins ólínuleg jöfnuhneppi.

Látum \(f_k : I \to {\mathbb R}\), \(k = 1, \ldots, n\), þar sem \(I\) er svæði í \({\mathbb R}^n\) vera samfelld föll. Það getur komið sér vel að geta leyst ólínuleg jöfnuhneppi af gerðinni

\[\begin{split}\left\{ \begin{array}{c} f_1(x_1, \ldots, x_n) = 0 \\ f_2(x_1, \ldots, x_n) = 0 \\ \vdots \\ f_n(x_1, \ldots, x_n) = 0 \\ \end{array} \right.\end{split}\]

Svo heppilega vill til að aðferð Newtons virkar næstum óbreytt fyrir slík hneppi.

8.7.1. Jacobi-fylki

Skilgreinum \(\mbox{${\bf f}$}: I \to R^n\) með

\[\mbox{${\bf f}$}(\mbox{${\bf x}$}) = \left(f_1(\mbox{${\bf x}$}),\ldots,f_n(\mbox{${\bf x}$})\right)\]

og gerum ráð fyrir að allar hlutafleiðurnar \(\dfrac{\partial f_k}{\partial x_j}\) séu til og séu samfelldar.

Táknum Jacobi-fylki \(\mbox{${\bf f}$}\) með \(\mbox{${\bf f}$}'\), það er

\[\begin{split}\mbox{${\bf f}$}'(\mbox{${\bf x}$}) = \begin{pmatrix} \frac{\partial f_1}{\partial x_1}(\mbox{${\bf x}$}) & \frac{\partial f_1}{\partial x_2}(\mbox{${\bf x}$}) & \cdots & \frac{\partial f_1}{\partial x_n}(\mbox{${\bf x}$}) \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1}(\mbox{${\bf x}$}) & \frac{\partial f_n}{\partial x_2}(x) & \cdots & \frac{\partial f_n}{\partial x_n}(\mbox{${\bf x}$}) \end{pmatrix}\end{split}\]

8.7.2. Aðferð Newtons fyrir hneppi

Lausn á hneppinu hér að ofan er vigur \(\mbox{${\bf r}$}\) þannig að \(\mbox{${\bf f}$}(\mbox{${\bf r}$}) =0\).

Ef \(\mbox{${\bf r}$}\) er lausn hneppisins og \(\mbox{${\bf x}$}_0 \in {\mathbb R}^n\) er upphafságiskun á \(\mbox{${\bf r}$}\) má sjá að runan \((\mbox{${\bf x}$}_n)\), þar sem

\[\mbox{${\bf x}$}_{n+1} = \mbox{${\bf x}$}_n + \mbox{${\bf h}$}_n^T\]

og \(\mbox{${\bf h}$}_n^T\) er lausn á jöfnuhneppinu

\[\mbox{${\bf f}$}'(\mbox{${\bf x}$}_n) \mbox{${\bf h}$}_n^T = -\mbox{${\bf f}$}(\mbox{${\bf x}$}_n)\]

stefnir á lausnina \(\mbox{${\bf r}$}\).

Við getum metið skekkjuna með

\[\mbox{${\bf e}$}_{n+1} \approx \| \mbox{${\bf x}$}_{n+1} - \mbox{${\bf x}$}_n \|\]

og forritið okkar helst næstum óbreytt, við þurfum aðeins að skipta abs út fyrir skipunina norm.

8.7.3. Matlab-forrit fyrir hneppi

function x = newtonNullHneppi(f,df,x0,epsilon)
%
%   x = newtonNullHneppi(f,df,x0,epsilon)
%
% Nálgar núllstöð fallsins f:Rn --> Rn með aðferð Newtons.
% Fallið df er Jacobi-fylki f, x0 er upphafságiskun
% á núllstöð og epsilon er tilætluð nákvæmni.
% x0 verður að vera dálkvigur og f verður að
% skila dálkvigrum

x = x0; mis = -df(x)\f(x);
% Ítrum meðan ástæða er til
while (norm(mis) >= epsilon)
    x = x + mis;
    mis = -df(x)\f(x);
end

Dæmi

Grafið \(y=e^x\) sker lokaða ferilinn sem gefinn er með jöfnunni \(x^4+y^2=1\) í tveimur punktum. Notið aðferð Newtons til þess að nálga hnit þeirra með 5 aukastafa nákvæmni.

Það er alveg augljóst að punkturinn \({\mathbf r}=(0,1)\) gefur lausn á jöfnuhneppinu. Við látum eins og ekkert sé og giskum á \({\mathbf x}^{(0)}=(0.5,0.75)\)

Hér er

\[\begin{split}{\bf f}({\bf x}) = \begin{bmatrix} y - e^x\\ x^4+y^2-1 \end{bmatrix}\end{split}\]

og

\[\begin{split}{\bf f'}({\bf x}) = \begin{bmatrix} -e^x & 1 \\ 4x^3 & 2y \end{bmatrix}\end{split}\]

Forritið hér að ofan gefur svo eftirfarandi töflu.

\(n\)	\(x^{(n)}\)	\(y^{(n)}\)	\(\|{\mathbf x}^{(n+1)}-{\mathbf x}^{(n)}\|\)
0	0.50000000000000	0.75000000000000
1	0.17270262414568	1.10909912528477	0.18447541668198
2	0.01946538693088	1.00638822766059	0.02028257413953
3	0.00020831857772	1.00002048613263	0.00020930163934
4	0.00000002190660	1.00000000020984	0.00000002190761
5	0.00000000000000	1.00000000000000	0.00000000000000
6	-0.00000000000000	1.00000000000000	0.00000000000000

Tökum nú fyrir hinn skurðpunktinn og notum upphafságiskun \((-0.8,0.25)\).

\(n\)	\(x^{(n)}\)	\(y^{(n)}\)	\(\|{\mathbf x}^{(n+1)}-{\mathbf x}^{(n)}\|\)
0	-0.80000000000000	0.25000000000000
1	-1.03486380522268	0.34379785380788	0.07380487278262
2	-0.96968875917544	0.37842981331349	0.00919771982977
3	-0.96137076039507	0.38235523639344	0.00014098927991
4	-0.96124395918305	0.38241687590740	0.00000003252214
5	-0.96124392995056	0.38241689016050	0.00000000000000
6	-0.96124392995055	0.38241689016050	0.00000000000000

Nálgun okkar á skurðpunkti ferlanna í vinstra hálfplaninu er \((-0.96124392995055, 0.38241689016050)\)

Í töfluna var ekki hægt að koma fyrir athugun á samleitnistiginu en hlutfallið

\[\dfrac{\|e_{n+1}\|}{\|e_n\|^2} \approx\dfrac{\|{\mathbf x}^{(n+1)}-{\mathbf x}^{(n)}\|}{\|{\mathbf x}^{(n)}-{\mathbf x}^{(n-1)}\|^2} =1.6\]

fyrir fjögur síðustu gildin.