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

Öll eigingildi $A$ liggja í sammengi skífanna $R_i$.
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ð

Öll eigingildi $A$ liggja í sammengi skífanna $C_i$.
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. Eiginvigragrunnar

Nokkrar staðreyndir um eigingildi og eiginvigra:

Eiginvigrar sem svara til ólíkra eigingilda eru línulega óháðir.
Eiginvigrar sem svara til eins ákveðins eigingildis $\lambda$ spanna hlutrúm í ${{\mathbb C}}^n$.
Við segjum að fylkið $A$ sé 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$.
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$ að $(\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.

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$.
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$.

Finnum $q\in {{\mathbb R}}$ sem liggur næst eigingildinu $\lambda_k$ af öllum eigingildum $A$
Þáttum $LU=A-qI$.
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)}.\]
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.