动机
有理逼近是否有用,须把误差与分母大小一同考虑。连分数反复取整数部分,再把余下部分取倒数,构造误差与分母有很强联系的分数。输入是有理数时,这正是欧几里得(Euclid)算法;输入无理数时,算法无限进行,其有限截段则有可证明的收敛与误差界。
相邻两个逼近的行列式是不变量:相应整数向量组成整数格的一组基。把任何竞争分数写成这组基的整数组合,逼近问题便成为符号问题。我们也会证明一个反向判据:若既约分数的误差特别小,它必定已出现在渐近分数之中。
本章输入 是正实数。证明使用精确比较与恒等式,不把有限小数当作有理性或两个尾项相等的证据。有理数的终止情形与无理数的无限情形会分开处理。
定义
定义 11.1.1
(连分数算法)
设 ,取 ;若 不是整数,令
称为部分商, 称为完全商。有 ,而 时 。有限的逐层倒数式 是第 个渐近分数,记为 。
对正有理输入 ,分子除以分母的整数除法产生下一余数;取倒数则交换余数与原分母的角色。正余数严格递减,故过程终止。除了单项整数展开,最后一个部分商至少为二。反过来,有此末项约定时,逐步取整数部分能恢复所有项,证明标准有限展开唯一。若容许末项一,则 时有另一形式 。
无理输入不会终止,因为减整数与取倒数保持无理性。定义有限渐近分数时,尚未赋予无限嵌套式意义;它们确实收敛到原输入,须由下文证明。
定义 11.1.2
(递推与放大误差)
取辅助初值
并令 、。零分母初值只用于递推,不是一个有理逼近。对无理数 记 。候选分数 的放大误差是 ;当 时,普通绝对误差是 。
定理
定理 11.1.3
(行列式、尾项与收敛)
递推确实给出所述有限渐近分数,分母为正,分子分母互素,并满足
若 无理,则
所以渐近分数交替位于 两侧,收敛到它,并有 。
定理 11.1.4
(最佳放大误差与 Legendre 判据)
若 无理,整数 满足 ,则
若既约分数 的 ,且
则 是渐近分数。这是充分判据,并不是说每个渐近分数都满足这个更强误差界。
概念视角几何
最接近一条直线的格点
把每个候选分数 画成格点 。放大误差 就是该点到直线 的竖直距离。因此最佳放大误差定理是说:在第一坐标满足 的格点中,没有一点比 在竖直方向上更接近这条直线。符号交替表示相继的渐近分数点交替落在直线两侧;行列式恒等式则表示相邻两点张成面积为一的平行四边形,其中不含其他格点。
证明思路
递推与整数可逆矩阵
证明
(矩阵乘积、行列式与精确误差)
逐步代入嵌套分数,或相乘矩阵 ,得到
由右乘读出的正是两个递推,起始为 。每个因子的行列式是负一,故得到行列式公式。 的公因数必整除此行列式,所以只能是一。分母为正,;当 时,因前一分母为正,故 。
尾项式在 时是 。把尾项换成 ,整理分子分母便由递推得到下一步。减去 ,再用行列式,便得精确误差式;分母为正,所以符号交替。
由 ,误差式内的分母大于 ,得到严格界。又因 ,分母无界,误差趋零,从而证明收敛。单凭分数在两侧交替并不足以推出此结论。初时可能有 ,不妨碍其后严格增长。
任何竞争整数对都有整数坐标
证明
(渐近分数基中异号的坐标)
两列 、 的行列式为正或负一,故逆矩阵仍为整数矩阵。任何 因而唯一写成
相应误差是 ,而两个 符号相反。
若 ,由 得 ,所需界立即成立。若 ,则 会使 为 的正倍数,违反分母限制。 不可同正,否则 ;亦不可同负,否则 。所以两者异号,它们与异号的 相乘后反而同号,故
这对所有允许候选都成立,即使候选尚未约分。分母范围与放大误差的定义,都是定理不可略去的部分。
小到整数格不能容许的误差
证明
(小于一的非零整数)
证 Legendre 判据时,选最大的 使 。分母无界且最终严格增加,故此 存在,且 。设 ,最佳逼近给出 。
若 ,整数 非零,故 。但
矛盾。因此两分数相等;既约及正分母使表示也与渐近分数一致。证明的关键是非零整数不可能绝对值小于一,并非从小数展开猜出部分商。常数二分之一有明确作用:两个误差项都用同一候选误差估计,所乘分母也不超过候选分母。严格界使总和小于一;若只有等号,整数矛盾便消失,所以此证明没有额外建立边界情形。
大部分商究竟说明什么
完全商严格位于整数部分与下一整数之间,把两界代入精确误差式,可加强为
这不只给符号,也控制误差的真实大小。因为 ,下一部分商很大,表示当前渐近分数相对于分母平方特别准确。受惠的是当前分数,不是下一个。例如 的有理展开中, 后面的十六说明 为何接近该有理输入;但无限无理定理本身仍要求输入无理。
对无理数还有精确的二分。若首项以后全有 ,,由 得 。上面的下界使每个渐近分数误差严格大于 。不是渐近分数的既约分数,则由 Legendre 判据的逆否命题知误差至少 ,比 更大。所以每个既约有理数都满足统一界
反之,部分商若无界,对任何候选正常数 都可选下一部分商大于 。由上误差界及 ,得到误差小于 的渐近分数,故不存在这种统一正常数。两方向合起来证明:部分商有界,恰好等价于存在分母平方型的统一下界。这类无理数称为难逼近数;名称指统一常数,并非完全没有准确逼近。
对 ,已证尾项重复,后续部分商全为二,故 是可行常数。渐近分数仍会随分母增长而任意接近它;下界本身也随分母缩小,所以不违反收敛。本章不宣称这个简单常数已是最佳值。
证明透视
相邻渐近分数为何控制所有竞争者
行列式使两个向量成为整数基,而不只是两个相近的实数。分母限制迫使竞争者的基底系数异号,于是两项误差相加而不能抵消。反向判据再把一个非零整数行列式压到一以下。逼近估计背后是这些离散限制。
例题
例题 11.1.5
(有理输入与末项约定)
整数除法给出 、、,所以 ,渐近分数为 。最后的行列式为 。 值相同,但不是标准形式。两者都是有限式,不需要无限过程的收敛定理。
例题 11.1.6
(平方根二的精确重复尾项)
因为 ,第一完全商的整数部分为二,分数部分是 ,所以同一完全商重现,展开为 。首几个渐近分数为 ;误差依定理交替。前四个的精确值 为 ,引出下一章的二次方程。重复由代数恒等式证明,不是从有限小数图样推测。
例题 11.1.7
(用范数恒等式辨认渐近分数)
整数九十九与七十满足 ,所以
它们互素,因公因数的平方须整除一。Legendre 判据证明 是渐近分数;递推亦确认它接在 之后,因为 、。范数恒等式提供无须浮点近似的精确证书。
反例模式
放大误差与普通误差不同
对 ,渐近分数 的下一个是 ,但 的普通误差比 小;比较等价于 。这不违反最佳放大误差,因为 ,等价于 。两个有理界都可把正数平方后验证。修正方法是保留定理误差中的分母因子 ,不能悄悄更换所最小化的量。
常见错误
常见错误
(初值或零余数都不是渐近分数)
零分母的递推初值不是渐近分数。有理算法在余数零时停止,不能再对零取倒数。标准有限展开可有另一个不标准形式;无理输入则始终不终止。
常见错误
(Legendre 界是充分而非必要条件)
最佳逼近定理有明确的分母范围及误差种类。Legendre 界是辨认渐近分数的充分条件,不是每个渐近分数都满足的必要条件。
常见错误
(有限个重复的部分商不能证明周期性)
精确的二次尾项恒等式可证重复,有限个系数看似重复则不能证一般周期定理。例如有理数 与 的前五个部分商相同,但它的展开会终止。任何有限长的部分商序列,都为无穷多个输入所共有。
小结
欧几里得倒数程序产生的相邻渐近分数,具有行列式正负一的关系。完全商给出精确带号误差并证明收敛;同一行列式提供整数基,证明最佳放大逼近及 Legendre 判据,为二次整数方程建立严格工具。
练习
快速检查
(求 的标准连分数及所有渐近分数。)
对 与 进行欧几里得算法。
解答 · 答案
除法为 、、、。故展开是 ,递推给出 。
快速检查
(证明严格位于相邻渐近分数之间的既约有理数,其分母至少为两分母之和。)
把 写成两个相邻渐近分数所成整数基的组合。
解答 · 答案
在整数基中写 。分别与两邻向量取行列式,由严格介于其间及 得 。两者为整数,故至少一,于是 。中项分数达到等号;其分子分母互素,因公因数亦须整除相邻行列式。
快速检查
(用完全商恒等式证明 ,并求首四个渐近分数。)
把 有理化,并跟踪各完全商。
解答 · 答案
第一尾项为 ,整数部分一;下一个为 ,整数部分二;再下一个回到第一尾项。所以重复项为一、二,渐近分数是 。首两个分母同为一是递推允许的,不影响其后增长。
快速检查
(Legendre 充分判据的逆命题成立吗?用 的渐近分数 ,精确证明相关误差比较。)
把正数平方,比较 与 。
解答 · 答案
不成立。上一题证明 是渐近分数,但由 知 ,故 。这个真正的渐近分数不满足充分界。因此不能因误差达到或超过该界,就排除一个分数是渐近分数。