Метод бисопряженного градиента

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

${\displaystyle Ax=b.\,}$

В отличие от метода сопряженных градиентов , этот алгоритм не требует, чтобы матрица была самосопряженной , но вместо этого необходимо выполнять умножения на сопряженную транспонированную матрицу A ^* . ${\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 \beta _{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}+\beta _{k}\cdot p_{k}\,}$
   8. ${\displaystyle p_{k+1}^{*}\leftarrow r_{k+1}^{*}M^{-1}+{\overline {\beta _{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 \beta _{k}\leftarrow {{\hat {r}}_{k+1}r_{k+1} \over {\hat {r}}_{k}r_{k}}\,}$
   7. ${\displaystyle p_{k+1}\leftarrow r_{k+1}+\beta _{k}\cdot p_{k}\,}$
   8. ${\displaystyle {\hat {p}}_{k+1}\leftarrow {\hat {r}}_{k+1}+\beta _{k}\cdot {\hat {p}}_{k}\,}$

Обсуждение

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

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

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

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

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

с

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

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

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

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

Связь с квазиньютоновскими методами определяется соотношением и , где ${\displaystyle P_{k}=A_{k}^{-1}A}$ ${\displaystyle x_{k+1}=x_{k}-A_{k+1}^{-1}\left(Ax_{k}-b\right)}$

${\displaystyle A_{k+1}^{-1}=A_{k}^{-1}+\left(1-A_{k}^{-1}A\right)u_{k}\otimes {v_{k}^{*}\left(1-AA_{k}^{-1}\right) \over v_{k}^{*}A\left(1-A_{k}^{-1}A\right)u_{k}}.}$

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

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

${\displaystyle p_{k}^{*}=v_{k}^{*}A\left(1-P_{k}\right)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}=A\left(1-P_{k}\right)A^{-1}r_{j},}$

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

где . ${\displaystyle i,j<k}$

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

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

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

При таком выборе явные оценки и A ⁻¹ избегаются, и алгоритм принимает форму, указанную выше. ${\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 i\neq j}$
• если — многочлен с , то . Таким образом, алгоритм создает проекции на подпространство Крылова . ${\displaystyle P_{j'}\,}$ ${\displaystyle \deg \left(P_{j'}\right)+j<k}$ ${\displaystyle r_{k}^{*}P_{j'}\left(M^{-1}A\right)u_{j}=0}$
• если — многочлен с , то . ${\displaystyle P_{i'}\,}$ ${\displaystyle i+\deg \left(P_{i'}\right)<k}$ ${\displaystyle v_{i}^{*}P_{i'}\left(AM^{-1}\right)r_{k}=0}$

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

• Метод стабилизированного биконъюгатного градиента (BiCG-Stab)
• Метод сопряженных градиентов (CG)
• Метод сопряженных квадратов градиентов (CGS)

Ссылки

• Флетчер, Р. (1976). Уотсон, Г. Алистер (ред.). «Методы сопряженных градиентов для неопределенных систем». Численный анализ . Конспект лекций по математике. 506. Springer Berlin / Heidelberg: 73–89. doi : 10.1007/BFb0080109 . ISBN 978-3-540-07610-0. ISSN  1617-9692.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Раздел 2.7.6". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8.