連分数展開とその計算方法【連分数計算アプリの紹介付き】

今回の記事は「シリーズ：連分数とペル方程式」の１日目の記事となっています。関連する記事はこちらからご覧いただけます。

今日は、連分数展開について紹介したいと思います。

３日連続で「連分数」に関連する記事を公開したいと思っています。明日以降の記事の準備として、以下の３つのトピックを紹介したいと思います：

連分数展開を計算するためのウェブアプリの紹介
連分数展開の計算方法の紹介（２通り）
連分数を用いた無理数の近似

連分数とは

$\displaystyle a_0 + \cfrac{b_1}{a_1 + \cfrac{b_2}{a_2 + \cfrac{\ddots}{\ddots + \cfrac{b_{n}}{a_n}}}} \tag{1}$

という形に、分数が入れ子になった構造の分数のことを指します。

特に、各分子の数列 $b_1, b_2, \ldots , b_n$ がすべて $1$ であるものを正則連分数といいます。

$\displaystyle a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{\ddots}{\ddots + \cfrac{1}{a_n}}}} \tag{2}$

今回の記事では、正則連分数のみを扱いたいと思います。正則連分数は

$[a_0; a_1, a_2, a_3, \ldots, a_n ]$

のように表すことができます。

また、分数の入れ子を無限に繰り返すことで

$\displaystyle a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{a_4 + \cfrac{1}{\ddots}}}}} \tag{3}$

なるものを考えることができ、これも連分数ということにします。（特に、分子が $1$ であるものを正則連分数といいます。）

与えられた数が連分数の形で表せるかどうかは気になるところですが、重要な事実として任意の実数は必ず連分数の形で表すことができます。

実数 $\alpha$ を式 $(3)$ の形で表すことを $\alpha$ の連分数展開 といいます。

たとえば $\sqrt{3}$ の場合は

$\displaystyle \sqrt{3} = 1 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{\ddots}}}}} \tag{4}$

のように正則連分数に展開できます。式 $(3)$ の分母の数列がそれぞれ

$a_0 = 1, \; a_1 = 1, \; a_2 = 2, \; a_3 = 1, \; a_4 = 2, \; \ldots$

というわけですね。

今日は、実数（特に $\sqrt{D}$ という形の無理数）の連分数展開を計算する方法を２通り紹介したいと思います。２通りといいつつ、基本的な考え方はどちらも同じです。

宣伝：連分数を計算するアプリを作りました！

計算方法の紹介の前に、今回のために作成した自作アプリの紹介をさせてください！

これから連分数展開の計算を行うのですが、実際やってみると手順が込み入っていて、計算するのはなかなか大変です。そこで、計算結果をすぐに調べることができるよう $\sqrt{D}$ の連分数展開を計算してくれるアプリを作りました。
tsujimotter.info

使い方は簡単です。

たとえば、 $D = 3$ 、 $n = 5$ と入力して「計算」ボタンを押すと、 $\sqrt{3}$ の連分数展開を $5$ 項目（ $a_5$ ）まで計算してくれます：

f:id:tsujimotter:20210227225151p:plain:w400

あとで説明するように、 $n$ 項目までの近似分数も計算してくれます。LaTeXのテキストも一緒に出力してくれるので、ブログに貼り付けたりすることも簡単にできます。

計算が面倒なときに使ったり、手計算の験算に使ったり、ぜひご活用いただけると嬉しいです！

なお、連分数の計算アルゴリズムは、こちらのサイトの記事を参考にさせていただきました。
parametron.blogspot.com

それでは、計算方法の紹介にいきましょう！

連分数展開の計算方法①：小数展開を用いる方法

まずは、小数展開を用いた方法を紹介したいと思います。手元に電卓がある方は、一緒に計算してみてください。

なお、電卓を使う際に、必要な操作は「引き算」「√」「逆数をとる」の３つとなります。いずれのボタンもあると楽に計算できます。

逆数については、そのようなボタンがないことが多いです。しかしながら、たとえばシャープの電卓では「÷＝」、カシオの電卓では「÷÷」を押すことで逆数を計算できるそうです。
pro-boki.com

まず、 $\sqrt{3}$ を小数展開します。電卓では $3$ を入力したあと「√」ボタンを押すとよいでしょう。

$\sqrt{3} \approx 1.7320508$

1. 整数部分をとる：
上の数の整数部分をとると $a_0 = 1$ となります。これを覚えておきます（どこかにメモする）。計算結果から整数部分 $1$ を引いてみてください。すると、残った小数部分は

$0.7320508$

となりますね。

2. 小数部分の逆数をとる：
小数部分は $0$ 以上 $1$ 未満の数となります。これの逆数をとると

$1.3660254$

となります。

3. 2. の整数部分をとる：
上の数の整数部分をとると $a_1 = 1$ となります（これもメモを取るか覚えておいてください）。小数部分は

$0.3660254$

となります。

4. 小数部分の逆数をとる：
再度逆数をとると

$2.7320508$

となります。

5. 4. の整数部分をとる：
整数部分をとると $a_2 = 2$ となります（これもメモを取るか覚えておいてください）。

こんな風に繰り返していくことで、 $\sqrt{3}$ の連分数展開を得ることができます。

$\displaystyle \sqrt{3} = 1 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{\ddots}}}$

まとめると、 $\sqrt{3}$ を小数展開して、以下の手順を実行すれば良いわけですね。

1. 整数部分をとる（ $a_0 = 1$ ）
2. 小数部分の逆数をとる
3. 2. の整数部分をとる（ $a_1 = 1$ ）
4. 小数部分の逆数をとる
5. 4. の整数部分をとる（ $a_2 = 2$ ）

以上を繰り返す。

ところで、上の手順5.で整数部分をとった後、残った数は

$0.7320508$

となりました。この数にピンときた方はいますでしょうか。

実はこれは $\sqrt{3}$ の小数部分となっているのです。すなわち、ここから先はずっと同じ計算になります。 $1, 2, \ldots$ の周期が繰り返されるというわけです。

一般に $D$ を平方数ではない数としたとき、 $\sqrt{D}$ の正則連分数展開は循環することが知られています。そのため、計算していくなかで元々の小数展開が現れた時点で計算を終了して良いわけですね。

もっと一般に、係数が整数の二次方程式の解であるようなすべての無理数は、正則連分数展開が循環します。

ただし、循環周期の長さを決定する上で、①の方法には注意点があります。それは予め十分な長さの桁数を取って、小数展開をしなければならないということです。ステップを進めるたびに小数の有効桁数が減っていきますので、最初に十分な桁数を取っておかないと、途中で結果がおかしくなってしまうのですね。

この問題を回避するために、小数展開をせず直接計算するというのが②の方法です。

連分数展開の計算方法②：直接計算する方法

先ほどは小数に展開してから連分数を計算しましたが、循環するかどうかが厳密に評価できないという問題がありました。そこで今度は、上とまったく同じ手順を「 $\sqrt{3}$ を小数展開せずに（ $\sqrt{3}$ をそのまま残しつつ）」実行する方法を紹介します。これによって、循環するポイントを厳密に評価できます。

今回は電卓は基本的に使えないので、手計算でがんばりましょう。

1. 整数部分をとる：
$\sqrt{3}$ の整数部分をとると $a_0 = \lfloor\sqrt{3}\rfloor = 1$ となります。 $\lfloor x \rfloor$ は $x$ の整数部分を取り出す記号です（小数点以下を切り捨てと思ってもいいです）。

整数部分をとる操作については小数展開を用いてもいいですし、 $n^2 \leq D < (n+1)^2$ となる整数 $n$ を探しても良いです。

2. 小数部分の逆数をとる：
整数部分を取り除いた小数部分は、 $\sqrt{3}$ から $1$ を引いて

$\sqrt{3} - 1$

となりますが、これは $0$ 以上 $1$ 未満の数となります。これの逆数をとると

$\displaystyle \frac{1}{\sqrt{3} - 1}$

となります。

3. 2. の整数部分をとる：
整数部分をとると $a_1 = \lfloor \frac{1}{\sqrt{3} - 1} \rfloor$ となります。この部分の計算は、一旦分数を有理化して

$\displaystyle \frac{1}{\sqrt{3} - 1} = \frac{\sqrt{3} + 1}{2}$

結果の整数部分 $\lfloor \frac{\sqrt{3} + 1}{2} \rfloor$ をとればよいでしょう。この計算もやはり $\sqrt{3}$ の小数展開が必要そうに見えるかもしれませんが、必要なのは $\sqrt{3}$ の整数部分だけです。 $1 \leq \frac{\sqrt{3} + 1}{2} < 2$ なので $a_1 = 1$ が得られます。

4. 小数部分の逆数をとる：
$\frac{\sqrt{3} + 1}{2}$ から $1$ を引くと、 $\frac{\sqrt{3} + 1}{2}$ の小数部分が得られます：

$\displaystyle \frac{\sqrt{3} + 1}{2} - 1 = \frac{\sqrt{3} - 1}{2}$

再度逆数をとると

$\displaystyle \frac{2}{\sqrt{3} - 1}$

となります。

5. 4. の整数部分をとる：
$\frac{2}{\sqrt{3} - 1}$ の整数部分 $a_2 = \lfloor \frac{2}{\sqrt{3} - 1} \rfloor$ を計算します。やはり有理化すると

$\displaystyle \frac{2}{\sqrt{3} - 1} = \sqrt{3} + 1$

となりますが、 $2 \leq \sqrt{3} + 1 < 3$ より、整数部分は $a_2 = 2$ となります。

こんな風に繰り返していけばいいわけですね。

ここで、最後の結果から整数部分を除いた小数部分は

$\displaystyle \sqrt{3} - 1$

となることに気づきます。これは手順2. に登場した結果と等しいので、ここから先は同じ計算が繰り返されるというわけですね。

今回の場合は、 $\sqrt{3}$ をそのまま残しているので、厳密に循環することが評価できていることに注意しましょう。ただし、手計算でないと実行できないことと、循環周期が長くなると計算が煩雑になるという問題があります。また、 $\sqrt{D}$ 以外の無理数だと、この方法はなかなか難しいかもしれません。良し悪しですね。

なお、最初に紹介したアプリは、基本的にはこの②の方法を使っています。したがって、 $\sqrt{D}$ の計算は厳密に実行できています。なので、計算が大変だと思ったら、どんどんアプリを使っちゃってください。

連分数を用いた無理数の近似

最後に、連分数展開の面白い応用を一つ紹介します。それは無理数の精度の高い近似分数を得ることです。

まず、連分数展開の近似分数を定義したいと思います。ある無理数 $\alpha$ が

$\displaystyle \alpha = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{a_4 + \cfrac{1}{\ddots}}}}}$

と表せるとき、この右辺を $n$ 項目の $a_n$ までで打ち切って得られる分数

$\displaystyle a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{\ddots}{\ddots + \cfrac{1}{a_n}}}}$

を、 $\alpha$ の近似分数と呼びます。（ $n$ 次の近似分数と言ったりもします。）

近似分数は、分数の計算を順次実行していくことで、分数 $\frac{p_n}{q_n}$ の形にすることができます。これは有理数なので、つまり近似分数とは無理数を有理数に近似する操作ということになりますね。

もちろん、分数の計算を順次実行していっても良いのですが、これは結構手間なことが多いです。近似分数を計算するには、以下の漸化式が便利です：

定理1

連分数

$\displaystyle \frac{p_n}{q_n} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{\ddots}{\ddots + \cfrac{1}{a_n}}}}$

が与えられたとき、次の漸化式が成り立つ：

$\begin{cases} p_0 = a_0, \;\; & p_1 = a_0 a_1 + 1, \;\; & p_n = a_n p_{n-1} + p_{n-2} \\ q_0 = 1, \;\; & q_1 = a_1, \;\; & q_n = a_n q_{n-1} + q_{n-2} \end{cases} \;\;\; (n\geq 2)$

この方法のよいところは前から順に機械的に計算できることですね。普通、上記の連分数を計算しようと思ったら、 $a_{n-1}$ と $1/a_n$ を足すところから始めると思います。上の方法では、 $a_0$ の方から計算することができ、自然な順序で計算できるのがポイントです。

三項間漸化式なので、フィボナッチ数列と同じ要領で計算することができます。実際、 $a_i = 1$ のときはフィボナッチ数列そのものになりますので、以下の連分数はフィボナッチ数の比 $F_{n+1} / F_{n}$ の極限となります。すなわち、黄金比 $\phi$ の連分数展開ですね：

$\displaystyle \phi = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{\ddots}}}}}$

また、漸化式を観察すると、分母と分子が独立に計算できることがわかります。したがって、分母だけの評価をしたいときにも有効です。

さて、 $\sqrt{3}$ の近似分数を求めてみましょう。

$\displaystyle \frac{p_0}{q_0} = 1$ （ $\sqrt{3}$ との誤差： $0.73205080756$ ）
$\displaystyle \frac{p_1}{q_1} = 1 + \cfrac{1}{1} = \frac{2}{1}$ （ $\sqrt{3}$ との誤差： $0.26794919243$ ）
$\displaystyle \frac{p_2}{q_2} = 1 + \cfrac{1}{1 + \cfrac{1}{2}} = \frac{5}{3}$ （ $\sqrt{3}$ との誤差： $0.0653841409$ ）
$\displaystyle \frac{p_3}{q_3} = 1 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{1}}} = \frac{7}{4}$ （ $\sqrt{3}$ との誤差： $0.01794919243$ ）
$\displaystyle \frac{p_4}{q_4} = 1 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{2}}}} = \frac{19}{11}$ （ $\sqrt{3}$ との誤差： $0.00477808029$ ）
$\displaystyle \frac{p_5}{q_5} = 1 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{1}}}}} = \frac{26}{15}$ （ $\sqrt{3}$ との誤差： $0.00128252576$ ）

こんな風に、だんだんと良い精度の近似分数が得られます。

面白い例を紹介すると、アルキメデスが円周率を計算する際に使った

$\displaystyle \sqrt{3} \approx \frac{265}{153}$

という近似があるのですが、これは $\sqrt{3}$ の連分数展開の $9$ 次近似分数となっています。

$\displaystyle 1 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{2}}}}}}}} = \frac{265}{153}$

このときの $\sqrt{3}$ との誤差は $0.00002466$ となります。かなり小さいですね。
tsujimotter.hatenablog.com

連分数展開の近似分数の著しい性質として、分母の大きさに対して最良近似を与えるというものがあります。

連分数展開による無理数 $\alpha$ の近似分数が $\frac{p_n}{q_n}$ であるとき、これより分母の小さい分数であって、 $\frac{p_n}{q_n}$ より誤差の小さい分数は存在しないということです。このような性質を最良近似といいます。 $\frac{265}{153}$ の例でいうと、分母が $153$ より小さい分数であって、 $\sqrt{3}$ との誤差が $0.00002466$ 未満になるものは存在しないということですね。

実際、分母 $q$ を固定したとき、誤差 $\left|\sqrt{3} - \frac{p}{q}\right|$ が最も小さくなるような分子 $p$ を選ぶことにします。このとき、横軸 $q$ に対して縦軸 $\left|\sqrt{3} - \frac{p}{q}\right|$ をプロットすると、次のようなグラフが描けます：