数値解析において、ブロイデン法（ブロイデンほう、）とは準ニュートン法の1種であり、多変数関数の求根に用いられるアルゴリズムである。1965年にが発表した。
ニュートン法によりを解く場合、各イテレーションごとにヤコビアンを用いることになる。しかし、ヤコビアンを計算するには困難で複雑な演算を要する。ブロイデン法では、ヤコビアン全体を最初のイテレーションで1回だけ計算し、以降のイテレーションではランク1更新を用いる。
1979年、Gayによりブロイデン法はサイズの線形システムに適用したときステップで終了することが証明された。しかし、他の準ニュートン法と同様、非線形システムに対しては収束する保証はない。
手法の詳細 1変数方程式の求根 割線法では、のにおける1階微分を有限差分近似する。
その上で、ニュートン法と同様の操作を繰り返す
ここではイテレーション指数である。
非線形方程式系の求根 本の非線形方程式の系
を考える。ここではベクトルのベクトル値関数である。
このような問題に対して、ブロイデンは1次元ニュートン法の微分をヤコビアンで置き換えて一般化した手法を考案した。ヤコビアンは、次のように割線法における有限差分近似にもとづいて反復的に決定される。
ここではイテレーション指数である。
のように定義すると、上式は以下のように簡潔に書ける。
上式はが1より大きい場合はとなる。ブロイデンは、以下のようにヤコビアンの現状の推定値を最低限の変更により割線方程式を満たすよう改善することを提案した。
これにより以下のフロベニウスノルムが最小化される。
これによりニュートン方向へ進むことができる。
ブロイデンはを用いてヤコビアンの逆行列を直接更新することも提案している。
この1つ目の手法は「良いブロイデン法」とも呼ばれる。
類似手法として、に若干異なる変更を加える手法も導出できる。この2つめの手法は「悪いブロイデン法」とも呼ばれる（ただし、を参照）。
これは上とはことなる以下のフロベニウスノルムを最小化する。
他にも多くの準ニュートン法が提案されており、これを用いてある関数の勾配の求根を行うことによりその関数の最大値または最小値を見つける、すなわち最適化を行うために活用されている。勾配のヤコビアンはヘッシアンと呼ばれ、対称行列であるため更新式にさらなる制約が追加される。
Broyden Classの手法 上述の2つの手法に加え、ブロイデンは関連する手法の1群を定義した。一般に、Broyden Classの手法は以下の形式で与えられる。ここで、および、であり、に対して各を定めることによりその手法が決定される。
Broyden classに分類できる手法のいくつかは他の著者により提案されている。
DFP法はBroyden classに分類できる手法のうち、先述の2手法がブロイデンにより提案されるようりも前に発表されていた唯一の手法である。DFP法はを用いる。 Schubert's algorithmまたは疎ブロイデン法は疎なヤコビアン向けの修正版である。 Klement (2014) は多方程式系の求根を少ないイテレーションで解く。
脚注
参考文献
関連項目 割線法 ニュートン法 準ニュートン法 最適化におけるニュートン法 DFP法 BFGS法
外部リンク Simple basic explanation: The story of the blind archer