Algorisme QMR

L'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ó[modifica]

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[modifica]

El procés de Biortogonalització per a matrius no simètriques de Lanczos, consisteix a construir dues bases ortogonals als subespais ${\mathcal {K}}_{m}\left(A,v_{1}\right)=\mathrm {span} \left\{v_{1},Av_{1},\ldots ,A^{m-1}v_{1}\right\}$ i ${\mathcal {K}}_{m}\left(A^{T},w_{1}\right)=\mathrm {span} \left\{w_{1},A^{T}w_{1},\ldots ,\left(A^{T}\right)^{m-1}v_{1}\right\}$ .

Per construir aquestes bases biortogonals en els subespais ${\mathcal {K}}_{m}\left(A,v_{1}\right)$ i ${\mathcal {K}}_{m}\left(A^{T},w_{1}\right)$ s'utilitza l'algorisme que es mostra a continuació:

Després d'usar aquest algorisme es garanteix en aritmètica exacta que $\left(v_{i},w_{j}\right)=0$ si $i\neq j$ i $\left(v_{i},w_{j}\right)=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&\ldots &0\\\delta _{2}&\alpha _{2}&\beta _{3}&&0\\0&\ddots &\ddots &\ddots &\vdots \\0&\ldots &\delta _{m-1}&\alpha _{m-1}&\beta _{m}\\0&\ldots &0&\delta _{m}&\alpha _{m}\end{array}}\right)$

Algorisme Quasi-Minimal Residual[modifica]

Es construeix la matriu ${\overline {T}}_{m}$ a partir de la qual es va obtenir en la biortogonalització de Lanczos de la següent forma:

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

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}}}},\quad 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

\Omega _{1},\ldots ,\Omega _{i-1}

.

Referències[modifica]

R. W. Freund, N. M. Nachtigal «QMR: a quasi-minimal residual method for non-Hermitian linear systems». Numerische Mathematik, 60, 1991.
Yousef Saad. Iterative methods for sparse linear systems, 2000.

Enllaços externs[modifica]