Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




05.08.2022


05.08.2022


03.08.2022


02.08.2022


02.08.2022


01.08.2022





Яндекс.Метрика

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

20.07.2022

Стабилизированный метод бисопряжённых градиентов (англ. 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 }} .