ブロイデン法

1変数方程式の求根

割線法では、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}}}$

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

${\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}}}$

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