Algorisme QMR

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

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.

El procés de Biortogonalització per a matrius no simètriques de Lanczos, consisteix a construir dues bases ortogonals als subespais ${\displaystyle {\mathcal {K}}_{m}\left(A,v_{1}\right)=\mathrm {span} \left\{v_{1},Av_{1},\ldots ,A^{m-1}v_{1}\right\}}$ i ${\displaystyle {\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 ${\displaystyle {\mathcal {K}}_{m}\left(A,v_{1}\right)}$ i ${\displaystyle {\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 ${\displaystyle \left(v_{i},w_{j}\right)=0}$ si ${\displaystyle i\neq j}$ i ${\displaystyle \left(v_{i},w_{j}\right)=1}$ si ${\displaystyle i=j}$. Ara amb els valors ${\displaystyle \alpha _{j}}$, ${\displaystyle \beta _{j}}$ i ${\displaystyle \delta _{j}}$ obtinguts per l'algorisme anterior anem a construir la matriu ${\displaystyle T_{m}}$ com una matriu tridiagonal de la següent forma:

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

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

on ${\displaystyle c_{i}}$ i ${\displaystyle s_{i}}$ s'aconsegueixen de la següent forma:$${\displaystyle 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 ${\displaystyle a_{ii}^{(i-1)}}$${\displaystyle a_{i+1,i}}$ corresponen a les respectives entrades de la matriu després d'aplicar-se les rotacions ${\displaystyle \Omega _{1},\ldots ,\Omega _{i-1}}$.

• 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. 

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