連分数から近似分数を求める

前回は $\sqrt{2}$ の連分数を求めるところまで説明しました。

ただ、連分数だけでは使い勝手が悪いです。見た目も気持ち悪いですし、近似分数がまだ求まっていません。今回は連分数から近似分数を求める話をします。

無理数を $\omega$ とし、 $\omega$ の連分数展開を $[a_0,a_1,a_2,...]$ としましょう。 $\omega$ は $\sqrt{2}$ や $\sqrt{3}$ だと思ってください。 $[a_0,a_1,a_2,...]$ は数列と見ることができますね。連分数展開から得られた数列の第 $i$ 項目までを使って得られた近似分数を $\gamma _i = \frac{p_i}{q_i}$ と表記し、第 $i$ 近似分数と呼びます。今後は $p_i,q_i$ がどのように求まるかを実際に計算をしながら見ていきます。

ためしに第0近似分数を求めてみましょう。といっても簡単ですね。第0近似分数は $a_0$ のみから得られる近似分数なので、

$\gamma _0 = \frac{a_0}{1}$

となります。よって、

$p_0=a_0, q_0=1$ ・・・(1)

です。第1近似分数はどうでしょうか。

$\gamma _1 = a_0 + \frac{1}{a_1}$

$\gamma _1 = \frac{a_0 a_1 + 1}{a_1}$

ということで、(1)式を使うと、

$p_1 = p_0 a_1 + 1, q_1 = q_0 a_1$ ・・・(2)

となります。ちょっとくどいですが、第2近似分数まで求めてみます。

$\gamma _2 = a_0 + \frac{1}{a_1 + \frac{1}{a_2}}$

$\gamma _2 = a_0 + \frac{a_2}{a_1 a_2 + 1}$

$\gamma _2 = \frac{a_0(a_1 a_2 + 1) + a_2}{a_1a_2 + 1}$

$\gamma _2 = \frac{a_2(a_0 a_1 + 1) + a_0}{a_1a_2 + 1}$

$\gamma _2 = \frac{a_2p_1 + p_0}{a_2q_1 + q_0}$ . ((1),(2)より)

ということで、

$p_2 = a_2 p_1 + p_0, q_2 = a_2 q_1 + q_0$

となります。なにかそれっぽい漸化式が出ましたね。偶然出てきた感じもしますが、この漸化式は一般に成り立ちます。すなわち、第 $i$ 近似分数の $\gamma_i = \frac{p_i}{q_i}$ は

$p_i = a_i p_{i-1} + p_{i-2}, q_i = a_i q_{i-1} + q_{i-2}$

となります。証明はこの記事ではしません。(次の記事でやるかも)

以上、この漸化式を解くことで連分数から近似分数を得ることができます。試しに $\sqrt{2}$ の第4近似分数までを求めてみましょう。 $\sqrt{2}$ の連分数展開は $[1,2,2,2,...]$ でした。

	分子	分母	値	誤差
$\gamma_0$	1	1	1	約0.41
$\gamma_1$	2*1+1=3	2*1	1.5	約0.11
$\gamma_2$	2*3+1=7	2*2+1=5	1.4	約0.01
$\gamma_3$	2*7+3=17	2*5+2=12	1.4166...	約0.002
$\gamma_4$	2*17+7=41	2*12+5=29	1.4137...	約0.0004

前の記事で書いた41/29が確かに $\gamma_4$ に出てきました。
誤差を見るとすごいですね。どんどん小さくなっています。

今回はこのへんで終わりにしたいと思います。次回は今回省略した証明の話か、最良性の話をできればなと思います。

[2016/2/14 追記]
pythonのMatplotlibで遊ぶついでに誤差をグラフにしてみました。
緑の直線が $\sqrt{2}$ 、青の折れ線が第 $i$ 近似分数の値です。
第4近似分数あたりからほぼ誤差がなくなっていることが視覚的にもわかると思います。
f:id:g0nChang:20160214190418p:plain

参考：
www.amazon.co.jp