ブロイデン法

数値解析において、ブロイデン法（ブロイデンほう、テンプレート:Lang-en-short）とは準ニュートン法の1種であり、多変数関数の求根に用いられるアルゴリズムである。1965年にテンプレート:仮リンクが発表した。

ニュートン法によりテンプレート:Mathを解く場合、各イテレーションごとにヤコビアンテンプレート:Mvarを用いることになる。しかし、ヤコビアンを計算するには困難で複雑な演算を要する。ブロイデン法では、ヤコビアン全体を最初のイテレーションで1回だけ計算し、以降のイテレーションではランク1更新を用いる。

1979年、Gayによりブロイデン法はサイズテンプレート:Mathの線形システムに適用したときテンプレート:Mathステップで終了することが証明された。しかし、他の準ニュートン法と同様、非線形システムに対しては収束する保証はない。

手法の詳細

1変数方程式の求根

割線法では、テンプレート:Mathのテンプレート:Mathにおける1階微分を有限差分近似する。

$f^{\prime }(x_n)\simeq \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}$

その上で、ニュートン法と同様の操作を繰り返す

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

ここでテンプレート:Mathはイテレーション指数である。

非線形方程式系の求根

テンプレート:Math本の非線形方程式の系

$𝒇(𝒙)=\mathrm{𝟎}$

を考える。ここでテンプレート:Mvarはベクトルテンプレート:Mvarのベクトル値関数である。

$𝒙=(x_1,x_2,x_3,\dots ,x_k)$

$𝒇(𝒙)=(f_1(x_1,x_2,\dots ,x_k),f_2(x_1,x_2,\dots ,x_k),\dots ,f_k(x_1,x_2,\dots ,x_k))$

このような問題に対して、ブロイデンは1次元ニュートン法の微分をヤコビアンテンプレート:Mvarで置き換えて一般化した手法を考案した。ヤコビアンは、次のように割線法における有限差分近似にもとづいて反復的に決定される。

${𝑱}_n({𝒙}_n-{𝒙}_{n-1})\simeq 𝒇({𝒙}_n)-𝒇({𝒙}_{n-1})$

ここでテンプレート:Mathはイテレーション指数である。

${𝒇}_n=𝒇({𝒙}_n)$

$\mathrm{\Delta }{𝒙}_n={𝒙}_n-{𝒙}_{n-1}$

$\mathrm{\Delta }{𝒇}_n={𝒇}_n-{𝒇}_{n-1}$

のように定義すると、上式は以下のように簡潔に書ける。

${𝑱}_n\mathrm{\Delta }{𝒙}_n\simeq \mathrm{\Delta }{𝒇}_n$

上式はテンプレート:Mathが1より大きい場合はテンプレート:仮リンクとなる。ブロイデンは、以下のようにヤコビアンの現状の推定値テンプレート:Mathを最低限の変更により割線方程式を満たすよう改善することを提案した。

${𝑱}_n={𝑱}_{n-1}+\frac{\mathrm{\Delta }{𝒇}_n-{𝑱}_{n-1}\mathrm{\Delta }{𝒙}_n}{\Vert \mathrm{\Delta }{𝒙}_n{\Vert }^2}\mathrm{\Delta }{𝒙}_n^{\mathrm{\top }}$

これにより以下のフロベニウスノルムが最小化される。

$\Vert {𝑱}_n-{𝑱}_{n-1}{\Vert }_{\mathrm{F}}$

これによりニュートン方向へ進むことができる。

${𝒙}_{n+1}={𝒙}_n-{𝑱}_n^{-1}𝒇({𝐱}_n)$

ブロイデンはテンプレート:仮リンクを用いてヤコビアンの逆行列を直接更新することも提案している。

${𝑱}_n^{-1}={𝑱}_{n-1}^{-1}+\frac{\mathrm{\Delta }{𝒙}_n-{𝑱}_{n-1}^{-1}\mathrm{\Delta }{𝒇}_n}{\mathrm{\Delta }{𝒙}_n^{\mathrm{T}}{𝑱}_{n-1}^{-1}\mathrm{\Delta }{𝒇}_n}\mathrm{\Delta }{𝒙}_n^{\mathrm{\top }}{𝑱}_{n-1}^{-1}$

この1つ目の手法は「良いブロイデン法」テンプレート:訳語疑問点とも呼ばれる。

類似手法として、テンプレート:Mathに若干異なる変更を加える手法も導出できる。この2つめの手法は「悪いブロイデン法」テンプレート:訳語疑問点とも呼ばれる（ただし、を参照）。

${𝑱}_n^{-1}={𝑱}_{n-1}^{-1}+\frac{\mathrm{\Delta }{𝒙}_n-{𝑱}_{n-1}^{-1}\mathrm{\Delta }{𝒇}_n}{\Vert \mathrm{\Delta }{𝒇}_n{\Vert }^2}\mathrm{\Delta }{𝒇}_n^{\mathrm{\top }}$

これは上とはことなる以下のフロベニウスノルムを最小化する。

$\Vert {𝑱}_n^{-1}-{𝑱}_{n-1}^{-1}{\Vert }_{\mathrm{F}}$

他にも多くの準ニュートン法が提案されており、これを用いてある関数の勾配の求根を行うことによりその関数の最大値または最小値を見つける、すなわち最適化を行うために活用されている。勾配のヤコビアンはヘッシアンと呼ばれ、対称行列であるため更新式にさらなる制約が追加される。

Broyden Classの手法

上述の2つの手法に加え、ブロイデンは関連する手法の1群を定義したテンプレート:Rp。一般に、Broyden Classテンプレート:訳語疑問点の手法は以下の形式で与えられるテンプレート:Rp。$${𝑱}_{k+1}={𝑱}_k-\frac{{𝑱}_k{s}_k{s}_k^{\mathrm{\top }}{𝑱}_k}{s_k^{\mathrm{\top }}{𝑱}_k{s}_k}+\frac{y_k{y}_k^{\mathrm{\top }}}{y_k^T{s}_k}+{\varphi }_k\left(s_k^{\mathrm{\top }}{𝑱}_k{s}_k\right)v_k{v}_k^{\mathrm{\top }}$$ここで、$y_k:=𝒇({𝒙}_{k+1})-𝒇({𝒙}_k)$および$s_k:={𝒙}_{k+1}-{𝒙}_k$、$$v_k=[\frac{y_k}{y_k^T{s}_k}-\frac{{𝐉}_k{s}_k}{s_k^T{𝐉}_k{s}_k}]$$であり、$k=1,2,...$に対して各${\varphi }_k\in ℝ$を定めることによりその手法が決定される。

Broyden classに分類できる手法のいくつかは他の著者により提案されている。

• DFP法はBroyden classに分類できる手法のうち、先述の2手法がブロイデンにより提案されるようりも前に発表されていた唯一の手法であるテンプレート:Rp。DFP法は${\varphi }_k=1$を用いるテンプレート:Rp。
• Schubert's algorithmテンプレート:訳語疑問点または疎ブロイデン法は疎なヤコビアン向けの修正版である。
• Klement (2014) は多方程式系の求根を少ないイテレーションで解く。

参考文献

• テンプレート:Cite book
• テンプレート:Cite book

関連項目

• 割線法
• ニュートン法
• 準ニュートン法
• 最適化におけるニュートン法
• DFP法
• BFGS法

外部リンク

• Simple basic explanation: The story of the blind archer