Algoritme QMR

El algoritme QMR va ser creat per a resoldre el sistema llineal $Ax=b$ a on $A$ és una matriu quadrada que no requerix ser simètrica.

Introducció

L'algoritme QMR Quasi-Minimal Residual es deu a Roland W. Freund i Noël M. Nachtigal els quals en 1991 varen publicar este algoritme el qual es basa en la biortogonalización de Lanczos.

Quas-Minimal Residual

L'algoritme Quasi-Minimal Residual es basa en la Biortogonalización de Lanczos el qual és una extensió per a matrius no simètriques de la ortogonalización de Lanczos simètric.

Biortogonalización de Lanczos

EL procés de Biortogonalización per a matrius no simètriques de Lanczos, consistix en construir dos bases ortogonals als subespacios ${𝒦}_m(A,v_1)=\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}\{v_1,A{v}_1,\dots ,A^{m-1}{v}_1\}$ i ${𝒦}_m(A^T,w_1)=\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}\{w_1,A^T{w}_1,\dots ,{\left(A^T\right)}^{m-1}{v}_1\}$.

Per a construir estes bases Biortogonales en els subespacios ${𝒦}_m(A,v_1)$ i ${𝒦}_m(A^T,w_1)$ s'utilisara l'algoritme que es mostra a continuació

Archiu:Alglanczos.png

Després d'usar este algoritme es garantisa en aritmètica exacta que $(v_i,w_j)=0$ si $i\ne j$ i $(v_i,w_j)=1$ si $i=j$. Ara en els valors ${\alpha }_j$, ${\beta }_j$ i ${\delta }_j$ obtinguts per l'algoritme anterior anem a construir la matriu $T_m$ com una tridiagonal de la següent forma.

$T_m=\left(\begin{array}{ccccc}{\alpha }_1& {\beta }_2& 0& \dots & 0\\ {\delta }_2& {\alpha }_2& {\beta }_3& & 0\\ 0& \ddots & \ddots & \ddots & ⋮\\ 0& \dots & {\delta }_{m-1}& {\alpha }_{m-1}& {\beta }_m\\ 0& \dots & 0& {\delta }_m& {\alpha }_m\end{array}\right)$

Algoritme Quasi-Minimal Residual

Es construïx la matriu ${\bar{T}}_m$ a partir de la que es va obtindre en la biortogonalización de Lanczos de la següent forma

${\bar{T}}_m=\left(\begin{array}{c}{T}_m\\ {\delta }_{m+1}{e}_m^T\end{array}\right)$

Unes atres de les coses que s'usaren en l'algoritme és la factorización QR, la qual s'obté aplicant les rotacions ${\Omega }_i$ obtingudes de la següent forma.

${\Omega }_i=\left(\begin{array}{ccc}{I}_{i-1}& 0& 0\\ 0& \begin{array}{cc}{c}_i& s_1\\ -s_i& c_i\end{array}& 0\\ 0& 0& I_{n-(i+1)}\end{array}\right)$

a on $c_i$ i $s_i$ es conseguixen de la següent forma. $s_i=\frac{a_{i+1,i}}{\sqrt{{\left(a_{ii}^{(i-1)}\right)}^2+a_{i+1,i}^2}}{c}_i=\frac{a_{ii}^{(i-1)}}{\sqrt{{\left(a_{ii}^{(i-1)}\right)}^2+a_{i+1,i}^2}}$

A on $a_{ii}^{(i-1)}$ $a_{i+1,i}$ corresponen a les respectives entrades de la matriu després d'aplicar-se les rotacions ${\Omega }_1,\dots ,{\Omega }_{i-1}$.

Archiu:Algqmr.png

Referències

• Yousef Saad (2000). Iterative methods for sparse linear systems.

Vore també

• Basic Linear Algebra Subprograms
• Automatically Tuned Linear Algebra Software
• Algoritme TFQMR
• Subespacio de Krylov