ブロイデンの方法

割線法では、 x _nにおける一次導関数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 より大きい場合、不確定です。Broyden は、ヤコビ行列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})。}$

もし${\displaystyle \alpha =1}$これは完全なニュートンステップです。一般的には、ラインサーチまたはトラストリージョン法を使用して制御します。${\displaystyle \alpha }$初期ヤコビ行列は対角単位行列とすることもできますが、最初のステップに基づいてスケーリングするのが一般的です。^{[ 3 ]}ブロイデンはまた、シャーマン・モリソン公式^{[ 4 ]}を使用して近似ヤコビ行列の逆行列を直接更新することを提案しました。

${\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}}}\デルタ \mathbf {f} _{n}^{\mathrm {T} }.}$

これは別のフロベニウスノルムを最小化する

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

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