我对区间算术 (IA) 有一个非常基本的概念,但它似乎是计算科学的一个非常有趣的分支,无论是理论上还是实践上。很明显,明显的应用是验证计算和不适定问题,但这太抽象了。由于这里有很多人参与应用计算,我对没有 IA 很难或不可能解决的现实世界问题感到好奇。
哪些应用需要区间算术?
这个答案部分回应了JackPoulson 的评论(因为它很长),部分回答了这个问题。
区间算术是一种计算过程,用于对计算量给出严格的界限,仅在某个区间上实值函数的区间扩展包含该函数在同一区间上的图像的意义上。在不计算任何内容的情况下,区间算术无法让您深入了解哪些因素会影响计算中的数值误差,而 Higham 和其他书中的定理确实可以让您深入了解影响数值误差的因素,但代价是潜在的弱界限。当然,由于所谓的依赖问题,使用区间算术获得的界限也可能很弱,但有时它们要强得多。例如,使用集成包COZY Infinity获得的区间界限比你从 Dahlquist 的结果中得到的数值积分的错误界限类型要严格得多(有关详细信息,请参阅Hairer、Wanner 和 Nørsett);这些结果(我特别提到了第一部分中的定理 10.2 和 10.6)更深入地了解了错误的来源,但是界限很弱,而使用 COZY 的界限可能很紧。(他们使用几种技巧来缓解依赖问题。)
在描述区间算术的作用时,我犹豫使用“证明”这个词。有涉及区间算术的证明,但使用带外舍入的区间算术计算结果实际上只是一种记账方式,以保守地限制函数的范围。区间算术计算不是证明;它们是传播不确定性的一种方式。
就应用而言,除了 Stadtherr 在化学工程方面的工作外,区间算术也被用于计算粒子束实验的界限(参见 Makino 和 Berz 的工作,链接到 COZY Infinity 网站),它们已经Barton用于全球优化和化学工程设计应用(除其他外)(链接指向出版物列表),Neumaier用于航天器设计和全局优化(除其他外) (同样,链接指向出版物列表) )、 Kearfott的全局优化和非线性方程求解器(另一个出版物列表),以及不确定性量化(各种来源;Barton 就是其中之一)。
最后,免责声明:巴顿是我的论文顾问之一。
区间算术给你一个数学严谨的证明。
实际应用的好例子是Mark Stadtherr和他的研究小组的工作。特别是,相平衡和稳定性计算成功地解决了区间方法。
ALIAS 网站上有一组很好的基准,参考了它们的物理背景。
区间算术及其推广的另一个特点是它允许对函数的域进行自适应探索。因此,它可以用于自适应几何建模、处理和渲染,仅以计算机图形为例。
区间方法在最近的一些困难数学定理的证明中得到了体现,例如洛伦兹吸引子和开普勒猜想中混沌的存在。有关这些和其他应用程序,请参见http://www.cs.utep.edu/interval-comp/kearfotPopular.pdf。
区间算术对于几何算法非常有用。这种几何算法将一组几何对象(例如一组点)作为输入,并基于点之间的空间关系构建组合数据结构(例如三角剖分)。这些算法依赖于少数称为“谓词”的函数,这些函数将固定数量的几何对象作为输入并返回一个离散值(通常是“上、对齐、下”之一)。这样的谓词通常对应于点坐标的行列式的符号。
使用标准浮点数是不够的,因为它可能无法准确计算行列式的符号,更糟糕的是,返回不连贯的结果(即,说 A 在 B 之上且 B 在 A 之上,从而使算法创建一个混乱而不是网格!)。系统地使用多精度(例如在 Gnu Multi-Precision 库及其对多精度浮点数的 MPFR 扩展)可以工作,但会导致显着的性能损失。当几何谓词是某事物的符号时(如在大多数情况下),使用区间算术可以进行更快的计算,然后仅在区间中为零时才启动更广泛的多精度计算。
这种方法用于几个大型计算几何代码(例如 CGAL)。