√自然数の形の無理数を極限に持つ漸化式を紹介します。
とりわけ√２を求めるのに優秀なアルゴリズムで、
√３なども指数関数の速さで計算できます。
式自体は簡単で
プログラムを組みやすいので
コンピュータで無理数を
数値計算してみたい人の入門にお勧めです。
漸化式
２以上の自然数aについて
定理
漸化式
$$ a_{n+1}= \frac{1}{a_n} +\frac{(a-1)a_n}{a} \hspace{20cm} $$
は√aを極限に持つ。
ただし初項a1は任意の正の実数。
（できるだけ√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} $$
√３が求まります。
収束する理由
なぜこの漸化式で求まるかと言うと
複素力学系で説明されます。
漸化式のanをxで置き換えた関数
$$ f(x)= \frac{1}{x} +\frac{(a-1)x}{a} $$
において±√aは吸引不動点と呼ばれる物です。
吸引不動点は、その名の通り
近くの点をすべて引き寄せる性質を持つので
初項a1を√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まで求まるので
入門には向いていると思います。
まとめ
元の数の逆数と定数倍の足し算
という簡単なステップで
√自然数へと収束する漸化式を紹介しました。
特に√２は超吸引不動点なため求めやすく、
√３以降の数値計算にも
弱点はあるものの使えます。
ルートを自分の手で計算してみたい人にお勧めです。