英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

---

对区间计算的回顾

--软件和应用

Chenyi Huy, Shanying Xu z, and Xiaoguang Yangx

摘要：区间计算已成为计算科学与工程中的有用工具。在本文中，我们简要回顾一下区间计算是什么还有为什么我们需要区间计算的原因。 特别是回顾一些免费的区间计算软件和应用程序。我们还列出了这些软件和应用程序的网址。

自从R.E.摩尔在1950年代末提出区间计算的思想，它就已成为科学计算的积极研究分支。 在本文中，我们主要回顾我们所参与的这一领域的工作成果。

1介绍

在本节中，我们将介绍为什么需要区间计算。为此，我们需要回顾一下浮点算术。

1.1浮点运算

从第一台现代电脑出现是，浮点运算就已经被普遍用于科学计算。在浮点算术，一个实数

R，被写为R =plusmn;b0：b1b1times;,其中B0; b1; b2是二进制数字0或1，p是二进制整数。

我们称之为b0：b1b2的尾数，p指数r。如果r ne;0，则b0 = 1。例如，在IEEE 32位实数中表示中，RST位被指定为符号位（0 和1－）;第2位至第9位用偏置127（e = p 127）存储偏置指数;假设存在尾数f的第10到第32位f前的1。 因此，实际尾数为1：f。

由于大多数实数需要许多位存储，所以当存储大多数实数时如果不使用精确的浮点形式表示，电子计算结果一定会显示表示错误。 在这些机器上执行浮点运算可代表的数字可能会导致额外的错误。通过我们的经验，我们如果使用更多的比特来表示一个实数可以使表示错误和失去意义大大减少。 但是，下面的例子告诉我们更多的位无法完全解决问题。

1.2不可靠的计算与浮点运算

许多人认为如果只是在浮点运算的最后几位出现错误，不会对计算中产生巨大的影响。 但是，这种想法是错误的。

1.2.1 例1

问题是：给定a = 77617：0和b = 33096：0进行评估。这是Rump在IBM S / 370上运行的一个非常简单的例子。

f = 333:75 (11 －－ 121 －2) 5:5 ,

获得的计算结果为：单精度f = 1：172603；双精度f = 1：1726039400531；更高的精确度

f = 1：172603940053178。通过这些，我们会相信少第一个数字1：1726应该是正确的。

然而真正的答案是﹣0：82739605994683135带有错误界限10。 甚至计算结果的符号也是错误的。

1.2.2例2

问题：数值评估递归定义的序列 =1; =; =-对于n = {1; 2; 3; }在一台电脑上浮点运算，然后预测序列是否收敛。

计算结果浮点运算意味着序列将分歧到正无穷还是负无穷这需要取决于机器，编程语言，和编译器使用; 但不管使用单一或双重精度。通过数学归纳，很容易证明递归地去除序列与相同。因此，在数学中以上递归数学序列应该收敛到零。

1.2.3例3

在数学中，我将我们在x = x0处的函数f的导数被定义为. 如果试图在h接近0的情况下形成一个数值序列，以便在电脑上使用浮点算法估计，最后我们会发现所有连续的功能都是不可靠的，而且他们的衍生品几乎遍布各地。

误导的原因是f( h)和f（）在足够小的h之后是完全相同的。 由于f是连续的，当h足够小时，f( h)和f（）几乎相等。 这些可以证明分子中的数字丢失。

1.3区间算术

上述简单而极端的例子表明我们得到的数值结果用浮点运算并不总是可靠的。 在复杂的计算中，为了确定数值结果的可靠性，每一步都非常重要。

随着自动数值结果验证的出现，R. E. Moore在20世纪50年代末提出了他的方法。 为了表示实数r，他建议使用包含r（遏制机器可代表的区间原则），而不是切碎或四舍五入。 例如，无理数字可以表示为区间[3：141592653; 3：141592654] 在一个假想机器只能记录10位数字。 操作应该是在这些机器可表示的区间上也执行。 他断了区间算术如下：定义（区间算术）：令x1和y为两个实际区间并且作为算术运算（ ， - ，*，/）。 然后，x op y ={x op y| x x; y y}

例如: [1; 2] [2; 3] = [3; 5]; [3; 5] - [1; 2] = [1; 4]; [1; 2] [2; 3] = [2; 6]: 区间表示和算术中没有信息丢失。因此，计算的真正数值解决方案应该包含在结果区间。 在这种情况下，区间获得的数值结果计算可靠。

区间计算与传统方法相比具有不同的特性算术。 例如，z x y even x y = z。 另外，设置

可以容易地进行操作。 区间分析已经成为一个研究部门。 已经开发了基于区间分析的新算法。

有兴趣的读者可以参考[20]等文献分析。

区间计算也可以直接包含区间值,经常出现在现实应用中的参数变成数值计算。

2区间计算软件

在本节中，我们将回顾几个区间计算软件包。

2.1基本区间算术软件

基础区间算术软件包已经开发出来不同的计算机语言，如C，C ，Fortran，Pascal-XSC等。在这里，我们审查了我们参与的两个包。

2.1.1 INTLIB

B.Kearfott等人在1994年出版了区间库[16] INTLIB库是用Fortran 77编写的，可移植到几乎所有常用的电脑平台中。 Kearfott后来将其转换成Fortran 95。

INTLIB中的子程序通过定向执行严格的区间算法四舍五入。 该库中的子程序可以按照他们的功能分成四个组。它们是区间算术例程(; 设置操作例程（）; 实用程序（直接四舍五入和其它）和约束基本数学函数的程序（三角，反三角，对数，指数，双曲线等）。严格的区间算术。 库的源代码可以免费下载

从URL：www.netlib.org/toms/737。

2.1.2在线区间计算器

为了提供一个手持式计算器，例如区间计算的基本工具，胡鸿和C.胡[13]开发了一个在线区间计算器。该计算器的功能与INTLIB大致相同，不同之处在于计算器可通过用户友好的图形用户界面在线访问。这款计算器是用Java编写的。 它可以通过网址在线访问：www.mscs.mu.edu/~globsol/javaIntervalCalc/I_C.html.

2.2区间BLAS

基本线性代数子程序（BLAS）是科学计算中的基础工具。 来自政府机构的一批国际科学家，

计算机行业和大学组建了一个工作委员会从1996年2月至1999年3月，BLAS技术的新标准。该委员会提出了第一次BLAS标准。 功能包括区间向量运算，区间矩阵向量运算，

区间矩阵矩阵运算，涉及区间向量的集合运算矩阵和涉及区间向量和矩阵的效用函数。 语言Fortran 77,95和C的绑定和接口问题被规定约200个功能和子程序。 作为样本，我们从提出的标准中复制一般区间矩阵矩阵乘积的Fortran 95接口这里。

SUBROUTINE gem_1(a,b,c[,transb] [,alpha] [,betal])

TYPE(INTERVAL)(lt;WPgt;),INTENT(IN)::a(:,:),b(:,:)

TYPE(INTERVAL)(lt;WPgt;),INTENT(OUT)::c(:,:)

TYPE(blas_trans_type),INTENT(IN),OPTIONAL::transa,transb

TYPE((INTERVAL) (lt;WPgt;),INTENT(IN),OPTIONAL::alpha,beta

Where

C has shape (m,n)

a has shape (m,k) if transa=blas_no_trans(the default)

(k,m) if transa/=blas_no_trans

B has shape (k,n) if transb=blas_no_trans(the default)

(n,k) if transb/=blas_no_trans

本标准的完整文件可以从www.netlib.org/blass/blast-forum/免费下载。

2.3 INTBIS

非线性系统的根本是可靠的方程式F(X)=0（1）, 在给定的域上计算。

区间分析提供了实际的算法攻击问题[21]。在1990年，Kearfott和Novoa发布了名为INTBIS的Fortran 77 [18]。所使用的基本算法是区间牛顿/广义平分方法。 该算法将（1）转换为区间线性系统方程式（2）然后用区间算术迭代求解（2），然后更新=和2的下一次迭代的。在此过程中，可以应用广义平分分离,根据不同的盒子存储在一个堆栈进一步执行。

解决许多非线性系统的方程式因此成功。为了提高这个包的整体效率，胡先生研究了预处理器[9,17]和并行算法[6,7]方法。 该软件包的源代码可以从URL下载：www.netlib.org/toms/681.

2.4 GlobSol

一个给定的目标函数f的一般全局优化问题定义域和，使得f（）f（X）X 定义域D可能需要满足一些线性和/或非线性约束。这是计算数学中的一个根本问题。

在区间分析中，在数学计算中可靠的算法已被开发用于不可靠的目标函数[4，14，22]。

还开发了可以实现的软件。 被Kearfott命名为GlobSol [15]的Fortran 95已经实现并被广泛应用。Ratz在Pascal-XSC同样完成了实现。

Kearfott的GlobSol中使用的基本算法是区间分支，牛顿/广义平分法除外。 GlobSol

集成INTLIB，INTBIS，LINPACK，MINPACK，以及差异化。 搜索区域是最初的区间框。区间分支和绑定算法的原则是维护一个或多个列表：要处理的框的列表L，已经被还原的框的列表U，通过算法小直径，是已经验证的框的列表C通过算法包含关键点L。L中的盒子可以移出一边用于处理。 当L耗尽时，我们评估目标函数在列表U的每个框和列表C中的关键点上，然后可能是全局最优的。GlobAl包与指令一起可以从网址：www.interval.usl.edu/GlobSol/download_GlobSol.html免费下载。

2.5 ParaGlobSol

在解决工业应用问题时，GlobSol的CPU有时需要几个小时的时间。 为提高总体效能，胡胡设计制造GlobSol的并行实现，名为ParaGlobSol [10]。 ParaGlobSol采用单程序多数据（SPMD）数据并行方式进行粗粒度化处理。所有进程与本地数据并发运行GlobSol。 数据通过消息传递接口（MPI）的分配/收集以及静态和动态负载平衡来实现

。由于显着降低总计算量，已经观察到超线性加速对于几个计算密集型应用程序，。 有关ParaGlobSol，读者想要获取更多信息可以参考URL：www.mscs.mu.edu/~globsol/ParaGlobSol.html.

3应用

区间计算已经成功应用于许多科学领域工程。 在本节中，我们将回顾一些这些成功的应用程序。

3.1 Portfolio管理

对于投资组合经理，他们面临的基本问题是组合各种投资限制下的证券（现金流量，风险因素，到期结构，企业投资政策等），以最大化获利。

在[1]中，G. Corliss和B.Kearfott报道说，Thalacker等人发现BancOne的两个样本收入组合的最佳资产配置GlobSol。 所有的制约因素都令人满意。

其中一个收入投资组合只包含3个月，6个月和12个月的国库票据 来自美国财政部的每种类型的T-bill的实际现货价格数据拍卖被使用。 每个帐单的历史现货价格数据也被用于计算每种类型的T法案和法案之间协方差的差异。GlobSol计算出最优资产配置约为：3个月内的10％T账单，6个月T账单中为60％，12个月账单为30％。 回报率是每年5.363％。

另一个投资组合只包含1年，5年，10年和30年期国债四个投资限制：平均持续时间，现金流量，差异和总计值。 历史数据用于计算T键方差和协方差债券之间。 选择假设价值的现货价格，优惠券付款，和面值。 对于典型的约束集，GlobSol确定最优资产配置约为：一年4％，5年65％，10年期限为4％，30年期限为26％。 最佳速率回报约为7.388％。

在Sun Ultra-1站上GlobSol的 CPU花了2352.7秒的解决问题。而同样的问题，使用ParaGlobSol [10]，CPU花了15.75秒内就解决了9个过程。加速效果如此明显原因，是由于总体减少了并行执行中的计算量。

3.2货币交易风险控制

G. Corliss和B.Ke

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[26398]，资料为PDF文档或Word文档，PDF文档可免费转换为Word