当記事では下記に基づいてニュートン法の2次収束について確認します。
前提の確認
ニュートン法
\begin{align}
x_{K+1} = x_{K} - \frac{f'(x_{K})}{f^{''}(x_{K})} \quad (1)
\end{align}
最適化アルゴリズムの収束(1次収束、2次収束)
漸化式を用いた反復によって最適化を行うアルゴリズムの$n$回目の近似値の誤差を$\epsilon^{(K)}$とおきます。このとき誤差が一定の割合で減少する反復手法を1次収束、$\epsilon_{K+1}$が$\epsilon_{K}^{2}$の定数倍となる反復手法を2次収束といいます。
勾配法など、多くの最適化アルゴリズムが1次収束であるのに対し、ニュートン法は2次収束のアルゴリズムであり収束が速いです。
ニュートン法の2次収束の導出
1変数関数
真の解を$x=a$とし、$K$回目の反復の解$x_{K}$を誤差$\epsilon_{K}$を用いて下記のように定義します。
\begin{align}
x_{K} = a + \epsilon_{K}
\end{align}
このとき解$x=a$では$f'(a)=0$であるので$f'(x_{K})$と$f^{''}(x_{K})$、$f^{''}(x_{K})$のテイラー展開はそれぞれ下記のように表すことができます。
\begin{align}
f'(x_{K}) &= f'(a + \epsilon_{K}) \\
&= f'(a) + f^{''}(a) \epsilon_{K} + \frac{1}{2}f^{'''}(a) \epsilon_{K}^{2} + \cdots \\
&= f^{''}(a) \epsilon_{K} + \frac{1}{2}f^{'''}(a) \epsilon_{K}^{2} + O(\epsilon_{K}^{3}) \quad (2) \\
f^{''}(x_{K}) &= f^{''}(a + \epsilon_{K}) \\
&= f^{''}(a) + f^{'''}(a) \epsilon_{K} + O(\epsilon_{K}^{2}) \\
\frac{1}{f^{''}(x_{K})} &= \frac{1}{f^{''}(a + \epsilon_{K})} \\
&= \frac{1}{f^{''}(a)} - \frac{f^{'''}(a)}{f^{''}(a)^{2}} \epsilon_{K} + O(\epsilon_{K}^{2}) \\
&= \frac{1}{f^{''}(a)} \left( 1 - \frac{f^{'''}(a)}{f^{''}(a)} \epsilon_{K} + O(\epsilon_{K}^{2}) \right) \quad (3)
\end{align}
ここで$(2)$式と$(3)$式を$(1)$式に代入すると下記のように変形を行うことができます。
\begin{align}
x_{K+1} &= x_{K} - \frac{f'(x_{K})}{f^{''}(x_{K})} \quad (1) \\
&= x_{K} - \left( f^{''}(a) \epsilon_{K} + \frac{1}{2}f^{'''}(a) \epsilon_{K}^{2} + O(\epsilon_{K}^{3}) \right) \times \frac{1}{f^{''}(a)} \left( 1 - \frac{f^{'''}(a)}{f^{''}(a)} \epsilon_{K} + O(\epsilon_{K}^{2}) \right) \\
&= x_{K} - \left( \epsilon_{K} - \frac{f^{'''}(a)}{f^{''}(a)} \epsilon_{K}^{2} + \frac{f^{'''}(a)}{2f^{''}(a)} \epsilon_{K}^{2} + O(\epsilon_{K}^{3}) \right) \\
&= (x_{K} - \epsilon_{K}) + \frac{f^{'''}(a)}{2f^{''}(a)} \epsilon_{K}^{2} + O(\epsilon_{K}^{3}) \\
&= a + \frac{f^{'''}(a)}{2f^{''}(a)} \epsilon_{K}^{2} + O(\epsilon_{K}^{3})
\end{align}
$x_{K+1} = a + \epsilon_{K+1}$であるので下記のような$\epsilon_{K}$と$\epsilon_{K+1}$に関する式が得られます。
\begin{align}
x_{K+1} = a + \frac{f^{'''}(a)}{2f^{''}(a)} \epsilon_{K}^{2} + O(\epsilon_{K}^{3}) &= a + \epsilon_{K+1} \\
\epsilon_{K+1} &= \frac{f^{'''}(a)}{2f^{''}(a)} \epsilon_{K}^{2} + O(\epsilon_{K}^{3})
\end{align}
上記より$\epsilon_{K+1}$が$\epsilon_{K}$の2乗に比例することが確認できるので、ニュートン法は2次収束であるということが示されます。