连分数 是将分式反复嵌入另一个分式的分母中所构成的表达式。其最常见的形式通过一列整数系数来表示一个实数 :
a 0 + 1 a 1 + 1 a 2 + 1 a 3 + ⋯ . a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cdots}}}. a 0 + a 1 + a 2 + a 3 + ⋯ 1 1 1 .
将这个表达式截断,便得到称为渐近分数 的有理数。相对于分母的大小,这些近似值的误差往往格外小,因此连分数成为数论 中的重要工具。
连分数将欧几里得算法 、有理近似、二次方程和动力系统联系起来。更一般的连分数允许分子与分母变化,可用于表示数学函数和进行数值计算。连分数理论的研究范围,从特定数的精确恒等式,一直延伸到描述几乎所有实数的连分数展开的统计规律。
简单连分数及其构造 简单连分数 ,也称正则连分数 ,具有如下形式:
[ a 0 ; a 1 , a 2 , … ] = a 0 + 1 a 1 + 1 a 2 + ⋯ , [a_0;a_1,a_2,\ldots] = a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cdots}}, [ a 0 ; a 1 , a 2 , … ] = a 0 + a 1 + a 2 + ⋯ 1 1 ,
其中,a 0 a_0 a 0 是整数 ,其后的每个系数 a n a_n a n 都是正整数。这些系数称为部分商 。分号将开头的整数部分与其余系数分隔开来。有限表达式 [ a 0 ; a 1 , … , a n ] [a_0;a_1,\ldots,a_n] [ a 0 ; a 1 , … , a n ] 表示一个有理数 ,而无限简单连分数表示一个无理数 。
实数 x x x 的连分数系数可通过反复取整数部分和取倒数求得。令 x 0 = x x_0=x x 0 = x ,并在 x n − a n ≠ 0 x_n-a_n\ne0 x n − a n = 0 时定义
a n = ⌊ x n ⌋ , x n + 1 = 1 x n − a n a_n=\lfloor x_n\rfloor,\qquad x_{n+1}=\frac{1}{x_n-a_n} a n = ⌊ x n ⌋ , x n + 1 = x n − a n 1
数 x n x_n x n 称为完全商 。若输入的是无理数,这一过程将无限继续;若输入的是有理数,过程则会终止,因为它等价于对该数的分子和分母应用欧几里得算法。例如,
415 93 = 4 + 43 93 , 93 43 = 2 + 7 43 , 43 7 = 6 + 1 7 , \frac{415}{93} =4+\frac{43}{93}, \qquad \frac{93}{43}=2+\frac7{43}, \qquad \frac{43}{7}=6+\frac17, 93 415 = 4 + 93 43 , 43 93 = 2 + 43 7 , 7 43 = 6 + 7 1 ,
因此
415 93 = [ 4 ; 2 , 6 , 7 ] . \frac{415}{93}=[4;2,6,7]. 93 415 = [ 4 ; 2 , 6 , 7 ] .
各个部分商恰好就是逐次相除所得的商。
每个无理实数都恰好有一种无限简单连分数展开。按照首项之后的所有系数均为正数的通常约定,有理数有两种有限展开:
[ a 0 ; … , a n ] = [ a 0 ; … , a n − 1 , 1 ] if a n ≥ 2. [a_0;\ldots,a_n] = [a_0;\ldots,a_n-1,1] \quad\text{if }a_n\ge2. [ a 0 ; … , a n ] = [ a 0 ; … , a n − 1 , 1 ] if a n ≥ 2.
除展开仅含一个整数的情形外,要求末项系数大于 1 1 1 ,就能选定一种规范表示。因此,3 / 2 = [ 1 ; 2 ] = [ 1 ; 1 , 1 ] 3/2=[1;2]=[1;1,1] 3/2 = [ 1 ; 2 ] = [ 1 ; 1 , 1 ] 。同样,整数 m m m 也有 [ m ] [m] [ m ] 和 [ m − 1 ; 1 ] [m-1;1] [ m − 1 ; 1 ] 两种表示。对于负数,构造过程仍采用向下取整,而非向零截断;例如,− 3 / 2 = [ − 2 ; 2 ] -3/2=[-2;2] − 3/2 = [ − 2 ; 2 ] 。
与位值制记数法 不同,连分数不使用固定的基数,其系数也不受某个固定的数位上限约束。它记录的是逐次取倒数的关系,而非十或二的逐次幂。因此,有些数具有极为简单的连分数展开,而这种简洁性从其十进制数字中并不容易看出:
2 = [ 1 ; 2 , 2 , 2 , … ] , 1 + 5 2 = [ 1 ; 1 , 1 , 1 , … ] . \sqrt2=[1;2,2,2,\ldots], \qquad \frac{1+\sqrt5}{2}=[1;1,1,1,\ldots]. 2 = [ 1 ; 2 , 2 , 2 , … ] , 2 1 + 5 = [ 1 ; 1 , 1 , 1 , … ] .
后一个数就是黄金比例 。不过,简单连分数通常并不能使加法和乘法变得容易:对两个以连分数表示的数进行一次简单的算术运算,可能需要掌握两个系数序列中的大量信息。
渐近分数、递推关系与收敛性 第 n n n 个渐近分数是将连分数截断后得到的有限连分数:
p n q n = [ a 0 ; a 1 , … , a n ] . \frac{p_n}{q_n}=[a_0;a_1,\ldots,a_n]. q n p n = [ a 0 ; a 1 , … , a n ] .
其分子和分母满足相同的递推关系 :
p n = a n p n − 1 + p n − 2 , q n = a n q n − 1 + q n − 2 , p_n=a_np_{n-1}+p_{n-2}, \qquad q_n=a_nq_{n-1}+q_{n-2}, p n = a n p n − 1 + p n − 2 , q n = a n q n − 1 + q n − 2 ,
初始值为
p − 2 = 0 , p − 1 = 1 , q − 2 = 1 , q − 1 = 0. p_{-2}=0,\quad p_{-1}=1,\qquad q_{-2}=1,\quad q_{-1}=0. p − 2 = 0 , p − 1 = 1 , q − 2 = 1 , q − 1 = 0.
利用这些公式,可以用整数运算代替对嵌套分式的反复求值。对于 2 \sqrt2 2 ,由此得到
1 , 3 2 , 7 5 , 17 12 , 41 29 , … . 1,\quad \frac32,\quad \frac75,\quad \frac{17}{12},\quad \frac{41}{29},\ldots. 1 , 2 3 , 5 7 , 12 17 , 29 41 , … .
分母的增长速度至少与下标平移后的斐波那契数列 一样快,因为对于 n ≥ 1 n\ge1 n ≥ 1 ,每个 a n a_n a n 都至少为 1 1 1 。
一种有用的表示方式是使用矩阵 :
( a 0 1 1 0 ) ( a 1 1 1 0 ) ⋯ ( a n 1 1 0 ) = ( p n p n − 1 q n q n − 1 ) . \begin{pmatrix}a_0&1\\1&0\end{pmatrix} \begin{pmatrix}a_1&1\\1&0\end{pmatrix} \cdots \begin{pmatrix}a_n&1\\1&0\end{pmatrix} = \begin{pmatrix} p_n&p_{n-1}\\ q_n&q_{n-1} \end{pmatrix}. ( a 0 1 1 0 ) ( a 1 1 1 0 ) ⋯ ( a n 1 1 0 ) = ( p n q n p n − 1 q n − 1 ) .
取两边的行列式 ,得到
p n q n − 1 − p n − 1 q n = ( − 1 ) n − 1 . p_nq_{n-1}-p_{n-1}q_n=(-1)^{n-1}. p n q n − 1 − p n − 1 q n = ( − 1 ) n − 1 .
因此,每个渐近分数都是最简分数,且相邻两个渐近分数之差恰为
p n q n − p n − 1 q n − 1 = ( − 1 ) n − 1 q n q n − 1 . \frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}} = \frac{(-1)^{n-1}}{q_nq_{n-1}}. q n p n − q n − 1 p n − 1 = q n q n − 1 ( − 1 ) n − 1 .
行列式的绝对值很小,这同时解释了分子与分母的互素性、近似值的交替性,以及相邻近似值之间的紧密间距。
对于无限简单连分数,令
α n + 1 = [ a n + 1 ; a n + 2 , … ] . \alpha_{n+1}=[a_{n+1};a_{n+2},\ldots]. α n + 1 = [ a n + 1 ; a n + 2 , … ] .
此时,可以由渐近分数及剩余的尾部重构原数:
x = p n α n + 1 + p n − 1 q n α n + 1 + q n − 1 . x=\frac{p_n\alpha_{n+1}+p_{n-1}} {q_n\alpha_{n+1}+q_{n-1}}. x = q n α n + 1 + q n − 1 p n α n + 1 + p n − 1 .
减去 p n / q n p_n/q_n p n / q n ,便得到精确的误差公式:
x − p n q n = ( − 1 ) n q n ( q n α n + 1 + q n − 1 ) . x-\frac{p_n}{q_n} = \frac{(-1)^n} {q_n(q_n\alpha_{n+1}+q_{n-1})}. x − q n p n = q n ( q n α n + 1 + q n − 1 ) ( − 1 ) n .
因此,偶数下标的渐近分数小于 x x x ,奇数下标的渐近分数则大于 x x x 。偶数下标子序列递增,奇数下标子序列递减。两者共同给出一系列相互嵌套的上下界区间,区间宽度趋于零,从而确立了收敛性。
由于
a n + 1 < α n + 1 < a n + 1 + 1 , a_{n+1}<\alpha_{n+1}<a_{n+1}+1, a n + 1 < α n + 1 < a n + 1 + 1 ,
误差满足
1 q n ( q n + 1 + q n ) < ∣ x − p n q n ∣ < 1 q n q n + 1 . \frac{1}{q_n(q_{n+1}+q_n)} < \left|x-\frac{p_n}{q_n}\right| < \frac{1}{q_nq_{n+1}}. q n ( q n + 1 + q n ) 1 < x − q n p n < q n q n + 1 1 .
一个特别有用的推论是
∣ x − p n q n ∣ < 1 a n + 1 q n 2 . \left|x-\frac{p_n}{q_n}\right| < \frac{1}{a_{n+1}q_n^2}. x − q n p n < a n + 1 q n 2 1 .
因此,下一个部分商很大,就意味着当前渐近分数的精度特别高。这一关系比仅仅计算保留了多少个系数更能说明问题:近似的精度在很大程度上取决于下一个系数。
有理逼近与最优性 丢番图逼近 研究在控制分母大小的条件下,有理数能够以多高的精度逼近实数。连分数为一维情形提供了明确的答案。其自然的误差尺度为 q − 2 q^{-2} q − 2 :分母较大的有理数 p / q p/q p / q 往往能使逼近误差达到与 1 / q 2 1/q^2 1/ q 2 成正比的量级,而连分数的渐近分数能够系统地找出这样的逼近。
关于最优性的一个精确表述采用了量 ∣ q x − p ∣ |qx-p| ∣ q x − p ∣ ,这种衡量方式有时称为第二类逼近。若 p n / q n p_n/q_n p n / q n 是无理数 x x x 的一个渐近分数,则对于满足 0 < q < q n + 1 0<q<q_{n+1} 0 < q < q n + 1 的整数 p , q p,q p , q ,有
∣ q x − p ∣ ≥ ∣ q n x − p n ∣ , |qx-p|\ge |q_nx-p_n|, ∣ q x − p ∣ ≥ ∣ q n x − p n ∣ ,
且仅当整数对为 ( p n , q n ) (p_n,q_n) ( p n , q n ) 时等号成立。因此,在分母达到下一个渐近分数的分母之前,当前渐近分数使这一缩放后的误差最小。这与使通常的距离 ∣ x − p / q ∣ |x-p/q| ∣ x − p / q ∣ 最小并不相同;区分这两种概念,可以避免对“最佳逼近”作出过于宽泛的理解。
中间渐近分数 ,也称半渐近分数,填补了相邻渐近分数之间的部分空隙。它们的形式为
r p n + p n − 1 r q n + q n − 1 , 1 ≤ r ≤ a n + 1 . \frac{rp_n+p_{n-1}}{rq_n+q_{n-1}}, \qquad 1\le r\le a_{n+1}. r q n + q n − 1 r p n + p n − 1 , 1 ≤ r ≤ a n + 1 .
当 r = a n + 1 r=a_{n+1} r = a n + 1 时,这就成为下一个渐近分数。如果目标是在 q q q 不超过给定上界的条件下使 ∣ x − p / q ∣ |x-p/q| ∣ x − p / q ∣ 最小,就还必须考虑中间渐近分数。它们在选择齿轮传动比、将十进制测量值转换为分母较小的分数,或用大小受限的整数之比逼近频率比等实际任务中十分重要。
若干经典定理对这种逼近的精度作出了定量描述。勒让德判据指出,若一个既约分数满足
∣ x − p q ∣ < 1 2 q 2 , \left|x-\frac pq\right|<\frac{1}{2q^2}, x − q p < 2 q 2 1 ,
则它必定是 x x x 的一个渐近分数。赫尔维茨定理指出,对于每个无理数 x x x ,都存在无穷多个有理逼近满足
∣ x − p q ∣ < 1 5 q 2 . \left|x-\frac pq\right|<\frac{1}{\sqrt5\,q^2}. x − q p < 5 q 2 1 .
常数 1 / 5 1/\sqrt5 1/ 5 不能替换为更小的通用常数。黄金分割数的部分商全为 1 1 1 ,它正是阻止这一常数进一步减小的极端情形。其渐近分数是相邻斐波那契数的比值。
对于圆周率 π \pi π ,其连分数展开的开头为
π = [ 3 ; 7 , 15 , 1 , 292 , … ] . \pi=[3;7,15,1,292,\ldots]. π = [ 3 ; 7 , 15 , 1 , 292 , … ] .
它最初的几个渐近分数包括 22 / 7 22/7 22/7 、333 / 106 333/106 333/106 和 355 / 113 355/113 355/113 。系数 292 292 292 解释了为什么 355 / 113 355/113 355/113 格外精确:
∣ π − 355 113 ∣ ≈ 2.67 × 10 − 7 . \left|\pi-\frac{355}{113}\right| \approx2.67\times10^{-7}. π − 113 355 ≈ 2.67 × 1 0 − 7 .
更一般地,如果存在常数 c > 0 c>0 c > 0 ,使得对每个有理数 p / q p/q p / q 都有 ∣ x − p / q ∣ > c / q 2 |x-p/q|>c/q^2 ∣ x − p / q ∣ > c / q 2 ,则称无理数 x x x 为难逼近数 。这一性质等价于其部分商有界。因此,连分数将一种一致逼近性质转化成了整数序列上的简单条件。
周期性、二次无理数与佩尔方程 二次无理数 是整系数二次方程的实无理根。拉格朗日定理给出了这类数的完整刻画:无限简单连分数最终具有周期性,当且仅当其值为二次无理数。周期部分用上划线表示,例如
2 = [ 1 ; 2 ‾ ] , 23 = [ 4 ; 1 , 3 , 1 , 8 ‾ ] . \sqrt2=[1;\overline2], \qquad \sqrt{23}=[4;\overline{1,3,1,8}]. 2 = [ 1 ; 2 ] , 23 = [ 4 ; 1 , 3 , 1 , 8 ] .
“最终具有周期性”允许在循环节开始之前有一段有限的初始项。
其中一个方向可以直接由循环尾部的代数关系推出。若
y = [ b 0 , b 1 , … , b ℓ − 1 ‾ ] , y=[\overline{b_0,b_1,\ldots,b_{\ell-1}}], y = [ b 0 , b 1 , … , b ℓ − 1 ] ,
则展开一个完整周期后,可将 y y y 表示为
y = A y + B C y + D y=\frac{Ay+B}{Cy+D} y = C y + D A y + B
其中 A , B , C , D A,B,C,D A , B , C , D 均为整数。整理后便得到一个二次方程。反方向的证明则更为精细:对二次无理数应用连分数算法,所生成的完全商的代数参数最终会落入一个有限集合。因此,一旦某个完全商重复出现,其后的所有系数也必然随之重复。还有一个更精确的结果刻画了纯周期展开:实二次无理数 α > 1 \alpha>1 α > 1 的连分数展开为纯周期,当且仅当其代数共轭数介于 − 1 -1 − 1 与 0 0 0 之间。
对于非完全平方的正整数 D D D ,D \sqrt D D 的展开可以完全通过整数运算求出。从
m 0 = 0 , d 0 = 1 , a 0 = ⌊ D ⌋ , m_0=0,\quad d_0=1,\quad a_0=\lfloor\sqrt D\rfloor, m 0 = 0 , d 0 = 1 , a 0 = ⌊ D ⌋ ,
开始,使用递推式
m n + 1 = d n a n − m n , m_{n+1}=d_na_n-m_n, m n + 1 = d n a n − m n ,
d n + 1 = D − m n + 1 2 d n , a n + 1 = ⌊ a 0 + m n + 1 d n + 1 ⌋ . d_{n+1}=\frac{D-m_{n+1}^2}{d_n}, \qquad a_{n+1}= \left\lfloor\frac{a_0+m_{n+1}}{d_{n+1}}\right\rfloor. d n + 1 = d n D − m n + 1 2 , a n + 1 = ⌊ d n + 1 a 0 + m n + 1 ⌋ .
循环节以 2 a 0 2a_0 2 a 0 结尾;循环节中此前的部分构成回文序列。这种特殊结构使平方根的连分数展开在整数问题中尤为有效。
最主要的例子是佩尔方程
u 2 − D v 2 = 1. u^2-Dv^2=1. u 2 − D v 2 = 1.
设 ℓ \ell ℓ 为 D \sqrt D D 的周期长度,其渐近分数从 p 0 / q 0 p_0/q_0 p 0 / q 0 开始编号。若 ℓ \ell ℓ 为偶数,最小的非平凡正整数解为
( u , v ) = ( p ℓ − 1 , q ℓ − 1 ) ; (u,v)=(p_{\ell-1},q_{\ell-1}); ( u , v ) = ( p ℓ − 1 , q ℓ − 1 ) ;
若 ℓ \ell ℓ 为奇数,则为
( u , v ) = ( p 2 ℓ − 1 , q 2 ℓ − 1 ) . (u,v)=(p_{2\ell-1},q_{2\ell-1}). ( u , v ) = ( p 2 ℓ − 1 , q 2 ℓ − 1 ) .
方程 u 2 − D v 2 = − 1 u^2-Dv^2=-1 u 2 − D v 2 = − 1 有整数解,当且仅当 ℓ \ell ℓ 为奇数。当 D = 2 D=2 D = 2 时,周期长度为 1 1 1 :1 2 − 2 ⋅ 1 2 = − 1 1^2-2\cdot1^2=-1 1 2 − 2 ⋅ 1 2 = − 1 ,而下一个渐近分数则给出 3 2 − 2 ⋅ 2 2 = 1 3^2-2\cdot2^2=1 3 2 − 2 ⋅ 2 2 = 1 。
最小解可能大得出人意料。当 D = 61 D=61 D = 61 时,最小解为
u = 1766319049 , v = 226153980. u=1766319049,\qquad v=226153980. u = 1766319049 , v = 226153980.
一旦求得基本解,就可以通过 u + v D u+v\sqrt D u + v D 的幂得到更多正整数解。因此,这一递推过程与二次数域中的乘法密切相关。有限的周期展开使我们能够求出无穷多个整数解,而其中最小的解就可能已经远远超出直接搜索所能企及的范围。
广义连分数与函数论 广义连分数 允许部分分子和部分分母任意取值:
b 0 + a 1 b 1 + a 2 b 2 + a 3 b 3 + ⋯ . b_0+\cfrac{a_1}{b_1+\cfrac{a_2}{b_2+\cfrac{a_3}{b_3+\cdots}}}. b 0 + b 1 + b 2 + b 3 + ⋯ a 3 a 2 a 1 .
其中的系数可以是实数、复数,也可以是某个变量的函数。简单连分数是其中的特例,其每个部分分子都等于 1 1 1 ,部分分母则满足相应的整数限制。这一更广泛的类别在数学分析 中十分重要,因为许多函数即使其简单连分数没有易于掌握的规律,也仍有实用的连分数表示。
广义连分数的渐近分数 A n / B n A_n/B_n A n / B n 满足
A n = b n A n − 1 + a n A n − 2 , B n = b n B n − 1 + a n B n − 2 , A_n=b_nA_{n-1}+a_nA_{n-2}, \qquad B_n=b_nB_{n-1}+a_nB_{n-2}, A n = b n A n − 1 + a n A n − 2 , B n = b n B n − 1 + a n B n − 2 ,
初始条件为
A − 1 = 1 , A 0 = b 0 , B − 1 = 0 , B 0 = 1. A_{-1}=1,\quad A_0=b_0,\qquad B_{-1}=0,\quad B_0=1. A − 1 = 1 , A 0 = b 0 , B − 1 = 0 , B 0 = 1.
相应的行列式恒等式变为
A n B n − 1 − A n − 1 B n = ( − 1 ) n − 1 ∏ k = 1 n a k . A_nB_{n-1}-A_{n-1}B_n = (-1)^{n-1}\prod_{k=1}^{n}a_k. A n B n − 1 − A n − 1 B n = ( − 1 ) n − 1 k = 1 ∏ n a k .
然而,与正项简单连分数的情形不同,广义连分数并不必然收敛。符号、复数的相位、分母为零以及系数的增长都可能影响收敛性。沃尔皮茨基定理给出了一个实用的充分条件:对于标准化连分数
a 1 1 + a 2 1 + ⋯ \cfrac{a_1}{1+\cfrac{a_2}{1+\cdots}} 1 + 1 + ⋯ a 2 a 1
若对所有 n ≥ 1 n\ge1 n ≥ 1 都有 ∣ a n ∣ ≤ 1 / 4 |a_n|\le1/4 ∣ a n ∣ ≤ 1/4 ,则该连分数收敛,且其值位于以原点为圆心、半径为 1 / 2 1/2 1/2 的圆盘内。
函数论中的一个重要例子是兰伯特连分数:
tan z = z 1 − z 2 3 − z 2 5 − z 2 7 − ⋯ , \tan z= \cfrac{z}{1-\cfrac{z^2}{3-\cfrac{z^2}{5-\cfrac{z^2}{7-\cdots}}}}, tan z = 1 − 3 − 5 − 7 − ⋯ z 2 z 2 z 2 z ,
这一表达式可在其收敛域内理解,也可通过相应的亚纯函数恒等式来理解。一个相关的展开式是
arctan z = z 1 + 1 2 z 2 3 + 2 2 z 2 5 + 3 2 z 2 7 + ⋯ , \arctan z= \cfrac{z}{1+\cfrac{1^2z^2}{3+\cfrac{2^2z^2}{5+\cfrac{3^2z^2}{7+\cdots}}}}, arctan z = 1 + 3 + 5 + 7 + ⋯ 3 2 z 2 2 2 z 2 1 2 z 2 z ,
例如,当 z z z 为实数且 ∣ z ∣ ≤ 1 |z|\le1 ∣ z ∣ ≤ 1 时,该式成立。在 z = 1 z=1 z = 1 处,后一个连分数表示 π / 4 \pi/4 π /4 。这类表达式不仅用于逼近某个固定的数值常数,还蕴含着一整族有理逼近式。
连分数也为帕德逼近 提供了一种系统的组织方式。帕德逼近选取两个多项式 之比,使其尽可能多地匹配某个幂级数 的系数。适当选取连分数,其渐近分数便可给出特定的帕德逼近序列。有理逼近式能够直接刻画极点,而截断多项式则不能;因此,在展开点的一个小邻域之外,有理逼近的效果可能更好,但其收敛性仍需单独分析。
另一个重要联系是与正交多项式 的联系。正交多项式的三项递推关系可以导出相关积分变换的连分数表示。对于适当的正测度 μ \mu μ ,变换
F ( z ) = ∫ R d μ ( t ) z − t F(z)=\int_{\mathbb R}\frac{d\mu(t)}{z-t} F ( z ) = ∫ R z − t d μ ( t )
具有连分数结构,其结构由该测度所对应的正交多项式的递推系数决定。这一关系将连分数与矩问题、数值求积以及三对角算子的谱定理 联系起来。在这些应用中,连分数所记录的不只是一个数值,还包括测度或算子的结构信息。
统计规律与高斯映射 尽管某些数的连分数展开具有高度规整的结构,典型连分数的性质却由概率规律来描述。在 ( 0 , 1 ) (0,1) ( 0 , 1 ) 内的无理数点上,定义高斯映射
T ( x ) = 1 x − ⌊ 1 x ⌋ . T(x)=\frac1x-\left\lfloor\frac1x\right\rfloor. T ( x ) = x 1 − ⌊ x 1 ⌋ .
若 x = [ 0 ; a 1 , a 2 , … ] x=[0;a_1,a_2,\ldots] x = [ 0 ; a 1 , a 2 , … ] ,则
T ( x ) = [ 0 ; a 2 , a 3 , … ] . T(x)=[0;a_2,a_3,\ldots]. T ( x ) = [ 0 ; a 2 , a 3 , … ] .
每迭代一次,就去掉一个开头的系数。因此,可以将连分数算法作为区间上的动力系统 来研究,其中的部分商则是对其轨道的符号化观测。
高斯映射保持如下概率 测度不变:
d μ ( x ) = d x log 2 ( 1 + x ) . d\mu(x)=\frac{dx}{\log2\,(1+x)}. d μ ( x ) = log 2 ( 1 + x ) d x .
这里的保持不变,是指一个集合与它在 T T T 下的原像具有相同的测度。该系统具有遍历性:不变可测集的测度不是零就是一。因此,沿几乎每条轨道的长期出现频率,都等于由这一测度算出的概率。这里的“几乎每条”是指除去一个勒贝格测度 为零的集合。由于高斯测度与勒贝格测度在 ( 0 , 1 ) (0,1) ( 0 , 1 ) 上具有相同的零测集,无论使用哪一种测度,对例外集合的理解都是一致的。
对于几乎每个初始点,部分商 k k k 出现的极限频率为
μ ( a 1 = k ) = log 2 ( ( k + 1 ) 2 k ( k + 2 ) ) . \mu(a_1=k) = \log_2\left(\frac{(k+1)^2}{k(k+2)}\right). μ ( a 1 = k ) = log 2 ( k ( k + 2 ) ( k + 1 ) 2 ) .
因此,1 1 1 出现的频率为
log 2 ( 4 / 3 ) ≈ 0.4150. \log_2(4/3)\approx0.4150. log 2 ( 4/3 ) ≈ 0.4150.
部分商的分布具有重尾:
μ ( a 1 ≥ k ) = log 2 ( 1 + 1 k ) . \mu(a_1\ge k)=\log_2\left(1+\frac1k\right). μ ( a 1 ≥ k ) = log 2 ( 1 + k 1 ) .
在这一分布下,部分商的均值为无穷大。相继出现的系数在统计上并不独立,因此,关于它们的统计理论不能简单地归结为从这一分布中反复独立抽样的理论。
尽管算术平均值为无穷大,几何平均值却有一个普适的有限极限。辛钦定理指出,对于几乎每个实数,
lim n → ∞ ( a 1 a 2 ⋯ a n ) 1 / n = K , K ≈ 2.685452001. \lim_{n\to\infty}(a_1a_2\cdots a_n)^{1/n} = K, \qquad K\approx2.685452001. n → ∞ lim ( a 1 a 2 ⋯ a n ) 1/ n = K , K ≈ 2.685452001.
其中的 K K K 称为辛钦常数 。另一个几乎处处成立的定理描述了分母的增长:
lim n → ∞ log q n n = π 2 12 log 2 . \lim_{n\to\infty}\frac{\log q_n}{n} = \frac{\pi^2}{12\log2}. n → ∞ lim n log q n = 12 log 2 π 2 .
等价地,q n 1 / n q_n^{1/n} q n 1/ n 趋于约 3.275822918 3.275822918 3.275822918 ,这个值通常称为莱维常数 。
这些结论并不自动适用于某个具体的知名常数。例如,二次无理数的系数序列是周期性的,不一定具有上述典型极限。对于一些熟知的数,其系数仍有重要问题悬而未决:人们尚不知道 π \pi π 的部分商是否有界。更一般地,人们既不知道是否存在次数大于二、部分商有界的实代数无理数,也不知道是否存在这类数的部分商无界的例子。几乎处处成立的强有力规律,与针对具体代数数所得结果的局限性之间的反差,是这一领域的一个核心特征。
几何、法里分数与模变换 渐近分数的行列式恒等式有一种几何解释。将 ( p n , q n ) (p_n,q_n) ( p n , q n ) 和 ( p n − 1 , q n − 1 ) (p_{n-1},q_{n-1}) ( p n − 1 , q n − 1 ) 看作整数格 Z 2 \mathbb Z^2 Z 2 中的向量。它们的行列式为 1 1 1 或 − 1 -1 − 1 ,因此构成该格的一组整数基。它们张成的平行四边形面积为 1 1 1 。同时,量
衡量了相对于直线 p = x q p=xq p = x q 的带符号偏移。连分数选取能够高效逼近这条直线的格向量,同时使相邻两次选取的向量所张成的格面积保持为最小的非零值。
法里数列 中也存在一种相关结构。法里数列是将 0 0 0 到 1 1 1 之间、分母不超过某个指定上限的既约分数按递增顺序排列而成的数列。如果 a / b < c / d a/b<c/d a / b < c / d 是该数列中的两个相邻分数,则
它们的中介分数
a + c b + d , \frac{a+c}{b+d}, b + d a + c ,
严格位于两者之间。当两个既约分数满足这一行列式关系时,严格位于两者之间的任何分数,其分母都至少为 b + d b+d b + d 。这就解释了为什么随着分母上限增大,中介分数会给出下一批可出现的分数。
从边界分数 0 / 1 0/1 0/1 和 1 / 0 1/0 1/0 开始,反复插入中介分数,就得到斯特恩–布罗科特树 。每个正有理数都恰好作为一个内部节点出现一次。搜索一个正实数时,根据当前中介分数大于还是小于目标值,向左或向右前进。若目标是无理数,搜索路径便是无限的。沿同一方向连续前进的各段长度编码了连分数的部分商;具体采用哪种路径约定,会使最初一段的长度需要略作调整。这样,可能包含许多次单独中介分数操作的一系列步骤,就被压缩成了一个整数系数。
连分数也源于分式线性变换:
x ⟼ a x + b c x + d , a d − b c = ± 1. x\longmapsto\frac{ax+b}{cx+d}, \qquad ad-bc=\pm1. x ⟼ c x + d a x + b , a d − b c = ± 1.
这些变换作用于扩充实数轴,并将有理点映为有理点。连分数构造中的基本操作——整数平移和取倒数——都属于这类变换。将仅相差一个符号的矩阵视为相同后,行列式为一的变换构成模群 。模群在上半平面上的作用将连分数与非欧几何 联系起来;在这里,有理数表现为法里镶嵌的边界点。
由此可得到一个算术结论,即尾部等价定理:两个无理实数可以通过一个行列式为 1 1 1 或 − 1 -1 − 1 的整系数分式线性变换相互变换,当且仅当它们的简单连分数展开最终具有完全相同的尾部。因此,对开头有限个系数的修改,对应于一种代数群作用。这在符号化的系数序列、格几何与二次无理数的分类之间架起了一座桥梁。
计算与实际应用 对于精确的有理数输入,提取连分数系数的过程就是欧几里得算法的一种应用,使用的是精确整数运算。如果分子和分母的二进制位数都不超过 N N N ,则除法次数为 O ( N ) O(N) O ( N ) ;相邻的斐波那契数构成了步数最多的经典最坏情形。这里统计的是除法次数,而不是单个位运算的次数。实际计算成本还取决于整数的大小以及所用的除法算法,快速变体则可以利用加速的最大公约数算法。
对于以数值形式给出的实数输入,系数提取需要更加谨慎。当当前的小数部分很小时,取倒数会放大不确定性。因此,输入的微小变化可能导致后面的某个部分商发生剧烈变化。任何有限精度的十进制观测值,都无法确定其背后的精确数究竟是有理数还是无理数。可靠的实现可以采用区间算术:只有在当前区间内所有数的整数部分都相同时,才能确认相应的系数。如果区间跨过整数边界,就需要提高精度。
这种敏感性与浮点运算 尤为相关。每一个有限的二进制浮点值本身都是有理数,因此它的精确连分数展开必定终止。但这一展开未必会一直与该浮点值所近似的理想实数的展开相似。因此,有理数重构需要明确的误差模型或分母上限。给定分母上限 Q Q Q ,可以利用收敛分数和适当的中间收敛分数,找出与近似值相符的小分数。所得结果是一个分母有界的近似,并不能证明某个测量值或舍入值恰好等于该分数。
广义连分数需要额外关注数值稳定性 。直接按递推式求值时,即使分子与分母之比大小适中,两者本身也可能变得非常大。在保持比值不变的前提下同时缩放分子和分母,可以控制溢出,但这本身并不能解决所有病态性问题。反向求值从一个假定的尾部值出发,逐步向开头计算;当尾部的影响逐渐衰减时,这种方法可能很有效。改进的 Lentz 类算法则通过更新收敛分数的乘法修正因子来求值,并采取措施,避免中间量接近零所引发的问题。这类算法广泛用于特殊函数的连分数表示,包括不完全伽马函数和不完全贝塔函数的某些公式。
其他应用还包括整数方程的精确求解、工程比值的有理逼近,以及从精度足够高的数值数据中恢复隐藏的有理数值。在基于量子力学 的量子计算中,Shor 阶查找算法的经典后处理阶段会使用连分数,从测得的相位估计值中恢复一个与未知周期相关的分数。在密码分析中,针对某些 RSA 密钥的 Wiener 攻击利用一个公开比值的连分数展开,找出异常小的秘密指数的候选值。这两种应用都依赖于相应的逼近定理:当某个有理数与估计值足够接近时,该有理数必定出现在收敛分数中;同时,它们还需要满足各自问题的附加条件,并对结果进行验证。
历史发展 连分数的思想源自多种传统,并非某一次单独的发明。约公元前300年成书的《几何原本》 记载了欧几里得算法,其中已包含有限连分数展开所依据的逐次求商过程。与之对应的几何过程,即对量反复作减法或比较,通常称为辗转相减法(anthyphairesis)。这些古代方法应与发展得晚得多的现代记号及无限连分数的一般理论加以区分。
印度数学发展出了求解整系数方程的强大方法,与连分数技巧密切相关。婆罗摩笈多在七世纪关于二次方程的研究,以及后来由婆什迦罗第二于十二世纪详细阐述的轮转法(chakravala),都能求出如今称为佩尔方程的方程的解。这些方法并非仅仅换了一套记号的现代简单连分数;不过,它们处理的是相同的算术结构,有时还能求出数值大得惊人的解。
在近代早期的欧洲,拉斐尔·邦贝利于1572年出版的《代数学》(L’Algebra)收录了与平方根的连分数近似有关的方法。彼得罗·卡塔尔迪于1613年出版的《求数的平方根的极简方法论》(Trattato del modo brevissimo di trovare la radice quadra delli numeri)明确讨论了平方根的连分数。十七世纪,威廉·布朗克尔发现了著名的广义连分数
4 π = 1 + 1 2 2 + 3 2 2 + 5 2 2 + ⋯ . \frac4\pi = 1+\cfrac{1^2}{2+\cfrac{3^2}{2+\cfrac{5^2}{2+\cdots}}}. π 4 = 1 + 2 + 2 + 2 + ⋯ 5 2 3 2 1 2 .
约翰·沃利斯于1656年在《无穷算术》(Arithmetica Infinitorum)中发表了这一结果。它与沃利斯乘积之间的联系,帮助人们认识到,连分数不仅可用于初等算术算法,也能表示分析学中的常数。
十八世纪,莱昂哈德·欧拉 极大地拓展了这一领域,推导出多种变换,建立了连分数与级数之间的联系,并找到了重要常数具有规律的展开式。他在1737年的研究证明了自然常数e e e e 的无理性;其简单连分数为
e = [ 2 ; 1 , 2 , 1 , 1 , 4 , 1 , 1 , 6 , 1 , … ] . e=[2;1,2,1,1,4,1,1,6,1,\ldots]. e = [ 2 ; 1 , 2 , 1 , 1 , 4 , 1 , 1 , 6 , 1 , … ] .
约翰·海因里希·兰伯特在1760年代利用连分数论证,证明了有关正切值无理性的结果,并由此证明了 π \pi π 的无理性。约瑟夫-路易·拉格朗日于1770年确立了二次无理数的周期性定理,为周期简单连分数展开给出了完整的代数刻画。
十九至二十世纪,连分数逐渐分化为几个紧密联系的研究方向。卡尔·弗里德里希·高斯 研究了与连分数变换相关的统计分布。托马斯·约安内斯·斯蒂尔切斯在1890年代发展了解析连分数理论,并研究了它们与矩问题之间的关系。亚历山大·辛钦在1930年代的研究奠定了连分数度量理论的基础,而保罗·莱维则确定了渐近分数分母几乎处处成立的指数增长率。此后,遍历理论与数值分析的发展,将这些算术和分析传统纳入了动力系统、有理逼近与计算等更广泛的理论框架。