连分数

连分数

连分数 是实数作为有理数的特定收敛序列的表示。它们在算法竞赛（competitive programming）中很有用，因为它们易于计算，并且可以有效地用于在分母不超过给定值的所有数字中，找到基础实数（underlying real number）的最佳可能有理近似（best possible rational approximation）。

除此之外，连分数与欧几里得算法密切相关，这使得它们在一系列数论问题中非常有用。

定义

连分数是一种记号。例如，长为 的连分数：

只是为了形式上简洁，才记成等号左边的样子。这里的四个变元可以任意取值。

连分数各变元的下标从 开始。

简单连分数

可以证明，任何有理数都可以精确地以两种方式表示为连分数：

此外，对于 ，这种连分数的长度 估计为 。

一旦深入研究了连分数构造的细节，这背后的原因就会很清楚。

定义

设 和 。然后表达式

称为有理数 的 连分数表示，并简短地表示为 。

示例

设 。有两种方法可以将其表示为连分数：

对于有限连分数，全体结尾为 的有限连分数和全体结尾不为 的有限连分数一一对应，即同一个连分数有两种表示：

简单连分数：连分数从第 项开始全都是正整数。如果有限，要求最后一项不为 。（第 项可以任意）

简单连分数的值，一定大于偶数的渐进分数，一定小于奇数的渐进分数。无限简单连分数一定收敛。

仿照一般分数的概念，第 项是 的连分数称为「真分数」。显然如果这之后的所有变元都大于等于 ，那么得到的真分数一定落在 到 之间。

无限连分数

如果分式无限地写下去，有无限个变元，就得到无限连分数。无限连分数收敛等价于渐进分数收敛。

有定理：

无限连分数，如果各变元均大于等于 ，那么一定收敛。

因为只要各变元为正，无限连分数的偶渐进分数单调递增（都比它小），奇渐进分数单调递减（都比它大）。而在均大于等于 时，相邻（奇偶间）两个渐进分数之间距离可以给出估计式，趋于 ，因此收敛。

显然可以看到，连分数关于下标为偶数的变元单调递增，关于下标为奇数的变元单调递减。这无论它有限或无限都成立。

定义

设 为整数序列，使得 。设 。然后表达式

称为无理数 的 连分数表示，并简短地表示为 。

注意，对于 和整数 ，有 。

另一个重要的观察结果是，当 时，；当 ＝ 时，。

渐进分数

定义

在上面的定义中，有理数 称为 的 渐进分数（convergents，意为「收敛」）。

相应地，单个 称为 的第 个渐进分数。

示例

考虑 。可以通过归纳法证明 ，其中 是斐波那契序列，定义为 、 和 。从 Binet 公式可知

其中 是黄金比率，。因此

请注意，在这种特定情况下，找到 的另一种方法是求解方程

定义

设 。对于 ， 称为 中间分数（semiconvergents，「semi」意为「半」）。

通常将大于 的分数称为 上（upper）渐进分数或中间分数，将小于 者称为 下（lower）渐进分数或中间分数。

余项和部分商

定义

作为渐进分数的补充，定义 余项（完全商，complete quotients）为 。

相应地，将单个 称为 的第 个完全商。

相应地，取整得到的 称为部分商。

对于各项均为正数的连分数，所有的余项也都是正数。

根据以上定义，可以得出 代表 的结论。

将 视为一个形式代数表达式，并允许任意实数代替 ，得到

特别地，。另一方面，可以将 表示为

这意味着可以从 计算 和 。

序列 定义良好，除非 ，这仅在 为有理数时发生。

因此，对于任何无理数 ，连分数表示都是唯一的。

求解简单连分数表示

在代码片段中主要假设有限的连分数。

如果要求 区间内某个数的简单连分数表示（第 项为 ），只需：

• 取倒数，得到的余项大于 。
• 取整得到整数部分为部分商，小数部分在 到 之间。
• 对小数部分重复上述操作。

这样就得到了相应的表示。

从 到 的转换如下

从这个表达式中，下一个完全商 如下

对于 ，这意味着

因此， 的连分数表示的计算遵循 和 的欧几里得算法的步骤。

由此， 的 。因此，渐进分数总是不可约的。

1
2
3
4
5
6
7
8

auto fraction(int p, int q) {
  vector<int> a;
  while (q) {
    a.push_back(p / q);
    tie(p, q) = make_pair(q, p % q);
  }
  return a;
}

1
2
3
4
5
6

def fraction(p, q):
    a = []
    while q:
        a.append(p // q)
        p, q = q, p % q
    return a

如果规定第 项是该数的取整，那么全体实数都有「唯一的简单连分数表示」。其中：

如果两个无限简单连分数的值相等，必然逐项相等。

如果两个有限简单连分数的值相等，不仅要逐项相等，而且必然项数也相同。

无限简单连分数不能与有限简单连分数值相等。有理数与有限简单连分数具有一一对应关系，因此无限简单连分数全都是无理数。

性质

为了给连分数的进一步研究提供一些动力，现在给出一些性质。

递推

递推

对于渐进分数 ，以下递推公式适用于它们的快速计算：

其中 并且 。

渐进分数分子和分母具有完全相同的递推关系：

这里和 Farey 数列的递推关系很像。

形式上记初项：

只是形式上成立。第 项渐进分数是 1/0，没有实际意义。

反序定理

如果 ：

如果 ：

证明

对递推关系稍加改造，有：

又利用初值，即可证明反序定理。

渐进分数的差分

计算相邻两项渐进分数的差，需要通分。通分后的分子代入递推关系：

代入初值就有渐进分数的差分：

根据递推式，如果连分数各项均为整数，则渐进分数分子分母总是互素。

对于有理数的简单连分数展开，常用渐进分数差分的等式，求解一次线性不定方程（参见 扩展欧几里得算法）：

因为 a 与 b 互素， 就是最简的有理数，也就是它本身的最后一个渐进分数。那么，它的前一个渐进分数就是所求的解。

倒数定理

由于实数与简单连分数一一对应，称实数的简单连分数的渐进分数，就是实数的渐进分数。于是就有倒数定理：

对于大于 1 的实数 x，x 的渐进分数的倒数恰好是 的渐进分数。显然，该定理也应该对于 0 到 1 之间的实数 x 成立。

证明

于是根据新的初值与递推就能发现倒数关系成立。

最佳逼近

因此允许通过检查 是否中间分数来找到其最佳有理逼近。

下面会对这些性质建立一些直觉并做出进一步解释。

连行列式

继续看前面定义的渐近分数。对于 ，其渐近分数为

渐近分数是连分数的核心概念，因此研究它们的性质很重要。

对于数字 ，其第 个渐近分数 可以计算为

其中 是连行列式（continuant），定义为

因此， 是 和 的加权中间值（mediant）。

为了一致性，定义了两个额外的渐近分数 和 。

详细说明

渐进分数 的分子和分母可以看作 的多元多项式：

根据渐进分数的定义，

由此得出 。这产生了关系

最初， 和 ，因此

为了保持一致性，可以方便地定义 和 ，并正式表示 和 。

从数值分析可知，任意三对角矩阵的行列式

可以递归地计算为 。将其与 进行比较，得到一个直接表达式

这个多项式也被称为连行列式（continuant），由于其与连分数的密切关系。如果主对角线上的顺序颠倒，则连行列式不会改变。这产生了一个计算公式：

实现

把渐进分数计算为一对序列 和 ：

1
2
3
4
5
6
7
8
9

auto convergents(vector<int> a) {
  vector<int> p = {0, 1};
  vector<int> q = {1, 0};
  for (auto it : a) {
    p.push_back(p[p.size() - 1] * it + p[p.size() - 2]);
    q.push_back(q[q.size() - 1] * it + q[q.size() - 2]);
  }
  return make_pair(p, q);
}

1
2
3
4
5
6
7

def convergents(a):
    p = [0, 1]
    q = [1, 0]
    for it in a:
        p.append(p[-1]*it + p[-2])
        q.append(q[-1]*it + q[-2])
    return p, q

误差和余项的估计

误差

渐进分数 与 的误差（deviation）通常可以估计为

将两边乘以 ，得到另一个估计：

从上面的循环可以看出， 的增长速度至少与斐波那契数一样快。

在下图中可以看到收敛 渐进分数 的可视化：

无理数 由蓝色虚线表示。奇数渐进分数从上面接近它，偶数渐进分数从下面接近它。

实数 x 也可以写成：

最后一项渐近分数就是 x 本身。于是根据渐进分数的递推式，就有：

于是可以估计渐进分数的误差：

分别对 k 取奇数偶数就得到，x 总小于其奇数阶渐近分数，大于其偶数阶渐近分数。

对于数字 及其第 个渐进分数 ，以下公式成立：

特别地，这意味着

并且

由此可以得出结论

后一种不等式是由于 和 通常位于 的不同侧面，因此