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

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

Обозначения

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

• ( u , v ) = ∑ i = 1 n u ¯ i v i {displaystyle (u,v)=sum _{i=1}^{n}{overline {u}}_{i}v_{i}}
• [ u , v ] = ∑ i = 1 n u i v i {displaystyle [u,v]=sum _{i=1}^{n}u_{i}v_{i}}

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

Для решения СЛАУ вида A x = b {displaystyle Ax=b} , где A {displaystyle A} — комплексная матрица, стабилизированным методом бисопряжённых градиентов может использоваться следующий алгоритм:

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

Выберем начальное приближение x 0 {displaystyle x^{0}}

r 0 = b − A x 0 {displaystyle r^{0}=b-Ax^{0}}

r ~ = r 0 {displaystyle { ilde {r}}=r^{0}}

ρ 0 = α 0 = ω 0 = 1 {displaystyle ho ^{0}=alpha ^{0}=omega ^{0}=1}

v 0 = p 0 = 0 {displaystyle v^{0}=p^{0}=0}

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

ρ k = ( r ~ , r k − 1 ) {displaystyle ho ^{k}=({ ilde {r}},r^{k-1})}

β k = ρ k ρ k − 1 α k − 1 ω k − 1 {displaystyle eta ^{k}={frac { ho ^{k}}{ ho ^{k-1}}}{frac {alpha ^{k-1}}{omega ^{k-1}}}}

p k = r k − 1 + β k ( p k − 1 − ω k − 1 v k − 1 ) {displaystyle p^{k}=r^{k-1}+eta ^{k}(p^{k-1}-omega ^{k-1}v^{k-1})}

v k = A p k {displaystyle v^{k}=Ap^{k}}

α k = ρ k ( r ~ , v k ) {displaystyle alpha ^{k}={frac { ho ^{k}}{({ ilde {r}},v^{k})}}}

s k = r k − 1 − α k v k {displaystyle s^{k}=r^{k-1}-alpha ^{k}v^{k}}

t k = A s k {displaystyle t^{k}=As^{k}}

ω k = [ t k , s k ] [ t k , t k ] {displaystyle omega ^{k}={frac {[t^{k},s^{k}]}{[t^{k},t^{k}]}}}

x k = x k − 1 + ω k s k + α k p k {displaystyle x^{k}=x^{k-1}+omega ^{k}s^{k}+alpha ^{k}p^{k}}

r k = s k − ω k t k {displaystyle r^{k}=s^{k}-omega ^{k}t^{k}}

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

Кроме традиционных критериев остановки, как число итераций ( k ≤ k m a x {displaystyle kleq k_{max}} ) и заданная невязка ( ‖ | r k | | / | | b | | < ε {displaystyle ||r^{k}||/||b||<varepsilon } ), так же остановку метода можно производить, когда величина | ω k | {displaystyle |omega ^{k}|} стала меньше некоторого заранее заданного числа ε ω {displaystyle varepsilon _{omega }} .