Algorithm for solving systems of linear equations
数学 、より具体的には 数値線形代数 において、 共役勾配法は連立 一 次方程式 を解く アルゴリズム です
A x = b . {\displaystyle Ax=b.\,} 共役勾配法 とは異なり、このアルゴリズムでは 行列が 自己随伴で ある 必要はありませんが、代わりに 共役転置 A * による乗算を実行する必要があります 。 A {\displaystyle A}
アルゴリズム 初期推定値 、他の2つのベクトル 、 および 前処理を選択します 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}.\,} この特定の選択により、 および A −1 の明示的な評価が回避され、アルゴリズムは上記の形式になります。 P k {\displaystyle P_{k}}
性質 が 自己随伴 、 かつ 、 の 場合 、、、 共役勾配法は 同じシーケンスを 半分の計算コストで生成します 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}
参照
参考文献 Fletcher, R. (1976). 「不定値系に対する共役勾配法」. Watson, G. Alistair (編). 数値解析：ダンディー数値解析会議議事録 . 数学講義ノート. 第506巻. Springer. pp. 73– 89. doi :10.1007/BFb0080116. ISBN 978-3-540-07610-0 。 Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). 「セクション2.7.6」. 数値レシピ：科学計算の芸術 （第3版）. ニューヨーク：ケンブリッジ大学出版局. ISBN 978-0-521-88068-8 。
![{\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)
