Memorandum

有理数と無理数

●有理数の定義

「有理数 (rational number)」は、整数の比 (ratio) で表すことができる数のことです。有理数の集合を \(\mathbb{Q}\) と書くことがあります。\(\mathbb{Q}\) は商 (Quotient) の頭文字です。

\(\mathbb{Z}\) は整数の集合を表す記号です。整数は分母が 1 の分数として考えると、有理数の特別な場合となります。もちろん、0 も 0 / 1 と考えれば有理数になります。

●有理数の演算

4 つの整数 \(a, b, c, d, \ (b \ne 0, \ d \ne 0\)) において、等式 \(ad - bc = 0\) を満たすとき、有理数 \(\frac{a}{b}\) と \(\frac{c}{d}\) は等しいといい、次式で表します。

有理数の加法 (\(+\)) を以下の式で定義します。

\(\frac{a}{b}\) の単位元は 0 (\(\frac{0}{1}\)) で、逆元は \(-\frac{a}{b} = \frac{-a}{b} = \frac{a}{-b}\) であることがわかります。これにより、減法 (\(-\)) を次のように定めることができます。

次に、有理数の乗法 (\(\times\)) を以下の式で定義します。

\(\frac{a}{b}\) の単位元は 1 (\(\frac{1}{1}\)) で、逆元は \(\left(\frac{a}{b}\right)^{-1} = \frac{b}{a}\) であることがわかります。これにより、除法 (\(\div\)) を次のように定めることができます。

有理数の加法と乗法は結合法則、交換法則、分配法則を満たします。

このように、有理数は普通に加減乗除ができるので、「体 (field)」ということになります。

●循環小数

次は、有理数を小数に直すことを考えてみましょう。1/2, 1/5, 1/8, 1/10 などは 0.5, 0.2, 0.125, 0.1 のように途中で割り切れて、有限な桁で表すことができます。これを「有限小数」といいます。ところが、1/3, 1/6, 1/7 は、次のように有限な桁では表すことができません。

1/3 は 3 を無限に繰り返し、1/6 は 0.1 のあと 6 を無限に繰り返し、1/7 は数列 142857 を無限に繰り返します。このような少数を「循環小数 (repeating decimal)」といい、繰り返される数字の列を「循環節」といいます。有理数を小数に直すと、有限小数か循環小数のどちらかになります。

循環小数は次のように循環節の始めと終わりを点で示します。

このほかに、循環節に下線を引いたり、カッコで囲む表記法もあります。

●有理数を循環小数に変換

有理数を循環小数に直すのは簡単です。筆算と同じように計算していくだけです。次の図を見てください。

     0 1 4 2 8 5 7
   ----------------
 7 ) 1
     0
    ----- 
     1 0  <-- 余り 1
       7
    ------- 
       3 0
       2 8
      -------
         2 0
         1 4
        -------
           6 0
           5 6
          -------
             4 0
             3 5
            -------
               5 0
               4 9
              -----
                 1  <-- 余り 1 

7 で割った余り 1 が 2 回現れていますね。これから先は同じ数列を繰り返すことがわかります。7 の剰余は 0 から 6 まであり、剰余が 0 の場合は割り切れるので循環小数にはなりません。現れる余りの数が限られているので、割り切れなければ循環することになるわけです。また、このことから循環節の長さは分母の値よりも小さいことがわかります。

●循環小数を有理数に変換

循環小数を有理数に直すことも簡単にできます。循環小数 - Wikipedia によると、有限小数部分を a、循環節の小数表記を b、節の長さを n とすると、循環小数 x は次の式で表すことができる、とのことです。

ここで、カッコの中は初項 1, 公比 \(\frac{1}{10^n}\) の無限等比級数になるので、その和は次の公式より求めることができます。

簡単な例を示しましょう。

●連分数

「連分数 (continued fraction)」は、分数の分母にさらに分数が含まれる形をした分数のことです。

連分数の中で、分子 \(c_1, c_2, \ldots\) がすべて 1 で、\(b_0\) が整数、\(b_1, b_2, \ldots\) がすべて正の整数であるような連分数を「正則連分数」といいます。正則連分数は \(b_i\) の情報を保持するだけで、連分数に復元することができます。そこで、以下の右辺のように記述することが多いようです。

●有理数の連分数展開

有理数は「ユークリッドの互除法」を使って正則連分数に展開することができます。

\(a, b\) の問題を \(b, r\) の問題に帰着させるのは「ユークリッドの互除法」と同じです。この計算を繰り返し行うと、\(a, b\) はどんどん小さくなっていき、\(r = 0\) になったとき連分数展開が終了します。

簡単な例を示します。

●無理数

「無理数 (irrational number)」とは有理数で表すことができない数のことです。有理数と無理数を合わせた数を「実数 (real number)」といいます。実数全体の集合は \(\mathbb{R}\) と表記するのが一般的です。たとえば、\(\sqrt n\) は \(n\) が平方数でなければ無理数になります。ここで、\(\sqrt 2\) が無理数であることを背理法で証明してみましょう。

●無理数の連分数展開

有理数の連分数展開は有限回で終了しますが、無理数の連分数展開は無限に続きます。たとえば、\(\sqrt 2\) の連分数展開を求めてみましょう。

係数が有理数の二次方程式の根を「二次無理数」といいます。二次無理数の正則連分数展開は循環することが知られています。

●実数の連分数展開

実数 \(\alpha\) の正則連分数展開は次のアルゴリズムで求めることができます。

Python でプログラムすると、次のようになります。

リスト : 実数を正則連分数に展開する

def cont_frac_flt(x, k = 8, e = 1e-16):
    xs = []
    for _ in range(k):
        xs.append(floor(x))
        y = x - xs[-1]
        if abs(y) < e: break
        x = 1 / y
    return xs

引数 x が連分数展開を行う実数、k が段数、e が 0 と判定する基準値です。プログラミング言語は実数を浮動小数点数で表します。浮動小数点数は不正確な数なので、演算誤差が発生します。k の値を増やしても、規則性は無限に続かずに途中で失われることがあります。

また、0.5 や 1.25 など浮動小数点数でも正確に表現できる数では、途中で y の値が 0 になるので、そこで展開を終了します。ただし、演算誤差が生じる場合があるので、ぴったり 0 になるとは限りません。そこで、\(|y| \lt e\) よりも小さくなったならば、0 と判定して展開を終了します。

簡単な実行例を示します。

>>> cont_frac_flt(math.sqrt(2), k=8)
[1, 2, 2, 2, 2, 2, 2, 2]
>>> cont_frac_flt(math.sqrt(2), k=16)
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
>>> cont_frac_flt(math.sqrt(2), k=32)
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1809]

>>> cont_frac_flt(math.sqrt(7), k=9)
[2, 1, 1, 1, 4, 1, 1, 1, 4]
>>> cont_frac_flt(math.sqrt(7), k=17)
[2, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4]
>>> cont_frac_flt(math.sqrt(7), k=25)
[2, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4]
>>> cont_frac_flt(math.sqrt(7), k=33)
[2, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, 1, 2, 7, 1, 1, 93, 1, 2]

>>> cont_frac_flt(1.1)
[1, 9, 1, 112589990684262, 2, 2, 6, 46912496118442]
>>> cont_frac_flt(1.1, e=1e-14)
[1, 9, 1]

●平方根の連分数展開

正の整数 m の平方根は二次無理数なので連分数は循環します。ただし、循環節が長くなると浮動小数点数の計算誤差により、上記プログラムでは正確に連分数展開できない場合があります。参考 URL 2 には、平方根の連分数展開 (循環節) を正確に求めるプログラム (Python) が掲載されています。ここで、簡単にアルゴリズムを紹介しましょう。

二次無理数 \(\alpha\) を次式のように連分数展開するとします。

このとき、\(\alpha_n\) を整数 \(a_n, b_n\) を使って以下のように表すと、\(\alpha\) の連分数展開を \(a_n, b_n\) の漸化式で表すことができます。

\(a_n, b_n\) の漸化式は以下のように求めることができます。

参考 URL 2 によると、\(c_{n+1}\) を求める計算は、\( \left\lfloor \frac{c_0 + b_n}{a_{n+1}} \right\rfloor \) に置き換えることができるそうです。証明もなされているので、興味のある方はお読みくださいませ。

●連分数を有理数に変換

連分数を有理数に変換 (約分) するのは簡単です。n 段の連分数 \([a_0; a_1, a_2, \ldots, a_{n-2}, a_{n-1}]\) であれば、一番最後の連分数 \(a_{n-2} + \frac{1}{a_{n-1}}\) から順番に前へ向かって約分していくだけです。

Python のモジュール SymPy には正則連分数を通常の分数に戻す関数 continued_fraction_reduce() が用意されていますが、私達でも簡単にプログラムすることができます。

リスト : 連分数を有理数に約分する

from fractions import Fraction
from functools import reduce

def cont_frac_reduce1(xs):
    return reduce(lambda a, x: x + Fraction(1, a), reversed(xs))

Python の標準ライブラリ fractions には、有理数を扱うクラス Fraction が定義されています。Fraction を import すると、式の計算に有理数を使うことができます。標準ライブラリ functools に用意されている関数 reduce は畳み込みを行います。Fraction と reduce を使うと、簡単に連分数を約分することができます。

もう一つ、簡単な方法を紹介しましょう。参考 URL 4 によると、連分数 \([a_0; a_1, a_2, \ldots, a_{n-2}, a_{n-1}]\) を約分した有理数 \(\frac{p_n}{q_n}\) の分子と分母 \(p_n, q_n\) は、以下に示す漸化式で求めることができるそうです。

Python でプログラムすると、次のようになります。

リスト : 連分数を有理数に約分する (2)

def cont_frac_sub(xs, a0, a1):
    _, a = reduce(lambda a, x: (a[1], x * a[1] + a[0]), xs[1:], (a0, a1))
    return a

def cont_frac_reduce2(xs):
    p = cont_frac_sub(xs, 1, xs[0])
    q = cont_frac_sub(xs, 0, 1)
    return Fraction(p, q)

関数 cont_frac_sub は漸化式を計算します。これも reduce を使うと簡単です。cont_frac_reduce2 は cont_frac_sub を 2 回呼び出して分子 p と分母 q を求めます。あとは、Fraction で有理数を生成して return で返すだけです。

簡単な実行例を示します。

>>> cont_frac_reduce1([1,2,2,2,2])
Fraction(41, 29)
>>> cont_frac_reduce2([1,2,2,2,2])
Fraction(41, 29)
>>> 41 / 29
1.4137931034482758
>>> cont_frac_reduce1([1,1,2,1,2])
Fraction(19, 11)
>>> cont_frac_reduce2([1,1,2,1,2])
Fraction(19, 11)
>>> 19 / 11
1.7272727272727273
>>> cont_frac_reduce1([2,1,1,1,4,1,1,1,4])
Fraction(590, 223)
>>> cont_frac_reduce2([2,1,1,1,4,1,1,1,4])
Fraction(590, 223)
>>> 590 / 223
2.6457399103139014

●無理数の有理数近似

無理数を有理数で近似することを考えます。たとえば、\(\sqrt 2 = 1.4142135623730951\) の近似値として、以下のような有理数を考えることができます。

これらの近似値の誤差を Python (SymPy) を使って求めると、次のようになります。

>>> import sympy as sy
>>> import math
>>> a = math.sqrt(2)
>>> a
1.4142135623730951

>>> for q in [10, 100, 1000, 10000]:
...     r = sy.Rational(math.floor(a * q), q)
...     print(abs(a - r), 1 / q, 1 / (q*q))
...
0.0142135623730952 0.1 0.01
0.00421356237309523 0.01 0.0001
0.000213562373095222 0.001 1e-06
1.35623730952439e-5 0.0001 1e-08

近似値を \(r = \frac{p}{q}\) とすると、誤差は \(\frac{1}{q}\) の範囲に収まりますが、\(\frac{1}{q^2}\) には収まっていません。実数 \(\alpha\) の近似値 \(\frac{p}{q}\) が次の不等式を満たすとき、有理数 \(\frac{p}{q}\) を「\(\alpha\) の良い近似」といいます。

誤差を \(\frac{1}{q^2}\) の範囲内に収めるのは難しいように思いますが、「\(\alpha\) が無理数なら \(\alpha\) の良い近似が無限個ある」ことが証明されています。これを「ディリクレのディオファントス近似定理」といいます。無理数 \(\alpha\) の正則連分数展開を途中で打ち切ったもの \(\frac{p_n}{q_n} = [b_0, b_1, \ldots, b_n]\) は、無理数 \(\alpha\) の良い近似になることが知られていて、その誤差は以下の式で表されます。

SymPy を使って確認してみましょう。

>>> xs = [1]
>>> for _ in range(5):
...     xs.append(2)
...     r = sy.continued_fraction_reduce(xs)
...     print(xs, r, abs(math.sqrt(2) - r), float(1 / (sy.denom(r) ** 2)))
...
[1, 2] 3/2 0.0857864376269049 0.25
[1, 2, 2] 7/5 0.0142135623730952 0.04
[1, 2, 2, 2] 17/12 0.00245310429357160 0.006944444444444444
[1, 2, 2, 2, 2] 41/29 0.000420458924819345 0.0011890606420927466
[1, 2, 2, 2, 2, 2] 99/70 7.21519126192227e-5 0.00020408163265306123

誤差は \(\frac{1}{{q_n}^2}\) の範囲内に収まっていることがわかります。

●参考文献・URL

1. 奥村晴彦,『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991
2. 平方根の連分数とペル方程式 (PDF), (有澤健治さん)
3. 連分数展開とその計算方法, (マスオさん)
4. 連分数 - Wikipedia

プログラミングに興味のある方は拙作のページもお読みくださいませ。

• Alogrithms with Python: 分数
• Common Lisp 入門: 分数