連分數

連分數（continued fraction）是特殊繁分數。如果a0，a1，a2，…an，…都是整數，則將分別稱為無限連分數和有限連分數。可簡記為a0 ，a1，a2，…，an，…和a0，a1，a2，…，an。一般一個有限連分數表示一個有理數，一個無限連分數表示一個無理數。如果a0，a1，a2，…，an，…都是實數，可將上述形式連分數分別叫無限連分數和有限連分數 。近代數學的計算需要，還可將連分數中的a0，a1 ，a2，…，an，…取成以x為變元的多項式。在近代計算數學中它常與某些微分方程式差分方程有關，與某些遞推關係有關的函式構造的套用相聯繫。

基本介紹

• 中文名：連分數
• 外文名：continued fraction
• 學科：數學
• 分類1：有限連分數
• 分類2：無限連分數

動機

研究連分數的動機源於想要有實數在“數學上純粹”的表示。

連分數

多數人熟悉實數的小數表示：（右圖）

這裡的a0 可以是任意整數，其它ai 都是 {0, 1, 2, ..., 9} 的一個元素。在這種表示中，例如數 π 被表示為整數序列 {3, 1, 4, 1, 5, 9, 2, ...}。

這種小數表示有些問題。例如，在這種情況下使用常數 10 是因為我們使用了 10進制系統。我們還可以使用 8進制或 2 進制系統。另一個問題是很多有理數在這個系統內缺乏有限表示。例如，數 1/3 被表示為無限序列 {0, 3, 3, 3, 3, ....}。

連分數表示法是避免了實數表示的這兩個問題。讓我們考慮如何描述一個數如 415/93，約為 4.4624。近似為 4，而實際上比 4 多一點，約為 4 + 1/2。但是在分母中的 2 是不準確的；更準確的分母是比 2 多一點，約為 2 + 1/6，所以 415/93 近似為 4 + 1/(2 + 1/6)。但是在分母中的 6 是不準確的；更準確分母是比 6 多一點，實際是 6+1/7。所以 415/93 實際上是 4+1/(2+1/(6+1/7))。這樣才準確。

去掉表達式 4 + 1/(2 + 1/(6 + 1/7)) 中的冗餘部分可得到簡略記號 [4; 2, 6, 7]。

實數的連分數表示可以用這種方式定義。它有一些可取的性質：

一個數的連分數表示是有限的，若且唯若這個數是有理數。 “簡單”有理數的連分數表示是簡短的。 任何有理數的連分數表示是唯一的，如果它沒有尾隨的 1。（但是 [a0; a1, ... an, 1] = [a0; a1, ... an + 1]。） 無理數的連分數表示是唯一的。 連分數的項將會重複，若且唯若它是一個二次無理數（即整數係數的二次方程的實數解）的連分數表示 [1]。 數 x 的截斷連分數表示很早產生 x 的在特定意義上“最佳可能”的有理數逼近（參閱下述定理 5 推論 1）。 最後一個性質非常重要，且傳統的小數點表示就不能如此。數的截斷小數表示產生這個數的有理數逼近，但通常不是非常好的逼近。例如，截斷 1/7 = 0.142857... 在各種位置上產生逼近比，如 142/1000、14/100 和 1/10。但是明顯的最佳有理數逼近是“1/7”自身。π 的截斷小數表示產生逼近比，如 31415/10000 和 314/100。π 的連分數表示開始於 [3; 7, 15, 1, 292, ...]。截斷這個表示產生極佳的有理數逼近 3、22/7、333/106、355/113、103993/33102、...。 314/100 和 333/106 的分母相當接近，但近似值 314/100 的誤差是遠高於 333/106 的 19 倍。作為對π的逼近，[3; 7, 15, 1] 比 3.1416 精確 100 倍。

算法

考慮實數r。設i是r的整數部分，而f是它的小數部分。則r的連分數表示是 [i; …]，這裡的“…”是 1/f的連分數表示。習慣上用分號取代第一個逗號。

要計算實數r的連分數表示，寫下r的整數部分（技術上floor）。從r減去這個整數部分。如果差為 0 則停止；否則找到這個差的倒數並重複。這個過程將終止，若且唯若r是有理數。

數 3.245 還可以表示為連分數展開 [3; 4, 12, 3, 1]；參見下面的有限連分數。

連分數

這個算法適合於實數，但如果用浮點數實現的話，可能導致數值災難。作為替代，任何浮點數是一個精確的有理數（在現代計算機上分母通常是 2 的冪，在電子計算器上通常是 10 的冪），所以歐幾里得GCD算法的變體可以用來給出精確的結果......

表示法

連分數的表示方法：

連分數

連分數

連分數

分類

有限連分數

所有有限連分數都表示一個有理數，而所有有理數都可以按兩種不同的方式表示為有限連分數。這兩種表示除了最終項之外都是一致的。在較長的連分數表示，其最終項是 1；較短的表示去掉了最後的 1，而向新的終項加 1。在短表示中的最終項因此大於 1，如果短表示至少有兩項的話。其符號表示：

=

連分數

連分數

連分數

連分數的倒數

有理數的連分數表示和它的倒數除了依據這個數小於或大於 1 而分別左移或右移一位以外是相同的。換句話說，（左圖）和（右圖）互為倒數。這是因為如果 a是整數，接著如果x<1,則x=0+1/(a+1/b)且1/x=a+1/b,而且如果x>1,則x=a+1/b且1/x=0+1/(a+1/b)帶有最後的數生成對x和它的倒數是同樣的連數的餘數。

連分數

連分數

連分數

無限連分數

所有無限連分數都是無理數，而所有無理數可用一種精確的方式表示為無限連分數。

無理數的無限連分數表示是非常有用的，因為它的初始段提供了對這個數的優異的有理數逼近。這些有理數可以叫做這個連分數的收斂（convergent，也譯為“漸進”）。所有偶數編號的收斂都小於最初的數，而奇數編號的收斂都大於它。

定理

如果a0,a1,a2, ... 是正整數的無限序列，遞歸的定義序列 hn 和 kn：

連分數

連分數

半收斂

則如下形式的任何分數

連分數

這裡的a是非負整數，而分子和分母在n和 n + 1 項（包含它們）之間，叫做“半收斂”、次收斂或中間分數。這個術語經常意味著排除了是收斂的可能性，而不是收斂是一種半收斂。

對實數x的連分數展開的半收斂包括了所有比有更小分母的任何逼近都好的有理數逼近。另一個有用的性質是連續的半收斂 a/b 和 c/d 有著 。

逼近

最佳有理數逼近

設 是實數α的第k個漸進分數，則對任意分數 滿足0<q<= 有 。

證明：若 則顯然成立。否則不妨設 ，若 則有 且 ，所以 矛盾！若 則有 ，由 有 矛盾！所以 此時由不等式性質顯然成立，或者 即 所以定理得證。

算法：對實數x的最佳有理數逼近是有理數 n/d（d > 0），它比帶有更小分母的任何逼近都接近於 x。依據如下三個規則，從 x 的簡單連分數生成所有對 x 的最佳有理數逼近：

截斷連分數，並儘可能減小它的最後項。 減小的項不能小於它最初的值的一半。 如果最終項是偶數，則用特殊規則確定它的值是否可接受。（見後） 例如，0.84375 有連分數 [0;1,5,2,2]。下面是它的所有最佳有理數逼近。

 [0;1]  [0;1,3]  [0;1,4]  [0;1,5]  [0;1,5,2]  [0;1,5,2,1]  [0;1,5,2,2] 13/4 4/5 5/6 11/13 16/19 27/32包含了分母嚴格單調遞增的增補項允許在算法上施加限制，要么在分母的大小上，要么在逼近的接近性上。

要向有理數逼近併入新項，只需要兩個前面的收斂。如果ak+1 是新項，則新分子和分母是

nk+1 = nk−1 + ak+1 nk dk+1 = dk−1 + ak+1 dk 初始的收斂（要求前兩項）是 0⁄1 和 1⁄0。例如，以下是對 [0;1,5,2,2] 的收斂。

k−2−101234ak01522nk010151127dk101161332減半規則的形式描述是減半的項 1/2 ak 是可接受的，若且唯若

[ak; ak−1, …, a1] > [ak; ak+1, …] 在實踐中，經常使用類似歐幾里得GCD的算法依序生成這些項，且它提供的輔助值可更方便的測試。例如，以下是為 0.84375 = 27⁄32 生成的項。

a0 = ⌊27⁄32⌋ = 0,  f0 = 27 − 32a0 = 27a1 = ⌊32/27⌋ = 1, f1 = 32 − 27a1 = 5a2 = ⌊27/5⌋ = 5, f2 = 27 − 5a2 = 2a3 = ⌊5/2⌋ = 2, f3 = 5 − 2a3 = 1a4 = ⌊2/1⌋ = 2, f4 = 2 − 1a4 = 0使用以此生成的f值，1/2 ak 的可接受性測試是 dk−2 ⁄ dk−1 > fk ⁄ fk−1。對於例中的 a3，d1 ⁄ d2 = 1/6 且 f3 ⁄ f2 = 1/2，所以 1/2 a3 是不可接受的；在對 a4 的時候，d2 ⁄ d3 = 6⁄13 且 f4 ⁄ f3 = 0⁄1，所以 1/2 a4 是可接受的。

對x的收斂在更強的意義上是最佳逼近：n/d 是 x 的逼近，若且唯若 |dx−n| 是在所有逼近 m⁄c 帶有 c ≤ d 中是最小的相對誤差的；就是說，我們有 |dx−n| < |cx−m| 只要 c < d。（注意還有 |dkx−nk| → 0 當 k→∞。）