小清水 (@curekoshimizu) です。

この記事は 日曜数学 Advent Calendar 2016 の 15日目の記事になります。

日曜数学ということばを各所で聞いて、

僕も数学科時代の わくわく数学 を社会人になっても 感じたい・伝えたい！

そう思うようになりました！

f:id:curekoshimizu:20161211183048p:plain:w500

現在はプログラマとして仕事をしており、

「コンピューターの世界と数学の世界」の間を埋めて

面白さを伝えたい！と思い始め、

本当につい最近、

重い腰を上げてこのブログを立ち上げました。

誰かの役に、または、面白く思って頂ければ幸いです。

Abstract

今回の 「コンピューターの世界と数学の世界」 をつなぐお話は Newton法 です。

非常にメジャーなテーマです。

Newton法 を「除算」計算に使うとどうなるのか？

紹介したい話としては実数空間だけじゃなく modulo (余り) の世界でも

活きてくる方法なんだ！っていうのが今回のアドベントカレンダーのオチです。

数値計算例もでてくる！

ので数式がわからなくてもフィーリングは伝わると思います！

Newton法とは？
実数空間の除算とNewton法
$Z/2^{n}Z$ ( $2^{n}$ で割った余りで考えた空間 ) の除算と Newton法
今後ブログで伝えていきたいと考えている面白い内容！！！

1. Newton 法

Newton 法は滑らかな函数 $f$ のある解 $\alpha$ (ただし $f'(\alpha)\neq 0$ ) の近似解を求めるための技法です。

1669 年に Newton がその数年後に Raphson が一般化したため、 Newton-Raphson法 とも呼ばれます。

初期値 $x_0$ が $\alpha$ に近いと

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

という漸化式で $\displaystyle \lim_{n\to\infty} x_n = \alpha$ を得ることができます。

この漸化式は下の図を元に導かれています：

f:id:curekoshimizu:20161211183105p:plain:w300

収束証明

この節に書く証明は、明らかに modulo の世界である $Z/2^{n}Z$ には適用できないことにご注意ください。

実数空間の証明は、先の図をみれば感覚的にはOKです！

(読み飛ばしても大丈夫です！)

きちんとした証明も

$f$ が $\alpha$ の近傍で $C^{2}$ 級であれば

解 $\alpha$ の閉近傍で $f'\neq 0$ となるようとり、

$x_0$ がこの近傍にいるようにすれば、

次式より帰納的に $x_n$ はこの閉近傍に収まっており、さらにこの不等式が証明できます。

$\displaystyle | x_{n+1} - \alpha |$

$\displaystyle = \left| x_n - \alpha - \frac{f(x_n)}{f'(x_n)} \right|$

Taylor の定理より

$\displaystyle = \left|x_n - \alpha - \frac{ f(\alpha)+f'(x_n)(x_n - \alpha)+f''(\theta) \left( x_n - \alpha \right)^{2} }{f'(x_n)} \right|$

$\displaystyle = \left| \frac{ f''(\theta) \left( x_n - \alpha \right)^{2} }{f'(x_n)} \right|$

閉区間内で、連続函数の最大値が存在することから

$\displaystyle \leq \left\lVert \frac{ f'' }{f'} \right\rVert_{\infty} \left( x_n - \alpha \right)^{2}$

これは

精度が2乗ずつよくなっていくことを示しています！

実際それを「除算」の例でみてみましょう。

2. 実数の除算と Newton法

$\displaystyle f(x) = \frac{1}{x} - a$ に Newton法の公式を当てると

$\displaystyle x_{n+1} = x_{n} (2-ax_{n})$

となります！減算と乗算だけで除算の近似値が得られることを意味します！

生活の中で考えても、例えば、小学生時代を思い出しましょう！

除算ってすごく計算が大変だったと思います。

とくに商に何が立つのかという計算が実に厄介です。

次の計算は8がたつかな？と予測し、あー間違ってた…。

9じゃないかーという風に

筆算で除算を計算していると思います。

コンピューターにとっても除算は激しく大変です。

コンピューターでも上のような予測を入れながら計算する方法があるのですが、

Newton 法による計算は予測なしに愚直に計算するだけで得られます。

ためしに $a = 1.5$ として逆数の $2/3$ の近似値を得てみましょう。

n	$x_n$	正しく得られた桁数
0	0.5	0桁
1	0.625	1桁
2	0.6640625	2桁
3	0.666656494140625	4桁
4	0.6666666665114462375640869140625	9桁
5	0.6666666666666666666 3052659425048318553308490 …	19桁
6	0.66666666666666666666666666666666666666470750 …	38桁

と先の証明の精度が2乗ずつよくなっていく様子がわかります。

続いて $Z/2^{n}Z$ へ全く同じ方法で計算するか計算してみましょう。

3. $Z/2^{n}Z$ の除算と Newton法

もちろん注意すべきは $Z/2^{n}Z$ は体ではないので一般に除算はできません。

しかしながら

$ax = 1 \quad\mathrm{mod}\; 2^{n}$

という等式を $a$ が奇数に限り考えることができます。

偶数は明らかに解なしです。(左辺が偶数、右辺が奇数になってしまうためです。)

そのため、お話としては逆元を Newton 法で求めてみようという話になります。

皆さん大好きな $a = 691$ を

$Z/2^{32}Z$ の世界で Newton 法にかけてみますと

次のようになります。

ここでは $x_0 = 1$ として

$\displaystyle x_{n+1} = x_{n} (2-ax_{n})$

を計算してきます。

n	$x_n$	2進法表現	正しく得られた桁数
0	1	00000000000000000000000000000001	1桁
1	4294966607	11111111111111111111110101001111	2桁
2	3966933707	11101100011100101001101011001011	4桁
3	3802448251	11100010101001001100000101111011	8桁
4	2476047483	10010011100101010111110001111011	16桁
5	2660269179	10011110100100000111110001111011	32桁
6	2660269179	10011110100100000111110001111011	32桁