6
高校数学解説
文献あり

無理数の最良近似分数と連分数展開・加比の理・ファレイ数列の関係(前編)

1410
0

はじめに

この記事では、次のような問題について考えます。

ネイピア数 e の近似分数であって、分母が300以下の分数のうちもっともeとの差の絶対値が小さいものはなんでしょうか。

ネイピア数の近似値(いわゆる「ふなひとはちふたはちひとはちふたはち」)
e=2.718281828
は既知としてよいです。

この問題を解くために、無理数の最良近似分数を得る方法についての解説をします。

(前編)では、単純に連分数展開を途中で打ち切る方法では得られない最良近似分数が存在することを紹介し、さらに、加比の理を使えばすべての最良近似分数が得られることを紹介します。

(後編)では、連分数展開を途中で打ち切る方法を改良することで、改良前の方法では得られなかった最良近似分数を得ることができることを紹介し、さらに、その方法を使えば、無理数の具体的な値が不明な場合であっても、その無理数の連分数展開が既知であれば最良近似分数を得られることを示す予定です。

この記事は当初「連分数展開では得られない無理数の最良近似分数を加比の理とファレイ数列で得る」のタイトルで公開していましたが、記事公開後、いろいろな情報がTwitterでよせられたり、木村俊一著「連分数のふしぎ」の本を読んだりした結果、当初は連分数展開では得られないと思っていた無理数の最良近似分数について、連分数展開から得る方法もあることがわかりましたので、記事の内容を大幅に加筆修正してタイトルを「無理数の最良近似分数と連分数展開・加比の理・ファレイ数列の関係」に変更したうえ、(前編)(後編)に分けて再構成したものです。

最良近似分数の定義

 「最良近似分数」の定義はいろいろ考えられます。この記事では、以下の議論をわかりやすくするため、「第1種最良近似分数」「第2種最良近似分数」の二つを定義します。
この記事で主に話題とする「第1種最良近似分数」はこんな感じです。

第1種最良近似分数

無理数 ω を近似する分数 PQ について, q<Q なるどんな分数 pq に対しても

|ωPQ|<|ωpq|

がなりたつとき,分数 PQ を無理数 ω の第1種最良近似分数という。

 要するに、これより小さい分母ではよりよい近似が得られないということであり、素朴な定義だと思います。
 「最良」という言葉から一つしかないようなニュアンスを感じるかもしれませんが、実際には最良近似分数となるような分数は無数にあることに注意してください。

第2種最良近似分数

無理数 ω を近似する分数 PQ が, q<Q なるどんな分数 pq に対しても

|QωP|<|qωp|

がなりたつとき,分数 PQ を無理数 ω の第2種最良近似分数という。

定義がやや直感的ではないですが、実は第2種最良近似分数は連分数と相性がよく扱いやすいです。

第1種最良近似分数と第2種最良近似分数の違い

第2種最良近似分数は全て第1種最良近似分数になりますが、第1種最良近似分数は第2種最良近似分数になるとは限りません。言い換えると、第2種最良近似分数の方が範囲がせまいということです。そのことは次の不等式からわかります。

第2種最良近似分数は全て第1種最良近似分数になる

|QωP|<|qωp|

1Q|QωP|<1q|qωp|1Q<1q

|ωPQ|<|ωpq|

また、第1種最良近似分数、第2種最良近似分数ともに、分母が大きいものほど無理数との差の絶対値が小さくなります。

この記事では、主に第1種最良近似分数を得る方法について解説します。単に「最良近似分数」としか書いていない場合は、第1種最良近似分数のことを指していると思って読んでください。

名称について

「第1種最良近似分数」「第2種最良近似分数」という名称は私のオリジナルではなく、ネットでみかけたものをそのまま真似して使っています。もとは連分数についての教科書「 A. Ya. Khinchin. Continued Fractions. Dover(1997)」で使われていた用語のようです。

連分数展開で主近似分数を得る方法と第2種最良近似分数

例えば、円周率 π の近似分数を連分数展開を途中で打ち切る方法で次々と求めると、次のようになります。

π は次のように連分数展開できることが知られています。

π=3+17+115+11+1292+11+11+

途中で打ち切ると次のように次々と近似分数が得られます。

3=31

3+17=227=3.1428571428

3+17+115=333106=3.1415094339

3+17+115+11=355113=3.1415929203

3+17+115+11+1292=10399333102=3.1415926530

3+17+115+11+1292+11=10434833215=3.1415926539

3+17+115+11+1292+11+11=20834166317=3.1415926534

このように、連分数を途中で止めて作る近似分数を「主近似分数」と呼びます。また、打ち切る位置で順に「第0主近似分数」「第1主近似分数」「第 n 主近似分数」と呼びます。
上記の例を見ると、止める位置を後ろにするほど近似精度が上がっていることが確認できますね。実は、主近似分数について次の事実が知られています。

第2種最良近似分数は主近似分数である。

逆に、主近似分数は一般に第2種最良近似分数である。

(ただし、第0主近似分数(すなわち整数部分)は除く)

証明はこの記事では省略します。「 実数の有理数近似と連分数(詫間電波工業高等専門学校) 」のpdfを参照してください。

さて、前置きが長かったですが、これでようやく準備ができました。
改めて、次の問題を考えてみましょう。

問題

最良近似分数を求める問題

ネイピア数 e の近似分数であって、分母が300以下の分数のうちもっともeとの差の絶対値が小さいものはなんでしょうか。

ネイピア数の近似値(いわゆる「ふなひとはちふたはちひとはちふたはち」)
e=2.718281828
は既知としてよいです。

この問題は、「第1種最良近似分数のうち、分母が300以下で一番大きいもの」を求めればよいことになります。

第2種最良近似分数はこの問題の解ではない

実はこの問題の解は第1種最良近似分数ですが第2種最良近似分数ではありません。一応、そのことを具体的な計算で確認しておきましょう。

連分数展開の主近似分数(=第2種最良近似分数)を求める

e は次のように連分数展開できることが知られています。

e=2+11+12+11+11+14+11+11+16+11+

連分数展開を途中でとめることで近似分数を次々と得られます。

2+11=31

e=2+11+12=83

e=2+11+12+11=114

e=2+11+12+11+11=197

e=2+11+12+11+11+14=8732

e=2+11+12+11+11+14+11=10639

e=2+11+12+11+11+14+11+11=19371

この方法で得られる主近似分数(=第2種最良近似分数)を分母が小さい順に並べるとこうなります。

31,83,114,197,8732,10639,19371,1264465,1457536,27211001,

(実は、e より大きいものと e より小さいものが交互に並んでいます。)

上記の近似分数たちのうち、分母が 300 以下で最大なのは 19371 です。しかし、19371 はこの問題の答えではありません。

数値計算で確かめる

具体的な解き方を考える前に、あらかじめ第1種最良近似分数がどのように現れるのかを確認しておきましょう。

分母分数誤差最良
131-0.28171817Y
2520.21828183Y
3830.051615162Y
4114-0.031718172Y
5145-0.081718172-
61660.051615162-
71970.0039961142Y
8228-0.031718172-
92490.051615162-
1027100.018281828-
113011-0.0089908988-
123312-0.031718172-
1335130.025974136-
1438140.0039961142-
154115-0.015051505-
1643160.030781828-
1746170.012399476-
184918-0.0039403938Y
195219-0.018560277-
2054200.018281828-

表の右列が「Y」となっているのが第1種最良近似分数で、「-」は第1種最良近似分数ではない近似分数です。第1種最良近似分数を並べると次のとおりです。

31,52,83,114,197,4918,6825,8732,10639,19371,685252,878323,1071394,1264465,1457536,27211001,

連分数展開で得られる主近似分数(=第2種最良近似分数)を並べるとこうでした。

31,83,114,197,8732,10639,19371,1264465,1457536,27211001,

比較すると、連分数展開の主近似分数を得る方法では全ての最良近似分数が得られるわけではないことがわかります。

加比の理で第1種最良近似分数を得る

まず、不等式バージョンの加比の理を説明します。

加比の理(不等式バージョン)

不等式バージョンの加比の理は次のようなものです。

加比の理(不等式バージョン)

ba<dc のとき ba<b+da+c<dc

この不等式が成立することは次の図から明らかでしょう。

加比の理の図形的証明 加比の理の図形的証明

アルゴリズム

さて、次の作り方で加比の理を使ってどんどん e の近似分数を作っていきます。

(作り方)
次の不等式からスタートする。

21<e<31

加比の理で新しい分数を作る。

21<52<31

e との大小を比較して新しい不等式を作る。

52<e<31

以下くりかえし

このアルゴリズムで次のように近似分数の不等式が次々と得られます。

加比の理で近似分数を得る

21<e<31

52<e<31

83<e<31

83<e<114

197<e<114

197<e<3011

197<e<4918

197<e<6825

197<e<8732

10639<e<8732

10639<e<19371

299110<e<19371

492181<e<19371

685252<e<19371

878323<e<19371

1071394<e<19371

1264465<e<19371

1264465<e<1457536

27211001<e<1457536

27211001<e<41781537

実は、それぞれの不等式で

eより小さいもののうち最良近似<e<eより大きいもののうち最良近似

となっています。つまり、不等式の左右のうち少なくとも片方は第1種最良近似分数になっています。両方が第1種最良近似分数となっている場合もあります。

得られた分数を並べると次のようになります。

31,52,83,114,197,3011,4918,6825,8732,10639,19371,299110,492181,685252,878323,1071394,1264465,1457536,27211001,

それでは、第1種最良近似分数、第2種最良近似分数と加比の理で得られた分数を比較してみましょう。

第1種第2種加比の理
3131<e<31
52-52<e<
838383<e<
114114<e<114
197197197<e<
--<e<3011
4918-<e<4918
6825-<e<6825
87328732<e<8732
106391063910639<e<
1937119371<e<19371
--299110<e<
--492181<e<
685252-685252<e<
878323-878323<e<
1071394-1071394<e<
126446512644651264465<e<

この表を見れば、「加比の理を使えば第1種最良近似分数を得られそう」であることがわかります。

また、「第2種最良近似分数は、"e より小さいもの" と "e より大きいもの" が切り替わる直前に現れる」という法則があることもわかります。

さらに、「加比の理を使って得られる近似分数の中には、最良近似分数でないものも含まれている」こともわかりますね。さらに注意深く観察すると、「加比の理を使って得られる近似分数で最良近似分数でないものは、不等式の逆側の近似分数の中に『より分母が小さくて誤差も小さいもの』がある」という法則があることがわかります。

ファレイ数列との関係

それでは、上記の法則の正当性を確認しましょう。
加比の理で近似分数を得るアルゴリズムは、ファレイ数列に現れる無理数の近似分数を順に得る手順と全く一致しています。ファレイ数列の性質から、加比の理で最良近似分数をすべて得られることが理解できるようになります。

ファレイ数列とは、つぎのような一群の数列です。

ファレイ数列 (Farey sequence)

ファレイ数列とは、既約分数を順に並べた一群の数列である。 正確にいえば、

自然数 n に対して、n に対応する(または、属する)ファレイ数列 (Farey sequence of order n) Fn とは、分母が n 以下で、 0 以上 1 以下の全ての既約分数を小さい順から並べてできる有限数列である。 ただし、整数 0,1 はそれぞれ分数 01,11 として扱われる。

ファレイ数列 Fn は、具体的に n=1,,8 のとき次のようになります。

F1=(01,11)
F2=(01,12,11)
F3=(01,13,12,23,11)
F4=(01,14,13,12,23,34,11)
F5=(01,15,14,13,25,12,35,23,34,45,11)
F6=(01,16,15,14,13,25,12,35,23,34,45,56,11)
F7=(01,17,16,15,14,27,13,25,37,12,47,35,23,57,34,45,56,67,11)
F8=(01,18,17,16,15,14,27,13,38,25,37,12,47,35,58,23,57,34,45,56,67,78,11)

ファレイ数列(Wikipediaより) ファレイ数列(Wikipediaより)

ファレイ数列の面白い性質(隣接する分数と中間数)

ファレイ数列に新たな分数が加わる法則があります。

隣接する分数と中間数

2 つの分数 abcd が、あるファレイ数列で隣接しているならば、この 2 つの分数の間に新たな分数が加わるのは次数 b+d のファレイ数列においてであり、それは ab,cd の中間数 (mediant) と呼ばれる分数、

a+cb+d

である。

例えば、F5 では隣接している 1325 の間に現れる最初の項は F8

38

です。この中間数の式は加比の理で二つの分数の間にある分数を求める計算式と全く同じであることがわかりますね!

加比の理で最良近似分数が得られる理由

これで、加比の理で最良近似分数が得られる理由がわかります。

具体例で考えましょう。たとえば F5 の中で (e2) の入る位置を考えると

01<<23<(e2)<34<<11

となることから、分母が 5 以下の分数のうち、e より小さくて e に最も近い分数は 83 で、e より大きくて e に最も近い分数は 114 であることがわかります。

次にファレイ数列にeに更に近い分数が現れるのは、3+4=7 より F7 であることがわかり、F7の中で (e2) の入る位置を考えると

01<<23<57<(e2)<34<<11

となることから、分母が 7 以下の分数のうち、e より小さくて e に最も近い分数は 197 で、e より大きくて e に最も近い分数は 114 であることがわかります。

問題の答え

ここまでを踏まえて、冒頭の問題を解いてみましょう。

最良近似分数を求める問題(再掲)

ネイピア数 e の近似分数であって、分母が300以下の分数のうちもっともeとの差の絶対値が小さいものはなんでしょうか。

ネイピア数の近似値(いわゆる「ふなひとはちふたはちひとはちふたはち」)
e=2.718281828
は既知としてよいです。

e=2.718281828828 と加比の理を使って得られる不等式を再掲します。

21<e<31

52<e<31

83<e<31

83<e<114

197<e<114

197<e<3011

197<e<4918

197<e<6825

197<e<8732

10639<e<8732

10639<e<19371

299110<e<19371

492181<e<19371

685252<e<19371

252+71>300 ですから、分母が 300 以下の分数でこれ以上 e に近いものはありません。

685252 と 19371 を比較すると

|e685252|=0.0000278

|e19371|=0.0000280

ですから、求める最良近似分数は

685252

であることがわかります。

おわりに

今回の記事は、M\{R}さんのツイート、ととさんのツイート、しおあびびさんのツイートを参考にさせていただきした。ありがとうございました。

M\{R}さんのツイート

ととさんのツイート

しおあびびさんのツイート

(前編)の記事はここでおしまいです。

(後編)の記事では、連分数展開を途中で打ち切る方法を改良することで、無理数の具体的な値が不明な場合であっても、その無理数の連分数展開が既知であれば最良近似分数を得られることを示す予定です。お楽しみに!

参考文献

投稿日:202152
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

apu_yokai
apu_yokai
483
65135

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. 最良近似分数の定義
  3. 第1種最良近似分数と第2種最良近似分数の違い
  4. 連分数展開で主近似分数を得る方法と第2種最良近似分数
  5. 問題
  6. 第2種最良近似分数はこの問題の解ではない
  7. 数値計算で確かめる
  8. 加比の理で第1種最良近似分数を得る
  9. 加比の理(不等式バージョン)
  10. アルゴリズム
  11. ファレイ数列との関係
  12. ファレイ数列の面白い性質(隣接する分数と中間数)
  13. 加比の理で最良近似分数が得られる理由
  14. 問題の答え
  15. おわりに
  16. 参考文献