Método residual conjugado

El método residual conjugado es un método numérico iterativo utilizado para resolver sistemas de ecuaciones lineales . Es un método subespacial de Krylov muy similar al mucho más popular método del gradiente conjugado , con propiedades de construcción y convergencia similares.

Este método se utiliza para resolver ecuaciones lineales de la forma

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

donde A es una matriz hermitiana e invertible , y b es distinto de cero.

El método residual conjugado difiere del método del gradiente conjugado, estrechamente relacionado . Implica más operaciones numéricas y requiere más almacenamiento.

Dada una estimación inicial (arbitraria) de la solución , el método se describe a continuación: ${\displaystyle \mathbf {x} _{0}}$

${\displaystyle {\begin{aligned}&\mathbf {x} _{0}:={\text{Some initial guess}}\\&\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&{\text{Iterate, with }}k{\text{ starting at }}0:\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathrm {T} }\mathbf {Ar} _{k}}{(\mathbf {Ap} _{k})^{\mathrm {T} }\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathrm {T} }\mathbf {Ar} _{k+1}}{\mathbf {r} _{k}^{\mathrm {T} }\mathbf {Ar} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad \mathbf {Ap} _{k+1}:=\mathbf {Ar} _{k+1}+\beta _{k}\mathbf {Ap} _{k}\\&\qquad k:=k+1\end{aligned}}}$

la iteración puede detenerse una vez que se haya considerado convergente. La única diferencia entre este y el método de gradiente conjugado es el cálculo de y (más el cálculo incremental opcional de al final). ${\displaystyle \mathbf {x} _{k}}$ ${\displaystyle \alpha _{k}}$ ${\displaystyle \beta _{k}}$ ${\displaystyle \mathbf {Ap} _{k}}$

Nota: el algoritmo anterior se puede transformar para realizar solo una multiplicación simétrica de matriz-vector en cada iteración.

Preacondicionamiento

Al realizar algunas sustituciones y cambios de variables, se puede derivar un método residual conjugado precondicionado de la misma manera que se hace para el método del gradiente conjugado:

${\displaystyle {\begin{aligned}&\mathbf {x} _{0}:={\text{Some initial guess}}\\&\mathbf {r} _{0}:=\mathbf {M} ^{-1}(\mathbf {b} -\mathbf {Ax} _{0})\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&{\text{Iterate, with }}k{\text{ starting at }}0:\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k}}{(\mathbf {Ap} _{k})^{\mathrm {T} }\mathbf {M} ^{-1}\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {M} ^{-1}\mathbf {Ap} _{k}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad \mathbf {Ap} _{k+1}:=\mathbf {A} \mathbf {r} _{k+1}+\beta _{k}\mathbf {Ap} _{k}\\&\qquad k:=k+1\\\end{aligned}}}$

El precondicionador debe ser simétrico positivo definido. Tenga en cuenta que el vector residual aquí es diferente del vector residual sin precondicionamiento. ${\displaystyle \mathbf {M} ^{-1}}$

Referencias

• Yousef Saad , Métodos iterativos para sistemas lineales dispersos (2ª ed.), página 194, SIAM. ISBN  978-0-89871-534-7 .