連分數

在數學中，連分數或繁分數即如下表達：

$$x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{\ddots\,}}}}$$

這裡的$a_0$是某個整數，而所有其他的數$a_n$都是正整數，可依樣定義出更長的表達式。如果部分分子（partial numerator）和部分分母（partial denominator）允許假定任意的值，在某些上下文中可以包含函數，則最終的表達式是廣義連分數。在需要把上述標準形式與廣義連分數相區別的時候，可稱它為簡單或正規連分數，或稱為是規範形式的。

## 例子

連分數常用於無理數的逼近，例如：

$$\sqrt{2} = 1 + \frac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \ddots}}}}}}$$

由此得到$\sqrt{2}$的漸近分數：

$\frac{1}{1},\frac{3}{2},\frac{7}{5},\frac{17}{12}$、…

$$\frac{\sqrt{5}+1}{2} = 1 + \frac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \ddots}}}}}}$$

由此得到黃金分割的漸近分數：

$\frac{1}{1},\frac{2}{1},\frac{3}{2},\frac{5}{3},\frac{8}{5},\frac{13}{8}$、…

注意將上述系列的分母1,1,2,3,……等數依序排列均可得到斐波那契數列。

$$\pi = 3 + \frac{1}{7 + \cfrac{1}{15 + \cfrac{1}{1 + \cfrac{1}{292 + \cfrac{1}{1 + \cfrac{1}{1 + \ddots}}}}}}$$ 由此得到圓周率的漸近分數$\frac{3}{1},\frac{22}{7}$（約率）、$\frac{333}{106},\frac{355}{113}$（密率）、$\frac{103993}{33102}$、…

數學上可以證明，由（狹義）連分數得到的漸近分數，在分子或分母小於下一個漸進分數的分數中，其值是最接近精確值的近似值。

## 動機

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

多數人熟悉實數的小數表示：

$$r = \sum_{i=0}^\infty a_i 10^{-i}$$

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

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

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

去掉表達式$4+\frac{1}{2+\frac{1}{6+\frac{1}{7}}}$中的冗餘部分可得到簡略記號$[4;2,6,7]$。

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

- 一個有理數的連分數表示是有限的。
- 「簡單」有理數的連分數表示是簡短的。
- 任何有理數的連分數表示是唯一的，如果它沒有尾隨的1。（$[a_0; a_1,\ldots,a_n,1]=[a_0; a_1,\ldots,a_n+1]$）
- 無理數的連分數表示是唯一的。
- 連分數的項會循環，若且唯若它是一個二次無理數（即整數係數的二次方程的實數解）的連分數表示。
- 數x的截斷連分數表示很早產生x的在特定意義上「最佳可能」的有理數逼近（參閱下述定理5推論1）。

最後一個性質非常重要，且傳統的小數點表示就不能如此。數的截斷小數表示產生這個數的有理數逼近，但通常不是非常好的逼近。例如，截斷$\frac{1}{7}=0.142\ 857\ldots$在各種位置上產生逼近比，如$\frac{142}{1000}$、$\frac{14}{100}$和$\frac{1}{10}$。但是明顯的最佳有理數逼近是「$\frac{1}{7}$」自身。$\pi$的截斷小數表示產生逼近比，如$\frac{31415}{10000}$和$\frac{314}{100}$。$\pi$的連分數表示開始於$[3; 7,15,1,292,\ldots]$。截斷這個表示產生極佳的有理數逼近3、$\frac{22}{7}$、$\frac{333}{106}$、$\frac{355}{113}$、$\frac{103\ 993}{33\ 102}$、...。$\frac{314}{100}$和$\frac{333}{106}$的分母相當接近，但近似值$\frac{314}{100}$的誤差是遠高於$\frac{333}{106}$的19倍。作為對$\pi$的逼近，$[3; 7,15,1]$比3.1416精確100倍。

## 連分數表示的演算法

考慮實數$r$。設$i$是$r$的整數部分，而$f$是它的小數部分。則r的連分數表示是$[i;\ldots]$，這裡的「…」是$\frac{1}{f}$的連分數表示。習慣上用分號取代第一個逗號。

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

找出3.245的連分數

$3\,$｜$3.245 - 3\,$｜$= 0.245\,$｜$\frac{1}{0.245}\,$｜$= 4.082...\,$

$4\,$｜$4.082... - 4\,$｜$= 0.082...\,$｜$\frac{1}{0.082...}\,$｜$= 12.250\,$

$12\,$｜$12.250 - 12\,$｜$= 0.250\,$｜$\frac{1}{0.250}\,$｜$= 4.000\,$

$4\,$｜$4.000 - 4\,$｜$= 0.000\,$｜停止

3.245的連分數是$[3;4,12,4]$ $$3.245 = 3 + \cfrac{1}{4 + \cfrac{1}{12 + \cfrac{1}{4}}}$$

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

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

## 連分數的表示法

可以把連分數簡寫作：

$$x = [a_0; a_1, a_2, a_3] \;$$

或者，用Pringsheim的記法寫作：

$$x = a_0 + \frac{1 \mid}{\mid a_1} + \frac{1 \mid}{\mid a_2} + \frac{1 \mid}{\mid a_3}$$

還有一個有關的記法：

$$x = a_0 + {1 \over a_1 + } {1 \over a_2 +} {1 \over a_3 +}$$

有時使用尖括號，如：

$$x = \left \langle a_0; a_1, a_2, a_3 \right \rangle \;$$

在使用尖括號的時候，分號是可選的。

還可以定義無限簡單連分數為極限：

$$[a_{0}; a_{1}, a_{2}, a_{3}, \,\ldots ] = \lim_{n \to \infty} [a_{0}; a_{1}, a_{2}, \,\ldots, a_{n}]$$

對於正整數a1, a2, a3 ...的任意選擇，皆存在此一極限。

或者可以用高斯的記法

$$x = a_0 + \underset{i=1}{\overset{3}{\mathrm K}} ~ \frac{1}{a_i} \;$$

## 有限連分數

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

$$[a_{0}; a_{1}, a_{2}, a_{3}, \,\ldots ,a_{n}, 1]=[a_{0}; a_{1}, a_{2}, a_{3}, \,\ldots, a_{n} + 1] \;$$

例如：

$$2.25 =\frac{9}{4} = [2; 3, 1] = [2; 4] \;$$

$$-4.2 = -\frac{21}{5} = [-5; 1, 3, 1] = [-5; 1, 4] \;$$

## 連分數的倒數

有理數的連分數表示和它的倒數除了依據這個數小於或大於1而分別左移或右移一位以外是相同的。換句話說，$[a_0;a_1,a_2,a_3,\ldots,a_n]$和$[0;a_0,a_1,a_2,\ldots,a_n]$互為倒數。這是因為如果$a\ $是整數，接著如果$x<1\ $，則$x = 0+\tfrac{1}{a+\frac{1}{b}}\ $且$\tfrac{1}{x} = a+\tfrac{1}{b}\ $，而且如果$x>1\ $，則$x = a+\tfrac{1}{b}\ $且$\tfrac{1}{x} = 0+\tfrac{1}{a+\frac{1}{b}}\ $帶有最後的數生成對$x\ $和它的倒數是同樣的的連分數的餘數。

例如：

$$2.25 = \frac{9}{4} = [2; 4] \;$$

$$\frac{1}{2.25} = \frac{4}{9} = [0; 2, 4] \;$$

## 無限連分數

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

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

對於連分數$[a_0;a_1,a_2,\ldots]$，前四個收斂子（編號$0$到$3$）是

$$\frac{a_0}{1},\qquad \frac{a_1a_0+1}{a_1},\qquad \frac{ a_2(a_1a_0+1)+a_0}{a_2a_1+1},\qquad \frac{a_3[a_2(a_1a_0+1)+a_0]+(a_1a_0+1)}{a_3(a_2a_1+1)+a_1}$$

用普通語言來說，第3個收斂子的分子是藉由第3個商（$a_2$）乘上第2個收斂子的分子，並加上第1個收斂子的分子而成。分母的形成也很類似。

如果找到連續的收斂子，帶有分子$h_1,h_2,\ldots$和分母$k_1,k_2,\ldots$，則相關的遞歸關係是：

$$h_n=a_nh_{n-1}+h_{n-2},\qquad k_n=a_nk_{n-1}+k_{n-2}$$

連續的收斂子由如下公式給出

$$\frac{h_n}{k_n}= \frac{a_nh_{n-1}+h_{n-2}}{a_nk_{n-1}+k_{n-2}}$$

## 一些有用的定理

如果$a_0,a_1,a_2,\ldots$是正整數的無限序列，遞歸的定義序列$h_n$和$k_n$：

$h_{n}=a_nh_{n-1}+h_{n-2}\,$｜$h_{-1}=1\,$｜$h_{-2}=0\,$

$k_{n}=a_nk_{n-1}+k_{n-2}\,$｜$k_{-1}=0\,$｜$k_{-2}=1\,$

### 定理1

對於任何正數$x\in\mathbb{R}$

$$\left[a_0; a_1, \,\dots, a_{n-1}, x \right]= \frac{x h_{n-1}+h_{n-2}} <pre> {x k_{n-1}+k_{n-2}}$$

### 定理2

$[a_0,a_1,a_2,\ldots]$的 收斂子 序列是

$$\left[a_0; a_1, \,\dots, a_n\right]= \frac{h_n} <pre> {k_n}, </pre> n\in \mathbb{N}$$

所組成數列，它收斂到極限 $[a_0,a_1,a_2,\ldots]$。

### 定理3

如果對連分數的第n個收斂子是$h_n/k_n$，則

$$k_nh_{n-1}-k_{n-1}h_n=(-1)^n \,$$

推論1：每個收斂子都在它的最低的那些項中（如果$h_n$和$k_n$有不尋常的公約數，則它可除$k_nh_{n-1}-k_{n-1}h_n$，這當然是不可能的）。

推論2：在連續的收斂子之間的差是單位分數：

$$\left|\frac{h_n}{k_n}-\frac{h_{n-1}}{k_{n-1}} \right|= \left|\frac{h_nk_{n-1}-k_nh_{n-1}}{k_nk_{n-1}}\right|= \frac{1}{k_nk_{n-1}}$$

推論3：連分數等價於交替（alternating）項的級數：

$$a_0 + \sum_{n=0}^\infty \frac{(-1)^{n}}{k_{n+1}k_{n}}$$

推論4：矩陣

$$\begin{bmatrix} h_n & h_{n-1} \\ k_n & k_{n-1} \end{bmatrix}$$

行列式值為正1或負1，因此屬於2x2 么模矩陣$S^*L(2,\mathbb{Z})$的群。

### 定理4

每個（第$s$個）都比任何前面（第$r$個）收斂子更接近於後續的（第$n$個）收斂子。用符號來說，如果第$n$個收斂子是$[a_0;a_1,a_2,\ldots a_n]=x_n$，則

$$\left| x_r - x_n \right| > \left| x_s - x_n \right|$$

對於所有$r<s<n$。

推論1：奇數收斂子（在第$n$個之前）持續遞增而總是小於$x_n$。

推論2：偶數收斂子（在第$n$個之前）持續遞減而總是大於$x_n$。

### 定理5

$$\frac{1}{k_n(k_{n+1}+k_n)}< \left|x-\frac{h_n}{k_n}\right|< \frac{1}{k_nk_{n+1}}$$

推論1：任何收斂子都比其分母小於這個收斂子的分母的任何其他分數更接近於這個連分數。

推論2：立即前導於一個大商的任何收斂子都是對這個連分數的接近逼近。

## 半收斂子

如果$\frac{h_{n-1}}{k_{n-1}}$和$\frac{h_n}{k_n}$是連續的收斂子，則如下形式的任何分數

$$\frac{h_{n-1} + ah_n}{k_{n-1}+ak_n}$$

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

對實數$x$的連分數展開的半收斂子包括了所有比有更小分母的任何逼近都好的有理數逼近。另一個有用的性質是連續的半收斂子$\frac{a}{b}$和$\frac{c}{d}$有著$ad-bc = \pm 1$。

## 最佳有理數逼近

連分數理論在丟番圖逼近領域起基礎性的作用，可以解決實數的最佳逼近問題，具體可參閱相應主頁面。事實上，最初發展連分數理論的動機正是為了解決實數的最佳逼近問題。

## 連分數歷史

- 公元前300年－歐幾里得，《Elements》 - 最大公約數的演算法生成一個連分數作為副產品
- 1579年－Rafael Bombelli,《L'Algebra Opera》 -
- 1613年－Pietro Cataldi,《Trattato del modo brevissimo di trovar la radice quadra delli numeri》 - 第一種連分數的記號

Cataldi表示連分數為$a_0.\,$ &$n_1 \over d_1$。&$n_2 \over d_2$。&${n_3 \over d_3}$帶有指示隨後連分數要去的地方的點

- 1695年－約翰·沃利斯，《Opera Mathematica》 - 介入了術語「連分數」
- 約1780年－約瑟夫·拉格朗日 - 使用類似於Bombell的連分數提供了佩爾方程的通用解
- 1748 萊昂哈德·歐拉，《Introductio in analysin infinitorum》. Vol. I, Chapter 18 - 證明了特定形式的連分數和廣義無窮級數的等價性
- 1813年－卡爾·弗里德里希·高斯，《Werke》,第三冊, 134-138頁 - 通過涉及到超幾何級數的一個聰明的恆等式推導出非常一般性的複數值的連分數

## 參考文獻

- Oskar Perron, Die Lehre von den Kettenbrüchen, Chelsea Publishing Company, New York, NY 1950.
- Andrew M. Rockett and Peter Szusz, Continued Fractions, World Scientific Press, 1992 ISBN 978-981-02-1052-6
- H. S. Wall, Analytic Theory of Continued Fractions, D. Van Nostrand Company, Inc., 1948 ISBN 978-0-8284-0207-1

## 外部連結

- Online continued fraction calculator
- Linas Vepstas The Minkowski Question Mark and the Modular Group SL(2,Z) (2004) reviews the isomorphisms of continued fractions.
- Linas Vepstas Continued Fractions and Gaps (2004) reviews chaotic structures in continued fractions.
- Continued Fractions on the Stern-Brocot Tree at cut-the-knot
- Francois Balsalobre cfc - a (cli) continued fraction calculator for POSIX and Cygwin
- Continued Fractions and Fermat's Last Theorem.
- The Antikythera Mechanism I: Gear ratios and continued fractions
- Mathematical Constants, Steven Finch: Generalized Continued Fractions, Chap I, art. 1.1.1 based on the Generalized Mediant
- The Irish Scientist: New Generalized Continued Fractions based on the Generalized Mediant
- 認識連分數
- 網上互動式多功能服務站－連分數計算器