Método de gradiente biconjugado

El método de gradiente biconjugado ( BiCG ) es un método numérico iterativo para resolver SLAE tipo Krylov . Es una generalización del método del gradiente conjugado .

Planteamiento del problema

Sea dado un sistema de ecuaciones algebraicas lineales de la forma: . A diferencia de la MSH, la matriz no está sujeta a la condición autoadjunta, es decir, es posible que . Para una matriz real, esto significa que la matriz puede no ser simétrica. $hacha = b$ $A \ne A^*$

Algoritmo para matrices reales

Preparación antes del proceso iterativo

Elegimos una aproximación inicial $x^0$
$r^0 = b - Ax^0$
$p^0 = r^0$
$z^0 = r^0$
$s ^ 0 = r ^ 0$

k

-ésima iteración del método [1]

$\alpha_k = \frac{(p^{k-1}, r^{k-1})}{(s^{k-1}, Az^{k-1})}$
$x^k = x^{k-1} +\alpha_k z^{k-1}$
$r^{k} = r^{k-1} - \alpha_k Az^{k-1}$
$p^k = p^{k-1} - \alpha_k A^T s^{k-1}$
$\beta_k = \frac{(p^k, r^k)}{(p^{k-1}, r^{k-1})}$
$z^k = r^k + \beta_k z^{k-1}$
$s^k = p^k + \beta_k s^{k-1}$

Criterio para detener el proceso iterativo

La parada puede ocurrir según el número de iteraciones, según la discrepancia, según la diferencia de aproximaciones, etc. Dado que el método es inestable, al usarlo, el número de iteraciones debe limitarse adicionalmente desde arriba.

Algoritmo para un sistema precondicionado

Sea dado un sistema precondicionado $M^{-1}AP^{-1}x = M^{-1}b$

Preparación antes del proceso iterativo

Elegimos una aproximación inicial $x^0$
$\widetilde{x}^0 = P^{-1}x^0$
$r^0 = M^{-1}\left( b - A \widetilde{x}^0 \right)$
$p^0 = r^0$
$z^0 = r^0$
$s ^ 0 = r ^ 0$

k

-ésima iteración del método

$\alpha_k = \frac{(p^{k-1}, r^{k-1})}{(s^{k-1}, M^{-1}AP^{-1}z^{k -una})}$
$\widetilde{x}^k = \widetilde{x}^{k-1} +\alpha_k z^{k-1}$
$r^{k} = r^{k-1} - \alpha_k M^{-1}AP^{-1}z^{k-1}$
$p^k = p^{k-1} - \alpha_k P^{-T} A^TM^{-T} s^{k-1}$ [2]
$\beta_k = \frac{(p^k, r^k)}{(p^{k-1}, r^{k-1})}$
$z^k = r^k + \beta_k z^{k-1}$
$s^k = p^k + \beta_k s^{k-1}$

Después del proceso iterativo

$x^* = P \widetilde{x}^m$ , donde es la solución aproximada del sistema, es la solución del sistema precondicionado en la última iteración. $x^{*}$ $\widetilde{x}^m$

Criterio para detener el proceso iterativo

Características y modificaciones del método

BiCG es un método inestable [1] , por lo que rara vez se usa para resolver problemas reales. Más a menudo, se usa su modificación [3] : el método estabilizado de gradientes biconjugados .

Notas

↑ 1 2 Henk A. van der Vorst. Métodos iterativos de Krylov para sistemas lineales grandes. - Prensa de la Universidad de Cambridge, 2003. - 221 p. — ISBN 9780521818285 .
↑ $P^{-T} = (P^{-1})^T$
↑ T. Huttunen, M. Malinen, P. Monk. Resolviendo las Ecuaciones de Maxwell usando la Formulación Variacional Ultra Débil . — 2006.

Métodos para resolver SLAE
Métodos directos	método matricial método de Gauss Método de Gauss-Jordan método Cramer descomposición LU Descomposición de Cholesky método de barrido
Métodos iterativos	método jacobi Método de Gauss-Seidel Método de iteración método de relajación método de gradiente conjugado Método de gradiente biconjugado Método de gradiente biconjugado estabilizado
General	matriz inversa Métodos de proyección para resolver SLAE preacondicionamiento