Newton法

定義1. 収束の次数

関数 \(f:\mathbb{R}\rightarrow\mathbb{R}\) について方程式 \(x=f(x)\) が根 \(p\in\mathbb{R}\) をもつとき

実数列 \(\{x_n\}\) について

\begin{align} &\{x_n\}\ がn次収束である\\[6pt] &\overset{\mathrm{def}}{\iff} \exists M\in(0,\infty)\ \;\forall i\in\mathbb{Z}^+ \ (\ |x_{i+1}-p|\le M|x_i-p|^n\ ) \end{align}

定理1. Newton法の2次収束

\(\exists! x\in I\ (f(x)=0)\) かつ \(\forall x\in I\ (f'(x)\neq 0)\) が成り立つような

任意の \(I\subseteq\mathbb{R}\), \(f:I\rightarrow I\in C^2(I)\) において,

\[x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}\quad(i\in\mathbb{Z}^+)\]

によって定められる実数列 \(\{x_n\}\) および \(f(x)=0\) の解 \(p\in I\) について

\[\exists I'\subseteq I\quad\forall x_0\in I\quad \bigl(|x_{i+1}-p|=O(|x_i-p|^2)\bigr)\]

定理の証明

補題1.

\begin{align} &\forall I\subseteq\mathbb{R}\quad \forall g:I\to I\in C^1(I)\\[5pt] &\bigl(\forall x\in I\ \ (|g'(x)|\lt1) \Longrightarrow g\ は縮小写像である\bigr) \end{align}

補題1の証明

任意の \(I\subseteq\mathbb{R}\), \(g:I\to I\in C^1(I)\) について

\begin{align} &\forall x\in I\quad(|g'(x)|\lt1)\\[5pt] &\Longrightarrow\exists p\in I\quad\forall x\in I\quad (|g'(x)|\le p\lt1) \end{align}
また平均値の定理より
\[\forall x,y\in I\quad\exists c\in [x,y]\quad(|g(x)-g(y)|=|g'(c)||x-y|)\]

以上より

\begin{align} &\forall x\in I\quad(|g'(x)|\lt1)\\[5pt] &\Longrightarrow\exists p\in I\quad\forall[x,y]\subseteq I\quad (|g(x)-g(y)|\le p|x-y|)\\[5pt] &\Longrightarrow g\ は縮小写像である \end{align}

よって補題1は示された.

定理1の証明

任意の \(I\subseteq\mathbb{R}\), \(g:I\to I\in C^2(I)\) を考える.

\[g(x)\triangleq x-\frac{f(x)}{f'(x)}\]

\(\exists I'\subseteq I\;(g|_{I'}\ は縮小写像である)\)

を示す. (ただし \(g|_{I'}\) は \(g\) の \(I'\) への制限写像)
\begin{align} &g'(x)=\frac{f'(x)f''(x)}{(f'(x))^2},\quad f(p)=0\\[4pt] &g'(p)=0\\[10pt] &\exists I'\subseteq I\quad\forall x\in I'\quad(|g|_I'(x)|\lt1) \end{align}
よって補題1より示された.
Taylorの定理より, ある \(c\in[\min(x_i,p),\max(x_i,p)]\) について
\[ 0=f(p)=f(x_i)+f'(x_i)(p-x_i) +\frac{1}{2}f''(c)(p-x_i)^2 \]
よって
\begin{align} x_{i+1}-p&=x_i-\frac{f(x_i)}{f'(x_i)}-p \\[4pt] &=-\frac{1}{f'(x_i)} \left(f(x_i)+f'(x_i)(p-x_i)\right)\\[6pt] &=\frac{f''(c)}{2f'(x_i)}(x_i-p)^2 \end{align}
よって
\begin{align} &\forall A\in(0,|f'(x)|]\quad\forall B\gt |f''(x)|\\[4pt] &\forall i\in\mathbb{Z}^+\quad \left(|x_{i+1}-p|\le \frac{B}{2A}\ |x_i-p|^2\right) \end{align}

以上より, 定理1は示された.