Metoda deflației Wielandt#
O altă metodă de deflație este metoda deflației Wielandt, o îmbunătățire a deflației Hotelling[3] și o alternativă pentru metoda deflației Householder. Ne amintim cum, în cea din urmă, am utilizat proprietățile unei transformări de asemănare utilizând un reflector Householder.
Această operație este însă costisitoare, căci presupune produse de matrice dense. Din acest motiv, propunem deflația Wielandt, care poate fi rescrisă vectorial pentru a facilita viteza de calcul.
Vector propriu la stânga#
În mod tradițional, înțelegem prin vector propriu noțiunea de vector propriu la dreapta, adică, pentru o matrice \(A\in\mathbb{R}^{n\times n}\), \(n\in\mathbb{N}^*\), vectorul \(\bm{x}\in\mathbb{R}^n\) se consideră vectorul propriu la dreapta asociat valorii proprii \(\lambda\in\mathbb{R}\) dacă și numai dacă:
\[ A\bm{x}=\lambda\bm{x} \]Observăm cum, în ecuația de mai sus, vectorul \(\bm{x}\) se află în dreapta matricei \(A\). Alternativ, noțiunea de vector propriu la stânga este descrisă de relația:
\[ \bm{y}A=\lambda\bm{y} \]unde \(\bm{y}\in\mathbb{R}^n\) este un vector linie.
Este de menționat că vectorii proprii la stânga ai matricei \(A\) corespund, în mod evident, vectorilor la dreapta ai matricei transpuse, adică \(A^T\).
Din acest motiv, valorile proprii asociate vectorilor la stânga corespund valorilor proprii asociate vectorilor la dreapta.
Explicația algoritmului#
Fie \(A\in\mathbb{R}^{n\times n}\) o matrice pătratică simplă, \(n\in\mathbb{N}^*\). Notăm cu \(\bm{x_1},\dots,\bm{x_n}\) vectorii proprii la dreapta, respectiv cu \(\bm{y_1},\dots,\bm{y_n}\) vectorii proprii la stânga specifici matricei \(A\). Vom nota și \(\lambda_1\in\lambda(A)\) valoarea proprie dominantă a matricei \(A\).
Dacă \(\bm{\hat{x_1}}\) este o aproximare a vectorului propriu \(\bm{x_1}\) aleasă astfel încât \(||\bm{\hat{x_1}}||=1\), atunci putem defini matricea \(A_1\in\mathbb{R}^{n\times n}\):
\[ A_1=A-\alpha\bm{\hat{x_1}}\bm{w}^T \]În ecuația anterioară, considerăm:
-
\(\alpha\in\mathbb{R}\) o constantă aleasă potrivit;
-
\(\bm{w}\in\mathbb{R}^n\) un vector ce are proprietatea că \(\left\langle\bm{w},\bm{\hat{x_1}}\right\rangle=1\).
Dacă prin \(\bm{\hat{x_1}}\) se înțelege chiar \(\bm{x_1}\) (amintim că \(\bm{\hat{x_1}}\approx\bm{x_1}\)), atunci se poate demonstra că valorile proprii ale lui \(A_1\) sunt date de:
\[ \lambda(A_1)=\left\{\lambda_1-\alpha,\lambda_2,\lambda_3,\dots,\lambda_n\right\} \]Suplimentar, vectorul propriu la dreapta \(\bm{x_1}\) și vectorii proprii la stânga \(\bm{y_2}\dots\bm{y_n}\) rămân neschimbați.
Plecăm de la relația \(A_1=A-\alpha\bm{\hat{x_1}}\bm{w}^T\), în care înlocuim \(\bm{\hat{x_1}}=\bm{x_1}\) și pe care o înmulțim la dreapta cu \(\bm{x_1}\):
\[A_1\bm{x_1}=(A-\alpha\bm{x_1}\bm{w}^T)\bm{x_1}=A\bm{x_1}-\alpha\bm{x_1}\bm{w}^T\bm{x_1}\]Dar am impus ca \(\left\langle\bm{w},\bm{\hat{x_1}}\right\rangle=\left\langle\bm{w},\bm{x_1}\right\rangle=\bm{w}^T\bm{x_1}=1\), deci:
\[A_1\bm{x_1}=A\bm{x_1}-\alpha\bm{x_1}\]Am explicat deja în cadrul MPI deplasat cum perechea \((\lambda_1, \bm{x_1})\) aparținând matricei \(A\) devine, pentru matricea \(A-\alpha I_n\), perechea \((\lambda_1-\alpha, \bm{x_1})\), așadar \(\bm{x_1}\) se conservă.
Pentru vectorii la stânga, înmulțim, pentru fiecare \(i\in\overline{2,n}\):
\[\bm{y_i}A_1=\bm{y_1}(A-\alpha\bm{x_1}\bm{w}^T)=\bm{y_i}A-\alpha\bm{y_i}\bm{x_1}\bm{w}^T\]Luăm o scurtă pauză pentru a demonstra că \(\bm{y_i}\bm{x_1}=0\). Plecăm de la:
\[\bm{y_i}A\bm{x_j}=\begin{cases} (\bm{y_i}A)\bm{x_j}=\lambda_i\bm{y_i}\bm{x_j}\\ \bm{y_i}(A\bm{x_j})=\lambda_j\bm{y_i}\bm{x_j} \end{cases}\,,\,\,\forall i\neq j\]Dar \(\lambda_i\bm{y_i}\bm{x_j}=\lambda_j\bm{y_i}\bm{x_j}\) nu este posibil decât dacă fie \(\lambda_i=\lambda_j\), fie \(\bm{y_i}\bm{x_j}=0\). Cum însă \(\lambda_i\neq\lambda_j\), înseamnă că \(\bm{y_i}\bm{x_j}\), \(\forall i\neq j\).
Așadar, \(\bm{y_i}A_1=\bm{y_i}A\), deci vectorii proprii la stânga se conservă, \(\forall i\in\overline{2,n}\).
Folosind aceste proprietăți, extragem radicalul: matricea \(A_1\) deplasează valoarea proprie a matricei \(A\) în poziția pe care ne-o dorim noi. Există multe modalități de a alege valoarea \(\bm{w}\):
-
Deoarece aceasta este o generalizare a deflației Hotelling[3], se poate alege \(\bm{w}=\bm{y_1}\);
-
Alternativ, poate fi ales \(\bm{w}=\bm{x_1}\).
Nu vom detalia aceste alegeri aici, însă puteți urmări lectura suplimentară.
Scrierea vectorială#
Motivul pentru care această tehnică de deflație prezintă interes este că ea poate fi scrisă utilizând în mod special operații pe vectori în loc de înmulțiri pe matrice. Dacă suntem atenți, nu vom calcula niciodată explicit \(A_1\), aceasta fiind o matrice densă.
Algoritmul poate fi definit recursiv astfel[31]:
-
Se calculează inițial \(\bm{y}=A\bm{x}\);
-
Apoi, recursiv, se calculează:
-
Valoarea \(\beta=\alpha\left\langle\bm{w},\bm{x}\right\rangle\);
-
Vectorul \(\bm{y}\rightarrow\bm{y}-\beta\bm{\hat{x_1}}\).
-
După cum se poate observa, algoritmul este foarte simplu de scris, odată înțeles.
Utilizarea în practică#
Algoritmul se poate repeta până se obțin toate valorile proprii ce se doresc. Cu toate acestea, în practică, algoritmul nu poate fi utilizat pentru mai mult de câteva valori proprii din cauza acumulării erorilor numerice. Pentru mai multe valori proprii, se poate utiliza metoda QR.
Licență#
The book "Metode Numerice", written by Valentin-Ioan Vintilă, is licensed under CC BY-NC-SA 4.0 
