ブロイデン法

Quasi-Newton root-finding method for the multivariable case

数値解析において、ブロイデン法はk変数の根を求める準ニュートン法です。 1965年にCGブロイデンによって最初に記述されました。^[1]

f ( x ) = 0を解くニュートン法では、ヤコビ行列Jをすべての反復で使用します。しかし、このヤコビ行列の計算は困難でコストのかかる操作になる可能性があります。量子力学におけるコーン・シャム方程式を解くような大規模な問題では、変数の数は数十万に達することがあります。ブロイデン法の背後にある考え方は、ヤコビ行列全体を最大で最初の反復でのみ計算し、他の反復ではランク1の更新を行うことです。

1979年、ゲイはブロイデン法をサイズn × nの線形システムに適用すると、 2 nステップで終了することを証明しました^[2]。ただし、すべての準ニュートン法と同様に、非線形システムでは収束しない可能性があります。

方法の説明

一変数非線形方程式の解法

セカント法では、 x _nにおける1次導関数f ′を有限差分近似に置き換えます。

${\displaystyle f'(x_{n})\simeq {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}},}$

そして、ニュートン法と同様に進めます

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f^{\prime }(x_{n})}}}$

ここで、nは反復回数のインデックスです。

非線形方程式系を解く

未知数k個の非線形方程式系を考える ${\displaystyle k}$

${\displaystyle \mathbf {f} (\mathbf {x} )=\mathbf {0} ,}$

ここで、fはベクトルxのベクトル値関数である

${\displaystyle \mathbf {x} =(x_{1},x_{2},x_{3},\dotsc ,x_{k}),}$

${\displaystyle \mathbf {f} (\mathbf {x} )={\big (}f_{1}(x_{1},x_{2},\dotsc ,x_{k}),f_{2}(x_{1},x_{2},\dotsc ,x_{k}),\dotsc ,f_{k}(x_{1},x_{2},\dotsc ,x_{k}){\big )}.}$

このような問題に対して、ブロイデンは1次元ニュートン法のバリエーションを提示し、導関数を近似ヤコビ行列 Jに置き換えます。近似ヤコビ行列は、有限差分 近似である割線方程式に基づいて反復的に決定されます。

${\displaystyle \mathbf {J} _{n}(\mathbf {x} _{n}-\mathbf {x} _{n-1})\simeq \mathbf {f} (\mathbf {x} _{n})-\mathbf {f} (\mathbf {x} _{n-1}),}$

ここで、 nは反復回数のインデックスです。明確にするために、

${\displaystyle \mathbf {f} _{n}=\mathbf {f} (\mathbf {x} _{n}),}$

${\displaystyle \Delta \mathbf {x} _{n}=\mathbf {x} _{n}-\mathbf {x} _{n-1},}$

${\displaystyle \Delta \mathbf {f} _{n}=\mathbf {f} _{n}-\mathbf {f} _{n-1},}$

と定義します。したがって、上記は次のように書き直すことができます。

${\displaystyle \mathbf {J} _{n}\Delta \mathbf {x} _{n}\simeq \Delta \mathbf {f} _{n}.}$

上記の式は、kが1より大きい場合、劣決定です。ブロイデンは、ヤコビ行列J _{n −1}の最新の推定値を使用し、新しい形式が最新の割線方程式の解であり、 J _{n −1}への変更が最小限であることを要求することで、それを改良することを提案しました。

${\displaystyle \mathbf {J} _{n}=\mathbf {J} _{n-1}+{\frac {\Delta \mathbf {f} _{n}-\mathbf {J} _{n-1}\Delta \mathbf {x} _{n}}{\|\Delta \mathbf {x} _{n}\|^{2}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }.}$

これにより、フロベニウスノルムが最小化されます

${\displaystyle \|\mathbf {J} _{n}-\mathbf {J} _{n-1}\|_{\rm {F}}.}$

次に、近似ヤコビアン（準ニュートン法）を使用して変数を更新します。

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\alpha \mathbf {J} _{n}^{-1}\mathbf {f} (\mathbf {x} _{n}).}$

これが完全なニュートンステップの場合、一般的に直線探索法または信頼領域法が制御に使用されます。初期のヤコビ行列は対角単位行列としてとることができますが、より一般的なのは最初のステップに基づいてスケーリングすることです。^[3] Broydenは、近似ヤコビ行列の逆行列を直接更新するために、 Sherman–Morrisonの公式^{[4]を使用することも提案しました。} ${\displaystyle \alpha =1}$ ${\displaystyle \alpha }$

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}.}$

この最初の方法は、一般に「良いブロイデン法」として知られています。

J _{n −1}にわずかに異なる修正を加えることで、同様の手法を導くことができます。これにより、いわゆる「悪いブロイデン法」と呼ばれる2番目の方法が得られます。

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\|\Delta \mathbf {f} _{n}\|^{2}}}\Delta \mathbf {f} _{n}^{\mathrm {T} }.}$

これは、異なるフロベニウスノルムを最小化します

${\displaystyle \|\mathbf {J} _{n}^{-1}-\mathbf {J} _{n-1}^{-1}\|_{\rm {F}}.}$

Broydenは元の論文では悪い方法をうまく機能させることができませんでしたが、うまく機能するケースがあり^[5]、いくつかの説明が提案されています^{[6] [7] 。最適}化においては、 BFGSのような多くの準ニュートン法が提案されています。BFGSでは、一次導関数の零点（多次元の勾配の零点）を見つけることで最大値または最小値を求めます。勾配のヤコビアンはヘッセ行列と呼ばれ、対称であるため、近似にさらなる制約が加わります。

ブロイデンの手法クラス

上記の2つの手法に加えて、Broydenはより広範な関連手法を定義しました。^{[1] ：578}一般に、Broydenの手法は^{[8] ：150} の形式で与えられ、各に対して、およびとなります。の選択によって手法が決まります。 $${\displaystyle \mathbf {J} _{k+1}=\mathbf {J} _{k}-{\frac {\mathbf {J} _{k}s_{k}s_{k}^{T}\mathbf {J} _{k}}{s_{k}^{T}\mathbf {J} _{k}s_{k}}}+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}s_{k}}}+\phi _{k}\left(s_{k}^{T}\mathbf {J} _{k}s_{k}\right)v_{k}v_{k}^{T},}$$ ${\displaystyle y_{k}:=\mathbf {f} (\mathbf {x} _{k+1})-\mathbf {f} (\mathbf {x} _{k}),}$ ${\displaystyle s_{k}:=\mathbf {x} _{k+1}-\mathbf {x} _{k},}$ $${\displaystyle v_{k}=\left[{\frac {y_{k}}{y_{k}^{T}s_{k}}}-{\frac {\mathbf {J} _{k}s_{k}}{s_{k}^{T}\mathbf {J} _{k}s_{k}}}\right],}$$ ${\displaystyle \phi _{k}\in \mathbb {R} }$ ${\displaystyle k=1,2,...}$ ${\displaystyle \phi _{k}}$

Broydenの手法クラスの他の方法は、他の著者によって導入されています

• Davidon–Fletcher–Powell（DFP）法は、Broydenによって定義された2つの方法より前に発表された、このクラスの唯一の方法です。^{[1] : 582} DFP法の場合、. ^{[8] : 150} ${\displaystyle \phi _{k}=1}$
• Andersonの反復法は、ヤコビ行列に最小二乗法を使用します。^[9]
• Schubertのアルゴリズムまたは疎Broydenアルゴリズム -疎ヤコビ行列の修正版です。^[10]
• Pulayアプローチは、密度汎関数理論でよく使用されます。^{[11] [12]}
• Srivastavaによる、根を求める問題に対する限定記憶法。これは最近の数回の反復のみを使用する。^[13]
• Klement (2014) – いくつかの系を解くために、より少ない反復を使用する。^{[14] [15]}
• 密度汎関数理論の問題に対する多重セカント法。^{[7] [16]}

関連項目

• 正割法
• ニュートン法
• 準ニュートン法
• 最適化におけるニュートン法
• ダビドン・フレッチャー・パウエルの公式
• ブロイデン・フレッチャー・ゴールドファーブ・シャノ（BFGS）法

参考文献

1. Broyden, CG (1965). "A Class of Methods for Solving Nonlinear Simultaneous Equations". Mathematics of Computation . 19 (92). American Mathematical Society: 577– 593. doi : 10.1090/S0025-5718-1965-0198670-6 . JSTOR  2003941
2. Gay, DM (1979). 「ブロイデン法の収束特性」. SIAM Journal on Numerical Analysis . 16 (4). SIAM: 623–630 . doi :10.1137/0716047.
3. Shanno, DF; Phua, Kang-Hoh (1978). 「行列条件付けと非線形最適化」 . Mathematical Programming . 14 (1): 149–160 . doi :10.1007/BF01588962. ISSN  0025-5610
4. シャーマン、ジャック；モリソン、ウィニフレッド・J. (1950). 「与えられた行列の1つの要素の変化に対応する逆行列の調整」．数理統計年報．21 ( 1): 124– 127. doi :10.1214/aoms/1177729893. ISSN  0003-4851.
5. クヴァーレン、エリック (1991). 「より高速なブロイデン法」．BIT数値数学．31 (2 ) . SIAM: 369– 372. doi :10.1007/BF01931297
6. Martı́nez, José Mario (2000). 「非線形系を解くための実用的な準ニュートン法」 . Journal of Computational and Applied Mathematics . 124 ( 1–2 ): 97–121 . doi :10.1016/s0377-0427(00)00434-9. ISSN  0377-0427.
7. Marks, LD; Luke, DR (2008). 「第一原理量子力学計算のためのロバスト混合」. Physical Review B. 78 ( 7). arXiv : 0801.3098 . doi :10.1103/physrevb.78.075114. ISSN  1098-0121
8. Nocedal, Jorge; Wright, Stephen J. (2006). 数値最適化. Springer Series in Operations Research and Financial Engineering. Springer New York. doi :10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1。
9. アンダーソン、ドナルド・G. (1965). 「非線形積分方程式の反復法」. Journal of the ACM . 12 (4): 547–560 . doi :10.1145/321296.321305. ISSN  0004-5411.
10. シューベルト、LK. (1970). 「疎ヤコビアンを持つ非線形方程式に対する準ニュートン法の修正」. Mathematics of Computation . 24 (109): 27–30 . doi : 10.1090/S0025-5718-1970-0258276-9 . ISSN  0025-5718
11. Pulay, Péter (1980). 「反復シーケンスの収束加速．SCF反復法の場合」．Chemical Physics Letters．73 ( 2 ): 393– 398. doi :10.1016/0009-2614(80)80396-4.
12. Kresse, G.; Furthmüller, J. (1996). 「平面波基底関数を用いた第一原理全エネルギー計算のための効率的な反復スキーム」．Physical Review B．54 ( 16): 11169– 11186. doi :10.1103/PhysRevB.54.11169. ISSN  0163-1829
13. Srivastava, GP (1984). 「自己無撞着な場の収束加速のためのブロイデン法」 . Journal of Physics A: Mathematical and General . 17 (6): L317 – L321 . doi :10.1088/0305-4470/17/6/002. ISSN  0305-4470.
14. Klement, Jan (2014). 「モデルとテストの相関のためのブロイデンクラスの準ニュートンアルゴリズムの使用について」. Journal of Aerospace Technology and Management . 6 (4): 407– 414. doi : 10.5028/jatm.v6i4.373 . ISSN  2175-9146
15. 「Broydenクラスメソッド – ファイル交換 – MATLAB Central」www.mathworks.com 。 2016年2月4日閲覧。
16. Woods, ND; Payne, MC; Hasnip, PJ (2019). 「Kohn–Sham密度汎関数理論における自己無撞着場の計算」Journal of Physics: Condensed Matter . 31 (45): 453001. arXiv : 1905.02332 . doi :10.1088/1361-648X/ab31c0. ISSN  0953-8984.

さらに詳しく

• Dennis, JE ; Schnabel, Robert B. (1983).制約なし最適化と非線形方程式の数値解析法. Englewood Cliffs: Prentice Hall. pp.  168– 193. ISBN 0-13-627216-9。
• Fletcher, R. (1987).実用的最適化法（第2版）. ニューヨーク: John Wiley & Sons. pp. 44–79. ISBN 0-471-91547-5。
• Kelley, CT (1995). 線形および非線形方程式の反復法. Society for Industrial and Applied Mathematics. doi :10.1137/1.9781611970944. ISBN 978-0-89871-352-7。

外部リンク

• 簡単な基本説明：盲目の射手の物語

Retrieved from "https://en.wikipedia.org/w/index.php?title=Broyden%27s_method&oldid=1301978487"