【√２、√３が求まる】
√自然数を極限に持つ漸化式の作り方

√自然数の形の無理数を極限に持つ漸化式を紹介します。

とりわけ√２を求めるのに優秀なアルゴリズムで、

√３なども指数関数の速さで計算できます。

式自体は簡単で
プログラムを組みやすいので

コンピュータで無理数を
数値計算してみたい人の入門にお勧めです。

漸化式

２以上の自然数aについて

ただし初項a₁は任意の正の実数。
（できるだけ√aの近くにとる）

√２を求める

試しに√２を求めてみます。

漸化式は

$$a_{n+1}= \frac{1}{a_n} +\frac{(2-1)a_n}{2} = \frac{1}{a_n} +\frac{a_n}{2}$$

です。

√２に近い値として

$a_1 = 1$

を初項に定めます。

順次、漸化式より

$$a_2 = \frac{1}{1} +\frac{1}{2} = \frac{3}{2} \quad (=1.5) \hspace{20cm}$$

$$a_3 = \frac{2}{3} +\frac{3}{4} = \frac{17}{12} \quad (\fallingdotseq 1.4167 ) \hspace{20cm}$$

$$a_4 = \frac{12}{17} +\frac{17}{24} = \frac{288}{408} +\frac{289}{408} = \frac{577}{408} \quad (\fallingdotseq 1.4142 ) \hspace{20cm}$$

のよう計算され次第に√２が求まります。

√３を求める

√３も求めてみます。

漸化式は

$$a_{n+1}= \frac{1}{a_n} +\frac{(3-1)a_n}{3} = \frac{1}{a_n} +\frac{2a_n}{3}$$

で、√３に近い値として

$a_1 = 2$

を初項に定めます。

順次、漸化式より

$$a_2 = \frac{1}{2} +\frac{4}{3} = \frac{11}{6} \quad (\fallingdotseq 1.8333) \hspace{20cm}$$

$$a_3 = \frac{6}{11} +\frac{11}{9} = \frac{54}{99} +\frac{121}{99} = \frac{175}{99} \quad (\fallingdotseq 1.7677 ) \hspace{20cm}$$

$$a_4 = \frac{99}{175} +\frac{350}{297} = \frac{90653}{51975} \quad (\fallingdotseq 1.7442 ) \hspace{20cm}$$

$$a_5 = \frac{51975}{90653} +\frac{181306}{155925} \fallingdotseq 0.5733 +1.1628 =1.7361 \hspace{20cm}$$

√３が求まります。

収束する理由

なぜこの漸化式で求まるかと言うと
複素力学系で説明されます。

漸化式のa_nをxで置き換えた関数

$$f(x)= \frac{1}{x} +\frac{(a-1)x}{a}$$

において±√aは吸引不動点と呼ばれる物です。

吸引不動点は、その名の通り
近くの点をすべて引き寄せる性質を持つので

初項a₁を√aの十分近くにとれば、

漸化式を施すにつれ
√aへ収束して行きます。

どれくらい近くの点を引き寄せるかは
吸引不動点によっていて

この場合は任意の正の実数が√aへ引き寄せられます。

証明

興味のある人向けに
±√aがf(x)の吸引不動点である事を証明します。

不動点である

$$x= \frac{1}{x} +\frac{(a-1)x}{a} \hspace{20cm}$$

の解を考える。

x=0は明らかに不適なのでx≠0とする。

両辺にxを掛けると

$$x^2= 1 +\frac{(a-1)x^2}{a} \hspace{20cm}$$

両辺に自然数aを掛けて整理すると

$x^2 = a$

よって

$x =\pm \sqrt{a}$

はf(x)の不動点である。$\square$

吸引的である

$$f'(x ) =-\frac{1}{x^2} +\frac{a-1}{a} \hspace{20cm}$$

なのでf(x)の√aにおける微分係数は

$$f'(\sqrt{a} ) =-\frac{1}{a} +\frac{a-1}{a} = \frac{a-2}{a} = 1 -\frac{2}{a} \hspace{20cm}$$

aは２以上の自然数なので

$$\left| 1 -\frac{2}{a} \right| < 1 \hspace{20cm}$$

微分係数の絶対値が１より小さいので吸引的である。$\square$

収束の速さ

吸引不動点への収束の速さは
微分係数の絶対値

すなわち

$$| f'(\sqrt{a} ) | = \left| 1 -\frac{2}{a} \right|$$

の大きさで決まります。

a=２の時

$$| f'(\sqrt{2} ) | = 0$$

絶対値は０なので
とても速く収束します。

（絶対値０の吸引不動点は超吸引不動点と呼ばれます）

a=３の時

$$| f'(\sqrt{3} ) | = \frac{1}{3}$$

絶対値は1/3です。

これは漸化式を一回施すごとに
真の値との距離が約1/3に縮まることを意味します。

底が1/3の指数関数の速さ程で√３が求まります。

aが大きい時

一般にこの漸化式をアルゴリズムに使えば

底が(1-2/a)の指数関数の速さ程で
√aを求めてくれます。

弱点は

$$\lim_{a \to \infty} \left( 1 -\frac{2}{a} \right) = 1 \hspace{20cm}$$

なので、

aが大きくなるに連れ動作が重くなります。

今のコンピュータのスペックなら
少なくとも√10まで求まるので

入門には向いていると思います。

まとめ

元の数の逆数と定数倍の足し算

という簡単なステップで
√自然数へと収束する漸化式を紹介しました。

特に√２は超吸引不動点なため求めやすく、

√３以降の数値計算にも
弱点はあるものの使えます。

ルートを自分の手で計算してみたい人にお勧めです。