简单连分数与收敛分数

形式陈述

对实数 $x$ ，令 $x_0=x$ ，依次取

a_n=\lfloor x_n\rfloor, \qquad x_{n+1}=\frac1{x_n-a_n}.

若 $x_n=a_n$ ，则在取倒数之前停止。这里 $a_n$ 称为部分商， $x_n$ 称为完全商； $a_0$ 可以是任意整数，而后续完全商均大于 $1$ ，因而 $a_n\ge1$ （ $n\ge1$ ）。算法停止于 $m$ 时，得到有限简单连分数

x=[a_0;a_1,\ldots,a_m] =a_0+\cfrac1{a_1+\cfrac1{\ddots+\cfrac1{a_m}}}.

单项情形规定为 $[a_0]=a_0$ 。这个过程对有理数恰好有限终止；对无理数则无限继续。无限记号 $[a_0;a_1,a_2,\ldots]$ 的意义由下面的收敛定理确定，而不是先假定无限嵌套分式已经有值。

截取前 $n+1$ 个部分商所得的分数称为第 $n$ 个收敛分数，记作 $p_n/q_n$ 。它们可用整数递推计算：

\begin{aligned} p_{-2}&=0,&p_{-1}&=1,&p_n&=a_np_{n-1}+p_{n-2},\\ q_{-2}&=1,&q_{-1}&=0,&q_n&=a_nq_{n-1}+q_{n-2}. \end{aligned}

对算法已经产生的每个 $n\ge0$ ，有 $[a_0;\ldots,a_n]=p_n/q_n$ ，且 $q_n>0$ 、分数既约。若 $x$ 无理，则

\frac1{q_n(q_{n+1}+q_n)} <\left|x-\frac{p_n}{q_n}\right| <\frac1{q_nq_{n+1}} \le\frac1{q_n^2},

并且偶数索引的收敛分数小于 $x$ ，奇数索引的收敛分数大于 $x$ 。这些结论既给出收敛，也给出每次截断的误差证书。

直觉

把带余除法读成分式

十进制展开每次抽取一个固定精度的数位；简单连分数每次抽取当前值的整数部分，再把不足 $1$ 的余量倒过来。倒数把小余量放大，使下一次取整仍能取得信息。对有理输入，这正是整数欧几里得算法的另一种读法：

A=a_0B+r \quad\Longrightarrow\quad \frac AB=a_0+\frac rB =a_0+\frac1{B/r} \qquad(r>0).

设 $B>0$ ，带余除法保证 $0\le r<B$ ，即使 $A$ 为负也一样。下一步处理 $B/r$ ，随后处理下一对除数与余数。正余数严格下降，所以一定终止。反过来，有限个整数经过加法和取倒数仍得到有理数，因此终止的输入必为有理数。

两项递推为什么能保存全部前缀

计算收敛分数时，不必每次重新展开整串嵌套分式。保留一个可变的末项 $t$ ，归纳可得

[a_0;\ldots,a_{n-1},t] =\frac{t p_{n-1}+p_{n-2}}{t q_{n-1}+q_{n-2}}.

$n=0$ 时左边就是 $t$ ，右边由初值也等于 $t$ 。将末项 $t$ 换成 $a_n+1/u$ ，分子、分母同乘 $u$ ，新的系数正好是 $a_np_{n-1}+p_{n-2}$ 与 $a_nq_{n-1}+q_{n-2}$ ，这就完成归纳。取 $t=a_n$ ，便得到收敛分数的递推。那两项初值是让这一个公式从第零项起统一成立的记账方式。

递推还有一个不会随部分商大小改变的量。令

D_n=p_nq_{n-1}-p_{n-1}q_n.

直接代入递推，含 $a_n$ 的项相消，留下 $D_n=-D_{n-1}$ 。由于 $D_0=-1$ ，所以

p_nq_{n-1}-p_{n-1}q_n=(-1)^{n+1}.

$p_n,q_n$ 的任何公约数都整除左边，因此只能为 $1$ 。同一个恒等式还给出相邻收敛分数的距离：

\left|\frac{p_{n+1}}{q_{n+1}}-\frac{p_n}{q_n}\right| =\frac1{q_nq_{n+1}}.

保留真实尾项，证明逼近的是原来的数

现在令 $x$ 无理，算法就始终拥有下一个完全商 $x_{n+1}$ 。在前缀后保留这个真实尾项，而不是把它删掉，上一小节的恒等式给出

x=\frac{p_nx_{n+1}+p_{n-1}}{q_nx_{n+1}+q_{n-1}}.

与 $p_n/q_n$ 相减，利用 $D_n$ 的符号，得到精确误差：

x-\frac{p_n}{q_n} =\frac{(-1)^n}{q_n(q_nx_{n+1}+q_{n-1})}.

分母为正，所以误差符号完全由 $n$ 的奇偶性决定。又因为

a_{n+1}<x_{n+1}<a_{n+1}+1, \qquad q_{n+1}=a_{n+1}q_n+q_{n-1},

误差分母中括号内的量严格介于 $q_{n+1}$ 与 $q_{n+1}+q_n$ 之间；取倒数就得到形式陈述中的双侧误差界。

最后还需确认这个界真的趋于零。 $q_0=1$ 、 $q_1=a_1\ge1$ ，且对 $n\ge2$ 有 $q_n\ge q_{n-1}+q_{n-2}$ ，所以分母无界增长。于是 $1/q_n^2\to0$ ，按序列收敛的定义， $p_n/q_n\to x$ 。这个证明从原实数的有限次运算出发，避免了用“无限连分数等于 $x$ ”来证明它自己收敛的循环。

例子与边界

一条余数链给出一个有限连分数

欧几里得算法的熟悉例子是

252=2\cdot105+42,\qquad 105=2\cdot42+21,\qquad 42=2\cdot21.

将三次除法的商顺次读出，得到

\frac{252}{105}=[2;2,2] =2+\frac1{2+1/2} =\frac{12}{5}.

递推则依次产生 $2/1$ 、 $5/2$ 、 $12/5$ 。最后一项是精确值，已经没有尾项，所以不能把无理数的严格正误差下界套在这里。

有限表示需要一个规范约定：有多个部分商时，要求末项 $a_m\ge2$ 。若允许末项为 $1$ ，就有

[a_0;\ldots,a_m] =[a_0;\ldots,(a_m-1),1] \qquad(m\ge1,\ a_m\ge2).

例如 $[2;2,2]=[2;2,1,1]$ ；整数也有 $[k]=[k-1;1]$ 。规范表示的唯一性来自取整：末项至少为 $2$ 时，每个非初始尾部的值都严格大于 $1$ ，所以各层余量严格在 $0$ 与 $1$ 之间，当前整数部分必为该层的部分商。随后取倒数便唯一恢复下一层。末项为 $1$ 的表示将最后两项合并后也回到这一规范表示。

负数同样适用，但必须向下取整。例如 $-7/3$ 的首项是 $-3$ ，得到 $[-3;1,2]$ 。另外，分母并非从第一步起就严格增加：若 $a_1=1$ ，则 $q_0=q_1=1$ ；严格增加从 $q_2$ 开始。这不影响无限情形中分母趋于无穷的结论。

为平方根给出一个可核验的区间

因为 $1<\sqrt2<2$ ，首项为 $1$ 。取一次倒数得到

x_1=\frac1{\sqrt2-1}=1+\sqrt2, \qquad \frac1{x_1-2}=1+\sqrt2=x_1.

因此完全商从这里开始重复， $\sqrt2=[1;2,2,2,\ldots]$ 。用递推逐项计算：

索引 $n$	部分商 $a_n$	分子 $p_n$	分母 $q_n$	收敛分数的位置
$0$	$1$	$1$	$1$	下侧
$1$	$2$	$3$	$2$	上侧
$2$	$2$	$7$	$5$	下侧
$3$	$2$	$17$	$12$	上侧
$4$	$2$	$41$	$29$	下侧
$5$	$2$	$99$	$70$	上侧

前五个收敛分数的最后一个是 $41/29$ ；再算一步便得到一个上界。因此

\frac{41}{29}<\sqrt2<\frac{99}{70}.

这个结论也有不依赖小数计算的独立核验： $41^2=1681<2\cdot29^2=1682$ ，而 $99^2=9801>2\cdot70^2=9800$ ；所有量为正，平方比较保留大小关系。区间宽度恰为

\frac{99}{70}-\frac{41}{29} =\frac{99\cdot29-41\cdot70}{29\cdot70} =\frac1{2030}<\frac1{1000}.

所以 $41/29$ 是下侧逼近，且其绝对误差严格小于 $1/1000$ 。这里 $1/2030$ 是上下端点的距离，并不是 $41/29$ 的实际误差；实际误差由有理化精确写成

\sqrt2-\frac{41}{29} =\frac{2\cdot29^2-41^2}{29(29\sqrt2+41)} =\frac1{29(29\sqrt2+41)}.

推论与应用

简单连分数把“算出一个接近的分数”变成了“算出分数及其误差证书”。对无理输入，连续两个收敛分数分居两侧，将较小者记为 $L_n$ 、较大者记为 $U_n$ ，就有

L_n<x<U_n, \qquad U_n-L_n=\frac1{q_nq_{n+1}}.

给定容许误差 $\varepsilon>0$ ，只要继续计算到 $q_nq_{n+1}>1/\varepsilon$ ，两端点对 $x$ 的绝对误差便都小于 $\varepsilon$ 。判断何时停止只需整数乘法与比较；上面的平方根例子正是这个步骤的一次完整执行。

误差公式还解释了为什么有些收敛分数特别准确。下一部分商很大时， $q_{n+1}=a_{n+1}q_n+q_{n-1}$ 也大，因此已经得到的 $p_n/q_n$ 满足更强的上界 $1/(q_nq_{n+1})$ 。精度由后续部分商控制，而不只是由当前分母决定。

这些证书依赖于正确的部分商。对精确有理数，可以直接沿整数余数链计算；对 $\sqrt2$ 这样的代数数，本例用代数恒等式确定了全部后续部分商。若输入只是一个有限精度的小数，取整与倒数得到的是该近似输入的信息；要把结论用于原数，还需另外控制输入误差。这与收敛分数的数学误差界是两项不同的工作。

本条建立的是交错夹逼与误差控制。若进一步比较同一分母限制下的所有有理数，还必须明确比较的是 $|x-p/q|$ 还是 $|qx-p|$ ，并证明相应的最佳逼近定理；这里的误差界本身不承担这一结论。

参考资料

Nicolas Mascot, MAU23101, Chapter 6: Continued Fractions，2021 年 4 月 17 日版，PDF pp. 8–12（终止性）、pp. 14–19（收敛分数递推与既约性）、pp. 22–24（交错收敛）、pp. 29–30（误差界）。本文的误差公式直接由真实尾项推导。
Rutgers University, Math 574, Lecture 1，Spring 2004，§2，pp. 2–3：简单连分数、欧几里得算法以及有限表示的末项约定。

形式陈述 ​

把带余除法读成分式 ​

两项递推为什么能保存全部前缀 ​

保留真实尾项，证明逼近的是原来的数 ​

一条余数链给出一个有限连分数 ​

为平方根给出一个可核验的区间 ​

反向链接