В математике , а точнее в числовой линейной алгебре , метод бисопряженного градиента представляет собой алгоритм решения систем линейных уравнений.
A x = b . {\displaystyle Ax=b.\,} В отличие от метода сопряженных градиентов , этот алгоритм не требует использования матрицы A {\displaystyle A} самосопряженным , но вместо этого нужно выполнить умножение на сопряженную транспозицию A *
Выберите первоначальное предположение x 0 {\displaystyle x_{0}\,} x 0 ∗ {\displaystyle x_{0}^{*}} b ∗ {\displaystyle b^{*}\,} предобуславливатель M {\displaystyle M\,} r 0 ← b − A x 0 {\displaystyle r_{0}\leftarrow b-A\,x_{0}\,} r 0 ∗ ← b ∗ − x 0 ∗ A ∗ {\displaystyle r_{0}^{*}\leftarrow b^{*}-x_{0}^{*}\,A^{*}} p 0 ← M − 1 r 0 {\displaystyle p_{0}\leftarrow M^{-1}r_{0}\,} p 0 ∗ ← r 0 ∗ M − 1 {\displaystyle p_{0}^{*}\leftarrow r_{0}^{*}M^{-1}\,} для k = 0 , 1 , … {\displaystyle k=0,1,\ldots } α k ← r k ∗ M − 1 r k p k ∗ A p k {\displaystyle \alpha _{k}\leftarrow {r_{k}^{*}M^{-1}r_{k} \over p_{k}^{*}Ap_{k}}\,} x k + 1 ← x k + α k ⋅ p k {\displaystyle x_{k+1}\leftarrow x_{k}+\alpha _{k}\cdot p_{k}\,} x k + 1 ∗ ← x k ∗ + α k ¯ ⋅ p k ∗ {\displaystyle x_{k+1}^{*}\leftarrow x_{k}^{*}+{\overline {\alpha _{k}}}\cdot p_{k}^{*}\,} r k + 1 ← r k − α k ⋅ A p k {\displaystyle r_{k+1}\leftarrow r_{k}-\alpha _{k}\cdot Ap_{k}\,} r k + 1 ∗ ← r k ∗ − α k ¯ ⋅ p k ∗ A ∗ {\displaystyle r_{k+1}^{*}\leftarrow r_{k}^{*}-{\overline {\alpha _{k}}}\cdot p_{k}^{*}\,A^{*}} β k ← r k + 1 ∗ M − 1 r k + 1 r k ∗ M − 1 r k {\displaystyle \beta _{k}\leftarrow {r_{k+1}^{*}M^{-1}r_{k+1} \over r_{k}^{*}M^{-1}r_{k}}\,} p k + 1 ← M − 1 r k + 1 + β k ⋅ p k {\displaystyle p_{k+1}\leftarrow M^{-1}r_{k+1}+\beta _{k}\cdot p_{k}\,} p k + 1 ∗ ← r k + 1 ∗ M − 1 + β k ¯ ⋅ p k ∗ {\displaystyle p_{k+1}^{*}\leftarrow r_{k+1}^{*}M^{-1}+{\overline {\beta _{k}}}\cdot p_{k}^{*}\,} В приведенной выше формулировке вычисленное r k {\displaystyle r_{k}\,} r k ∗ {\displaystyle r_{k}^{*}}
r k = b − A x k , {\displaystyle r_{k}=b-Ax_{k},\,} r k ∗ = b ∗ − x k ∗ A ∗ {\displaystyle r_{k}^{*}=b^{*}-x_{k}^{*}\,A^{*}} и, таким образом, являются соответствующими остатками, соответствующими x k {\displaystyle x_{k}\,} x k ∗ {\displaystyle x_{k}^{*}}
A x = b , {\displaystyle Ax=b,\,} x ∗ A ∗ = b ∗ ; {\displaystyle x^{*}\,A^{*}=b^{*}\,;} x ∗ {\displaystyle x^{*}} сопряженным , и α ¯ {\displaystyle {\overline {\alpha }}} комплексно-сопряженным .
Выберите первоначальное предположение x 0 {\displaystyle x_{0}\,} r 0 ← b − A x 0 {\displaystyle r_{0}\leftarrow b-A\,x_{0}\,} r ^ 0 ← b ^ − x ^ 0 A ∗ {\displaystyle {\hat {r}}_{0}\leftarrow {\hat {b}}-{\hat {x}}_{0}A^{*}} p 0 ← r 0 {\displaystyle p_{0}\leftarrow r_{0}\,} p ^ 0 ← r ^ 0 {\displaystyle {\hat {p}}_{0}\leftarrow {\hat {r}}_{0}\,} для k = 0 , 1 , … {\displaystyle k=0,1,\ldots } α k ← r ^ k r k p ^ k A p k {\displaystyle \alpha _{k}\leftarrow {{\hat {r}}_{k}r_{k} \over {\hat {p}}_{k}Ap_{k}}\,} x k + 1 ← x k + α k ⋅ p k {\displaystyle x_{k+1}\leftarrow x_{k}+\alpha _{k}\cdot p_{k}\,} x ^ k + 1 ← x ^ k + α k ⋅ p ^ k {\displaystyle {\hat {x}}_{k+1}\leftarrow {\hat {x}}_{k}+\alpha _{k}\cdot {\hat {p}}_{k}\,} r k + 1 ← r k − α k ⋅ A p k {\displaystyle r_{k+1}\leftarrow r_{k}-\alpha _{k}\cdot Ap_{k}\,} r ^ k + 1 ← r ^ k − α k ⋅ p ^ k A ∗ {\displaystyle {\hat {r}}_{k+1}\leftarrow {\hat {r}}_{k}-\alpha _{k}\cdot {\hat {p}}_{k}A^{*}} β k ← r ^ k + 1 r k + 1 r ^ k r k {\displaystyle \beta _{k}\leftarrow {{\hat {r}}_{k+1}r_{k+1} \over {\hat {r}}_{k}r_{k}}\,} p k + 1 ← r k + 1 + β k ⋅ p k {\displaystyle p_{k+1}\leftarrow r_{k+1}+\beta _{k}\cdot p_{k}\,} p ^ k + 1 ← r ^ k + 1 + β k ⋅ p ^ k {\displaystyle {\hat {p}}_{k+1}\leftarrow {\hat {r}}_{k+1}+\beta _{k}\cdot {\hat {p}}_{k}\,} Метод бисопряженных градиентов численно неустойчив. [ нужна ссылка (сравните с методом стабилизации бисопряженного градиента ), но очень важно с теоретической точки зрения. Определите шаги итерации по
x k := x j + P k A − 1 ( b − A x j ) , {\displaystyle x_{k}:=x_{j}+P_{k}A^{-1}\left(b-Ax_{j}\right),} x k ∗ := x j ∗ + ( b ∗ − x j ∗ A ) P k A − 1 , {\displaystyle x_{k}^{*}:=x_{j}^{*}+\left(b^{*}-x_{j}^{*}A\right)P_{k}A^{-1},} где j < k {\displaystyle j<k} проекцию
P k := u k ( v k ∗ A u k ) − 1 v k ∗ A , {\displaystyle P_{k}:=\mathbf {u} _{k}\left(\mathbf {v} _{k}^{*}A\mathbf {u} _{k}\right)^{-1}\mathbf {v} _{k}^{*}A,} с
u k = [ u 0 , u 1 , … , u k − 1 ] , {\displaystyle \mathbf {u} _{k}=\left[u_{0},u_{1},\dots ,u_{k-1}\right],} v k = [ v 0 , v 1 , … , v k − 1 ] . {\displaystyle \mathbf {v} _{k}=\left[v_{0},v_{1},\dots ,v_{k-1}\right].} Эти связанные прогнозы могут повторяться как
P k + 1 = P k + ( 1 − P k ) u k ⊗ v k ∗ A ( 1 − P k ) v k ∗ A ( 1 − P k ) u k . {\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}}.} Связь с квазиньютоновскими методами определяется выражением P k = A k − 1 A {\displaystyle P_{k}=A_{k}^{-1}A} x k + 1 = x k − A k + 1 − 1 ( A x k − b ) {\displaystyle x_{k+1}=x_{k}-A_{k+1}^{-1}\left(Ax_{k}-b\right)}
A k + 1 − 1 = A k − 1 + ( 1 − A k − 1 A ) u k ⊗ v k ∗ ( 1 − A A k − 1 ) v k ∗ A ( 1 − A k − 1 A ) u k . {\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}}.} Новые направления
p k = ( 1 − P k ) u k , {\displaystyle p_{k}=\left(1-P_{k}\right)u_{k},} p k ∗ = v k ∗ A ( 1 − P k ) A − 1 {\displaystyle p_{k}^{*}=v_{k}^{*}A\left(1-P_{k}\right)A^{-1}} тогда ортогональны остаткам:
v i ∗ r k = p i ∗ r k = 0 , {\displaystyle v_{i}^{*}r_{k}=p_{i}^{*}r_{k}=0,} r k ∗ u j = r k ∗ p j = 0 , {\displaystyle r_{k}^{*}u_{j}=r_{k}^{*}p_{j}=0,} которые сами удовлетворяют
r k = A ( 1 − P k ) A − 1 r j , {\displaystyle r_{k}=A\left(1-P_{k}\right)A^{-1}r_{j},} r k ∗ = r j ∗ ( 1 − P k ) {\displaystyle r_{k}^{*}=r_{j}^{*}\left(1-P_{k}\right)} где i , j < k {\displaystyle i,j<k}
Метод бисопряженного градиента теперь делает специальный выбор и использует настройку
u k = M − 1 r k , {\displaystyle u_{k}=M^{-1}r_{k},\,} v k ∗ = r k ∗ M − 1 . {\displaystyle v_{k}^{*}=r_{k}^{*}\,M^{-1}.\,} При этом конкретном выборе явные оценки P k {\displaystyle P_{k}} А −1
Если A = A ∗ {\displaystyle A=A^{*}\,} самосопряженным , x 0 ∗ = x 0 {\displaystyle x_{0}^{*}=x_{0}} b ∗ = b {\displaystyle b^{*}=b} r k = r k ∗ {\displaystyle r_{k}=r_{k}^{*}} p k = p k ∗ {\displaystyle p_{k}=p_{k}^{*}} метод сопряженного градиента создает ту же последовательность x k = x k ∗ {\displaystyle x_{k}=x_{k}^{*}} Последовательности, создаваемые алгоритмом, являются биортогональными , т. е. p i ∗ A p j = r i ∗ M − 1 r j = 0 {\displaystyle p_{i}^{*}Ap_{j}=r_{i}^{*}M^{-1}r_{j}=0} i ≠ j {\displaystyle i\neq j} если P j ′ {\displaystyle P_{j'}\,} deg ( P j ′ ) + j < k {\displaystyle \deg \left(P_{j'}\right)+j<k} r k ∗ P j ′ ( M − 1 A ) u j = 0 {\displaystyle r_{k}^{*}P_{j'}\left(M^{-1}A\right)u_{j}=0} подпространство Крылова . если P i ′ {\displaystyle P_{i'}\,} i + deg ( P i ′ ) < k {\displaystyle i+\deg \left(P_{i'}\right)<k} v i ∗ P i ′ ( A M − 1 ) r k = 0 {\displaystyle v_{i}^{*}P_{i'}\left(AM^{-1}\right)r_{k}=0}
скрывать Ключевые понятия Проблемы Аппаратное обеспечение Программное обеспечение
![{\displaystyle \mathbf {u} _{k}=\left[u_{0},u_{1},\dots,u_{k-1}\right],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/356e9dd32012d4b25f4a3c78179554570098e78e)
![{\displaystyle \mathbf {v} _{k}=\left[v_{0},v_{1},\dots,v_{k-1}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f9338d3797abffd4007c6c2ab27aaed7e04e893)
