この記事では、次のような問題について考えます。
ネイピア数
ネイピア数の近似値(いわゆる「ふなひとはちふたはちひとはちふたはち」)
は既知としてよいです。
この問題を解くために、無理数の最良近似分数を得る方法についての解説をします。
(前編)では、単純に連分数展開を途中で打ち切る方法では得られない最良近似分数が存在することを紹介し、さらに、加比の理を使えばすべての最良近似分数が得られることを紹介します。
(後編)では、連分数展開を途中で打ち切る方法を改良することで、改良前の方法では得られなかった最良近似分数を得ることができることを紹介し、さらに、その方法を使えば、無理数の具体的な値が不明な場合であっても、その無理数の連分数展開が既知であれば最良近似分数を得られることを示す予定です。
この記事は当初「連分数展開では得られない無理数の最良近似分数を加比の理とファレイ数列で得る」のタイトルで公開していましたが、記事公開後、いろいろな情報がTwitterでよせられたり、木村俊一著「連分数のふしぎ」の本を読んだりした結果、当初は連分数展開では得られないと思っていた無理数の最良近似分数について、連分数展開から得る方法もあることがわかりましたので、記事の内容を大幅に加筆修正してタイトルを「無理数の最良近似分数と連分数展開・加比の理・ファレイ数列の関係」に変更したうえ、(前編)(後編)に分けて再構成したものです。
「最良近似分数」の定義はいろいろ考えられます。この記事では、以下の議論をわかりやすくするため、「第1種最良近似分数」「第2種最良近似分数」の二つを定義します。
この記事で主に話題とする「第1種最良近似分数」はこんな感じです。
無理数
がなりたつとき,分数
要するに、これより小さい分母ではよりよい近似が得られないということであり、素朴な定義だと思います。
「最良」という言葉から一つしかないようなニュアンスを感じるかもしれませんが、実際には最良近似分数となるような分数は無数にあることに注意してください。
無理数
がなりたつとき,分数
定義がやや直感的ではないですが、実は第2種最良近似分数は連分数と相性がよく扱いやすいです。
第2種最良近似分数は全て第1種最良近似分数になりますが、第1種最良近似分数は第2種最良近似分数になるとは限りません。言い換えると、第2種最良近似分数の方が範囲がせまいということです。そのことは次の不等式からわかります。
また、第1種最良近似分数、第2種最良近似分数ともに、分母が大きいものほど無理数との差の絶対値が小さくなります。
この記事では、主に第1種最良近似分数を得る方法について解説します。単に「最良近似分数」としか書いていない場合は、第1種最良近似分数のことを指していると思って読んでください。
「第1種最良近似分数」「第2種最良近似分数」という名称は私のオリジナルではなく、ネットでみかけたものをそのまま真似して使っています。もとは連分数についての教科書「 A. Ya. Khinchin. Continued Fractions. Dover(1997)」で使われていた用語のようです。
例えば、円周率
途中で打ち切ると次のように次々と近似分数が得られます。
このように、連分数を途中で止めて作る近似分数を「主近似分数」と呼びます。また、打ち切る位置で順に「第0主近似分数」「第1主近似分数」
上記の例を見ると、止める位置を後ろにするほど近似精度が上がっていることが確認できますね。実は、主近似分数について次の事実が知られています。
第2種最良近似分数は主近似分数である。
逆に、主近似分数は一般に第2種最良近似分数である。
(ただし、第0主近似分数(すなわち整数部分)は除く)
証明はこの記事では省略します。「 実数の有理数近似と連分数(詫間電波工業高等専門学校) 」のpdfを参照してください。
さて、前置きが長かったですが、これでようやく準備ができました。
改めて、次の問題を考えてみましょう。
ネイピア数
ネイピア数の近似値(いわゆる「ふなひとはちふたはちひとはちふたはち」)
は既知としてよいです。
この問題は、「第1種最良近似分数のうち、分母が300以下で一番大きいもの」を求めればよいことになります。
実はこの問題の解は第1種最良近似分数ですが第2種最良近似分数ではありません。一応、そのことを具体的な計算で確認しておきましょう。
連分数展開を途中でとめることで近似分数を次々と得られます。
この方法で得られる主近似分数(=第2種最良近似分数)を分母が小さい順に並べるとこうなります。
(実は、
上記の近似分数たちのうち、分母が
具体的な解き方を考える前に、あらかじめ第1種最良近似分数がどのように現れるのかを確認しておきましょう。
分母 | 分数 | 誤差 | 最良 |
---|---|---|---|
1 | -0.28171817 | Y | |
2 | 0.21828183 | Y | |
3 | 0.051615162 | Y | |
4 | -0.031718172 | Y | |
5 | -0.081718172 | - | |
6 | 0.051615162 | - | |
7 | 0.0039961142 | Y | |
8 | -0.031718172 | - | |
9 | 0.051615162 | - | |
10 | 0.018281828 | - | |
11 | -0.0089908988 | - | |
12 | -0.031718172 | - | |
13 | 0.025974136 | - | |
14 | 0.0039961142 | - | |
15 | -0.015051505 | - | |
16 | 0.030781828 | - | |
17 | 0.012399476 | - | |
18 | -0.0039403938 | Y | |
19 | -0.018560277 | - | |
20 | 0.018281828 | - |
表の右列が「Y」となっているのが第1種最良近似分数で、「-」は第1種最良近似分数ではない近似分数です。第1種最良近似分数を並べると次のとおりです。
連分数展開で得られる主近似分数(=第2種最良近似分数)を並べるとこうでした。
比較すると、連分数展開の主近似分数を得る方法では全ての最良近似分数が得られるわけではないことがわかります。
まず、不等式バージョンの加比の理を説明します。
不等式バージョンの加比の理は次のようなものです。
この不等式が成立することは次の図から明らかでしょう。
加比の理の図形的証明
さて、次の作り方で加比の理を使ってどんどん
(作り方)
次の不等式からスタートする。
加比の理で新しい分数を作る。
以下くりかえし
このアルゴリズムで次のように近似分数の不等式が次々と得られます。
実は、それぞれの不等式で
となっています。つまり、不等式の左右のうち少なくとも片方は第1種最良近似分数になっています。両方が第1種最良近似分数となっている場合もあります。
得られた分数を並べると次のようになります。
それでは、第1種最良近似分数、第2種最良近似分数と加比の理で得られた分数を比較してみましょう。
第1種 | 第2種 | 加比の理 |
---|---|---|
● | ||
- | ||
● | ||
- | - | ● |
- | ● | |
- | ● | |
● | ||
● | ||
- | - | |
- | - | |
- | ||
- | ||
- | ||
この表を見れば、「加比の理を使えば第1種最良近似分数を得られそう」であることがわかります。
また、「第2種最良近似分数は、"
さらに、「加比の理を使って得られる近似分数の中には、最良近似分数でないものも含まれている」こともわかりますね。さらに注意深く観察すると、「加比の理を使って得られる近似分数で最良近似分数でないものは、不等式の逆側の近似分数の中に『より分母が小さくて誤差も小さいもの』がある」という法則があることがわかります。
それでは、上記の法則の正当性を確認しましょう。
加比の理で近似分数を得るアルゴリズムは、ファレイ数列に現れる無理数の近似分数を順に得る手順と全く一致しています。ファレイ数列の性質から、加比の理で最良近似分数をすべて得られることが理解できるようになります。
ファレイ数列とは、つぎのような一群の数列です。
ファレイ数列とは、既約分数を順に並べた一群の数列である。 正確にいえば、
自然数
ファレイ数列
ファレイ数列(Wikipediaより)
ファレイ数列に新たな分数が加わる法則があります。
である。
例えば、
です。この中間数の式は加比の理で二つの分数の間にある分数を求める計算式と全く同じであることがわかりますね!
これで、加比の理で最良近似分数が得られる理由がわかります。
具体例で考えましょう。たとえば
となることから、分母が
次にファレイ数列に
となることから、分母が
ここまでを踏まえて、冒頭の問題を解いてみましょう。
ネイピア数
ネイピア数の近似値(いわゆる「ふなひとはちふたはちひとはちふたはち」)
は既知としてよいです。
ですから、求める最良近似分数は
であることがわかります。
今回の記事は、M\{R}さんのツイート、ととさんのツイート、しおあびびさんのツイートを参考にさせていただきした。ありがとうございました。
(前編)の記事はここでおしまいです。
(後編)の記事では、連分数展開を途中で打ち切る方法を改良することで、無理数の具体的な値が不明な場合であっても、その無理数の連分数展開が既知であれば最良近似分数を得られることを示す予定です。お楽しみに!