连分数

在数学中，连分数或繁分数即如下表达：

$$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
- 认识连分数
- 网上互动式多功能服务站－连分数计算器