连分数

维库，知识与思想的自由文库

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

$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 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + ...}}}}}}$ 由此得到 $\sqrt{2}$ 的渐近分数 $\frac{1}{1}$ 、 $\frac{3}{2}$ 、 $\frac{7}{5}$ 、 $\frac{11}{7}$ 、……

$\frac{\sqrt{5} -1}{2} = \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + ...}}}}}}$ 由此得到黄金分割的渐近分数 $\frac{1}{1}$ 、 $\frac{1}{2}$ 、 $\frac{2}{3}$ 、 $\frac{3}{5}$ 、 $\frac{5}{8}$ 、 $\frac{8}{13}$ 、……

注意将上述系列的分子分母依序排列均可得到斐波那契数列。

$\pi = 3 + \frac{1}{7 + \frac{1}{15 + \frac{1}{1 + \frac{1}{292 + \frac{1}{1 + \frac{1}{1 + ...}}}}}}$ 由此得到圆周率的渐近分数 $\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₀ 可以是任意整数，其它 a_i 都是 {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。（但是 [a₀; a₁, ... a_n, 1] = [a₀; a₁, ... a_n + 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\,$	$3.245 - 3\,$	$= 0.245\,$	$1 / 0.245\,$	$= 4.082\,$
$4\,$	$4.082 - 4\,$	$= 0.082\,$	$1 / 0.082\,$	$= 12.250\,$
$12\,$	$12.250 - 12\,$	$= 0.250\,$	$1 / 0.250\,$	$= 4.000\,$
$4\,$	$4.000 - 4\,$	$= 0.000\,$	STOP
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 的幂），所以欧几里德GCD算法的变体可以用来给出精确的结果。

[编辑] 连分数的表示法

可以把连分数简写作︰

$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}]$

对于正整数 a₁, a₂, a₃ ... 的任意选择，皆存在此一极限。

[编辑] 有限连分数

所有有限连分数都表示一个有理数，而所有有理数都可以按两种不同的方式表示为有限连分数。这两种表示除了最终项之外都是一致的。在較長的连分数表示，其最终项是 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 = 9/4 = [2; 3, 1] = [2; 4] \;$

$-4.2 = -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+1/(a+1/b)\$ 且 $1/x = a+1/b\$ ，而且如果 $x>1\$ ，则 $x = a+1/b\$ 且 $1/x = 0+1/(a+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₀, a₁, a₂, ... 是正整数的无限序列，递归的定义序列 $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}} {x k_{n-1}+k_{n-2}}$

[编辑] 定理 2

[a₀; a₁, a₂, ...] 的收敛以

$\left[a_0; a_1, \,\dots, a_n\right]= \frac{h_n} {k_n}$

給出。

[编辑] 定理 3

如果对连分数的第 n 个收敛是 $h n / k n$ ，则

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

推论 1：每个收敛都在它的最低的那些项中（如果 $h n$ 和 $k n$ 有不尋常的公约数，则它可除 $k n h 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$ 的连分数展开的半收敛包括了所有比有更小分母的任何逼近都好的有理数逼近。另一个有用的性质是连续的半收敛 a/b 和 c/d 有着 $ad-bc = \pm 1$ 。

[编辑] 最佳有理数逼近

对实数 x 的最佳有理数逼近是有理数 ⁿ⁄_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]
1	³⁄₄	⁴⁄₅	⁵⁄₆	¹¹⁄₁₃	¹⁶⁄₁₉	²⁷⁄₃₂

包含了分母严格单调递增的增补项允许在算法上施加限制，要么在分母的大小上，要么在逼近的接近性上。

要向有理数逼近併入新项，只需要两个前面的收敛。如果 a_k+1 是新项，则新分子和分母是

n_k+1 = n_k−1 + a_k+1 n_k

d_k+1 = d_k−1 + a_k+1 d_k

初始的收敛（要求前两项）是 ⁰⁄₁ 和 ¹⁄₀。例如，以下是对 [0;1,5,2,2] 的收敛。

k	−2	−1	0	1	2	3	4
a_k			0	1	5	2	2
n_k	0	1	0	1	5	11	27
d_k	1	0	1	1	6	13	32

减半规则的形式描述是减半的项 ¹⁄₂ a_k 是可接受的，当且仅当

[a_k; a_k−1, …, a₁] > [a_k; a_k+1, …]

在实践中，经常使用类似欧几里德 GCD 的算法依序生成这些项，且它提供的辅助值可更方便的测试。例如，以下是为 0.84375 = ²⁷⁄₃₂ 生成的项。

a₀	= ⌊²⁷⁄₃₂⌋	= 0,	f₀	= 27 − 32a₀	= 27
a₁	= ⌊³²⁄₂₇⌋	= 1,	f₁	= 32 − 27a₁	= 5
a₂	= ⌊²⁷⁄₅⌋	= 5,	f₂	= 27 − 5a₂	= 2
a₃	= ⌊⁵⁄₂⌋	= 2,	f₃	= 5 − 2a₃	= 1
a₄	= ⌊²⁄₁⌋	= 2,	f₄	= 2 − 1a₄	= 0

使用以此生成的 f 值，¹⁄₂ a_k 的可接受性测试是 d_k−2 ⁄ d_k−1 > f_k ⁄ f_k−1。对於例中的 a₃，d₁ ⁄ d₂ = ¹⁄₆ 且 f₃ ⁄ f₂ = ¹⁄₂，所以 ¹⁄₂ a₃ 是不可接受的；在对 a₄ 的时候，d₂ ⁄ d₃ = ⁶⁄₁₃ 且 f₄ ⁄ f₃ = ⁰⁄₁，所以 ¹⁄₂ a₄ 是可接受的。

对 x 的收敛在更强的意义上是最佳逼近：ⁿ⁄_d 是 x 的逼近，当且仅当 |dx−n| 是在所有逼近 ^m⁄_c 带有 c ≤ d 中是最小的相对误差的；就是说，我们有 |dx−n| < |cx−m| 只要 c < d。（注意还有 |d_kx−n_k| → 0 当 k→∞。）

[编辑] 连分数历史

300 BC 欧几里德, 《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》 - 介入了术语“连分数”
ca 1780 约瑟夫·路易斯·拉格朗日 - 使用类似于 Bombell 的连分数提供了佩尔方程的通用解
1748 莱昂哈德·欧拉, 《Introductio in analysin infinitorum》. Vol. I, Chapter 18 - 证明了特定形式的连分数和广义无穷级数的等价性
1813 卡尔·弗里德里希·高斯, 《Werke》, Vol. 3, pp. 134-138 - 通过涉及到超几何级数的一个聪明的恒等式推导出非常一般性的复数值的连分数

[编辑] 参见

[编辑] 外部链接

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.1based on theGeneralized Mediant

[编辑] 引用

A. Ya. Khinchin, Continued Fractions, 1935, English translation University of Chicago Press, 1961 ISBN 0-486-69630-8
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-9-81-021052-6
H. S. Wall, Analytic Theory of Continued Fractions, D. Van Nostrand Company, Inc., 1948 ISBN 0-8284-0207-8 pms:Frassion continuà

来自“http://wwww.51txl.com/wiki/%E8%BF%9E%E5%88%86%E6%95%B0”

个人工具

连分数