NumMod 1 het 13

date: 2024.05.13

Sajátérték-feladatok közelítő megoldása

Emlék: Azt mondjuk, hogy az $A\in {\mathbb{C}}^{n\times n}$ mátrixnak a $\lambda \in \mathbb{C}$ szám sajátértéke, ha $\exists \underline{v}\in {\mathbb{C}}^n,\underline{v}\ne \underline{0}$ úgy, hogy $A\underline{v}=\lambda \underline{v}$. Ekkor $\underline{v}$ neve: sajátvektor.

Jelölje $\sigma (A)$ az $A$ mátrix sajátértékeinek a halmazát.

$$\lambda \in \sigma (A)⟺\det (A-\lambda I)=0$$

A fenti egyenletnek a jobboldalát a karakteriszikus egyenletnek hívjuk, ami egy $n$-ed fokú egyenlet. Ha $n>4$, akkor nem létezik már megoldóképlet. Tehát ha $n>4$, akkor iterációs módszert kell felépítenünk és így csak közelítő megoldást kapunk.

Az egyszerűség kedvéért a továbbiakban feltesszük, hogy minden a valós számok fölött van. A komplex számokra a kiterjesztést egyszerűen meg lehet oldani, ha már a valósokra tudjuk a dolgokat.

Először tegyük fel, hogy ismerjük az $A\in {\mathbb{R}}^{n\times n}$ mátrix $\underline{v}$ sajátvektorának egy közelítését: $\tilde{\underline{v}}$. Ekkor, hogyan tudjuk meghatározni a hozzátartozó $\lambda$ sajátértéket?

1. lehetőség: $A\tilde{\underline{v}}\approx \lambda \tilde{\underline{v}}$

$$\left[\begin{array}{c}A\end{array}\right]\cdot \left[\begin{array}{c}\widetilde{v_1}\\ \widetilde{v_2}\\ ⋮\\ \widetilde{v_n}\end{array}\right]\approx \lambda \cdot \left[\begin{array}{c}\widetilde{v_1}\\ \widetilde{v_2}\\ ⋮\\ \widetilde{v_n}\end{array}\right]$$

ezzel ekvivalens a következő

$$a_{i1}\cdot {\tilde{v}}_1+a_{i2}\cdot {\tilde{v}}_2+\dots a_{in}\cdot {\tilde{v}}_n=\lambda \cdot {\tilde{v}}_{i}i=1,\dots ,n$$

Ha ${\tilde{v}}_i\ne 0$ akkor $\lambda$ az $i$. egyenletből kifejezhető ($\tilde{v}\ne 0⟹$ legfeljebb egy $i$-re ${\tilde{v}}_i\ne 0$)

Vagy: a többiből/összesből kifejezve átlagolunk

2. lehetőség: $A\tilde{\underline{v}}\approx \lambda \tilde{\underline{v}}$
   Szorozzuk meg mindkét oldalt skalárisan $\tilde{\underline{v}}$-al. Ekkor a következőt kapjuk:

$$(\tilde{\underline{v}},A\tilde{\underline{v}})\approx \lambda (\tilde{\underline{v}},\tilde{\underline{v}})$$ $$\lambda \approx \frac{(\tilde{\underline{v}},A\tilde{\underline{v}})}{(\tilde{\underline{v}},\tilde{\underline{v}})}$$

Kérdés: Melyiket alkalmasabb használni a fenti két lehetőségből?

Állítás

Legyen $\underline{x}\in {\mathbb{R}}^n,\underline{x}\ne \underline{0},A\in {\mathbb{R}}^{n\times n}$ Ekkor

$$\underset{\alpha \in \mathbb{R}}{\min }\Vert A\underline{x}-\alpha \underline{x}{\Vert }_2^2=\Vert A\underline{x}-R(\underline{x})\cdot \underline{x}{\Vert }_2^2$$

ahol $R(\underline{x})$ a következő kifejezés

$$R(\underline{x})=\frac{(\underline{x},A\underline{x})}{(\underline{x},\underline{x})}$$

Bizonyítás:

$$\Vert A\underline{x}-\alpha \cdot \underline{x}{\Vert }_2^2=(A\underline{x}-\alpha \cdot \underline{x},A\underline{x}-\alpha \cdot \underline{x})=(A\underline{x},A\underline{x})-2\alpha (\underline{x},A\underline{x})+{\alpha }^2(\underline{x},\underline{x})$$

Ez a kifejezés $\alpha$-ban egy másodfokú polinoma, azaz egy parabola. Mivel $(\underline{x},\underline{x})$ a főeggyütható, amely nem mindig pozitív, mert $\underline{x}\ne 0$, ezért ennek a másodfokú polinomnak minimuma van, ami ott felvétetik, ahol a deriváltja $0$.

Deriváljunk $\alpha$ szerint:

$$-2(\underline{x},A\underline{x})+2\alpha (\underline{x},\underline{x})=0$$ $$⟹\alpha =\frac{(\underline{x},A\underline{x})}{(\underline{x},\underline{x})}$$

Definíció

Legyen $\underline{x}\in {\mathbb{R}}^n,x\ne \underline{0},A\in {\mathbb{R}}^{n\times n}$. Ekkor a következő számot az $\underline{x}$ vektorhoz tartozó Rayleigh-hányadosnak nevezzük:

$$R(\underline{x})=\frac{(\underline{x},A\underline{x})}{(\underline{x},\underline{x})}$$

Megjegyzés: Ha $\Vert \underline{x}{\Vert }_2=1$, akkor $R(\underline{x})=(\underline{x},A\underline{x})$, mert $(\underline{x},\underline{x})=\Vert \underline{x}{\Vert }^2=1^2=1$.

Következmény: Ha $\tilde{\underline{v}}\approx \underline{v}$, akkor a $\underline{v}$-hoz tartozó sajátértéket $R(\tilde{\underline{v}})$-vel érdemes kövezelíteni.

A hatványmódszer

A gyakorlatban általában nem tudjuk egyik sajátvektort sem, akár közelítőleg sem és így kell meghatároznunk a sajátvektorokat és sajátértékeket.

Legyen $A\in {\mathbb{R}}^{n\times n}$ ${\lambda }_i\in \mathbb{R}$ $(i=1,\dots ,n)$ sajátértékekkel. Tegyük fel, hogy $A$-nak van egyszeresen domináns sajátértéke, azaz

$$|{\lambda }_1|>|{\lambda }_2|\ge |{\lambda }_3|\ge |{\lambda }_4|\ge \cdots \ge |{\lambda }_n|$$

A következő módszer, amit bemutatunk ennek az egyszeresen domináns ${\lambda }_1$ sajátértéknek a meghatorázására fog szolgálni.

Tegyük fel, hogy $A$ normális, azaz kommutál a transzponáltjával, vagy komplex esetben az adjungáltjával, azaz $A\cdot A^T=A^T\cdot A$. Ekkor van ortonormált sajátvektorendszere. Azaz lehet mondani $n$ darab sajátvektort, melyekre mindegyik hossza $1$ és páronként egymásra merőlegesek.

$${\underline{v}}_1,{\underline{v}}_2,\dots ,{\underline{v}}_n$$

ahol ${\lambda }_i$ sajátértékhez tartozó sajátvektor a ${\underline{v}}_i$

Legyen $\underline{x}\in {\mathbb{R}}^n$ olyan kezdővektor, amelynek van ${\underline{v}}_1$ irányú komponense, azaz a következő előállításban ${\alpha }_1\ne 0$

$$\underline{x}={\alpha }_1\cdot {\underline{v}}_1+{\alpha }_2\cdot {\underline{v}}_2+\cdots +{\alpha }_n\cdot {\underline{v}}_n$$ $$\begin{array}{rl}{A}^k\underline{x}& =A^k({\alpha }_1\cdot {\underline{v}}_1+{\alpha }_2\cdot {\underline{v}}_2+\cdots +{\alpha }_n\cdot {\underline{v}}_n)\\ & ={\alpha }_1\cdot A^k{\underline{v}}_1+{\alpha }_2\cdot A^k{\underline{v}}_2+\cdots +{\alpha }_n\cdot A^k{\underline{v}}_n\\ & ={\alpha }_1\cdot {\lambda }_1^k{\underline{v}}_1+{\alpha }_2\cdot {\lambda }_2^k{\underline{v}}_2+\cdots +{\alpha }_n\cdot {\lambda }_n^k{\underline{v}}_n\\ & ={\lambda }_1^k\left({\alpha }_1\cdot {\underline{v}}_1+{\alpha }_2\cdot {\left(\frac{{\lambda }_2}{{\lambda }_1}\right)}^k{\underline{v}}_2+\cdots +{\alpha }_n\cdot {\left(\frac{{\lambda }_n}{{\lambda }_1}\right)}^k{\underline{v}}_n\right)\end{array}$$

Mivel ${\lambda }_1$ a legnagyobb abszolútértékben, ezért a $\left(\frac{{\lambda }_i}{{\lambda }_1}\right)$ kifejezések egyre kisebbek abszolútértékben, ezért a $k$-adik hatványik tart $0$-hoz, ha $k$-val tartunk $\infty$-hez.

Ha $k$-t növeljük, akkor $A^k\underline{x}$ vektor egyre inkább a ${\underline{v}}_1$ vektor irányába fog mutatni. Tehát egyre jobb közelítése lesz egy ${\lambda }_1$-hez tartozó sajátvektornak.

Ha ${\lambda }_1\ne \pm 1$ akkor ${\lambda }_1^k\to 0$ vagy $\infty$-hez tehát számítógépen előbbútóbb alul- vagy túlcsordulás fog fellépni. Elkerülésére a kapott vektort minden lépésben normáljuk. Jelölésben ${\underline{y}}^{(k)}$

A megfelelő sajátértéke közelítése:

$${\nu }^{(k)}:=R({\underline{y}}^{(k)})=({\underline{y}}^{(k)},A{\underline{y}}^{(k)})$$

Kérdés: Hogyan lehet meghatározni egyéb sajátértékeket és sajátvektorokat?

például: A legkisebb abszolót értékűt?

Emlék: Tegyük fel, hogy $0\notin \sigma (A)$, azaz invertálható az $A$ mátrix, ekkor $\frac{1}{\lambda }\in \sigma (A^{-1})$ mivel

$$\lambda \in \sigma (A)⟹\exists \underline{x}\ne \underline{0}$$ $$\begin{array}{rl}A\underline{x}& =\lambda \underline{x}\\ \underline{x}& =\lambda A^{-1}\underline{x}\\ \frac{1}{\lambda }\underline{x}& =A^{-1}\underline{x}\end{array}$$ $$|\lambda |\ge |{\lambda }_2|\ge \cdots \ge |{\lambda }_n|⟹\left|\frac{1}{{\lambda }_n}\right|\ge \cdots \ge \left|\frac{1}{l_1}\right|$$

Tehát ${\lambda }_n$ meghatározható, ha $A^{-1}$ mátrixra alkalmazzuk a hatványmódszert, mivel $A^{-1}$ domináns sajátértéke $\frac{1}{{\lambda }_n}$

Kérdés: És a többi sajátértéket hogyan határozzuk meg?

Tegyük fel, hogy $\mu \notin \sigma (A)$. Ekkor $\det (A-\mu I)\ne 0⟹\exists (A-\mu I{)}^{-1}$

Legyen $\underline{x}$ sajátvektora $A$-nak, tehát

$$A\underline{x}={\lambda }_i\underline{x}⟹(A-\mu I)\underline{x}=A\underline{x}-\mu \underline{x}={\lambda }_i\underline{x}-\mu \underline{x}=({\lambda }_i-\mu )\underline{x}$$

Tehát ha van egy $\underline{x}$ sajátvektor ${\lambda }_i$ sajátértékkel, akkor $\underline{x}$ sajátvektroa $(A-\mu I)$ mátrixnak is $({\lambda }_i-\mu )$ sajátértékkel.

Tehát a $(A-\mu I{)}^{-1}$ mátrix sajétértékeit: $\frac{1}{{\lambda }_i-\mu }$ ahol $i=1,\dots ,n$

Tegyük fel, hogy $A$-nak a $\mu$-höz legközelebbi sajátértéke ${\lambda }_j$. Ekkor az $(A-\mu I{)}^{-1}$ mátroxnak a domináns sajátértéke a következő

$$\frac{1}{{\lambda }_j-\mu }$$

Ezt a domináns sajátértéket már meg tudjuk találni a hatványmódszerrel, ha az $(A-\mu I{)}^{-1}$ mátrixra alkalmazzuk. Ezt a módszert inverz iterációnak nevezik.

Kérdés: Mennyire számításigényes a fenti módszer?

A $k.$ lépésben

$${\underline{x}}^{(k)}=(A-\mu I{)}^{-1}{\underline{y}}^{(k-1)}\leftrightarrow (A-\mu I){\underline{x}}^{(k)}={\underline{y}}^{(k-1)}$$

A fenti egy lináris algebrai egyenletrendszer, amire már tanultunk megoldási módszereket.

related: NumMod 1