9. Eigingildisverkefni

  • You can’t give her that! It’s not safe!
  • It’s a sword. They’re not meant to be safe.
  • She’s a child!
  • It’s educational.
  • What if she cuts herself?
  • That will be an important lesson.

– Terry Pratchett, Hogfather

9.1. Eigingildi og eiginvigrar

9.1.1. Nálgun á eigingildum og eiginvigrum

Skilgreining Látum \(A\) vera \(n\times n\) fylki. Munum að \(\lambda\in {{\mathbb C}}\) nefnist eigingildi fylkisins \(A\) ef til er \({\mbox{${\bf v}$}}\in {{\mathbb C}}^n\setminus\{{\mbox{${\bf 0}$}}\}\) þannig að

\[A{\mbox{${\bf v}$}}=\lambda{\mbox{${\bf v}$}}.\]

Vigurinn \({\mbox{${\bf v}$}}\) nefnist þá eiginvigur fylkisins \(A\) og við segjum að hann svari til eigingildisins \(\lambda\).

Athugasemd

Eigingildi fylkisins \(A\) eru nákvæmlega núllstöðvar kennimargliðunnar

\[p_A(z)=\det(zI-A), \qquad z\in {{\mathbb C}}.\]

Athugasemd

Ef \({\mbox{${\bf v}$}}\) er eiginvigur fylkisins \(A\), þá er \(\alpha {\mbox{${\bf v}$}}\) einnig eiginvigur fyrir sérhvert \(\alpha\in {{\mathbb C}}\setminus \{{\mbox{${\bf 0}$}}\}\).

9.1.2. Gróf staðsetning á eigingildum: Skífusetning Gerschgorins

Skilgreinum

\[\begin{split}r_i=\sum\limits_{{\substack{j=1 \\ j\neq i}}}^n|a_{ij}|,\end{split}\]

sem er summan af tölugildum stakanna í línu \(i\) utan hornalínunnar og látum

\[R_i=\{z\in {{\mathbb C}}\,;\, |z-a_{ii}|\leq r_i\}\]

tákna skífuna með miðju í \(a_{ii}\) og geislann \(r_i\). Þá gildir

  1. Öll eigingildi \(A\) liggja í sammengi skífanna \(R_i\).
  2. Ef \(k\) af skífunum \(R_i\) mynda samanhangandi svæði \(U\) í \({{\mathbb C}}\) sem er sundlægt við hinar \(n-k\) skífurnar, þá inniheldur \(U\) nákvæmlega \(k\) eigingildi.

9.1.3. Fylgisetning

Athugum fyrst að þar sem einingarfylkið er samhverft þá er \(\det(A^T-\lambda I) = \det(A-\lambda I)\) og þar af leiðandi eru eigingildi \(A^T\) og \(A\) þau sömu.

Með því að beita Skífusetningu Gerschgorins á fylkið \(A^T\) fæst að við getum notað skífur með geisla sem eru sumur tölugilda stakanna í hverjum dálki að hornalínunni undanskilinni. Þetta fæst af því að summa yfir línu í \(A^T\) jafngildir summu yfir dálk í \(A\).

Nánar tiltekið, ef

\[\begin{split}c_i=\sum\limits_{{\substack{j=1 \\ j\neq i}}}^n|a_{ji}|,\\ C_i=\{z\in {{\mathbb C}}\,;\, |z-a_{ii}|\leq c_i\}\end{split}\]

þá gildir að

  1. Öll eigingildi \(A\) liggja í sammengi skífanna \(C_i\).
  2. Ef \(k\) af skífunum \(C_i\) mynda samanhangandi svæði \(U\) í \({{\mathbb C}}\) sem er sundlægt við hinar \(n-k\) skífurnar, þá inniheldur \(U\) nákvæmlega \(k\) eigingildi.

9.1.4. Dæmi: Setning Gerschgorins

9.1.5. Eiginvigragrunnar

Nokkrar staðreyndir um eigingildi og eiginvigra:

  1. Eiginvigrar sem svara til ólíkra eigingilda eru línulega óháðir.

  2. Eiginvigrar sem svara til eins ákveðins eigingildis \(\lambda\) spanna hlutrúm í \({{\mathbb C}}^n\).

  3. Við segjum að fylkið \(A\)hornalínugeranlegt ef til eru eigingildi \(\lambda_1,\lambda_2,\dots,\lambda_n\) og tilsvarandi eiginvigrar \({\mbox{${\bf v}$}}_1,{\mbox{${\bf v}$}}_2,\dots,{\mbox{${\bf v}$}}_n\) sem mynda grunn í \({{\mathbb R}}^n\).Þá er hægt að skrifa

    \[A=T\Lambda T^{-1}\]

    þar sem \(\Lambda\) er hornalínufylki með eigingildin \(\lambda_1,\dots,\lambda_n\) á hornalínunni og \(T\) er \(n\times n\) fylki þannig að dálkur nr. \(k\) í því samanstendur af hnitum \({\mbox{${\bf v}$}}_k\) miðað við staðalgrunninn í \({{\mathbb R}}^n\).

  4. Ef fylkið \(A\) er samhverft, þá er það hornalínugeranlegt.

9.2. Veldaaðferð

9.2.1. Veldaaðferð

Hugsum okkur nú að við \(A\) sé hornalínugeranlegt og að við röðum eigingildunum á hornalínu \(\Lambda\) í minnkandi röð eftir tölugildi

\[|\lambda_1|\geq |\lambda_2|\geq \cdots\geq |\lambda_n|\]

Tökum einhvern vigur \({\mbox{${\bf x}$}}^{(0)}\) og lítum á liðun hans í eiginvigra

\[{\mbox{${\bf x}$}}^{(0)}=\alpha_1{\mbox{${\bf v}$}}_1+\cdots+\alpha_n{\mbox{${\bf v}$}}_n\]

Skilgreinum síðan rununa \(\big({\mbox{${\bf x}$}}^{(m)}\big)\) með ítruninni

\[{\mbox{${\bf x}$}}^{(m)}=A{\mbox{${\bf x}$}}^{(m-1)}.\]

Við fáum þá

\[\begin{split}\begin{aligned} {\mbox{${\bf x}$}}^{(1)} =A{\mbox{${\bf x}$}}^{(0)}&=\alpha_1A{\mbox{${\bf v}$}}_1+\cdots+\alpha_nA{\mbox{${\bf v}$}}_n\\ &=\alpha_1\lambda_1{\mbox{${\bf v}$}}_1+\cdots+\alpha_n\lambda_n{\mbox{${\bf v}$}}_n,\end{aligned}\end{split}\]
\[\begin{split}\begin{aligned} {\mbox{${\bf x}$}}^{(2)}=A{\mbox{${\bf x}$}}^{(1)}&=\alpha_1\lambda_1A{\mbox{${\bf v}$}}_1+\cdots+\alpha_n\lambda_nA{\mbox{${\bf v}$}}_n,\\ &=\alpha_1\lambda_1^2{\mbox{${\bf v}$}}_1+\cdots+\alpha_n\lambda_n^2{\mbox{${\bf v}$}}_n\\ \vdots & \\ {\mbox{${\bf x}$}}^{(m)}&=\alpha_1\lambda_1^m{\mbox{${\bf v}$}}_1+\cdots+\alpha_n\lambda_n^m{\mbox{${\bf v}$}}_n\end{aligned}\end{split}\]

Síðasti vigurinn gefur \({\bf x}^{(m)} = A^m {\bf x}^{(0)}\)

\[{\mbox{${\bf x}$}}^{(m)}= \lambda_1^m \big(\alpha_1{\mbox{${\bf v}$}}_1+(\lambda_2/\lambda_1)^m\alpha_2{\mbox{${\bf v}_2$}}_+\cdots+ (\lambda_n/\lambda_1)^m \alpha_n{\mbox{${\bf v}$}}_n\big)\]

Hnit númer \(i\) í þessum vigri er:

\[x_i^{(m)}= \lambda_1^m \big(\alpha_1v_{1,i}+(\lambda_2/\lambda_1)^m\alpha_2v_{2,i}+\cdots+ (\lambda_n/\lambda_1)^m \alpha_nv_{n,i}\big)\]

Hugsum okkur nú að \(|\lambda_1|>|\lambda_2|\). Þá fæst:

\[\dfrac{x_i^{(m)}}{x_i^{(m-1)}} = \dfrac{\lambda_1^m\big(\alpha_1v_{1,i}+O((\lambda_2/\lambda_1)^m)\big)} {\lambda_1^{m-1}\big(\alpha_1v_{1,i}+O((\lambda_2/\lambda_1)^{m-1})\big)}\]

Ef við höfum \(\alpha_1v_{1,i}\neq 0\), þá er niðurstaðan

\[\dfrac{x_i^{(m)}}{x_i^{(m-1)}} =\lambda_1 \dfrac{\big(1+O((\lambda_2/\lambda_1)^m)\big)} {\big(1+O((\lambda_2/\lambda_1))^{m-1}\big)} \to \lambda_1 \quad \text{ þegar } \quad m\to \infty.\]

Skoðum aftur

\[{\mbox{${\bf x}$}}^{(m)}= \lambda_1^m \big(\alpha_1{\mbox{${\bf v}$}}_1+(\lambda_2/\lambda_1)^m\alpha_2{\mbox{${\bf v}$}}_2+\cdots+ (\lambda_n/\lambda_1)^m \alpha_n{\mbox{${\bf v}$}}_n\big)\]

Ef \(|\lambda_1|>|\lambda_2|\), þá gildir fyrir \(j > 1\)\((\lambda_j/\lambda_1)^m \to 0\) þegar \(m \to \infty\) og

\[\lim_{m\to \infty} \frac{{\mbox{${\bf x}$}}^{(m)}}{\lambda_1^m} = \alpha_1 {\mbox{${\bf v}$}}_1.\]

Þannig að ef \({\mbox{${\bf x}$}}^{(0)}\) var valinn í upphafi þannig að \(\alpha_1 \neq 0\), þá skilar þetta eiginvigrinum \(\alpha_1{\mbox{${\bf v}$}}_1\) fyrir eigingildið \(\lambda_1\).

9.2.2. Reiknirit til þess að ákvarða stærsta eigingildi fylkis

Þegar við reiknum \({\mbox{${\bf x}$}}^{m}\) eins og hér að framan þá er ekki ólíklegt að við lendum í undir- eða yfirflæðisvillum ef lengd \({\mbox{${\bf x}$}}\) (skv. einhverjum staðli) stefnir á 0 eða \(+\infty\). Til þess að ráða bót á þessu þá stöðlum við vigurinn í hverju skrefi með \(\ell_\infty\) staðlinum á eftirfarandi hátt.

Við veljum \({\mbox{${\bf x}$}}^{(0)}\) með einhverjum hætti og skilgreinum síðan

\[{\bf x}^{(m)} = \frac{A{\bf x}^{(m-1)}}{\|A{\bf x}^{(m-1)}\|_\infty}.\]

Þetta jafngildir því að setja

\[{\mbox{${\bf y}$}}^{(m)}=A{\mbox{${\bf x}$}}^{(m-1)}, \quad \text{ og svo } \quad {\mbox{${\bf x}$}}^{(m)}=\dfrac{{\mbox{${\bf y}$}}^{(m)}}{y_{p_m}^{(m)}} \qquad\]

þar sem \(p_m\) er númerið á því hniti í vigrinum \({\mbox{${\bf y}$}}^{(m)}\) sem hefur stærst tölugildi, það er hnit \(p_m\) uppfyllir

\[\|A{\bf x}^{m-1}\| = |y_{p_m}^{(m)}|=\|{\mbox{${\bf y}$}}^{(m)}\|_\infty=\max_{1\leq j\leq n}|y_j^{(m)}|.\]

Ef mörg númer uppfylla þetta skilyrði, þá tökum við bara \(p_m\) sem lægsta gildið á \(j\) þar sem jafnaðarmerki gildir (það skiptir ekki máli fyrir nálgunina á hvaða \(j\) við veljum).

Þá fæst að

\[\begin{split}\begin{aligned} {\bf x}^{(m)} =& \frac{A{\bf x}^{(m-1)}}{y_{p_m}^{(m)}} \\ =& \frac{A^2{\bf x}^{(m-2)}}{y_{p_m}^{(m)} \ y_{p_{m-1}}^{(m-1)}}\\ =& \frac{A^3{\bf x}^{(m-3)}}{y_{p_m}^{(m)} \ y_{p_{m-1}}^{(m-1)} \ y_{p_{m-2}}^{(m-2)}}\\ \vdots & \\ =& \frac{A^m{\bf x}^{(0)}}{y_{p_m}^{(m)} \ \dots \ y_{p_{1}}^{(1)}} \end{aligned}\end{split}\]

Með því að skrifa \(A^m{\bf x}^{(0)}\) með eiginvigrum eins og hér fyrir ofan

\[{\mbox{${\bf x}$}}^{(m)}= \lambda_1^m \big(\alpha_1{\mbox{${\bf v}$}}_1+(\lambda_2/\lambda_1)^m\alpha_2{\mbox{${\bf v}_2$}}_+\cdots+ (\lambda_n/\lambda_1)^m \alpha_n{\mbox{${\bf v}$}}_n\big)\]

þá fæst

\[{\bf x}^{(m)} = \frac{\lambda_1^m}{|y_{p_m}^{(m)}| \ \dots \ |y_{p_{1}}^{(1)}|} \big(\alpha_1{\mbox{${\bf v}$}}_1+(\lambda_2/\lambda_1)^m\alpha_2{\mbox{${\bf v}_2$}}_+\cdots+ (\lambda_n/\lambda_1)^m \alpha_n{\mbox{${\bf v}$}}_n\big)\]

Stuðlarnir við \({\bf v}_2,\ldots,{\bf v}_n\) stefna allir á 0 þannig að það er ljóst að \({\bf x}^{(m)}\) stefnir á eiginvigur sem tilheyrir \(\lambda_1\). Nánar tiltekið stefnir \({\bf x}^{(m)}\) á eiginvigur sem hefur lengdina 1 í \(\ell_\infty\) staðlinum, samkvæmt skilgreiningunni á \({\bf x}^{(m)}\).

Þar sem \({\bf x}^{(m)}\) er um það bil eiginvigur þá er \({\bf y}^{(m)} = A{\bf x}^{(m-1)} \approx \lambda_1 {\bf x}^{(m-1)}\) sem segir okkur að ef við veljum \(p_{m-1}\)-ta hnitið úr jöfnunni þá fæst

\[y_{p_{m-1}}^{(m)} \approx \lambda_1\]

því \(p_{m-1}\)-ta hnitið í \({\bf x}^{(m-1)}\) er 1.

9.2.3. Samleitni

Nú kemur í ljós að \(y_{p_{m-1}}^{(m)}\) stefnir á \(\lambda_1\). Auk þess stefnir \({\mbox{${\bf x}$}}^{(m)}\) á eiginvigur sem svarar til \(\lambda_1\) og hefur lengdina \(1\) í \(l_\infty\) staðlinum.

Í útreikningum skilgreinum við því rununa \(\lambda^{(m)}=y_{p_{m-1}}^{(m)}\). Við gefum okkur síðan þolmörk á skekkju \(TOL\) og reiknum úr runurnar þar til eitt af stoppskilyrðunum gildir:

\[\begin{split}\begin{aligned} |\lambda^{(m)}-\lambda^{(m-1)}|&<TOL \qquad \text{ eða } \\ \|{\mbox{${\bf x}$}}^{(m)}-{\mbox{${\bf x}$}}^{(m-1)}\|&<TOL \qquad \text { eða } \\ \|A{\mbox{${\bf x}$}}^{(m)}-\lambda^{(m)}{\mbox{${\bf x}$}}^{(m)}\|&<TOL.\end{aligned}\end{split}\]

9.2.4. Samhverf fylki

Munum að ef \(A\) er samhverft, þá hefur \(A\) eiginvigragrunn og eiginvigra sem svara til ólíkra eigingilda eru hornréttir.

Í þessu tilfelli er einfaldara að smíða reiknirit svona:

\[\begin{split}\begin{aligned} {\mbox{${\bf y}$}}^{(m)}&=A{\mbox{${\bf x}$}}^{(m-1)}\\ \lambda^{(m)}&={{\mbox{${\bf x}$}}^{(m-1)}}^T{\mbox{${\bf y}$}}^{(m)}\\ {\mbox{${\bf x}$}}^{(m)}&= \frac{{\mbox{${\bf y}$}}^{(m)}}{\sqrt{({\mbox{${\bf y}$}}^{(m)})^T{\mbox{${\bf y}$}}^{(m)}}}\end{aligned}\end{split}\]

Samleitnin verður sú sama: \(\lambda^{(m)}\) stefnir á stærsta eigingildið og \({\mbox{${\bf x}$}}^{(m)}\) stefnir á tilsvarandi eiginvigur.

9.2.5. Setning um eigingildi og eiginvigra

Látum sem fyrr \(A\) vera \(n\times n\) fylki, \(\lambda_1,\dots,\lambda_n\) vera eigingildi og \({\mbox{${\bf v}$}}_1,\dots,{\mbox{${\bf v}$}}_n\) vera tilsvarandi eiginvigra.

  1. Látum \(p(x)=a_0+a_1x+\cdots+a_mx^m\) vera margliðu og skilgreinum \(n\times n\) fylkið \(B\) með því að stinga \(A\) inn í \(p\),

    \[B=p(A)=a_0I+a_1A+\cdots+a_mA^m\]

    Þá eru tölurnar \(p(\lambda_1),\dots,p(\lambda_n)\) eigingildi fylkisins \(B=p(A)\) með tilsvarandi eiginvigrum \({\mbox{${\bf v}$}}_1,\dots,{\mbox{${\bf v}$}}_n\).

  2. Ef \(A\) er andhverfanlegt þá eru \(1/\lambda_1,\dots,1/\lambda_n\) eigingildi \(A^{-1}\) með tilsvarandi eiginvigrum \({\mbox{${\bf v}$}}_1,\dots,{\mbox{${\bf v}$}}_n\).

9.2.6. Dæmi um veldaaðferð

Sjá vikublað 14.

9.3. Andhverf veldaaðferð

Af síðustu setningu leiðir að fylkið \(B=(A-qI)^{-1}\) hefur eigingildin

\[\mu_1=\dfrac 1{\lambda_1-q},\ \mu_2=\dfrac 1{\lambda_2-q},\ \cdots \ \mu_n=\dfrac 1{\lambda_n-q}.\]

Hugsum okkur nú að við viljum finna nálgunargildi fyrir eigingildið \(\lambda_k\) og að við vitum út frá setningu Gerschgorins skífunum nokkurn veginn hvar það er staðsett.

Ef við erum með \(q\) nógu nálægt \(\lambda_k\), þá verður \(\mu_k\) stærsta eigingildi fylkisins \(B=(A-qI)^{-1}\)

Þá getum við beitt veldaaðferðinni til þess að búa til runu \(\mu^{(m)}\to \mu_k\) og við fáum að

\[\lambda^{(m)}=\dfrac 1{\mu^{(m)}}+q\to \lambda_k.\]

Ef veldaaðferðinni er beitt á fylkið \(B=(A-qI)^{-1}\) þá þurfum við að reikna út \({\mbox{${\bf y}$}}^{(m)}=(A-qI)^{-1}{\mbox{${\bf x}$}}^{(m-1)}\) í hverju skrefi.

Þetta er gert þannig að fyrst framkvæmum við \(LU\)-þáttun á fylkinu \(LU=(A-qI)\) og framkvæmum síðan for- og endurinnsetningu til þess að leysa \(LU{\mbox{${\bf y}$}}^{(m)}=x^{(m-1)}\).

En tölulegar aðferðir fyrir LU-þáttun skoðuðum við í kafla 8.2.

9.3.1. Reiknirit til þess að nálga eigingildi og eiginvigra

Takmarkið er að finna nálgun á eigingildinu \(\lambda_k\).

  1. Finnum \(q\in {{\mathbb R}}\) sem liggur næst eigingildinu \(\lambda_k\) af öllum eigingildum \(A\)

  2. Þáttum \(LU=A-qI\).

  3. Við veljum \({\mbox{${\bf x}$}}^{(0)}\) með einhverjum hætti og leysum síðan \({\mbox{${\bf y}$}}^{(m)}\) út úr jöfnunni

    \[LU{\mbox{${\bf y}$}}^{(m)}={\mbox{${\bf x}$}}^{(m-1)}.\]
  4. Skilgreinum \({\mbox{${\bf x}$}}^{(m)}={{\mbox{${\bf y}$}}^{(m)}}/{y_{p_m}^{(m)}}\) þar sem \(p_m\) er númerið á því hniti í \({\mbox{${\bf y}$}}^{(m)}\) sem hefur stærst tölugildi, sem þýðir að það hnit uppfyllir

    \[|y_{p_m}^{(m)}|=\|{\mbox{${\bf y}$}}^{(m)}\|_\infty=\max_{1\leq j\leq n}|y_j^{(m)}|.\]

    Ef mörg númer uppfylla þetta skilyrði, þá tökum við bara \(p_m\) sem lægsta gildið á \(j\) þar sem jafnaðarmerki gildir.

Niðurstaðan verður að

\[\lambda^{(m)}=\dfrac 1{y_{p_{m-1}}^{(m)}}+q \to \lambda_k\]

og \({\mbox{${\bf x}$}}^{(m)}\) stefnir á tilsvarandi eiginvigur.

9.3.2. Dæmi um öfuga veldaaðferð

Sjá vikublað 14.