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

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

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

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

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}$ .

Referencias[editar]

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

Véase también[editar]

Enlaces externos[editar]

Datos: Q2878011