区间算法简介

区间算法简介 1 2 2胡承毅, 徐山鹰, 杨晓光 中国科学院数学与系统 2. (1. , , 72035, ;Com p u te r Sc ience D ep a r tm en tU n ive r sity o f C en t ra l A rk an sa s Co nw ayA R U SA )科学研究院, 北京 100080 摘要: 近年来, 国际上区间算法运用于计算科学和取得了一些显著成果, 国内也开始了这方面的 研究Λ 区间算法提出初衷是为了提高计算结果的可靠性, 但是人们很快发现区间算法可以有更广泛的应 用, 如工程, 金融等多方面Λ 区间算法对传统浮点算法进行了一个根本改革, 它把计算的数存储为区间, 并对这些区间进行运算, 使避免浮点算法所产生的计算误差成为可能Λ 另外, 区间算法使得区间参数能 被直接包含在计算之中, 这在实际应用里具有重要的意义Λ 区间算法是对浮点算法的一个有益补充, 值 O 242. 29 : 文献标识码: A 中图分类号得从事科技计算研究的工作者了解和应用Λ 关键词: 区间算法; 软件工具 A B r ief In t ro du c t io n to th e In te rva l M e tho d s 1 2 2, 2, 2HU C h en gy iXU Sh an y in gYA N G X iao gu an g ( 1. , , 72035, ; 2. Com p u te r Sc ience D ep a r tm en tU n ive r sity o f C en t ra l A rk an sa s Co nw ayA R U SA A cadem y o f M a th em a t2 ), , 100080, ic s and Sy stem Sc ience sC h ine se A cadem y o f Sc ience sB e ijing C h ina A bstrac t: In recen t yea r s, in te rva l m e tho d s a re succe ssfu lly app lied to eng inee r ing and f inance, and . h ave o b ta ined m any sign if ican t re su lt s in com p u ta t io na l sc ience and eng inee r ingSom e dom e st ic re2 . sea rch e r s a re a lso w o rk ing o n th is f ie ld a t hom eIn o rde r to le t m o re p e r so n s to unde r stand in te rva l , , m e tho d sw e w ill b r ief ly rev iew w h a t is and w h y in te rva l com p u ta t io nand in t ro duce som e in te rva l com 2 . p u t ing so f tw a re too ls th a t a re f ree ly ava ilab le th ro ugh in te rne t in th is p ap e rM o re app lica t io n o f in te rva l , , . .m e tho d s in m any a sp ec t ssuch a s eng inee r ing and f inancee tcw ill g ive in o th e r a r t ic le s : ; Key wordsin te rva l m e tho d sso f tw a re too ls 1- 3 () 为了自动核对计算结果, 摩尔 . . 于 20 世纪 50 年代末提出了区间算法的概念. 之后, REM oo re 区间算法很快就成了计算数学的一个活跃分支Λ 许多研究论文不断被发表在国际期刊上Λ 一个名为“可靠 () 计算 的国际期刊被专门用来发表区间算法方面的研究成果”Λ近年来, 这些成果在工R e liab le Com p u t in g 1 程, 金融等多方面已经取得了成功的应用Λ 我们希望通过本文将这一方法介绍给更多的读者Λ 区间算法之由来1 要说明为什么需要区间算法, 我们需要对通用的浮点算法作一点深入的了解Λ任何一个实数 r 都可以 n 被表达成 ? a . a a a ?3 10的形式. 这里 a , a , a , a , ? 为 0, 1, 2, ?, 9 中的任何一个, n 是一个整 01 2 3 0 1 2 3 数Λ 计算机内部使用二进制数Λ 为了表达一个实数, 计算机首先将它转换成二进制形式 ? b. bbb?301 2 3 p 2. 这里 b, b, b, b? 为 0 , 或 1 , p 是一个二进制整数Λ 如果 r ? 0 , 则 b= 1 . 计算机通过用一0 1 2 3 0 收稿日期: 2001210215 () 个二进制单元 序列来 b, b, b, b, ? 和指数 p , 来实现对于实数的记录和运算Λ 发布了这b it0 1 2 3 IE E E () 种表达和运算的Λ 如果用 32 个二进制单元 序列来记录一个实数, 这个标准规定用第一个单元来 b it (( ) ) 记录正负号 0 为+ , 1 为 - ; 用第二到第九个单元来记录加权后的指数 e e = p + 127 ; 而第十到第 三十二个单元则用来存储 b, b, b, ?, b, 假定 b= 1 Λ 第二到第三十二个单元都为零被用来专门存储 1 2 3 23 0 实数零Λ 标准里对于用 64 个, 128 个或更多的二进单元存储实数都作了相应的规定Λ 在以 32 单元存储实 数的机器里, 二进制小数的第 24 位之后的数位将无法被存入Λ计算机可以直接舍去第 24 位及之后的全部 小数或根据第 24 位的数值 0 舍 1 入Λ 显然, 绝大部分实数都无法被计算机精确存储Λ 这些不精确的存储 将会影响计算结果Λ 另外, 在对这些浮点表达实数的计算中, 新的误差也是会不断产生和难以避免的. 人 们通常认为, 小数点多位之后的误差应当不会对计算结果有太大的影响, 因此可以忽略不计Λ 然而, 事情 1 如果 i Ε 1 , x ;远 非那末简单Λ我们来看一个很简单的例子Λ无穷序列 {x } 定义如下: x = 1; x = i+ 1n 0 1 3 134 = x i -x i- 1 . 假如在计算机上用浮点算法来算出这个序列, 并根据数据结果来推断序列的敛散性,3 3 (人们会很容易地得到一个错误的结论Λ那就是该序列发散于无穷大 在一些计算机和计算语言下发散到正 n 1 )无穷, 而在另一些发散到负无穷. 但是用数学归纳法, 我们可以方便地证明该序列与 等价Λ 所以无 3 穷序列{ x }应当收敛于零Λ 所以, 人们不能简单地接受计算机提供的计算结果Λ 在大规模的计算中, 如何 n 确认结果的可靠性, 成为了一个极具挑战性的问Λ摩尔认识到这类计算结果的不可靠性完全是由于实数 的浮点表达和浮点运算本身产生的Λ 因此, 他提出了对计算机实数存储与运算方面一个根本上的改革Λ 2 实数的区间表达和区间算法 ? 摩尔扬弃了实数在计算机上的浮点近似表达方法Λ他提出一个实数 r 在计算机上应当用一个区间r = λλλ r, r ] 来表达Λ 这里 r 及 r 均可被计算机精确表达, 且 r Φ r Φ r Λ 在区间算法里, 这被称为表达的包含原理Λ 这样无论 r 本身能否被计算机用浮点精确表达, 区间 都包含了 r 的全部信息Λ 由于所有的实数 r 都用区间来表达, 那末对于它们之间的运算, 也必须给以定义Λ 摩尔给出的定义为: θ θ y , 若 op 为下列运算 + , - , × 之一, x = x , x] 和 y =y] 是两个区间Ζ 那末 ()1 x op y = {x op y | Π x ? x , y ? y } 0, 2 , 0, 2 - - 1, 0 = 0, 3 根据这个定义, 我们有下面的例子: 1, 2 + - 1, 0 = 和 1, λ 2 3 - 1, 0 = - 2, 0 . 从这些简单例子中, 我们注意到, x + y = z , 但是 z - y? x Ζ 在计算机上实现区间运算时, 应当注意到机器可精确表达的两个数字的运算结果可能是机器无法精确存储的Ζ因此在 () 计算机上进行区间运算时, 一切计算结果 包括中间步骤的存储都必须满足包含原理Ζ从而保证计算的可 靠性Ζ虽然区间算法的提出初衷是为了计算结果的可靠性, 但是人们很快发现区间算法可以有更广泛的应 用Ζ 从上面的简单例子中, 我们已经看到, 区间算术具有与传统算术不同的性质Ζ 另外, 由于区间本身的集 合属性, 区间之间的集合运算可以被很容易地施行Ζ 对于区间数学的研究衍生了区间这一近代数学 的分支Ζ 这一分支奠定了基于区间算法而形成的许多新的计算方法的理论基础Ζ 这些新的计算方法能够 4 可靠地解决一些传统方法难以解决的问题Ζ 例如求解非线性方程组在给定区域内的所有数值解, 整体 5, 6 优化等问题Ζ另外, 实践中许多计算参数是用区间来表述的Ζ人们可以很方便地运用区间算法把它们包 4 括在计算中Ζ 这些使得区间算法在诸如金融风险控制, 火箭喷口受力, 核磁共振机设计和机器人等应用 方面取得了一些成功Ζ 区间算法的若干软件工具3 3. 1 基本区间运算工具 人们开发了一些软件来实现在浮点计算机上进行严格的区间运算Λ 这些软件所用的语言包括 Fo r2 ? 在区间算法里许多人用黑体字符来表示区间, 而用非黑体表示实数. 字母下面加横线表示区间的下界, 上面加横线表 示上界Λ () + + , 2等Λ 克尔福特 . . 等人开发的经过了严格测试的 区间软 , , t ran C C P a sca lX SC RBK ea rfo t tFo r t ran 8 件库 可以通过因特网免费下载, 网址为 ƒƒƒƒ737Λ 这个软件库包括 : . . IN TL IB h t tp w w wn e t libo rgtom s 9 了所有的基本区间算术运算, 集合运算, 基本初等函数, 以及一些工具子程序Λ 绝大部分装有 编 Fo r t ran 译器的计算机都可以安装这个软件包Λ 胡承毅等人还开发了一个可以通过因特网直接操作的区间计算 10 , 器, 其中一个网址为: : ƒƒƒƒƒΛ 读者还可以通 . . . . h t tp w w wm sc sm uedu g lo b so lJ ava In te rva lC a lcI- Ch tm l过 ƒƒƒ2ƒ来查询用其它语言编写的基本区间运算软件Λ : . . . . h t tp w w wc su tepedu in te rva lcom p in t lan gh tm l 最近, 有一些计算机公司, 例如美国的 计算机公司, 已经在他们的商业软件中加入了基本区间计算的 Su n 功能Λ 3. 2 区间线性代数软件的一个标准 基本线性代数运算是解决实际问题中最常用的Λ从 1996 年 2 月到 1999 年 3 月, 一个国际工作小组制 定了新的线性代数软件标准Λ 其中的一项工作就是提出区间线性代数软件标准的一个草案Λ 这个草案里 包括了区间向量之间, 区间向量和矩阵之间, 区间矩阵和矩阵之间的代数和集合运算的标准Λ 计算机语言 包括 和 Λ 这个标准委员会的工作及制定的标准可从下面的网址获得: : 77, 95 ƒƒ.Fo r t ran C h t tp w w w . ƒƒ2Λ n e t libo rgb la sb la stfo rum 3. 3 两个应用软件 3. 3. 1 求非线性方程组的全部数值解 (x , ) 2 ?, f 1 x 1 ,x n n ()f x , x ,x 在给定的区域< 内, 可靠地求出下面非线性方程组所有的数值2 1 2 n 解, 是计算数学中一个基本而又 ?, D R (相当困难的问题Λ () f x , ) ()F X = 3 1 x = 02 x ,n 2 ?, fi () x , f n x 1 ,x 2 ?, n ( 区间分析对于这个问题给出了一个实用的算法: 区间牛顿对分法 in te rva l N ew to n ƒgen e ra lized b isec2 4 ) Λ 这个算法的基本思想是将上面的非线性方程组转化成区间线性方程组t io n m e tho d , () ()()k k k ()k ) () ()) (X = 2F X 3 F X′ X - , , ()()k + 1 k (())k k () 然后用区间算法解 X 并将结果置入下一步迭代计算 X ? X ? X Λ 在计算中间如果有需要的 () k ( ) 话可将 X 一分为二Λ将其中之一放入待处理的先进后出的堆栈 中, 接着对另一半进行计算Λ克尔 stack 福特等人发表了一个基于这个算法的 通用软件包Λ 这个软件包经过了严格的测试, 可从下面网址Fo r t ran 下载: h t tp : ƒƒw w w. n e t lib. o rgƒtom sƒ681Λ 为了提高运算速度, 胡承毅等人研究了这个算法的前置因子 11, 1213, 14 () Λ p reco n d it io n e r 和并行化 3. 3. 2 整体优化 n 在给定区域< 上对于目标函数 f 的整体优化问题可表述为 D R3 3 () () ()?, 使得 f X Φ f X , 4 寻找 Π X ? X D D 这也是应用和计算数学中的一个核心问题Λ 区间分析对于这个问题提出了在数学和计算方面都保证可靠 5, 6, 15, 16 14的一套算法Λ这一算法的若干软件包被开发了出来Λ其中克尔福特的 软件包 95 Fo r t ran G lo b So l 1 被较为广泛地采用, 并解决了一些有意义的应用问题Λ读者可以从下面网址获得这个软件及有关应用的 , 信息: : ƒƒƒ| ƒΛ 从这个网站上读者还可以得到胡承毅等人对这个软件包. . . h t tp w w wm sc sm uedu g lo b so l 17 的并行化方面所做的工作Λ 结论4 通过这个简介, 我们可以看到区间算法是对传统浮点算法的一个根本改革Λ把计算变量在计算机里存 储为区间, 并对这些区间来进行运算, 使得避免浮点算法所产生的计算误差成为可能Λ 区间分析还提供了 研究发展新的计算方法的空间Λ 另外, 区间算法使得区间参数能被直接包含在计算之中Λ 这在应用中也具 有实际的意义Λ所以, 区间算法是对浮点算法的一个有益补充Λ值得从事科技计算方面的工作者了解应用Λ 严格设计和开发的区间算法软件为区间算法的实际应用提供了有效的工具Λ 我们在以后专文介绍区间算 法软件在解决实际问题方面的具体表现Λ 本文是美国休斯敦大学胡承毅教授应邀访问中国科学院数学与系统科学研究院期间合作完成的Λ 作 者们对中国科学院数学与系统科学研究院提供的支持致以衷心的感谢Λ 参考文献: () 1 Co r liss G, Kea rfo t t B. R o go ro u s g lo ba l sea rch: indu st r ia l app lica t io n s[J . J R e liab le Com p u t ing, 1999, 0: 1- 16. 2 M oo re R , Yang C. In te rva l A na ly sis I[R . T ech n ica l D o cum en t, L o ck h eed M issile s and Sp ace D iv isio n, N um be r - 285875, 1959.LM SD 3 . [. ,M oo re RM e tho d s and A pp lica t io n s o f In te rva l A na ly sis M So c ie ty fo r Indu st r ia l and A pp lied M a th em a t ic s 1979. 4 . [. : , 1990. N eum a ie r AIn te rva l M e tho d s fo r Sy stem s o f E qua t io n sM C am b r idgeC am b r idge U n ive r sity P re ss . [. : , 1992.5 H an sen EG lo ba l O p t im iza t io n U sing In te rva l A na ly sisM N ew Yo rkM a rce l D ek k e r . : [. , 1996.Kea rfo t t BR o go ro u s G lo ba l Sea rchCo n t inuo u s P ro b lem sM K luw e r A cadem ic P re ss 6 , , . - [. H u C X u SYang XA rev iew o n in te rva l com p u ta t io n so f tw a re and app lica t io n sJ In t J o f Com p u ta t io na l and 7 () , 2002, 1 2: 149- 162.N um e r ica l A na ly sis and A pp lica t io n s 8 , , , . 737: : 277 Kea rfo t t B D aw ande M D u K H u CA lgo r ithm IN TL IBa po r tab le fo r t ran in te rva l standa rd func t io n li2 () 1994, 20 4: 447- 459. b ra ry [J . A CM , T ran s. o n M a th. So f tw a re, , , . 277 . 9 H u C A w ad A Kea rfo t t BO n bo und ing th e range o f som e e lem en ta ry func t io n s in fo r t ran J J In te rva l Com 2 , 1993, 3: 29- 40.p u ta t io n s 10 , . [. 1998 H ung M H u CA n o n line in te rva l ca lcu la to r M P ro c o f Co nfe rence o n S im u la t io n M e tho d s and A pp lica2 1998. 92- 97. t io n s[C . So c ie ty fo r Com p u te r S im u la t io n, 11 H u C. O p t im a l P reco nd it io ne r s fo r th e In te rva l N ew to n M e tho d s [D . P h. D d isse r ta t io n, T h e U n ive r sity o f , , 1990.L o u isianaL afaye t tJ une 12 , , . 2[. Kea rfo t t B H u C N o vo a M A rev iew o f p reco nd it io ne r s fo r th e in te rva l gau ssse ide l m e tho d J J In te rva l Com 2 () p u ta t io n s, 1991, 1 1: 59- 85. Gan Q , H u C , Yang Q. A ll2row p reco nd it io ned in te rva l linea r so lve r o f no n linea r sy stem equa t io n s o n m u lt ip ro ce s2 13 () [. , 1994, 20 9: 1249- 1268.so r s J J P a ra lle l Com p u t ing . 214 [. H u CP a ra lle l so lu t io n s fo r la rgesca le gene ra l sp a r se no n linea r sy stem s o f equa t io n s J J Com p u te r Sc ience and () 1996, 11 3: 258- 271. T ech no lo gy, 15 Kea rfo t t B , Co r liss G, H u C , Sch u lte M , S tad th e r r M . G lo ba l So lu t io n s: E n t ry P age [ EB OL . h t tp : www. ƒƒƒ , . . .m sc sm uedug lo b so l 16 , . 22R a tz D C sende s TO n th e se lec t io n o f subd iv isio n d irec t io n s in in te rva l b ranch andbo und m e tho d s fo r g lo ba l op t i2 1995, 7: 183- 207. m iza t io n [J , J G lo ba l O p t im iza t io n, , 17 . [ ƒ. : ƒƒ. . . ƒ| ƒ. .H u CP a ra lle l and D ist r ibu ted G lo bSo lEB L O h t tpwwwm sc sm uedu g lo b so lP a raG lo bSo lh tm l