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は示された.