Стабилизированный метод бисопряжённых градиентов

Разделы:

Стабилизированный метод бисопряжённых градиентов (англ. Biconjugate gradient stabilized method, BiCGStab) — итерационный метод решения СЛАУ крыловского типа. Разработан Ван дэр Ворстом (англ.) для решения систем с несимметричными матрицами. Сходится быстрее, чем обычный метод бисопряженных градиентов, который является неустойчивым[1], и поэтому применяется чаще[2].

Содержание

1 Обозначения
2 Алгоритм метода
3 См. также
4 Примечания

Обозначения

Для комплексных СЛАУ, в методе используются два вида скалярных произведений, в случае действительных матрицы и правой части они совпадают.

(u,v)=∑i=1nu¯ivi{displaystyle (u,v)=sum _{i=1}^{n}{overline {u}}_{i}v_{i}} $(u, v) = sum_{i=1}^n overline{u}_i v_i$
[u,v]=∑i=1nuivi{displaystyle [u,v]=sum _{i=1}^{n}u_{i}v_{i}} $[u, v] = sum_{i=1}^n u_i v_i$

Алгоритм метода

Для решения СЛАУ вида Ax=b{displaystyle Ax=b}

$Ax = b$ , где A{displaystyle A} $A$ — комплексная матрица, стабилизированным методом бисопряжённых градиентов может использоваться следующий алгоритм[1][3]:

Подготовка перед итерационным процессом

Выберем начальное приближение x0{displaystyle x^{0}} $x^0$
r0=b−Ax0{displaystyle r^{0}=b-Ax^{0}} $r^0 = b - Ax^0$
r~=r0{displaystyle {tilde {r}}=r^{0}} $tilde{r} = r^0$
ρ0=α0=ω0=1{displaystyle rho ^{0}=alpha ^{0}=omega ^{0}=1} $rho^0 = alpha^0 = omega^0 = 1$
v0=p0=0{displaystyle v^{0}=p^{0}=0} $v^0 = p^0 = 0$

k{displaystyle k} $k$ -я итерация метода

ρk=(r~,rk−1){displaystyle rho ^{k}=({tilde {r}},r^{k-1})} $rho^k = (tilde{r}, r^{k-1})$
βk=ρkρk−1αk−1ωk−1{displaystyle beta ^{k}={frac {rho ^{k}}{rho ^{k-1}}}{frac {alpha ^{k-1}}{omega ^{k-1}}}} $beta^k = frac{rho^{k}}{rho^{k-1}} frac{alpha^{k-1}}{omega^{k-1}}$
pk=rk−1+βk(pk−1−ωk−1vk−1){displaystyle p^{k}=r^{k-1}+beta ^{k}(p^{k-1}-omega ^{k-1}v^{k-1})} ${displaystyle p^{k}=r^{k-1}+beta ^{k}(p^{k-1}-omega ^{k-1}v^{k-1})}$
vk=Apk{displaystyle v^{k}=Ap^{k}} $v^k = A p ^k$
αk=ρk(r~,vk){displaystyle alpha ^{k}={frac {rho ^{k}}{({tilde {r}},v^{k})}}} $alpha^k = frac{rho^k}{(tilde{r}, v^k)}$
sk=rk−1−αkvk{displaystyle s^{k}=r^{k-1}-alpha ^{k}v^{k}} ${displaystyle s^{k}=r^{k-1}-alpha ^{k}v^{k}}$
tk=Ask{displaystyle t^{k}=As^{k}} $t^k = A s^k$
ωk=[tk,sk][tk,tk]{displaystyle omega ^{k}={frac {[t^{k},s^{k}]}{[t^{k},t^{k}]}}} $omega^k = frac{[t^k, s^k]} {[t^k, t^k]}$
xk=xk−1+ωksk+αkpk{displaystyle x^{k}=x^{k-1}+omega ^{k}s^{k}+alpha ^{k}p^{k}} $x^k = x^{k-1} + omega^k s^k + alpha^k p^k$
rk=sk−ωktk{displaystyle r^{k}=s^{k}-omega ^{k}t^{k}} $r^k = s^k - omega^k t^k$

Критерий остановки итерационного процесса

Кроме традиционных критериев остановки, как число итераций (k≤kmax{displaystyle kleq k_{max}}

$k le k_{max}$ ) и заданная невязка (‖|rk||/||b||<ε{displaystyle ||r^{k}||/||b||<varepsilon } $||r^k|| / ||b|| < varepsilon$ ), так же остановку метода можно производить, когда величина |ωk|{displaystyle |omega ^{k}|} $|omega^k|$ стала меньше некоторого заранее заданного числа εω{displaystyle varepsilon _{omega }} $varepsilon_{omega}$ .

См. также

Метод сопряжённых градиентов

Примечания

↑ 1 2 Henk A. van der Vorst. Iterative Krylov Methods for Large Linear System. — Cambridge University Press, 2003. — 221 с. — ISBN 9780521818285.
↑ T. Huttunen, M. Malinen, P. Monk. Solving Maxwell’s Equations using Ultra Weak Variational Formulation (англ.). — 2006.
↑ A. Formmer, V. Hannemann, B. Nokel, Th. Lippert, K. Schilling. Accelerating Wilson Fermion Matrix Invesion by Means of the Stibilized Biconjugate Cgadient Agorithm (англ.). — 1994.