MathLabs

解法:塔克利用区间算术给出的严格计算机辅助证明(1999年)

第 4/8 步:区间算术:用有保证的界来计算,而非单一数字
通俗地说

普通的计算机算术把实数存储为近似值,只是简单地寄希望于舍入误差不会造成麻烦;而在追踪混沌流所需的数百万步中,这种希望是没有根据的。区间算术则不同,它把每个量表示为一个有保证的范围 [x‾,x‾][\underline{x},\overline{x}],而不是单一的近似数字,并确保这个范围必定包含真实值;每一种算术运算(加法、乘法、求某个函数的值)都被重新定义,输出一个新的、依然有保证的范围,覆盖所有可能的结果。

代价是,如果不小心处理,范围会随着每次运算而变宽;而回报是,无论最终得出什么答案,它都不是猜测,而是一个经过数学认证的事实——这正是把数值模拟变成严格证明所需要的成分。

x∈[x‾,x‾]  ⟹  f(x)∈[f‾,f‾] with f‾≤f(x)≤f‾ guaranteedx \in [\underline{x}, \overline{x}] \implies f(x) \in [\underline{f}, \overline{f}] \text{ with } \underline{f} \le f(x) \le \overline{f} \text{ guaranteed}
详细分析

区间算术把计算中的每个实数 xx 替换为一个保证包含它的紧致区间 [x‾,x‾][\underline{x},\overline{x}],并重新定义算术运算,使得例如 [a‾,a‾]+[b‾,b‾]=[a‾+b‾,a‾+b‾][\underline a,\overline a] + [\underline b,\overline b] = [\underline a+\underline b, \overline a + \overline b],乘法及其他运算也类似(需按符号做适当分类讨论);把一个函数的区间扩展版本应用于某个区间自变量,可以保证得到一个包含该函数在此自变量上真实值域的区间。把这类运算组合起来,一整套数值算法(这里是用于求解洛伦兹常微分方程组的高阶泰勒级数积分器)就可以在区间值输入上运行,产生区间值的、经过数学认证的输出,代价是每一步区间会比真实的浮点误差稍微变宽一些(著名的「包裹效应」,在实践中可用 Lohner 方法等技术加以控制)。

这一技术从1960年代起(Ramon Moore)发展,并由 Lohner、Neumaier 等人为严格的常微分方程积分加以完善,正是它使得一个有限的、基于浮点数的计算机程序能够得出数学上滴水不漏的结论:塔克的实现所追踪的不是对单条轨道的近似,而是初始条件的整块整块的小盒子(区间的乘积)以及它们在流下经保证的像,因此任何关于一盒点最终会落到哪里的、被证明的论断,都是一条经过认证的定理,而不是一次数值观测。

有了这个工具,塔克证明的其余部分(在前面步骤中已用解析方法处理的小立方体 U0U_0 之外)就通过严格的区间计算而非启发式模拟来进行。

本步骤中的术语
包裹效应
区间计算中一种已知的过度估计来源:用一个与坐标轴对齐的方盒来表示某区域真实的(往往是弯曲、旋转的)像,往往会多包含一些多余的、虚假的点,而这种多余部分若不加特别控制,会在许多步骤中不断累积。
本步骤用到的知识