区间算术是一种用区间而非单个数值表示各个量的数值计算体系。区间记录一个值所处范围的下界和上界,算术运算则给出能够涵盖这些输入所对应的所有可能结果的界限。如果在实现时正确控制舍入,区间算术不仅能处理数据本身已有的不确定性,也能将浮点运算引入的误差纳入考量。
区间算术的核心目的不只是估计答案,而是依据数学规则,构造一个能够确保包含真实结果的区间。因此,区间算术是验证数值计算的基础:这类数值方法能够证明解的存在性、排除不可能的情形,并给出严格的误差界。其应用包括非线性方程、线性方程组、全局优化、微分方程以及计算机辅助证明。它面临的主要困难是,所保证的界限可能过于宽泛,尤其是在计算中反复使用同一组不确定量时。
区间与包围的含义
有界闭实区间是如下集合:
其端点是实数,且满足 。点区间(例如 )表示一个精确的数。宽度为正的区间可以表示不确定的测量值、近似误差,也可以表示研究某个函数时所考察的整个定义域。这些解释虽然在科学含义上有所不同,但使用的是同一套算术运算。
常用的描述量包括宽度、中点和半径:
因此,。端点表示便于进行定向舍入,而中点—半径表示往往有助于误差估计和矩阵界的计算。在机器算术中,这两种表示之间的转换本身也必须保持包围性;对中点和半径简单地进行舍入,并不一定能做到这一点。
对于实值函数 ,区间计算的目标是求得满足下式的区间 :
左侧的集合是精确值域。包含它的最小区间称为它的区间包。区间求值可能得到这个区间包,也可能得到更大的包围区间。这一区别至关重要:有效性意味着不遗漏任何可能的结果,而紧致性则关注额外包含的部分有多少。
区间通常并不为其中的元素赋予概率。断言 并不意味着 服从均匀概率分布,也不意味着靠近中点的值更有可能出现。同样,区间包围也并不自动构成置信区间。置信区间与某种统计程序及其覆盖性质相关;区间算术给出的界则是指定假设的确定性推论。统计方法得到的界可以作为区间计算的输入,但这些输入仍然带有其原有的概率限定条件。
在多维情形下,各个区间组合成一个区间盒:
它是各坐标区间的笛卡尔积。区间盒的存储和运算成本很低,但通常会丢失坐标之间的关系。如果所有可能的数对都满足 ,那么用一个区间盒替代这一集合,就会同时纳入违反该关系的数对。区间分析的很大一部分工作,就是恢复、保留或补偿这类表示所丢失的信息。
算术运算与代数结构
对于两个区间 和 ,基本运算的定义是:取两个区间中的元素两两运算所得的全部结果,再用区间将其包围。在精确实数算术中,
以及
当两个操作数独立变化时,这些公式给出了相应二元运算的精确区间值域。例如,
虽然实际实现中常根据端点的正负号简化乘法计算,但这些简化方法必须始终与上述包围定义等价。
若 ,则通过倒数定义除法:
无论 严格为正还是严格为负,这个公式都适用。除以包含零的区间则需要另作处理。例如,用 除以 中的非零元素,所得实数商构成集合
这个集合不连通,无法用单个区间精确表示。系统可以返回它的区间包,即整条实数轴,也可以保留两个分离的分支,或采用异常处理机制。这些选择属于区间系统的语义,而不是可以随意互换的计算细节。
在端点运算精确的情况下,区间加法和乘法满足交换律与结合律,但区间并不像实数那样构成一个域。对于非退化区间 ,减法不会消除不确定性:
而不是 。完全的分配律也不成立。对于 、 和 ,
取而代之的是次分配律:
右侧表达式允许两处出现的 各自独立变化。
一个核心性质是包含单调性:扩大输入区间不会使精确的区间结果缩小。例如,
乘法以及在适当定义域上的除法也满足类似性质。这一性质为逐步收缩区间盒或细分定义域的算法提供了支持。
集合求交是另一项重要运算。如果两个独立论证分别确定某个量属于 和 ,那么它就属于 。交集为空可以证明这些约束相互矛盾。因此,区间算法经常交替进行算术求值与求交,利用通过不同途径获得的多个有效界限相互收紧。
定向舍入与严格的机器计算
仅有实数公式,并不能保证计算机计算的严格性。如果两个端点都舍入到最近的机器数,下端点就可能向上移动,上端点也可能向下移动,从而将某个有效结果排除在外。为保证包围性,实现时应将下界向负无穷方向舍入,将上界向正无穷方向舍入。对于加法,机器运算的形式为
其中, 和 分别表示向下舍入和向上舍入。
即使对于普通的十进制常数,这一区别也很重要。十进制小数 没有有限的二进制浮点表示。如果程序先将其转换为某个邻近的二进制数,再创建一个点区间,那么所得区间通常表示的是该二进制数,而非精确的十进制小数。要包围这个十进制值,转换过程必须直接根据其文本表示或精确有理数表示,生成向外舍入的端点。同样,在一段已经完成的长串浮点计算的结果外加上一个区间,也不能追溯性地为该计算中的所有误差提供界限。
IEEE 754 浮点标准提供了基本包围运算所需的舍入方向。IEEE 1788-2015 则规定了区间算术,包括各种运算,以及用于记录定义性和连续性相关限定信息的机制。不过,要正确实现区间算术,仍须关注整个软件环境。编译器若通过变换来重新结合表达式、替换运算,或假定舍入模式固定不变,就可能使基于原始运算顺序的证明失效。下溢、上溢、带符号的零、无穷大以及异常值也都需要显式处理。
初等超越函数还会带来额外的挑战。对于单调的指数函数,只需包围端点处的函数值即可:
对于三角函数,还必须考虑区间内部的极值。如果某个区间包含一个正弦值为 的点,那么无论端点处的函数值是多少,所得区间的上界都必须涵盖 。当自变量很大时,即使只是判断某个临界点是否位于区间内,也可能需要严格的自变量约化和更高的精度。
有些实现会改变硬件舍入模式;另一些则采用无误差变换、更高精度的中间计算,或显式的误差估计。并不强制要求使用某一种实现技术。必须满足的性质是:返回的每一个界都符合所声明的包围保证。提高精度可以减少舍入造成的区间膨胀,但仅靠提高精度,无法消除因变量间依赖关系丢失而产生的过度估计。机器舍入误差与结构性的区间过度估计,是造成区间额外宽度的两种不同来源。
依赖性、表达式选择与包裹效应
当同一变量的多次出现被当作彼此独立的区间操作数时,就会产生依赖性问题。若 ,直接求值得到
然而函数 恒为零。对于两个独立变化的输入,这一算术运算本身是正确的;之所以高估了结果范围,是因为表达式要求这两个输入取值相同。
因此,等价公式的区间求值结果可能大不相同。对于
专门的平方运算给出 ,因此直接相减得到
配方后得到
其区间求值结果恰为
两种情况下的值域是同一个数学对象;计算所用的表示形式决定了能保留多少依赖性信息。
细分定义域是一种通用的补救办法:将定义域划分为较小的区间,分别求值,再合并结果。在更窄的定义域上,变量重复出现通常会带来较少的额外宽度。在适当的连续性和收敛性假设下,系统地细化划分可以逼近精确值域。不过,计算成本仍可能随维数迅速增长,这体现了维数灾难。将每个坐标方向都划分为十份,在 维空间中就会产生 个盒。
一个相关的几何问题是包裹效应。考虑将平面中的一个盒进行旋转。它的精确像是一个旋转后的矩形,但包围它的最小坐标轴对齐盒通常还包含额外的点。反复对集合进行变换,再用盒重新包围,会使这部分多余范围不断放大,尽管底层的旋转变换保持距离不变。在动力系统计算中,包裹效应造成的膨胀可能远超不确定性的真实增长,使原本有效的界在实际应用中失去价值。
有几种表示方法可用于缓解这些信息损失。仿射算术使用共享的噪声符号来表示各个量,从而保留变量各次出现之间的线性相关性。泰勒模型保留一个多元多项式及一个严格的余项区间,以刻画定义域上的非线性依赖关系。其他方法则在计算过程中传递椭球、平行多面体或由线性约束描述的集合,仅在必要时才将其转换为区间。
这些方法并不能使区间界在所有情况下都紧致。保留更多结构会增加存储需求和计算成本,而非线性运算仍可能引入近似误差。因此,实际选择并非简单地在“区间”与“非区间”计算之间二选一,而是在能够维持可检验包围范围的前提下,选择保留不同类型信息的表示方法。
函数求值、微分与值域界限
将公式中的实变量和运算替换为相应的区间变量和区间运算,就得到自然区间扩展。如果 由所支持的初等函数构成,那么在表达式有定义的所有地方,其自然扩展 都满足
更一般地,一个实用的区间扩展应当在输入为单点时,与普通求值的结果一致(允许存在机器计算中不可避免的包围误差),并且应保持包含关系。所得界限的紧致程度很大程度上取决于表达式树。
利用导数信息通常可以得到更紧的界限。对于在 上可微的标量函数,选取中心点 ,并令 包含所有导数值。根据中值定理,可得到中心形式的包围区间:
点值和所有算术运算的结果也都必须得到严格包围。对于多元函数,相应的形式使用在整个区间盒上求得的区间梯度或区间雅可比矩阵。
导数的符号有时可以免去细分。如果 严格为正,那么 在整个 上递增,其值域可由端点处的函数值界定。如果导数区间包含零,并不能据此认定存在驻点:这可能仅仅是过度估计造成的。进一步细分或分析导数可以区分这些情形。
高阶展开能够提供更多结构信息。对于 ,二阶泰勒公式给出
其中 是某个中间点。用 上的区间包围替换 ,即可得到严格的余项界限。高阶泰勒展开也可以类似处理,前提是确实给出了余项的界限;没有这种界限的截断级数不能作为严格保证。
自动微分可以沿计算图传播区间导数。它不同于基于邻近采样值的数值微分,而是对程序中的运算应用求导法则。所得界限可用于单调性检验、根的验证、灵敏度计算和优化。不可微运算和分支需要单独进行数学处理;仅对中点求值时所执行的分支求导,不一定能描述整个区间定义域上的情况。
定义域限制同样重要。例如,实对数要求自变量为正,平方根则要求自变量非负。跨越定义域边界的区间可能需要拆分、限制,或者在结果中明确注明表达式仅在部分区间上有定义。只有同时说明所表示的表达式在哪些定义域条件下存在,数值包围才有意义。
非线性方程解的验证
区间方法会区分近似求根往往未能解决的几个问题:根是否存在,在某一区域内是否唯一,以及是否已找到指定定义域内的所有根。仅凭很小的残差无法证明其中任何一点。如果函数变化十分平缓,即使远离根,函数值也可能很小;如果函数存在非零的局部极小值,则可能根本不存在根。
最简单的排除检验是计算区间扩展 。如果
则 在 中没有零点。反之则不成立:区间包含零可能只是区间过估计造成的。因此,一种基本的完备搜索策略是逐一计算各个区间盒,舍弃不可能含根的盒子,并细分其余盒子。导数信息可以大幅加快这一过程。
标量情形的区间牛顿法将近似解与区间内导数的整体界相结合。对于 ,
其中假设 。 中的每个根都属于 ,因此用 替换 ,会保留原区间中的所有根。如果该交集为空,则原区间不含根。在通常的连续性和可微性假设下,严格包含关系
可证明根的存在性;导数包围区间不含零还保证了根在 中的唯一性。
例如,设 、,且 。此时 ,而 ,由此得到
这个区间严格位于 内,从而证明其中存在唯一的正根。继续迭代可得到更窄且经过验证的界。普通的牛顿法可以提供良好的初始近似值,而区间步骤则负责验证。
对于方程组,直接的区间除法由经过验证的线性代数方法或克拉夫奇克算子等算子取代:
其中, 是近似雅可比矩阵之逆的点矩阵。在通常的假设下,自包含条件可证明解的存在性。如果能够给出使 成为压缩映射的界,就可证明解的唯一性。这些条件是充分条件,而非必要条件:验证失败可能是因为区间盒过宽、雅可比矩阵接近奇异或根是重根,而不一定是因为近似解有误。
区间线性代数与扰动界
区间矩阵表示一个矩阵族,其中各元素均位于指定的界限内。对于区间矩阵 和区间向量 ,一项常见任务是为联合解集
求包围范围。这里的量词至关重要。这个集合既不同于满足该族中所有方程组的向量所组成的集合,也不同于多个元素依赖共同参数的模型。若将各元素的区间视为彼此独立,就可能纳入原始物理模型绝不允许出现的矩阵。
用区间运算执行普通的高斯消元法,只有在各步运算始终有定义时,才能得到提供包围范围的算法,但所得区间往往过宽。即便原始矩阵族中的每个矩阵都非奇异,主元区间仍可能包含零。消元过程中引入的依赖性可能使除法无法有效进行,而用逐元素区间表示不断变化的矩阵族,则会丢失元素之间的关系。
预条件化可以解决其中一部分困难。对于固定的方程组 ,取近似解 和数值计算得到的近似逆矩阵 。令 ,可得
若区间盒 满足
那么在适当的存在性条件下,它就给出了不动点的包围范围。特别地,若某个相容矩阵范数满足
则该映射为压缩映射,解是唯一的。当 和 为区间矩阵和区间向量时,对同一表达式求统一的包围范围,就能为所有允许的方程组给出经过验证的界。
当 已经相当准确时,残差 尤其有用。即使原始解是用常规数值求解器得到的,只要严格计算残差——有时需要采用更高精度——仍可证明只需很小的修正量。这种将近似计算与严格验证分离的做法,是一种反复出现的设计原则:将高代价的精确计算集中用于验证凭据,而不是每一个探索步骤。
条件数决定了数据不确定性可能对解产生多大影响,但它与区间高估并不是一回事。病态方程组确实可能容许范围很广的解。良态方程组也可能因算法不佳而得到很差的区间界。验证时必须区分这两种效应。
相关技术还能验证矩阵的非奇异性、确定逆矩阵各元素的界,以及包围特征值与特征向量。对称性、正定性、稀疏性和共享参数结构都能显著改善这些界。若仅用彼此独立的元素区间来表示具有这些性质的矩阵,就可能丢失恰恰使问题易于处理的关键信息。
全局优化与约束求解
在数学优化中,局部方法可以找出一个有潜力的候选解,却无法证明其他位置不存在更优的点。区间方法能够给出整个区域上的下界,因此可用于提供全局性保证。对于盒域 上的最小化问题,包围关系
表明该盒域内处处都有 。在一个可行点处严格计算得到的目标函数值,则可提供全局最小值的上界。
区间分支定界法维护一组盒域,覆盖尚待搜索的区域。每个盒域都有一个下界,而经验证的最佳可行目标值则提供当前上界 。如果某个盒域的下界大于 ,它就不可能包含更优的极小点,因此可以将其舍弃。其余盒域则继续收缩或分割。如果所有剩余盒域的下界中最小者为 ,那么全局最小值就被包围在
之内。差值 给出的是目标函数值的误差保证,而不是对极小点位置的界限。
界限不一定只能通过直接计算函数值得到。中心形式、导数的符号、凸松弛以及海森矩阵估计,都可能给出更紧的下界。如果已知某个无约束极小点位于内部,则该点的梯度必为零,因此可以利用区间求根方法排除部分区域。边界面需要单独处理;仅在内部搜索驻点,无法为完整的约束问题提供保证。
区间约束传播利用单个方程或不等式缩小变量的取值域。例如,由 可以进行如下更新:
在约束网络中反复传播,可以在分支之前排除大片不可行区域。更强的收缩算子通过区间牛顿步、线性松弛或单调性分析,将多个约束结合起来。每次收缩都必须保留全部可行点,但不必排除所有不可行点。
同一框架也适用于参数估计和几何可行性问题。如果测量误差以有界范围给出,那么只要某个参数盒域对应的模型预测范围与观测范围不可能相交,就可以排除该盒域。因此,保留下来的盒域包围了所有与给定界限相容的参数值,而不是表示某种后验分布。
全局性保证始终以定义域、模型、算术运算和终止准则为前提。当原问题的定义域无界时,必须论证将搜索限制在有限区域内的合理性。严格不等式和奇异边界也需要谨慎处理。即使算法有效,仍可能留下大片尚未判定的区域:包围结果保证的是可靠性,并不承诺每个困难的优化问题都能得到高效求解。
微分方程与验证轨迹
对于初值问题
验证求解器旨在寻找一个集合,包住初始集合和模型假设所允许的所有轨迹。这与给单条数值轨迹附加启发式误差条不同。所得包络必须涵盖初始条件的不确定性、舍入误差、离散化误差,以及在纳入考虑时的有界不确定参数。
一个基本步骤是在某个时间区间上建立先验包络。将方程写成积分形式可得
如果试探盒 包含 ,且区间求值验证了相应积分算子在该时间步上满足适当的自包含条件,就可以据此证明解始终位于 内。连续性和利普希茨连续性条件提供了存在性与唯一性的理论框架。当时间步长足够小时,利用 的导数界可以证明该算子具有压缩性。
得到这样的轨迹管后,便可利用高阶展开推进端点包络。对于一个分量,
余项的界须利用整个已获验证的轨迹管上的导数信息来确定,而不能仅使用初始点处的信息。自动微分可以高效地生成高阶系数。多项式求值和余项计算都需要使用能够保证包络的算术运算。
在反复进行时间步进时,包裹效应尤为严重。即使系统本身稳定,如果其流使所表示的集合发生旋转或剪切,坐标盒也可能迅速膨胀。因此,验证积分器会采用坐标变换、矩阵分解、多种集合表示或泰勒模型来保持几何关系。不过,在真正不稳定的系统中,部分膨胀反映的是真实的敏感性,无法通过改进表示方式来消除。
验证积分还支持事件检测、周期轨道验证和边值问题的求解。对于穿过曲面 之类的事件,需要确定事件发生时间的界,并验证相关的穿越条件。对于周期轨道,可以通过积分构造返回映射,再利用区间不动点论证来验证解的存在性。这些结论是关于数学模型的存在性陈述,并非对模型物理假设的实证验证。
对于偏微分方程,仅靠有限维区间计算,并不能自动为原来的无限维问题给出界。严格计算还必须控制截断误差、空间离散化误差和未解析模态,这通常需要借助解析不等式和函数空间估计。只要计算机求解的是连续问题的有限近似,就存在同样的区别:验证有限计算只是验证完整模型的一部分。
历史发展、软件与证明实践
上下界的使用早于电子计算机,但现代区间算术是为系统应对数值误差和数据不确定性而发展起来的。Mieczysław Warmus 于 1956 年发表了区间计算方面的研究;Teruo Sunaga 在 1958 年的研究中介绍了区间代数及其在数值分析中的应用。Ramon E. Moore 在其 1962 年的博士论文及 1966 年出版的《区间分析》(Interval Analysis)一书中,对这一领域进行了深入而广泛的研究。这些贡献确立了区间作为计算对象的地位,使其不再只是偶尔附加在常规计算之后的估计。
后续研究将这一领域拓展到验证线性代数、非线性系统、优化和微分方程。Götz Alefeld、Jürgen Herzberger、Ulrich Kulisch、Arnold Neumaier 和 Siegfried Rump 等研究者为可靠数值计算开发了数学方法、实现技术和软件。Rudolf Krawczyk 提出的算子成为验证非线性问题解的重要工具,无须直接构造区间雅可比矩阵的逆。
相关软件有多种形式。INTLAB 在 MATLAB 环境中提供区间方法和验证数值方法。C-XSC 支持 C++ 中的扩展科学计算,而 MPFI 等库则将区间运算与多精度端点表示相结合。其他系统侧重于验证微分方程求解、约束求解或全局优化。这些软件的能力并不相同:它们支持的函数、对舍入的保证、对异常输入的处理方式,以及可用的验证算法各有差异。
计算机辅助的数学证明体现了找到结果与确证结果之间的区别。区间计算可以在大量子域上证明不等式成立,也可以验证某个分析定理的前提条件。Warwick Tucker 于 2002 年发表的关于洛伦兹吸引子的计算机辅助证明,是严格数值方法应用于动力系统的一个著名实例。这类工作将区间计算与大量数学论证结合起来;区间算术不能替代对计算所需证明的定理的明确界定。
一份证书所依赖的可信环节不止区间公式。输入的解释方式、初等函数的实现、编译器行为、分支覆盖情况,以及对排除域或奇异域的处理,都可能影响正确性。形式验证可以通过检查算术过程,或在证明助手中检查生成的证书,减少对未经审查的软件的依赖。但它并不能免除准确陈述数学模型和假设的必要性。
一种典型的成功工作流程是,先用快速的常规计算寻找候选结果,再用规模较小的严格计算加以验证。反过来,验证失败通常并不意味着反证成立:精度不足、坐标系选择不当、过强的依赖效应,或问题接近奇异,都可能导致充分条件无法得到满足。输出必须区分经过确证的结果、经过确证的排除结论,以及尚未解决的情形。