数値数学 において 、 宇沢反復法は 鞍点 問題を解くアルゴリズムである。 宇沢弘文 にちなんで名付けられ 、もともと凹計画法の文脈で導入された。 [1]
基本的な考え方 次のような形の鞍点問題を考える。
（
あ
B
B
∗
）
（
x
1
x
2
）
=
（
b
1
b
2
）
、
{\displaystyle {\begin{pmatrix}A&B\\B^{*}&\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}={\begin{pmatrix}b_{1}\\b_{2}\end{pmatrix}},}
ここで、は 対称 正定値行列 である。第1行にを掛け 、第2行から引くと、上三角行列が得られる。
あ
{\displaystyle A}
B
∗
あ
− 1
{\displaystyle B^{*}A^{-1}}
（
あ
B
− S
）
（
x
1
x
2
）
=
（
b
1
b
2
−
B
∗
あ
− 1
b
1
）
、
{\displaystyle {\begin{pmatrix}A&B\\&-S\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}={\begin{pmatrix}b_{1}\\b_{2}-B^{*}A^{-1}b_{1}\end{pmatrix}},}
ここで、は シュア補集合 を表す 。は 対称正定値なので、 勾配降下
法や 共役勾配法 などの標準的な反復法を適用して解く
ことができる。
S :=
B
∗
あ
− 1
B
{\displaystyle S:=B^{*}A^{-1}B}
S
{\displaystyle S}
S
x
2
=
B
∗
あ
− 1
b
1
−
b
2
{\displaystyle Sx_{2}=B^{*}A^{-1}b_{1}-b_{2}}
を計算するために 、ベクトルは 次のように解くことで再構成できる
。
x
2
{\displaystyle x_{2}}
x
1
{\displaystyle x_{1}}
あ
x
1
=
b
1
− B
x
2
。
{\displaystyle Ax_{1}=b_{1}-Bx_{2}.\,}
シュアー補数システムの反復中に並行して 更新することができ 、効率的なアルゴリズムを取得できます。
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
実装 共役勾配反復は残差を計算することから始まる。
r
2
:=
B
∗
あ
− 1
b
1
−
b
2
− S
x
2
=
B
∗
あ
− 1
（
b
1
− B
x
2
） −
b
2
=
B
∗
x
1
−
b
2
、
{\displaystyle r_{2}:=B^{*}A^{-1}b_{1}-b_{2}-Sx_{2}=B^{*}A^{-1}(b_{1}-Bx_{2})-b_{2}=B^{*}x_{1}-b_{2},}
シューア補体系の
x
1
:=
あ
− 1
（
b
1
− B
x
2
）
{\displaystyle x_{1}:=A^{-1}(b_{1}-Bx_{2})}
解ベクトルの上半分が 下半分の初期推定値と一致することを表す。最初の探索方向を選択することで初期化を完了する。
x
2
{\displaystyle x_{2}}
p
2
:=
r
2
。
{\displaystyle p_{2}:=r_{2}.\,}
各ステップで計算する
1つの
2
:= S
p
2
=
B
∗
あ
− 1
B
p
2
=
B
∗
p
1
{\displaystyle a_{2}:=Sp_{2}=B^{*}A^{-1}Bp_{2}=B^{*}p_{1}}
中間結果を保存する
p
1
:=
あ
− 1
B
p
2
{\displaystyle p_{1}:=A^{-1}Bp_{2}}
スケーリング係数は次のように与えられる。
α :=
p
2
∗
1つの
2
/
p
2
∗
r
2
{\displaystyle \alpha :=p_{2}^{*}a_{2}/p_{2}^{*}r_{2}}
そしてアップデートにつながる
x
2
:=
x
2
+ α
p
2
、
r
2
:=
r
2
− α
1つの
2
。
{\displaystyle x_{2}:=x_{2}+\alpha p_{2},\quad r_{2}:=r_{2}-\alpha a_{2}.}
先ほど保存した中間結果を使用して 、解ベクトルの上部も更新することができます。
p
1
{\displaystyle p_{1}}
x
1
:=
x
1
− α
p
1
。
{\displaystyle x_{1}:=x_{1}-\alpha p_{1}.\,}
ここで、グラム・シュミット過程 によって新しい探索方向を構築するだけです 。つまり、
β :=
r
2
∗
1つの
2
/
p
2
∗
1つの
2
、
p
2
:=
r
2
− β
p
2
。
{\displaystyle \beta :=r_{2}^{*}a_{2}/p_{2}^{*}a_{2},\quad p_{2}:=r_{2}-\beta p_{2}.}
残差が十分に小さくなるか、 のノルムが よりも大幅に小さくなり、 クリロフ部分空間 がほぼ使い果たされた
ことが示された場合 、反復は終了します。
r
2
{\displaystyle r_{2}}
p
2
{\displaystyle p_{2}}
r
2
{\displaystyle r_{2}}
変更と拡張 線形システムを 正確に解くことが不可能な場合は、不正確なソルバーを適用することができます。 [2] [3] [4]
あ x = b
{\displaystyle Ax=b}
シュア補体系が悪条件である場合、基礎となる勾配法の収束速度を改善するために前処理を採用することができる。 [2] [5]
不等式制約は、例えば障害物問題を扱うために組み込むことができる。 [5]
参考文献
^ Uzawa, H. (1958). 「凹面計画法の反復法」。Arrow, KJ、Hurwicz, L.、Uzawa, H. (編)。 線形および非線形計画法の研究 。スタンフォード大学出版局。 ^ エルマンHC; ゴルブ、GH (1994)。 「鞍点問題に対する不正確で事前条件付けされた宇沢アルゴリズム」。 サイアム J. ヌマーアナル。 31 (6): 1645 ～ 1661 年。 CiteSeerX 10.1.1.307.8178 。 土井 ：10.1137/0731085。 ^ JH、ブランブル ;パシアク、JE;ヴァシレフ、AT (1997)。 「鞍点問題に対する不正確な宇沢アルゴリズムの分析」。 サイアム J. ヌマーアナル 。 34 (3): 1072 ～ 1982 年。 CiteSeerX 10.1.1.52.9559 。 土井 ：10.1137/S0036142994273343。 ^ Zulehner, W. (1998). 「鞍点問題に対する反復法の解析。統一的アプローチ」。Math . Comp . 71 (238): 479–505. doi : 10.1090/S0025-5718-01-01324-2 。 ^ ab Gräser, C.; Kornhuber, R. (2007). 「不等式制約のある鞍点問題に対する前処理付き Uzawa 型反復について」. 科学と工学における領域分割法 XVI . Lec. Not. Comp. Sci. Eng. Vol. 55. pp. 91–102. CiteSeerX 10.1.1.72.9238 . doi :10.1007/978-3-540-34469-8_8. ISBN 978-3-540-34468-1 。
さらに読む Chen, Zhangxin (2006)。「線形システム解法テクニック」 有限要素法とその応用 ベルリン: Springer。pp. 145–154。ISBN 978-3-540-28078-1 。 
