現実と数学の区別が付かない

数学ネタのブログです

ニュートン法の2次収束性とヘンゼルの補題

可換環論でのニュートン法が「2次収束」することの証明をちゃんと書いておく.

可換環 S の可逆元全体を  S^\times で表す.可換環とそのイデアル  I\subset R に対し x\in R の剰余環 R/I での像を x+I と書く.

x\in R に対し x+I\in (R/I)^\times ならば  x+I^n\in (R/I^n)^\times

証明. (x+I)^{-1}=y+I とすると,a:=xy-1\in I である.

z=y(1-a+a^2+\cdots +a^{n-1}) とおくと,\begin{align}(x+I^n)(z+I^n)&=xy(1-a+a^2+\cdots a^{n-1})\\
&=(1+a)(1-a+a^2+\cdots +(-a)^{n-1})\\
&=1+ (-1)^{n-1}a^n\in 1+I^n\end{align}より z+I^n x+I^n の逆元となる.証明終

表記を簡単にするために R/J の可逆元 x+J の逆元 (x+J)^{-1}\cfrac{1}{x}+J と書くことにする.これは \cfrac{1}{x}R で考えてその像を取っているのではないことに注意(xR で可逆とは限らない).次の定理に現れる  \cfrac{1}{f'(a)}+I^{2n} もこの意味での逆元である.

定理
 I\subset R可換環とそのイデアルn を正整数, f(x)\in R[x] とする.a\in R が \begin{align}f(a)\in I^n,~f'(a)+I\in (R/I)^\times\end{align}を満たすとき,\begin{align}b\in a -\cfrac{f(a)}{f'(a)}+I^{2n}\end{align}となる  b を取ると a+I^n=b+I^n であり,\begin{align}f(b)\in I^{2n},~f'(b)+I\in (R/I)^\times\end{align}が成り立つ.

証明. a+I^n=b+I^nb の取り方より自明.

f(x)=f(a)+f'(a)(x-a)+(x-a)^2 g(x) となる g(x) が存在する.b\in a -\cfrac{f(a)}{f'(a)}+I^{2n} より \begin{gather}
f(a)+f'(a)(b-a)\in f'(a) I^{2n}\subset I^{2n},\\
b-a\in -\cfrac{f(a)}{f'(a)} +I^{2n} \subset I^n
\end{gather}であるので,f(b)=f(a)+f'(a)(b-a)+(b-a)^2g(b)\in I^{2n} が成り立つ.

また,b-a\in I^n \subset I より  f'(a)-f'(b) \in I であるので\begin{align}f'(b)+I=f'(a)+I\in (R/I)^\times\end{align}である.証明終

この定理はニュートン法の1ステップで, f(x)R/I^n における単根 a+I^n R/I^{2n} における根 b+I^{2n} に持ち上がるということを言っている.I^nI^{2n} に改善されており,ニュートン法は「2次収束」である.

系(ニュートン法
 I\subset R可換環とそのイデアル f(x)\in R[x] とする.a\in R が \begin{align}f(a)\in I,~f'(a)+I\in (R/I)^\times\end{align}を満たすとき, x_n \in R を次で定める
\begin{align}
x_0&= a, \\
x_{n+1}&\in x_n -\cfrac{f(x_n)}{f'(x_n)} + I^{2^{n+1}}.
\end{align}このとき,x_n+I^{2^n} \in R/I^{2^n} は一意に定まっており,\begin{align}
f(x_n) \in I^{2^n},~x_{n+1}-x_n \in I^{2^n}
\end{align}が成り立つ.

特に \displaystyle b=\lim_{n\to \infty}x_n が収束するとき, f(b)=0,~b-a\in I を満たす.

系(ヘンゼルの補題
R, I, f(x),a は上の系と同様とする.RI 進位相で完備のとき,\begin{align}f(b)=0,~b-a\in I\end{align}を満たす b\in R が存在する.