Algorisme QMR

LPlantilla:'algorisme QMR va ser creat per resoldre el sistema lineal $Ax=b$ on $A$ és una matriu quadrada que no requereix ser simètrica.

Introducció

L'algorisme QMR, de l'anglés Quasi-Minimal Residual es deu a Roland W. Freund i Noël M. Nachtigal, els quals el 1991 van publicar aquest algorisme, el qual es basa en la biortogonalització de Lanczos, una extensió per a matrius no simètriques de la ortogonalització simètrica de Lanczos.

Biortogonalització de Lanczos

El procés de Biortogonalització per a matrius no simètriques de Lanczos, consisteix a construir dues bases ortogonals als subespais ${𝒦}_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 construir aquestes bases biortogonals en els subespais

${𝒦}_m(A,v_1)$

i

${𝒦}_m(A^T,w_1)$

s'utilitza l'algorisme que es mostra a continuació:

Després d'usar aquest algorisme es garanteix en aritmètica exacta que

$(v_i,w_j)=0$

si

$i\ne j$

i

$(v_i,w_j)=1$

si

$i=j$

. Ara amb els valors

${\alpha }_j$

,

${\beta }_j$

i

${\delta }_j$

obtinguts per l'algorisme anterior anem a construir la matriu

$T_m$

com una matriu 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)$

Algorisme Quasi-Minimal Residual

Es construeix la matriu

${\bar{T}}_m$

a partir de la qual es va obtenir en la biortogonalització 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)$

Una altra tècnica que s'utilitza en l'algorisme és la factorització QR, la qual s'obté aplicant les rotacions ${\mathrm{\Omega }}_i$ obtingudes de la següent forma:

${\mathrm{\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)$

on

$c_i$

i

$s_i$

s'aconsegueixen 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}}$$

on els termes

$a_{ii}^{(i-1)}$$a_{i+1,i}$

corresponen a les respectives entrades de la matriu després d'aplicar-se les rotacions

${\mathrm{\Omega }}_1,\dots ,{\mathrm{\Omega }}_{i-1}$

.

Referències

• Plantilla:Ref-publicació
• Plantilla:Ref-llibre

Enllaços externs

• Implementacions dels mètodes QMR i TFQMR
• Altres algorismes per a sistemes lineals programats en c++ i anàlisi numèrica