连分数

连分数

连分数是一种记号。例如,长为 4 的连分数:

<a_0,a_1,a_2,a_3>=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3}}}

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

连分数中,从前面一直到第 k 个变元构成的连分数,是它的 k 渐进分数。连分数各变元的下标从 0 开始。

渐进分数有递推关系:

\frac{p_n}{q_n}=\frac{x_np_{n-1}+p_{n-2}}{x_nq_{n-1}+q_{n-2}}

这个式子和 Farey 数列的递推关系很像。

上面的例子是有限连分数。如果分式无限地写下去,有无限个变元,就得到无限连分数。无限连分数收敛等价于渐进分数收敛。

有定理:

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

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

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

还有一个事实,对于有限连分数,全体结尾为 1 的有限连分数和全体结尾不为 1 的有限连分数一一对应,即同一个连分数有两种表示:

<a_0,a_1,a_2,a_3>=<a_0,a_1,a_2,a_3-1,1>

简单连分数:连分数从第 1 项开始全都是正整数。如果有限,要求最后一项不为 1 (第 0 项可以任意)

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

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

如果“规定第 0 项是该数的取整”,那么全体实数都有“唯一的简单连分数表示”。其中:

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

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

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

如果要求 (0,1) 区间内某个数的简单连分数表示(第 0 项为 0 ),只需:

  1. 取倒数,得到的数大于 1
  2. 取整,得到的数在 0 1 之间。这个数称为余数。
  3. 对余数重复上述操作。

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

循环连分数

仿照循环小数的概念,如果在连分数后面形成了循环,则形成 循环连分数。如果循环节从第 0 项开始,称为 纯循环连分数,否则称为 混循环连分数。例如纯循环连分数:

<a_0,a_1,a_2,a_3,a_0,a_1,a_2,a_3,…>=<\overline{a_0,a_1,a_2,a_3}>

混循环连分数:

<a_0,a_1,a_2,a_3,a_1,a_2,a_3,…>=<a_0,\overline{a_1,a_2,a_3}>

混循环连分数后面循环的部分,一般要找最早循环的部分,称为它的“纯循环部分”。循环节一般取最小正整数。

二次有理数

形如 a+b\sqrt{d} a b 为有理数, d 为整数,称为二次有理数。二次有理数与整系数二次方程的解构成对应关系。

对于二次有理数 a+b\sqrt{d} ,记 N(a+b\sqrt{d})=a^2-db^2 ,称为它的范数。称 a-b\sqrt{d} 为它的共轭。于是范数就等于二次有理数与它的共轭的乘积。

以下的二次有理数,特指实二次有理数,即 d 应当为正。

对二次有理数执行“无限简单连分数”计算,即取倒数、取整交替,得到的余数还是二次有理数。

这里考虑一类特殊形式的二次有理数。设 \xi 是如下形式的二次有理数:

\xi_k=\frac{1}{q_k}\left(c_k+\sqrt{d}\right)=<a_k,a_{k+1},a_{k+2},a_{k+3},…>\quad q_k|N(c_k-\sqrt{d})

\xi_k k 余数

只要让分母整除分子的范数,取倒数、取整的交替过程会变得简单很多。事实上如果这条件不成立,只要分子分母同时乘以分母的绝对值,并强行压入根号,条件就成立了。因此,任何二次有理数都能写成这形式。

如果这条件成立,那么每个余数都满足这条件。

根据上文的简单连分数算法:对余数取整可以得到 a ,进而得到新的 c

a_k=\frac{c_{k+1}+c_k}{q_k}

取整后得到的新的 c 为负数,且绝对值一定比 \sqrt{d} 小,因此范数为负。取倒数,得到新的分母 q q 总是正的。

q_k q_{k+1}=-N(c_{k+1}-\sqrt{d})

由于范数为负,取倒数之后 \sqrt{d} 前面的符号不变,而 c 的符号由负变正(负数前面加负号变为正数)。

余数循环显然是循环连分数的循环条件。由于计算方法固定,只要余数重复必循环。

余数 \xi 里面,每个 c 都为负数,且绝对值一定比 \sqrt{d} 小,因此 c 的个数有限。每个 q 都整除对应 c 构成二次整数的范数,因此 q 的个数有限。

余数有限必重复。因此 所有二次有理数都可以写成循环连分数。反过来容易证明 循环连分数一定是二次有理数

由于无限简单连分数写法唯一,因此就找到了二次有理数的一种唯一表示。

最佳有理逼近

讨论如何用有理数“最佳地”逼近无理数,不妨假设无理数落入 (0,1) 区间。

“最佳”一词的概念:选定的有理数必须保证,比它与无理数的距离更近的有理数,分母都比它大。不存在分母比它小的有理数,到给定无理数的距离更近。

最佳有理数:在 Farey 数列的某一行中,与给定无理数距离最近的那个有理数。

这个有理数可能在下面几行依旧与无理数“距离最近”,但一定有某一行,会找到一个新的有理数,与无理数距离更近。因此去重复后可以得到 最佳逼近有理数列,分母严格递增,距离递减。

比无理数大的称为上逼近,否则为下逼近。由于无理数和有理数之间一定有有理数,最佳逼近有理数列必然为若干个上逼近,之后若干个下逼近,交替进行的形式。

有结论:

渐进分数必然为最佳逼近。偶项渐进分数全都是下逼近,奇项渐进分数全都是上逼近。渐进分数列是下上交错的逼近。

在最佳逼近有理数列中,渐进分数是下上关系改变之前的倒数第一个数。如果将最佳逼近有理数列都写成有限简单连分数,那么在渐进分数之后(下上关系改变之后),连分数长度加一。

例如, <0,2,4,2> \sqrt{6} 减去 2 的一个渐进分数。

那么它的渐进分数列是:

<0,2>=\frac{1}{2},<0,2,4>=\frac{4}{9},<0,2,4,2>=\frac{9}{20}\ldots

它的最佳逼近有理数列是:

<0,1>=1,<0,2>=\frac{1}{2},\\ <0,2,1>=\frac{1}{3},<0,2,2>=\frac{2}{5},<0,2,3>=\frac{3}{7},<0,2,4>=\frac{4}{9},\\ <0,2,4,1>=\frac{5}{11},<0,2,4,2>=\frac{9}{20},\ldots

从每个渐进分数(不包含)开始,到下一个渐进分数(包含)为止,同为上逼近,或同为下逼近。

在最佳逼近列中,每一个最佳分数是上一个最佳分数与再往前一个渐进分数的分子分母对应求和。

Dirichlet 逼近定理

Dirichlet 逼近定理是说,对于任意的一个无理数 \theta ,均能找到无穷个有理数逼近它,满足不等式:

\left|\frac{p}{q}-\theta\right|\leqslant\frac{1}{q^2}

更强的结论是,在右边的分母上能放一个 \sqrt{5} 。这个 \sqrt{5} 是最优的,在无理数为黄金分割的时候取等。因此,在上式中的小于等于号事实上也可以是小于号。

更进一步的定理是 Kronecker 的逼近定理。

如果 \theta 为无理数, \alpha 为实数,则对任意正数 \varepsilon , 存在整数 n 和整数 m ,使得:

\left|n\theta−m−\alpha\right|<\varepsilon

这两个定理都可以用抽屉原理来解决。事实上,历史上第一次正式提出抽屉原理,就是 Dirichlet 为了解决 Pell 方程 而研究这个有理数逼近条件才正式提出来抽屉原理的。

当然,采用抽屉原理的证明可以发现,上文中提到的最佳逼近有理数列,每项满足定理中右边改成分母为一次式的不等式。

进一步有结论,渐进有理数列中,每一项均满足 Dirichlet 逼近定理的不等式。


评论