ブロイデン法

ブロイデン法とは

ブロイデン法は、数値解析における多変数関数の求根アルゴリズムの一つで、準ニュートン法に分類されます。この手法は、ニュートン法におけるヤコビアンの計算を効率化するために考案されました。1965年にチャールズ・ジョージ・ブロイデンによって発表されました。

ニュートン法との比較

ニュートン法では、関数 f(x) = 0 の解を求める際に、各反復処理でヤコビアン J を使用します。しかし、ヤコビアンの計算は複雑でコストがかかる場合があります。ブロイデン法では、最初の反復でのみヤコビアンを計算し、それ以降の反復ではランク1更新を利用することで、計算コストを削減します。

ブロイデン法の収束性

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

ブロイデン法の詳細

1変数方程式の求根

1変数方程式の求根では、割線法を用いて f'(x) の1階微分を有限差分近似します。

math
f'(x_n) \simeq \frac{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}}

この近似を用いて、ニュートン法と同様に反復計算を行います。

math
x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

ここで n は反復回数を示します。

非線形方程式系の求根

k 個の非線形方程式からなる系 f(x) = 0 を考えます。ここで、f はベクトル x のベクトル値関数です。

math
x = (x_1, x_2, x_3, ..., x_k)

math
f(x) = (f_1(x_1, x_2, ..., x_k), f_2(x_1, x_2, ..., x_k), ..., f_k(x_1, x_2, ..., x_k))

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

math
J_n(x_n - x_{n-1}) \simeq f(x_n) - f(x_{n-1})

ここで n は反復回数です。

math
f_n = f(x_n)

math
\Delta x_n = x_n - x_{n-1}

math
\Delta f_n = f_n - f_{n-1}

と定義すると、上記式は以下のように簡潔に表現できます。

math
J_n \Delta x_n \simeq \Delta f_n

k > 1 の場合、上式は劣決定系となります。ブロイデンは、ヤコビアンの現在の推定値 J_{n-1} を最小限の変更で割線方程式を満たすように改善することを提案しました。

math
J_n = J_{n-1} + \frac{\Delta f_n - J_{n-1} \Delta x_n}{\|\Delta x_n\|^2} \Delta x_n^T

この更新式は、フロベニウスノルムを最小化します。

math
\|J_n - J_{n-1}\|_F

これにより、次のステップの探索方向（ニュートン方向）に進むことができます。

math
x_{n+1} = x_n - J_n^{-1}f(x_n)

ブロイデンは、シャーマン・モリソンの公式を用いてヤコビアンの逆行列を直接更新する方法も提案しています。

math
J_n^{-1} = J_{n-1}^{-1} + \frac{\Delta x_n - J_{n-1}^{-1} \Delta f_n}{\Delta x_n^T J_{n-1}^{-1} \Delta f_n} \Delta x_n^T J_{n-1}^{-1}

この手法は「良いブロイデン法」と呼ばれます。

別の手法として、J_{n-1}に異なる変更を加える手法も導出できます。この手法は「悪いブロイデン法」と呼ばれます。

math
J_n^{-1} = J_{n-1}^{-1} + \frac{\Delta x_n - J_{n-1}^{-1} \Delta f_n}{\|\Delta f_n\|^2} \Delta f_n^T

この更新式は、フロベニウスノルムを最小化します。

math
\|J_n^{-1} - J_{n-1}^{-1}\|_F

Broyden Classの手法

上記二つの手法に加えて、ブロイデンは関連する手法群を定義しました。一般に、Broyden Classの手法は次の形式で与えられます。

math
J_{k+1} = J_k - \frac{J_k s_k s_k^T J_k}{s_k^T J_k s_k} + \frac{y_k y_k^T}{y_k^T s_k} + \phi_k(s_k^T J_k s_k)v_k v_k^T

ここで、

math
y_k := f(x_{k+1}) - f(x_k)

math
s_k := x_{k+1} - x_k

math
v_k = \left[\frac{y_k}{y_k^T s_k} - \frac{J_k s_k}{s_k^T J_k s_k}\right]

そして、

math
k = 1, 2, ...

に対して、各

math
\phi_k \in \mathbb{R}

を定めることで、手法が決定されます。

その他の準ニュートン法

他にも多くの準ニュートン法が提案されており、関数の勾配の求根を通じて、関数の最大値または最小値を求める最適化に利用されています。勾配のヤコビアンはヘッセ行列と呼ばれ、対称行列であるため、更新式に制約が追加されます。

DFP法は、ブロイデンが提案する以前から存在した手法で、Broyden Classに分類できます。

DFP法では、

math
\phi_k = 1

を用います。

疎なヤコビアンのための修正版として、疎ブロイデン法があります。また、Klement (2014) は、少ない反復回数で多方程式系の根を求める方法を提案しています。