连分数（Continued fraction）

在数学中，连分数或繁分数即如下表达：x=a0+1a1+1a2+1a3+1⋱ {\displaystyle x=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots \,}}}}}}}}}x=a0+a1+a2+a3+⋱1111这里的 a0a_{0}a0 是某个整数，而所有其他的数

teengad

4490人浏览 · 2022-10-03 15:46:11

teengad · 2022-10-03 15:46:11 发布

文章目录

1. 常见应用
2. 研究动机
3. 连分数表示的算法
4. 连分数的表示法
5. 有限连分数
6. 连分数的倒数
7. 无限连分数
8. 一些有用的定理
9. 半收敛
10. 最佳有理数逼近
11. 连分数历史

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

$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）允许假定任意的值，在某些上下文中可以包含函数，则最终的表达式是广义连分数（Generalized continued fraction）。在需要把上述标准形式与广义连分数相区别的时候，可称它为简单或正规连分数，或称为是规范形式的。

1. 常见应用

连分数常用于无理数的逼近，例如：

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

由此得到 $\sqrt{2}$ 的渐近分数：

${\displaystyle {\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 }}}}}}}}}}}}$

由此得到黄金分割的渐近分数：

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

注意将上述系列的分母 $1,1,2,3,\cdots$ 等数依序排列均可得到斐波那契数列。

$\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}}\frac{103993}{33102}$ 、 $\cdots$

数学上可以证明，由（狭义）连分数得到的渐近分数，在分子或分母小于下一个渐进分数的分数中，其值是最接近精确值的近似值。

2. 研究动机

研究连分数的动机源于想要有实数在“数学上纯粹”的表示。

多数人熟悉实数的小数表示：

$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}}$ 、 $\cdots$ 。 ${\frac {314}{100}}$ 和 ${\frac {333}{106}}$ 的分母相当接近，但近似值 ${\frac {314}{100}}$ 的误差是远高于 ${\frac {333}{106}}$ 的 $19$ 倍。作为对 $\pi$ 的逼近， $[3; 7, 15, 1]$ 比 $3.1416$ 精确 $100$ 倍。

3. 连分数表示的算法

考虑实数 $r$ 。设 $i$ 是 $r$ 的整数部分，而 $f$ 是它的小数部分。则 $r$ 的连分数表示是 $[i;\ldots ]$ ，这里的“ $\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$ 的幂），所以欧几里得算法的变体可以用来给出精确的结果。

4. 连分数的表示法

可以把连分数简写作：

$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_{1}, a_{2}, a_{3}\cdots$ 的任意选择，皆存在此一极限。

或者可以用高斯的记法

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

5. 有限连分数

所有有限连分数都表示一个有理数，而所有有理数都可以按两种不同的方式表示为有限连分数。这两种表示除了最终项之外都是一致的。在较长的连分数表示，其最终项是 $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]\;$

6. 连分数的倒数

有理数的连分数表示和它的倒数除了依据这个数小于或大于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$ 和它的倒数是同样的的连分数的余数。

例如：

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

7. 无限连分数

所有无限连分数都是无理数，而所有无理数可用一种精确的方式表示为无限连分数。

无理数的无限连分数表示是非常有用的，因为它的初始段提供了对这个数的优异的有理数逼近。这些有理数可以叫做这个连分数的收敛（convergent，也译为“渐进”）。所有偶数编号的收敛都小于最初的数，而奇数编号的收敛都大于它。

对于连分数 $[a_{0};a_{1},a_{2},\ldots ]$ ，前四个收敛（编号 $0$ 到 $3$ 是

${\frac {a_{0}}{1}},\qquad {\frac {a_{1}a_{0}+1}{a_{1}}},\qquad {\frac {a_{2}(a_{1}a_{0}+1)+a_{0}}{a_{2}a_{1}+1}},\qquad {\frac {a_{3}[a_{2}(a_{1}a_{0}+1)+a_{0}]+(a_{1}a_{0}+1)}{a_{3}(a_{2}a_{1}+1)+a_{1}}}$

用普通语言来说，第 $3$ 个收敛的分子是借由第 $3$ 个商（ $a_2$ ）乘上第 $2$ 个收敛的分子，并加上第 $1$ 个收敛的分子而成。分母的形成也很类似。

如果找到连续的收敛，带有分子 $h_{1},h_{2},\ldots$ 和分母 $k_{1},k_{2},\ldots$ ，则相关的递归关系是：

$h_{n}=a_{n}h_{n-1}+h_{n-2},\qquad k_{n}=a_{n}k_{n-1}+k_{n-2}$

连续的收敛由如下公式给出

${\frac {h_{n}}{k_{n}}}={\frac {a_{n}h_{n-1}+h_{n-2}}{a_{n}k_{n-1}+k_{n-2}}}$

8. 一些有用的定理

如果 $a_{0},a_{1},a_{2},\ldots$ 是正整数的无限序列，递归的定义序列 $h_{n}$ 和 $k_{n}$ ：

$h_{n}=a_nh_{n-1}+h_{n-2}\,\quad h_{-1}=1\,\quad h_{-2}=0\\ k_{n}=a_nk_{n-1}+k_{n-2}\,\quad k_{-1}=0\,\quad k_{-2}=1$

定理 1

对于任何正数 $x\in \mathbb {R}$

$\left[a_{0};a_{1},\,\dots ,a_{n-1},x\right]={\frac {xh_{n-1}+h_{n-2}}{xk_{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}}{k_{n}}}$

给出。

定理 3

如果对连分数的第 $n$ 个收敛是 $h_{n}/k_{n}$ ，则

$k_nh_{n-1}-k_{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$ ，因此属于 $2\times2$ 幺模矩阵 $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：立即前导于一个大商的任何收敛都是对这个连分数的接近逼近。

9. 半收敛

如果 ${\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$ 。

10. 最佳有理数逼近

连分数理论在丢番图逼近领域起基础性的作用，可以解决实数的最佳逼近问题，具体可参阅相应主页面。事实上，最初发展连分数理论的动机正是为了解决实数的最佳逼近问题。

11. 连分数历史

公元前 300 年－欧几里得，《Elements》 - 最大公约数的算法生成一个连分数作为副产品。
499 年 Aryabhatiya 包含使用连分数的不确定方程的解。
1572 年－Rafael Bombelli,《L’Algebra Opera》 - 与连分数有关的提取平方根的方法。
1613 年－Pietro Cataldi,《Trattato del modo brevissimo di trovar la radice quadra delli numeri》 - 第一种连分数的记号
Cataldi 表示连分数为 $a_{0}.\, \& \frac{n_{1}}{d_{1}}。\&{n_{2} \over d_{2}}。\&{n_{3} \over d_{3}}$ 带有指示随后连分数要去的地方的点。
1695 年－约翰·沃利斯，《Opera Mathematica》 - 介入了术语“连分数”。
1737 年 Leonhard Euler, 《De fractionibus continuis dissertatio》 – 提供了第一个关于连分数属性的全面说明，并首次证明了数字 $e$ 是无理数。
1748年莱昂哈德·欧拉，《Introductio in analysin infinitorum》. Vol. I, Chapter 18 - 证明了特定形式的连分数和广义无穷级数的等价性。证明了每个有理数都可以写成有限连分数，并证明了无理数的连分数是无限的。
1768 年 Joseph-Louis Lagrange – 使用类似于 Bombelli 的连分数提供 Pell 方程的一般解。
1761 年 Johann Lambert – 使用 $\tan(x)$ 的连分数首次证明了 $\pi$ 的非理性。
1770 年 Lagrange ——证明了二次无理数扩展为周期性连分数。
1813 年－卡尔·弗里德里希·高斯，《Werke》,第三册, 134-138页 - 通过涉及到超几何级数的一个聪明的恒等式推导出非常一般性的复数值的连分数。
1892 年 Henri Padé 定义了 Padé 近似值
1972 年 Bill Gosper – 第一个用于连分数运算的精确算法。

参考文献

（前苏联）辛钦（A. Ya. Khinchin）著，刘诗俊、刘绍越译. 连分数. 上海: 上海科学技术出版社. 1965.

维基百科：连分数

wiki: Continued fraction

开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

MATLAB实现控制系统的时域分析

目的用 MATLAB 对控制系统进行时域分析，包括典型响应、判断系统稳定性和分析系统的动态特性。理论二、典型响应及其性能分析1、单位阶跃响应单位阶跃响应调用格式为：(1) step(num,den)(2) step(num,den,t)(3) step(G)(4) step(G,t)该函数将绘制出系统在单位阶跃输入条件下的动态响应图，同时给出稳态值。其中 t 为图像

开放原子开发者工作坊

【深度学习2】基于Pytorch的WGAN理论和代码解析

参考文章：令人拍案叫绝的Wasserstein GAN - 知乎 (zhihu.com)1 原始GAN存在问题实际训练中，GAN存在着训练困难、生成器和判别器的loss无法指示训练进程、生成样本缺乏多样性等问题。这与GAN的机制有关。GAN最终达到对抗的纳什均衡只是一个理想状态，而现实情况中得到的结果都是中间状态（伪平衡）。大部分的情况是，随着训练的次数越多判别器D的效果越好，会导致一直可以将生成

开放原子开发者工作坊

RocketMQ的顺序消费问题MessageListenerOrderly()

consumer.registerMessageListener(new MessageListenerOrderly() {@Overridepublic ConsumeOrderlyStatus consumeMessage(List<MessageExt> msgs, ConsumeOrderlyContext context) {for (MessageExt msg : ms