Метод двусопряженного градиента - Biconjugate gradient method

В математика, более конкретно в числовая линейная алгебра, то метод двусопряженных градиентов является алгоритм решать системы линейных уравнений

${displaystyle Ax=b.,}$

в отличие от метод сопряженных градиентов, этот алгоритм не требует матрица ${displaystyle A}$ быть самосопряженный, но вместо этого нужно выполнить умножение на сопряженный транспонировать А^*.

Алгоритм

1. Выберите первоначальное предположение ${displaystyle x_{0},}$, два других вектора ${displaystyle x_{0}^{*}}$ и ${displaystyle b^{*},}$ и предварительный кондиционер ${displaystyle M,}$
2. ${displaystyle r_{0}leftarrow b-A,x_{0},}$
3. ${displaystyle r_{0}^{*}leftarrow b^{*}-x_{0}^{*},A}$
4. ${displaystyle p_{0}leftarrow M^{-1}r_{0},}$
5. ${displaystyle p_{0}^{*}leftarrow r_{0}^{*}M^{-1},}$
6. за ${displaystyle k=0,1,ldots }$ делать
   1. ${displaystyle alpha _{k}leftarrow {r_{k}^{*}M^{-1}r_{k} over p_{k}^{*}Ap_{k}},}$
   2. ${displaystyle x_{k+1}leftarrow x_{k}+alpha _{k}cdot p_{k},}$
   3. ${displaystyle x_{k+1}^{*}leftarrow x_{k}^{*}+{overline {alpha _{k}}}cdot p_{k}^{*},}$
   4. ${displaystyle r_{k+1}leftarrow r_{k}-alpha _{k}cdot Ap_{k},}$
   5. ${displaystyle r_{k+1}^{*}leftarrow r_{k}^{*}-{overline {alpha _{k}}}cdot p_{k}^{*},A}$
   6. ${displaystyle eta _{k}leftarrow {r_{k+1}^{*}M^{-1}r_{k+1} over r_{k}^{*}M^{-1}r_{k}},}$
   7. ${displaystyle p_{k+1}leftarrow M^{-1}r_{k+1}+eta _{k}cdot p_{k},}$
   8. ${displaystyle p_{k+1}^{*}leftarrow r_{k+1}^{*}M^{-1}+{overline {eta _{k}}}cdot p_{k}^{*},}$

В приведенной выше формулировке вычисленное ${displaystyle r_{k},}$ и ${displaystyle r_{k}^{*}}$ удовлетворить

${displaystyle r_{k}=b-Ax_{k},,}$

${displaystyle r_{k}^{*}=b^{*}-x_{k}^{*},A}$

и, таким образом, соответствующие остатки соответствующий ${displaystyle x_{k},}$ и ${displaystyle x_{k}^{*}}$, как приближенные решения систем

${displaystyle Ax=b,,}$

${displaystyle x^{*},A=b^{*},;}$

${displaystyle x^{*}}$ это прилегающий, и ${displaystyle {overline {alpha }}}$ это комплексно сопряженный.

Безусловная версия алгоритма

1. Выберите первоначальное предположение ${displaystyle x_{0},}$,
2. ${displaystyle r_{0}leftarrow b-A,x_{0},}$
3. ${displaystyle {hat {r}}_{0}leftarrow {hat {b}}-{hat {x}}_{0}A}$
4. ${displaystyle p_{0}leftarrow r_{0},}$
5. ${displaystyle {hat {p}}_{0}leftarrow {hat {r}}_{0},}$
6. за ${displaystyle k=0,1,ldots }$ делать
   1. ${displaystyle alpha _{k}leftarrow {{hat {r}}_{k}r_{k} over {hat {p}}_{k}Ap_{k}},}$
   2. ${displaystyle x_{k+1}leftarrow x_{k}+alpha _{k}cdot p_{k},}$
   3. ${displaystyle {hat {x}}_{k+1}leftarrow {hat {x}}_{k}+alpha _{k}cdot {hat {p}}_{k},}$
   4. ${displaystyle r_{k+1}leftarrow r_{k}-alpha _{k}cdot Ap_{k},}$
   5. ${displaystyle {hat {r}}_{k+1}leftarrow {hat {r}}_{k}-alpha _{k}cdot {hat {p}}_{k}A}$
   6. ${displaystyle eta _{k}leftarrow {{hat {r}}_{k+1}r_{k+1} over {hat {r}}_{k}r_{k}},}$
   7. ${displaystyle p_{k+1}leftarrow r_{k+1}+eta _{k}cdot p_{k},}$
   8. ${displaystyle {hat {p}}_{k+1}leftarrow {hat {r}}_{k+1}+eta _{k}cdot {hat {p}}_{k},}$

Обсуждение

Метод двусопряженных градиентов численно нестабильный^{[нужна цитата ]} (сравните с метод двусопряженной градиентной стабилизации ), но очень важный с теоретической точки зрения. Определите шаги итерации с помощью

${displaystyle x_{k}:=x_{j}+P_{k}A^{-1}left(b-Ax_{j}ight),}$

${displaystyle x_{k}^{*}:=x_{j}^{*}+left(b^{*}-x_{j}^{*}Aight)P_{k}A^{-1},}$

куда ${displaystyle j<k}$ используя соответствующие проекция

${displaystyle P_{k}:=mathbf {u} _{k}left(mathbf {v} _{k}^{*}Amathbf {u} _{k}ight)^{-1}mathbf {v} _{k}^{*}A,}$

с

${displaystyle mathbf {u} _{k}=left[u_{0},u_{1},dots ,u_{k-1}ight],}$

${displaystyle mathbf {v} _{k}=left[v_{0},v_{1},dots ,v_{k-1}ight].}$

Эти связанные прогнозы могут быть повторены как

${displaystyle P_{k+1}=P_{k}+left(1-P_{k}ight)u_{k}otimes {v_{k}^{*}Aleft(1-P_{k}ight) over v_{k}^{*}Aleft(1-P_{k}ight)u_{k}}.}$

Отношение к Квазиньютоновские методы дан кем-то ${displaystyle P_{k}=A_{k}^{-1}A}$ и ${displaystyle x_{k+1}=x_{k}-A_{k+1}^{-1}left(Ax_{k}-bight)}$, куда

${displaystyle A_{k+1}^{-1}=A_{k}^{-1}+left(1-A_{k}^{-1}Aight)u_{k}otimes {v_{k}^{*}left(1-AA_{k}^{-1}ight) over v_{k}^{*}Aleft(1-A_{k}^{-1}Aight)u_{k}}.}$

Новые направления

${displaystyle p_{k}=left(1-P_{k}ight)u_{k},}$

${displaystyle p_{k}^{*}=v_{k}^{*}Aleft(1-P_{k}ight)A^{-1}}$

тогда ортогональны остаткам:

${displaystyle v_{i}^{*}r_{k}=p_{i}^{*}r_{k}=0,}$

${displaystyle r_{k}^{*}u_{j}=r_{k}^{*}p_{j}=0,}$

которые сами удовлетворяют

${displaystyle r_{k}=Aleft(1-P_{k}ight)A^{-1}r_{j},}$

${displaystyle r_{k}^{*}=r_{j}^{*}left(1-P_{k}ight)}$

куда ${displaystyle i,j<k}$.

Метод двусопряженного градиента теперь делает особый выбор и использует настройку

${displaystyle u_{k}=M^{-1}r_{k},,}$

${displaystyle v_{k}^{*}=r_{k}^{*},M^{-1}.,}$

При этом конкретном выборе явные оценки ${displaystyle P_{k}}$ и А⁻¹ избегаются, и алгоритм принимает форму, указанную выше.

Характеристики

• Если ${displaystyle A=A^{*},}$ является самосопряженный, ${displaystyle x_{0}^{*}=x_{0}}$ и ${displaystyle b^{*}=b}$, тогда ${displaystyle r_{k}=r_{k}^{*}}$, ${displaystyle p_{k}=p_{k}^{*}}$, а метод сопряженных градиентов производит ту же последовательность ${displaystyle x_{k}=x_{k}^{*}}$ за половину вычислительных затрат.
• Последовательности, производимые алгоритмом: биортогональный, т.е. ${displaystyle p_{i}^{*}Ap_{j}=r_{i}^{*}M^{-1}r_{j}=0}$ за ${displaystyle ieq j}$.
• если ${displaystyle P_{j'},}$ является многочленом с ${displaystyle mathrm {deg} left(P_{j'}ight)+j<k}$, тогда ${displaystyle r_{k}^{*}P_{j'}left(M^{-1}Aight)u_{j}=0}$. Таким образом, алгоритм производит проекции на Крыловское подпространство.
• если ${displaystyle P_{i'},}$ является многочленом с ${displaystyle i+mathrm {deg} left(P_{i'}ight)<k}$, тогда ${displaystyle v_{i}^{*}P_{i'}left(AM^{-1}ight)r_{k}=0}$.

Смотрите также

• Метод двусопряженной градиентной стабилизации
• Метод сопряженных градиентов

Рекомендации

• Флетчер Р. (1976). Уотсон, Г. Алистер (ред.). «Методы сопряженных градиентов для неопределенных систем». Числовой анализ. Конспект лекций по математике. Springer Berlin / Heidelberg. 506: 73–89. Дои:10.1007 / BFb0080109. ISBN  978-3-540-07610-0. ISSN  1617-9692.
• Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 2.7.6». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8.