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.

Contenido

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^Tw_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

Alglanczos.png

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 αj, βj y δj obtenidos por el algoritmo anterior vamos a construir la matriz Tm 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^T_m \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 Ω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 ci y si 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)} ai + 1,i corresponden a las respectivas entradas de la matriz luego de aplicarse las rotaciones \Omega_1,\ldots,\Omega_{i-1}.

Algqmr.png

Referencias

Véase también

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Algoritmo TFQMR — El Algoritmo TFQMR fue creado para resolver el sistema lineal Ax = b donde A es una matriz cuadrada que no requiere ser simétrica. Contenido 1 Introducción 2 Transpose Free QMR 3 Algoritmo Transpose Free QM …   Wikipedia Español

  • Método iterativo — En matemática computacional, un método iterativo trata de resolver un problema (como una ecuación o un sistema de ecuaciones) mediante aproximaciones sucesivas a la solución, empezando desde una estimación inicial. Esta aproximación contrasta con …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”