Algoritmo QMR
# Algoritmo QMR

El algoritmo QMR fue creado para resolver el sistema lineal $Ax=b$ donde $A$ es una matriz cuadrada que no requiere ser simétrica.

## Introducción

El algoritmo QMR Quasi-Minimal Residual se debe a Roland W. Freund y Noël M. Nachtigal los cuales en 1991 publicaron este algoritmo el cual se basa en la biortogonalización de Lanczos.

## Quas-Minimal Residual

El algoritmo Quasi-Minimal Residual se basa en la Biortogonalización de Lanczos el cual es una extensión para matrices no simétricas de la ortogonalización de Lanczos simétrico.

### Biortogonalización de Lanczos

EL proceso de Biortogonalización para matrices no simétricas de Lanczos, consiste en construir dos bases ortogonales a los subespacios ${\mathcal {K}}_{m}\left(A,v_{1}\right)=\mathrm {span} \left\{v_{1},Av_{1},\ldots ,A^{m-1}v_{1}\right\}$ y ${\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\}$.

Para construir estas bases Biortogonales en los subespacios ${\mathcal {K}}_{m}\left(A,v_{1}\right)$ y ${\mathcal {K}}_{m}\left(A^{T},w_{1}\right)$ se utilizara el algoritmo que se muestra a continuación

Luego de usar este algoritmo se garantiza en aritmética exacta que $\left(v_{i},w_{j}\right)=0$ si $i\neq j$ y $\left(v_{i},w_{j}\right)=1$ si $i=j$. Ahora con los valores $\alpha _{j}$, $\beta _{j}$ y $\delta _{j}$ obtenidos por el algoritmo anterior vamos a construir la matriz $T_{m}$ como una tridiagonal de la siguiente 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)$

### Algoritmo Quasi-Minimal Residual

Se construye la matriz ${\overline {T}}_{m}$ a partir de la que se obtuvo en la biortogonalización de Lanczos de la siguiente forma

${\overline {T}}_{m}=\left({\begin{array}{c}T_{m}\\\delta _{m+1}e_{m}^{T}\end{array}}\right)$

Otras de las cosas que se usaran en el algoritmo es la factorización QR, la cual se obtiene aplicando las rotaciones $\Omega _{i}$ obtenidas de la siguiente 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)$

donde $c_{i}$ y $s_{i}$ se consiguen de la siguiente 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}}}}$

Donde $a_{ii}^{(i-1)}$ $a_{i+1,i}$ corresponden a las respectivas entradas de la matriz luego de aplicarse las rotaciones $\Omega _{1},\ldots ,\Omega _{i-1}$.

