Lineaire Algebra – Eigenwaarden en eigenvectoren – Iteratieve benaderingen van eigenwaarden

We bestuderen twee iteratieve methoden voor het benaderen van de eigenwaarden van een matrix. De eerste methode is de machtmethode en de tweede is de inverse machtmethode. De tweede methode maakt gebruik van de eerste.

De machtmethode kan worden gebruikt om een strikt dominante eigenwaarde \(\lambda_1\) van een \(n\times n\) matrix \(A\) te vinden. Een eigenwaarde \(\lambda_1\) heet een (strikt) dominante eigenwaarde als deze in absolute waarde (strikt) groter is dan de andere eigenwaarden. Neem aan dat \(A\) diagonaliseerbaar is waaruit volgt dat er een basis \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) van \(\mathbb{R}^n\) bestaat geheel bestaande uit eigenvectoren van \(A\) behorende bij de eigenwaarden \(\lambda_1,\ldots,\lambda_n\) respectievelijk, waarbij

\[|\lambda_1| > |\lambda_2|\geq|\lambda_3|\geq\cdots\geq|\lambda_n|.\]

Dus, \(\lambda_1\) is een strikt dominante eigenwaarde van \(A\). Omdat \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) een basis is van \(\mathbb{R}^n\), kan elke vector \(\mathbf{x}\in\mathbb{R}^n\) geschreven worden als een lineaire combinatie van deze eigenvectoren: \(\mathbf{x}=c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n\). Omdat \(A\mathbf{v}_k=\lambda_k\mathbf{v}_k\) voor \(k=1,2,\ldots,n\) volgt hieruit dat

\[A^k\mathbf{x}=c_1\lambda_1^k\mathbf{v}_1+c_1\lambda_2^k\mathbf{v}_2+\cdots+c_n\lambda_n^k\mathbf{v}_n,\quad k=0,1,2,\ldots.\]

Deling door \(\lambda_1^k\) leidt nu tot

\[\frac{1}{\lambda_1^k}A^k\mathbf{x}=c_1\mathbf{v}_1+c_2\left(\frac{\lambda_2}{\lambda_1}\right)^k\mathbf{v}_2+\cdots+c_n\left(\frac{\lambda_n}{\lambda_1}\right)^k\mathbf{v}_n, \quad k=0,1,2,\ldots.\]

Nu geldt \(\left|\lambda_i/\lambda_1\right| < 1\) voor \(i=2,3,\ldots,n\) en dus \(\displaystyle\frac{1}{\lambda_1^k}A^k\mathbf{x}\to c_1\mathbf{v}_1\) voor \(k\to\infty\).

Deze observatie leidt tot het volgende algoritme (details laten we achterwege):

1. Kies een startvector \(\mathbf{x}_0\) waarvan het (in absolute waarde) grootste element gelijk is aan \(1\).


2. Voor \(k=0,1,2,\ldots\)
1. Bereken \(A\mathbf{x}_k\),


2. Laat \(\mu_k\) een element in \(A\mathbf{x}_k\) zijn, die in absolute waarde het grootst is,


3. Bereken \(\mathbf{x}_{k+1}=\displaystyle\frac{1}{\mu_k}A\mathbf{x}_k\).
3. Voor bijna alle keuzes van \(\mathbf{x}_0\), nadert de rij \(\{\mu_k\}\) naar de dominante eigenwaarde en nadert de rij \(\{\mathbf{x}_k\}\) naar een bijbehorende eigenvector.

Voorbeeld: De matrix \(A=\begin{pmatrix}1&4\\-4&11\end{pmatrix}\) heeft de eigenwaarden \(\lambda_1=9\) en \(\lambda_2=3\) met eigenruimtes \(\text{E}_9=\text{Span}\left\{\begin{pmatrix}1\\2\end{pmatrix}\right\}\) en \(\text{E}_3=\text{Span}\left\{\begin{pmatrix}2\\1\end{pmatrix}\right\}\).

Stel \(\mathbf{x}_0=\begin{pmatrix}1\\0\end{pmatrix}\), dan leidt het algoritme tot

\[A\mathbf{x}_0=\begin{pmatrix}1&4\\-4&11\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}1\\-4\end{pmatrix} \quad\Longrightarrow\quad\mu_0=-4\quad\text{and}\quad\mathbf{x}_1=\begin{pmatrix}-0.25\\1\end{pmatrix},\] \[A\mathbf{x}_1=\begin{pmatrix}1&4\\-4&11\end{pmatrix}\begin{pmatrix}-0.25\\1\end{pmatrix}=\begin{pmatrix}3.75\\12\end{pmatrix} \quad\Longrightarrow\quad\mu_1=12\quad\text{and}\quad\mathbf{x}_2=\begin{pmatrix}0.3125\\1\end{pmatrix},\] \[A\mathbf{x}_2=\begin{pmatrix}1&4\\-4&11\end{pmatrix}\begin{pmatrix}0.3125\\1\end{pmatrix}=\begin{pmatrix}4.3125\\9.75\end{pmatrix} \quad\Longrightarrow\quad\mu_2=9.75\quad\text{and}\quad\mathbf{x}_3\approx\begin{pmatrix}0.44231\\1\end{pmatrix},\] \[A\mathbf{x}_3=\begin{pmatrix}1&4\\-4&11\end{pmatrix}\begin{pmatrix}0.44231\\1\end{pmatrix}=\begin{pmatrix}4.44231\\9.231\end{pmatrix} \quad\Longrightarrow\quad\mu_2\approx9.231\quad\text{and}\quad\mathbf{x}_4\approx\begin{pmatrix}0.448125\\1\end{pmatrix}.\]

Hoewel de convergentie vrij traag is geldt dat: \(\lim\limits_{k\to\infty}\mu_k=9\) en \(\lim\limits_{k\to\infty}\mathbf{x}_k=\begin{pmatrix}0.5\\1\end{pmatrix}\).

De convergentie kan iets worden versneld als we de startvector wat beter in de richting van deze eigenvector kiezen. Bijvoorbeeld, als \(\mathbf{x}_0=\begin{pmatrix}0\\1\end{pmatrix}\), dan volgt:

\[A\mathbf{x}_0=\begin{pmatrix}1&4\\-4&11\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix}=\begin{pmatrix}4\\11\end{pmatrix} \quad\Longrightarrow\quad\mu_0=11\quad\text{and}\quad\mathbf{x}_1\approx\begin{pmatrix}0.364\\1\end{pmatrix},\] \[A\mathbf{x}_1=\begin{pmatrix}1&4\\-4&11\end{pmatrix}\begin{pmatrix}0.364\\1\end{pmatrix}=\begin{pmatrix}4.364\\9.55\end{pmatrix} \quad\Longrightarrow\quad\mu_1\approx9.55\quad\text{and}\quad\mathbf{x}_2\approx\begin{pmatrix}0.457\\1\end{pmatrix},\] \[A\mathbf{x}_2=\begin{pmatrix}1&4\\-4&11\end{pmatrix}\begin{pmatrix}0.457\\1\end{pmatrix}=\begin{pmatrix}4.457\\9.171\end{pmatrix} \quad\Longrightarrow\quad\mu_2\approx9.171\quad\text{and}\quad\mathbf{x}_3\approx\begin{pmatrix}0.486\\1\end{pmatrix},\] \[A\mathbf{x}_3=\begin{pmatrix}1&4\\-4&11\end{pmatrix}\begin{pmatrix}0.486\\1\end{pmatrix}=\begin{pmatrix}4.486\\9.056\end{pmatrix} \quad\Longrightarrow\quad\mu_2\approx9.056\quad\text{and}\quad\mathbf{x}_4\approx\begin{pmatrix}0.4954\\1\end{pmatrix}.\]

Door de machtmethode toe te passen op een andere matrix, kunnen we ook andere eigenwaarden van een matrix \(A\) benaderen. Neem aan dat \(\alpha\in\mathbb{R}\) een redelijke grove benadering is van één van de eigenwaarden \(\lambda_1,\ldots,\lambda_n\) van \(A\). Stel nu \(B=(A-\alpha I)^{-1}\), dan zijn de eigenwaarden van \(B\):

\[\frac{1}{\lambda_1-\alpha},\;\frac{1}{\lambda_2-\alpha},\;\ldots,\;\frac{1}{\lambda_n-\alpha}.\]

Als \(\alpha\) goed genoeg is gekozen, dan bestaat er één eigenwaarde waarvan de noemer \(\lambda_p-\alpha\) het kleinst is in absolute waarde. Dan is deze eigenwaarde \(\displaystyle\frac{1}{\lambda_p-\alpha}\) een strikt dominante eigenwaarde van \(B\). Als we nu de machtmethode toepassen op \(B\), dan vinden we een benadering van deze strikt dominante eigenwaarde \(\displaystyle\frac{1}{\lambda_p-\alpha}\). Omdat we de waarde van \(\alpha\) kennen, leidt tot een benadering van de eigenwaarde \(\lambda_p\) van \(A\). Dit heet de inverse machtmethode.

Er is echter een klein probleem als we \(B\mathbf{x}_k=(A-\alpha I)^{-1}\mathbf{x}_k\) willen berekenen, waant daarvoor hebben we de inverse van de matrix \(A-\alpha I\) nodig. Maar in plaats van de berekening van \(\mathbf{y}_k=(A-\alpha I)^{-1}\mathbf{x}_k\) kunnen we proberen om \((A-\alpha I)\mathbf{y}_k=\mathbf{x}_k\) op te lossen (bijvoorbeeld met behulp van de \(LU\) ontbinding).

Deze observatie leidt tot het volgende algoritme (details laten we achterwege):

1. Kies een geschikte waarde van \(\alpha\) voldoende dicht bij een eigenwaarde \(\lambda\) van \(A\).


2. Kies een startvector \(\mathbf{x}_0\) waarvan het (in absolute waarde) grootste element gelijk is aan \(1\).


3. Voor \(k=0,1,2,\ldots\)
1. Los \((A-\alpha I)\mathbf{y}_k=\mathbf{x}_k\) op,


2. Laat \(\mu_k\) een element zijn in \(\mathbf{y}_k\) waarvan de absolute waarde het grootst is,


3. Bereken \(\nu_k=\alpha+\displaystyle\frac{1}{\mu_k}\),


4. Bereken \(\mathbf{x}_{k+1}=\displaystyle\frac{1}{\mu_k}\mathbf{y}_k\).
4. Voor bijna alle keuzes van \(\mathbf{x}_0\), nadert de rij \(\{\nu_k\}\) naar de eigenwaarde \(\lambda\) van \(A\) en nadert de rij \(\{\mathbf{x}_k\}\) naar een bijbehorende eigenvector.

Voorbeeld: We kiezen \(\alpha=2\) als een grove benadering van de eigenwaarde \(\lambda_2=3\) van de matrix \(A=\begin{pmatrix}1&4\\-4&11\end{pmatrix}\). Dan geldt dat \(A-2I=\begin{pmatrix}-1&4\\-4&9\end{pmatrix}\).

Laat \(\mathbf{x}_0=\begin{pmatrix}1\\0\end{pmatrix}\), dan leidt het algoritme tot

\[(A-2I)\mathbf{y}_0=\mathbf{x}_0:\;\;\left(\left.\begin{matrix}-1&4\\-4&9\end{matrix}\,\right|\,\begin{matrix}1\\0\end{matrix}\right) \;\;\Longrightarrow\;\;\mathbf{y}_0=\begin{pmatrix}1.286\\0.571\end{pmatrix}\;\;\Longrightarrow\;\; \mu_0\approx1.286,\;\;\nu_0=2+\frac{1}{\mu_0}\approx2.78\;\;\text{and}\;\;\mathbf{x}_1\approx\begin{pmatrix}1\\0.44\end{pmatrix},\] \[(A-2I)\mathbf{y}_1=\mathbf{x}_1:\;\;\left(\left.\begin{matrix}-1&4\\-4&9\end{matrix}\,\right|\,\begin{matrix}1\\0.44\end{matrix}\right) \;\;\Longrightarrow\;\;\mathbf{y}_1=\begin{pmatrix}1.033\\0.508\end{pmatrix}\;\;\Longrightarrow\;\; \mu_1\approx1.033,\;\;\nu_1=2+\frac{1}{\mu_1}\approx2.969\;\;\text{and}\;\;\mathbf{x}_1\approx\begin{pmatrix}1\\0.492\end{pmatrix},\] \[(A-2I)\mathbf{y}_2=\mathbf{x}_2:\;\;\left(\left.\begin{matrix}-1&4\\-4&9\end{matrix}\,\right|\,\begin{matrix}1\\0.492\end{matrix}\right) \;\;\Longrightarrow\;\;\mathbf{y}_2=\begin{pmatrix}1.004\\0.501\end{pmatrix}\;\;\Longrightarrow\;\; \mu_2\approx1.004,\;\;\nu_2=2+\frac{1}{\mu_2}\approx2.996\;\;\text{and}\;\;\mathbf{x}_2\approx\begin{pmatrix}1\\0.499\end{pmatrix}.\]

Dan geldt: \(\lim\limits_{k\to\infty}\nu_k=3\) en \(\lim\limits_{k\to\infty}\mathbf{x}_k=\begin{pmatrix}1\\0.5\end{pmatrix}\).

---

Laatst gewijzigd op 5 april 2021