この項目「ブロイデン法」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en: Broyden's method） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2024年9月）

数値解析において、ブロイデン法（ブロイデンほう英: Broyden's method）とは準ニュートン法の1種であり、多変数関数の求根に用いられるアルゴリズムである。1965年にチャールズ・ジョージ・ブロイデン（英語版）が発表した^[1]。

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

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

割線法では、f′のx_nにおける1階微分を有限差分近似する。

${\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 {\boldsymbol {f}}({\boldsymbol {x}})=\mathbf {0} }$

を考える。ここでfはベクトルxのベクトル値関数である。

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

${\displaystyle {\boldsymbol {f}}({\boldsymbol {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 {\boldsymbol {J}}_{n}({\boldsymbol {x}}_{n}-{\boldsymbol {x}}_{n-1})\simeq {\boldsymbol {f}}({\boldsymbol {x}}_{n})-{\boldsymbol {f}}({\boldsymbol {x}}_{n-1})}$

ここでnはイテレーション指数である。

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

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

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

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

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

上式はkが1より大きい場合は劣決定系（英語版）となる。ブロイデンは、以下のようにヤコビアンの現状の推定値J_n−1を最低限の変更により割線方程式を満たすよう改善することを提案した。

${\displaystyle {\boldsymbol {J}}_{n}={\boldsymbol {J}}_{n-1}+{\frac {\Delta {\boldsymbol {f}}_{n}-{\boldsymbol {J}}_{n-1}\Delta {\boldsymbol {x}}_{n}}{\|\Delta {\boldsymbol {x}}_{n}\|^{2}}}\Delta {\boldsymbol {x}}_{n}^{\top }}$

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

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

これでNewton direction^{[訳語疑問点]}へ進むことができる。

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

ブロイデンはSherman-Morrisonの公式（英語版）を用いてヤコビアンの逆行列を直接更新することも提案している。

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

この1つめの手法は「良いブロイデン法」とも呼ばれる。

類似手法として、J_n−1に若干異なる変更を加える手法も導出できる。この2つめの手法は「悪いブロイデン法」とも呼ばれる(ただし、^[3]を参照)。

${\displaystyle {\boldsymbol {J}}_{n}^{-1}={\boldsymbol {J}}_{n-1}^{-1}+{\frac {\Delta {\boldsymbol {x}}_{n}-{\boldsymbol {J}}_{n-1}^{-1}\Delta {\boldsymbol {f}}_{n}}{\|\Delta {\boldsymbol {f}}_{n}\|^{2}}}\Delta {\boldsymbol {f}}_{n}^{\top }}$

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

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

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

上述の2つの手法に加え、ブロイデンは関連する手法の1群を定義した^[1]:578。一般に、Broyden Class^{[訳語疑問点]}の手法は以下の形式で与えられる^[4]:150。$${\displaystyle {\boldsymbol {J}}_{k+1}={\boldsymbol {J}}_{k}-{\frac {{\boldsymbol {J}}_{k}s_{k}s_{k}^{\top }{\boldsymbol {J}}_{k}}{s_{k}^{\top }{\boldsymbol {J}}_{k}s_{k}}}+{\frac {y_{k}y_{k}^{\top }}{y_{k}^{T}s_{k}}}+\phi _{k}\left(s_{k}^{\top }{\boldsymbol {J}}_{k}s_{k}\right)v_{k}v_{k}^{\top }}$$ここで、${\displaystyle y_{k}:={\boldsymbol {f}}({\boldsymbol {x}}_{k+1})-{\boldsymbol {f}}({\boldsymbol {x}}_{k})}$および${\displaystyle s_{k}:={\boldsymbol {x}}_{k+1}-{\boldsymbol {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 k=1,2,...}$に対して各${\displaystyle \phi _{k}\in \mathbb {R} }$を定めることによりその手法が決定される。

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

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

• 割線法
• ニュートン法
• 準ニュートン法
• ニュートン法による最適化（英語版）
• DFP法
• BFGS法

• Dennis, J. E.; Schnabel, Robert B. (1983). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice Hall. pp. 168–193. ISBN 0-13-627216-9 
• Fletcher, R. (1987). Practical Methods of Optimization (Second ed.). New York: John Wiley & Sons. pp. 44–79. ISBN 0-471-91547-5. https://archive.org/details/practicalmethods0000flet 

• Simple basic explanation: The story of the blind archer