小清水さんとコンピューター数学

コンピューター・数学 に関することを書きます

Newton法でつながるコンピューターと数学の隙間

小清水 (@curekoshimizu) です。

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

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

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

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

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

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

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

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

本当につい最近、

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

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


Abstract

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

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

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

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

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

数値計算例もでてくる!

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

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

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桁

最終的に収束して 不動点 が得られました。

精度が2乗ずつよくなっていく 様子も同じです。

実際

 691\times 2660269179 = 1 \quad\mathrm{mod}\; 2^{32}

となりますので 逆元が得られました。

たまたまなのでしょうか。

ちなみにですが、691 を持ち出した理由を知りたい方は

tsujimotterさんのブログ を御覧ください!

収束証明

 x_0 = 1 であり a は奇数であるから、

 ax_0 - 1 = 0 \quad\mathrm{mod}\; 2^{2^{0}}

ある n で

 ax_n - 1 = 0 \quad\mathrm{mod}\; 2^{2^{n}}

が満たされていたと仮定すると  a x_{n} - 1 = 2^{2^{n}} N となる 整数  N がとれる。

 a x_{n+1} - 1

 =ax_{n} (2 - ax_{n}) -1

 = (2^{2^{n}}N + 1) (1 - 2^{2^{n}}N) - 1

 = 2^{2^{n}} 2^{2^{n}} N^{2}
 = 2^{2^{n+1}} N^{2}

ゆえに

 ax_{n+1} - 1 = 0 \quad\mathrm{mod}\; 2^{2^{n+1}}

が満たされ、帰納法により示された。

なぜ  Z/2^{n}Z 系を扱った?

コンピューターでは 整数 を表現する際に

 Z/2^{n}Z として 扱われることが多いです。

特に  n = 8, 16, 32, 64 が頻出で、

プログラミング言語 を勉強しても登場します。

上の証明をよくよく見てみると、

これを発展させると p進数 にも応用できること簡単にわかりますよね!

Summary

Newton 法除算 につかうと

実は 「減算・乗算」 だけで計算できる式を導ける!

そんな、実数の 接線 と関係の深い Newton法

接線とは関係なさそうな

整数の世界 でも関係がある!

おまけにコンピュータとも関係あるなんて!

4. 今後ブログで伝えていきたいと考えている面白い内容!!!

このように 数学の知識とコンピューターの知識 の両方が登場する内容を書いて、

橋渡し的なブログになればいいなと思っております。

最近興味があるのは 浮動小数 という

コンピューターで実数を扱う際に

よく使われる計算体系を 数学的に見つめ直してみたい と思っており

その内容が多いかもしれません。

浮動小数点がどれくらい厄介?

浮動小数点体系では、例えば基本的にこうです…。

  •  (a + b) + c \neq a + (b + c)
  •  (a \times b) \times c \neq a \times (b \times c)

群・環・体を知っている人は

性質の悪さに 泣きそうになりますよね...。

非可換体なんて目じゃない難しさです。

この 難しい演算体系Excel などでは標準的に使われています。

下の内容は 三角函数の計算が定義通り計算できない!? 悲しい話になります:

math-koshimizu.hatenablog.jp

あなたも コンピュータと数学 に興味持ってみませんか?

以上、コンピューターと数学の間の話でした。


明日の 日曜数学 Advent Calendar 2016 の記事は

Toshiki Takahashi さんによる「リープグラフと複素確率」です。

確率って聞くだけでわくわくしちゃいます!