（计算数学专业论文）区间多项式与区间隐式化方法.pdf

摘要 本文研究了区间多项式的零点和参数曲线的区间隐式化问 题我们首先说明了误差控制在计算机辅助几何设计和几何计算 中的重要性，并回顾了关于区间多项式的零点问题和区河隐式化同 题的研究历史和现状 我们分别讨论了单变量区间多项式和多变量区间多项式方程 组的零点集，包括实零点集和复零点集对单变苣区间多项式，证 明了n 次单变量区闻多项式最多有 个实零区间，并且证明了在 计重数时，恰好有n 个复零域，还给出了单变量区间多项式复零域 的边界线，并分别给出求解单变量区间多项式的实零区间和复零域 的数值方法我们还讨论了单变量区闻多项式的最大公因子问题 对不含重零点的区间多项式，给出最犬公因子的数值求解算法 对于多变量区间多项式方程组，我们首先证明了当区闻多项式 方程组的系数区间收敛时，它的零点集也是收敛的，然后主要以二 元区间多项式方程组为例在射影窄i h 】中讨论k 阳l 多项式方程组的 零点集，给出了和单变最区间多项式旌本甲行的结论我们给出厂 实事域边界线对于复零域，证明r 复岑域的个数定理，同样给出 了复零域的边界，并分别给出求解：，亡p ( f i l 多项式方程组的实零域 和复零域的数值方法这峰内容都不难推广到更高维的区f 魂多项式 方程组 本文最后讨论了区问隐式化方法，t 要研究r 有理b 样条曲 线的区嘲隐式化我们将问题分为求中心曲线和求边界曲线两步， 分别给出求解算法我们也给出剪法卞u 赁倒讨论区f h j 隐式化方法在 参数曲线求交中的应用 关键词：区问算法，区汹i 多项式，_ = ! = i m ，实岑域，复零域，问 多项式的最大公因，问代数曲线( 曲断j ，k 间隐式化 a b s t r a c t i nt h i sp a p e r ，z e r o so fi n t e r v a lp o l y n o m i a l sa n di n t e r v a li m p l i c i t i z a t i o n u l e t h o d sa r es t u d i e d f i r s tw ee x p l a i nt h ei m p o r t a n c eo fe r r o rc o n t r o li n g e o m e t r i cc o m p u t a t i o n w er e v i e wt h er e s e a r c hh i s t o r ya n ds t a t u so ft h e s e t w op r o b l e m s t h er o o t so fu n i v a r i a t ei n t e r v a lp o l y n o m i a le q u a t i o n sa n dm u l t i v a r i a t e i n t e r v a lp o l y n o m i a ls y s t e m sa r ed i s c u s s e d ：i n c l u d i n gr e a lr o o t sa n dc o m p l e x r o o t s w ep r o v et h a tad e g r e enu n i v a r i a t ep o l y n o m i a lh a sa tm o s tnz e r o i n t e r v a l s w ea l s op r o v et h a ti th a snc o m p l e xz e r o si fm u l t i p l i c i t i e sa r e c o u n t e d t i l eb o u n d a r i e so fc o m p l e xz e r o sa r eg i v e nw ea l s og i v en u m e r i c a l g o r i t h l n st ot h l dt h ez e r oi n t e r v a l sa n dc o m p l e xz e r or e g i o n s t h eg r e a t e s t c o l n n l o nd i v i s o r so fu n i v a r i a t ei n t e r v a lp o l y n o m i a l sa r es tu d i e d f o rm u l t i v a r i a t ep o l y n o m i a ls y s t e m s w ep r o v et h ec o n v e r g e n c eo ft h e z e r os e t sw h e na l lt h ei n t e r v a lc o e f i c i e n t sa r ec o n v e r g e n tt os o m ec o n s t a n t s w e i n a i n l yd i s c u s st h ez e r o so fb i v a r i a t ep o l y n o n f i a ts 3 。s t e m si nt h ep r o j e c t i v e s p a c e t h ec o d ( h l s i o n sa r em o s t l yp a r a l l ( ，1t ou n i v a r i a t ei n t e r v a lp o l y n o m i a l s p x ie p tt h a tw e ( a m l o tg i v et h en u n l b e ro fr e a lz e l 0r e e d ( m s w eg i v et i l t - b o u n d a r ? o fr e a la n dc o m p l e xz e r or p g l e n s a n dt h ( 、n u n l l i e ro f c o m p l e xz e r o l e g l o u s w ea l s og i v en u m e r i ca l g o r l t h m st of i n dt h er - a la n dc o m p l e xz e r l ) r e g l o 】so fb i v a r i a t ep 0 1 ) m o m i a ls y s t e m s t h e s ( 、c o i t t e i l f sa r cn o th a r dt ob e e x i t t n d e dt 0h i g h e rd i m e n s i o ni n t e r v a l1 ) o l y n o n n a ls y s t l - i n s a tl a s tw ef l l hu s st i l ei n t e r v a li m p l i c i t i z a ti o np lo l h ，l u w em a i n l yd i s 一 ( r i b st h pi l l t t ，r l 、a li m p l i ( i t i z a t i o no fr a t i o n a lb - s p l i ) u - u l v p s w es o l v et h e p 1 0 1 ) l e n li nt v , t ) s t e p s ：f i n d i n ga na 1 ) 1 ) f o x l l n a t ( i m p l ni tb s p l i n t ( i l r v ea n t i f i n , l i l t o h eb l m n d m gi m p l i fi tc a r v e s1 1 5 。o l x i n gb o l n ( 1 i n e a rp r o b l e m s ，c a 卜g i 、pa l g o r i t h ma n de x a m p l e st od 1 1 i n t ) n s t i a t pt h ea p p l i ( a t ) o no fi n t e r v a l j i l i ，! l ( i t l 7 f i t i 0 1 1i ni n t e l s e c t i o n ( a ku l a t i o no ft w dp a l ；1 l i t e rr i ( c l u y e s k p ，w o r d s ：i n n ，r v a u r l t h l a e t i ( ) l i t e l 、n lp 1 3 u o i f t l i t ，川i oi n t e r v a l r p a lz t r i j fg 】l ，lj lo l n p l ( ，xz e l or f l g i , m l l t tr 、a l a l g e b r a i c l l - 、。fi b i l l t a ( e ) i n t e r x h 1i m 1 ) l u ! ：l a ti t 1 1 v 1 1 致谢 光阴似箭，白驹过隙在科大的九年时光即将成为美好的回忆此文作 为总结 本文足在导师陈发来教授和冯玉瑜教授的悉心指导下完成的在科大攻 读博士的五年期间，承蒙两位导师从各个方面给予了极大的关心和精心指 导他们不仅教会我大量的专业知识、研究学问的方法，还以严谨的治学态 度、谦逊的为人深深的影响了我，将使我受益终身在此，谨向他们致以最 深的敬意和衷心的感谢! 在此，我还要感谢邓建桧副教授在日常的学习研究和论文的撰写过程中 给我大量的指导和帮助还有科学计算与计算机图形学实验窀的师兄弟们， 无论足在完成论文期间还足平时的学习和生活中，他们都给予_ r 我无私的帮 助另外，还有数学系的很多老师和同学在学习和生活上给我许多的关心和 帮助，在此一并表示感谢 最后，我要感谢我的父母家人，感澍他( 她) 们一直以来对我的信任 宽容、鼓励和关爱 谨以此文献给所有关心过我的人 1 1 引言 第一章绪论 几何物体造型在计算机辅助几何设计与制造中的应用已经有很长的历 史边界表示( b o u n d a r yr e p r e s e n t a t i o n ) 是几何物体造型中最常用的表示 形式然而，用边界表示的几何造型缺乏可靠性，在几何计算中，它们遇到 数值不稳定和理论上的困难解决由于误差带来的数值计算不稳定性、几何 表示不可靠性一直是计算机辅助几何设计中的重要问题随着计算机辅助设 计技术应用的深入，c a d 系统制造零件的复杂度日益提高，对误差控制的 要求也越来越严格从三维几何造型的研究现状来看，尽管几何造型系统已 在工业界得到广泛应用，系统的稳定性仍是致命的闯题 在当前的边界表示中，几何实体( 点、线、面) 被看作理想的数学实体 但实际上，只有很少一部分数学实体能在计算机中精确表示，大部分的几何 物体在计算机中都只能以浮点数来近似的表示所以严格的说，一个以浮点 数表示的几何物体是不精确的，这个不精确性起围于浮点数的有限精度，对 连续的几何物体在计算讥堕只能用离散的几何表示这蝗不精确表示会带来 几何实体的几何与拓扑表示之间的不一致性。 另一一方面，在几何计算t ，由于计算机采用的是浮点运算，正如h l l “3 1 3 2 1 ) 所指出的，由浮点算法汁算得到的数只能足近似的陶而，即使对于精确表 示的几何实体，各冲几何操作的结果也足近似的例如，求交问题一一般被转 化为非线性多项式方程组的求解，由于浮点误差，求解的结聚很可能导致一 些根的丢失典型例：f 足坏条件的求交问题( 相切交和匿叠交) 这种问题 对r 初值千计算误蔗 e 常敏感，对初值的一个很小扰动( 增加或减少数值精 度) 或许计算中中间硅的误差控制不当，就可能橄火的改变计算结果增加 数值精腹的方法在一定程度卜可以改善结果，但并不能完伞解决这个问题 文：3 2 1 中给出f 【l ! i 耳个例子说明计算误差导敛丫锚i 是f ：, 3 f 4 爆 例1 1 设一条四阶- 翠面b e ：z * e r 曲线，其控制顶点为 _ ( 5 ( ) 0 1 , 2 5 i n2 3 一o0 6 2 s ) ( o ( j 0 6 2 3 ) ( f 2 5 一i j 2 5 1 f o 5 ( ) 0 6 2 5 ) 如 垄j1 】所示，这条b f z z e ：r 曲线等价于显式曲线j ，z 4 ( 一0 5 曼zs 1 2 0 0 5 年中国科学技术大学博士学位论文 第一章绪论 第2 页 1 1 引言 h 1 。，j | “ m 、 图1 1 ：y 4 和y = 0 在原点处密切交 o 5 ) ，曲线与z 轴在原点( z ，y ) = ( 0 0 ) 处相切然而，若把曲线沿y 轴正 方向平移一个单位，再往回分三次各移动一；1 ，如果计算机中以浮点算法 似似来表示，则得到的曲线一般与原曲线不同 移l 如。假设计算机有四位尾数，误差表示方法为四舍五入而不是截尾 则有理数一；1 在计算机中是以一03 3 3 3 1 0 0 存入在进行了四次平移之 后，曲线的控制顶点变为 ( 一( j 5 o 0 6 3 1 ) f 一( j2 5 一00 6 2 4 ) ( 0 f j 0 6 3 1 ) ( o 2 5 一0 ，( ) 6 2 4 ) ，( 0 5 0 0 6 3 1 ) 此时，计算曲线在参数t = ( j 5 的值，得到( 0 0 0 0 0 3 5 ) 而不是( 0 ，0 ) 假如 用这些新的控制点来求曲线与t 轴的交点，若误差界小于0 ，0 0 0 3 5 的话，将 会无交点 上面例说明，浮眨运算f ，变皱的代数变换会使误蔗增加下面例子 指出，即使原始数据是准确的，解的过程中也会产生误差 例1 2 求一个三次显式万程g = ( ji j l ) f = r o f j ) ，一0 7 ) f 0 曼，s1 ) 与 r 轴的交。 寂们莒毛鹊该曲线转化为r n 5 f ( c t t 基形式表示，以浮点、算法运算，基 于段nr f f t ? 2 分影算法( 如胁7 jr f ，裁减方法或射影多面体算法5 9 , j ，最后 得 i 的结果是丢失了07 这个根 2 0 0 5 年中国科学技术大学博士学位论文 第一章绪论 第3 页 1 1 引言 上述这些问题使得系统的稳定性很差，效率低下，严重时甚至造成系统 瘫痪在几何造型中的稳定性问题自8 0 年代就已经广泛被提出并且一直是 很活跃的研究课题围绕关于如何进行稳定的几何表示和计算，出现了大量 的研究成果区间方法是其中引人注目的一类方法 区间算法最早在6 0 年代由m o o r e ( 4 2 ) 等人引入到数值分析计算中， 用以保证算法的稳定性其主要思想足用一段区间来代替数值不精确的浮 点数进行计算在这一领域，区间算法很快发展为一种处理计算稳定性的很 好的工具 1 9 8 4 年m u d u r 和k o p a r k a r ( 4 4 ) 开始在几何处理中使用区间 算法t o t h ，t o m 和s n y d e r 等人又将其应用于计算机图形学，c a d 领域 ( f 6 9 6 7 ，65 】) 近几年，区间算法被h u ( 3 3 ，3 4 1 ) 等引入几何造型领域，取得 很有效的结果而后，利用区间算法在几何计算中的造型表示、几何运算等 领域的工作相继出现如区间运算应用于曲线、曲面求交及几何形体的表示 ( ! ：j 2 35 】) s e d e r b e r g ( 【5 8 1 ) 引入区间b 6 z i e r 曲线来逼近一般曲线，并指出用 区| 1 1 | j 表示物体通常町以避免浮点算法中的数值扰动导致的拓扑冲突。 m 1 t 教授p a tr i k a l a k i s 小组关于区间b 样条的工作( | 6 8 1 ) ，中阿科技大学的陈发 来教授和浙江大学的壬罔瑾教授研究r 区闻b 6 z i e r 蛆线( 面) 、区问b 佯条 曲线( 面) 的边界汁算、降阶、合并等一系列相关变换“3 ( ) 1 7 1 剐) 林群 在区间b d z i e r 曲线基础上发展出圆域b z i e r 曲线来逼近一般曲线f 5 3 1 在几何计算中，很多问题鄙可以归结为非线性多项式方程组的求解，例 f f l 曲线、曲面的求交问题等多项式的求根问题在理论研究和实际成t i 中都 具有煎嘎的意义这个问题有着悠久的研究历史和大鼍的研究成粜，然而由 1 二f u j 题本身的复杂性，各种方法都存在r 一些缺陷，很难找到一种完全令人满 意的方法。而问题本身义 分霞要，新的研究成果仍在不断涌现。 该r d j 题义可以分为精确求解和数值求锯两类方法精确求解包括单变 鼙多项式的实根隔离锋法和求解多元多项式方程组的( ；r o b n e r 基方法( 6 】： ) ，结式方法以及哭( 文俊) i f 7 4 j 方法等这鹫方法运舒链都比较犬，而 j = 必觚进行大整数的运算，虽然也有很多针对提高这砦算法效率的研究，彳日 总的艇蜕效率仍然较低，在实际膨用中碰到的往往又足浮点刊数据，如何彳 | 奇 的处理浮点运费，也足个很人的i u 题 彰 值锋法包括迭代法和区问方法等。这类方法在科学r 程汁露中广泛采 h j ，效率棚对较高，但j 稳定性和误差都较难控制迭代法初值的选取和收 2 0 0 5 年中国科学技术大学博士学位论文 第一章绪论 第4 页 1 1 引言 敛问题郁较难克服，并且很难求出方程组的所有解区间方法在这一问题的 研究中发挥了重要作用，近年来有很多新成果出现。其主要思路是给定一个 初始区问( 在高维时为超长方体) ，通过迭代或细分逐步缩小这些区间( 超 长方体) 得到一系列的区间( 超长方体) ，并保证方程( 组) 的根落在这些 区间( 超长方体) 内当计算精度足够高时，这些区间( 超长方体) 的宽度 可以达到任意小，从而得到原方程( 组) 的近似根具体的算法请参考文献 f 2 ，1 5 ，2 6 ，2 7 ，4 3 ，4 5 】等 由于多项式的根本身对系数的扰动可能非常敏感，数值计算的稳定性很 难得到保证例如i ( x ) = ( z + 1 ) ( z + 2 ) ( z + 1 9 ) ( x + 2 0 ) 有2 0 个实根， 而，( z ) 一1 0 曲z 1 9 有1 4 个实根、6 个虚根( 文献【7 3 1 ) ，而且相当一部分根 不在原来2 0 个根的附近这使得带误差的数值算法很难保证稳定性尽管 我们可以从理论上保证，当多项式系数的扰动趋于零时，扰动以后的多项式 的根会收敛至原多项式的根，但足很难有理沦结果可以保证究竟这个扰动多 小时，扰动后多项式的根才能落在原多项式的根的某个指定的e 一零域内 而实际测量的数值总是带误差的，在实际应用中遇到的多项式的系数往往不 是精确值，而是存在一定的误差为此我们有必要研究区间多项式的根，即 在某个给定的多项式的“邻域”内的所有其他多项式的根对于一个系数带 误差的多项式( 方程组) ，我们将其系数看作是包含误差范围的一个区间， 并求出这个区间多项式( 方程组) 的零域如果这砦零域的直径都很小，则 我们认为求出f 原带误差的方程( 组) 的解若零域的直径不能满足给定的 要求，则必须增加给定系数的精嗟。 对于系数带误差的线性方程组，目前已有较多的研究，例如文献f 1 0 ：40 1 ， 4 b ：4 9 ，5 4 5 5 6 4 l 等等求解区悯线性方程组的最佳区间解问题已被证明 足n p 问题( i ) ，在实际j j j 田巾，通常需要在求解速度和解的精度之闻做 一定的权衡和取含关j 二 e 线性区蝴多项式的求根叫题，h 前也自 一些研究 出现文献j 黯l 考察单变量区闻多项式的边界，给出r 单变鲢i 2 问多项式的 芟根刻画和求解在文献i 2 2 7 中，h j r r i i a 等主要从求根公式入f ，讨论了 低次孽变量i x 问多项式的实根辑l 复限分布，在文献f 2 捌中，义讨论r 一类特 殊的v - l b 】多项式方群组l 不禽交义项) 实根的分布文献四：刚给出了单变 鲢x 问多项式零点盼棱的上界这蝗都楚。些零散的结哭，而笑于区闻多项 式方程纽和尚次啦，笾够k 多项式的复零点，鲜有丈献提及。本文将对区间 多项式的岑点做个较为伞面的讨论 2 0 0 5 年中国科学技术大学博士学位论文 第一章绪论 第5 页 l1 引言 在计算机辅助几何设计中，除了b 6 z i e r 曲线、曲面与b 样条曲线、曲 面等参数表示形式外，隐式表示( 代数表示) 是另一类有效的表示方法一 条隐式曲线可以由多项式方程f ( x ，y ) = 0 定义类似的，一个隐式曲面则由 多项式方程f ( x ，y ，z ) = 0 定义与参数表示相比，隐式表示具有以下优点 1 易于判别一个点是否在曲线或曲面上； 2 易于表示封闭的形体； 3 在几何操作( 如求交、并等) 下，运算封闭 当然，代数表示也有一些缺陷如通常有多个分支，形状不易控制，绘制算法 较复杂等不过，鉴于代数表示的优越性，它仍然是一种可取的表示手段 如果同时拥有曲线曲面的参数表示和隐式表示，将是极为方便的事 从经典的代数几何可知，任何有理参数曲线、曲面都可以精确转化为隐 式形式，这一过程称为隐式化有理曲线、曲面的隐式化方法已经有较多的 研究，前面所提的多项式消无理论，包括g r 6 b n e r 基，结式方法和吴消元法 等，部“r 以直接用于有理曲线曲面的隐式化结式方法是求曲线曲面隐式 方程的有效力法遗憾的足，当曲面具有基点时，该方法失效g r 6 b n e r 基 疗法和吴，玎法对任何曲线曲面都适用，不过他们的效率较低，因而不太实用 动曲线与动曲面方法和p 基疗法( ( 6 2 2 l 】) 是s e d e r b e r g 和陈发来等提出 的一种令新的曲线、曲面隐式化方法如何求一般有理曲面的p 基仍足个 十分有鼓义的研究课题。最近，王东明( f 7 l j ) 提出了一个非常简单的方法： 将f i 线或曲面的隐式疗程( 对菜一给定或估计的次数m ) 写成待定系数的 形式，再将所给的参数表示代入该隐式方程并令其关于参数各次幂的系数为 0 ，：r 是得到一一组关1 ：待定系数的线性方程所给曲线或曲面有次数小f 等 ：m 的隐式方程当h 仪这组线性方程存非零解由于生成的线性疗程组 足部分一i 角化的而且通常足稀疏的，因此不难确定它足否有非零毹并求出它 的唆解，从而得到要；求的隐式方程 然而f 精确隐式化方法得到的隐式方程通常具有较高次数，饭易出现多分 乏，雁f 二控制，缺少实用价值另外，由 = 计算机浮点运算或给定的初始数 据的i 饕笼，得到的通常也j 楚近似结果，所以可以直接考虑低次的近似隐式 化止i ；近年夹涌现r 系列i ：作f j 1 4 5 8 2 5 7 2 j 9 ：等j 如面刀述，近似片法造成的微小淡蔗呵能会造成儿何操怍的不 u j 靠性0 2 0 0 5 年中国科学技术大学博士学位论文 第6 页 第一章绪论1 2 区问算法及其基本性质 不稳定性，例如边界求值和曲线求交的不可靠性，几何实体的几何与拓扑之 间的不一致性等等区间方法是解决这些问题的很好方法 结合近似隐式化和区间算法这两方面，我们考虑区间隐式化方法，即寻 求一条低次的区间隐式嗌线包含给定的参数曲线文【2 0 】考虑了有理b f i z i e r 曲线的区间隐式化问题，本文将讨论有理b 样条曲线的区间隐式化方法 1 2 区间算法及其基本性质 区间是指实闭区间 a ，砩：= z l a z 6 若a = b ，则称【a , b 】为一 个退化的区闻两个区间【a ，6 1 ，【c d 】相等，指的是a = c ，b = d 区闻【a 6 1 的宽度定义为钟( 【n 6 1 ) ：= b a ，中心定义为c f k6 】) ：= ( a + b ) 2 由所有 有界闭区间组成的集合通常记为i r 对于该集合上定义的代数与区闻运算 以及区间函数，在m o o r e 的经典著作。区问分析( i n t e r v a la n a l y s i s 4 2 ” 一书中，均作了详细讨论在这里我们作蝗简要的叙述 区间算法定义为 n ，b 】。f - d j = t cg f f “q 9 f c d l ( 1 , 2 1 ) 其中，。 4 - ，一，：) 乘法运算符通常用“”代替或者直接省略 其体地来说，即为 陋b l + f c d 】= k 斗( ：b + d j 【a 6 j i c ：d 】= f a d b t f n b 1 【c d j = f r a i n ( a ( a d kb d ! i l l a x ( a c a d b c b d ) 1 ( 1 22 ) 川他捌； m i n ( 磬孙删焉跨1 t 啡川 这啦，当o hd 】时，除法运锋足- e ；g 义的不过在有些应用中，也可以将 除法运算的结果定义为两个分别延伸到t t ：、负无穷的区间 除了以卜四种属衣运茸以外，我f 【j 迎”r 以对| l j 定义其他的运算例如 对 二单庀的连续函数r ，我们定义 2 0 0 5 年中国科学技术大学博士学位论文第7 页 第一章绪论1 2 区问算法及其基本性质 这里的r 可以是开方，三角函数，指数函数，对数函数，取绝对值等等 这样对于一般的一个函数，( z - ，z 2 ，z 。) ，我们就可以对其进行区间运算 川n ，6 t 】【a 2 ，6 2 l ，【a n ，k 】) 由区间运算的定义，很显然的，我们有 命题1 2 1 区间运算满足以下性质 j ，若【0 1 b l 】c 【a 1 ，6 1 】，一“，k lc 【磊k 】，则 ，( 【o ，“】，一，【a 。，k 】) c ，( a 1 ，b 1 ，【k ，州) 2 若z l 【a l ：6 l 】，z 。【a n ，k 】，则 ( z l ，z 。) 川n t ，6 - 】，k ，6 n 】) 这里第二条性质足第一条性质的特例，这条性质表明区间运算的结果将 包含原函数在这些区间上值域，即 r ( ，；l ”6 1 ，【k ) ：= ，( z 1 ：z 。) ：z l 【a l ，6 l 】：- i n f a 。，k 1 ) ( 1 2 4 ) c f ( a 1 6 ，卜，k k 】) 这止足区问运锋得到如此广泛应用的关键性质 且：如1 2 】式所定义，单步区i 日j 运尊的结果恰好是相应的实数运算操作 的值城 玎对于复合的运算，区间运算的结果通常会放大例如在z f 0 1 1 上考虑 ，) = 丁2 一z ，实际的值域为! 一1 4 o j ，丽区间运算的结果为 o 1 】2 一f 0 1 】= o 1 1 岍f 0 1 】= 1 1 】 运钟结足披放大j r 这足由i ：在区间运臂的过程中，z 2 项和一z 项中的t 被从为是h i t 独z 的变量，这样0 2 1 和12 0 都包含在区闻运算的结果 i i 。乃外，如果我“j 将( 1j 写为，( z j = f ，一lj ，则 0 】j jj 。一1 j 、= ；01 一1 t j ! = ：一1 0 】i _ i 1 ： 这说日q 埘填敬运锋等价的蛹数形式在陋j 运算v 会得到不同的结果 ：瞧l j 叫问运算的加法和乘法满足交换律和结合律，但是乘法对加 法的分m ： 扛一般彳：再成：t 事实i ：没：，：! ：。：为j 个区间则有 l z j ( ：j + ：z j ) cl ，；i ；一rf j f 2 j 1 2 5 ； 2 0 0 5 年中国科学技术大学博士学位论文第8 页 第一幸绪论l2 区间算法及其基本性质 反方向的包含关系不一定成立例如取h = f l ，1 1 ，m = 【0 ，1 】，吲= 卜1 ，0 】，则h ( + 【z 1 ) = 卜l ，1 】而【x l v 1 + 吲【z 】= f - 2 ，2 】不过对于z r 和恒1 ，嘲i r 我们有 z ( 可】+ 【z 1 ) = z 【可】十z 【z 】( 1 2 6 ) 区间运算存在加法零元【0 ，0 】，但对一般的h ，不存在加法逆元，即 z 】一f z 】【0 ，o 】例如 f 1 ，2 】一f 1 ，2 】= f - - 1 ，1 】【0 ，0 区间运算存在乘法么元【1 ，l 】，但对一般的f z 】，不存在乘法逆元，即 m ( 1 i x ) 【1 ，l 】例如l f l ，2 】= f 1 2 ，1 】而 1 1 ，2 】i ：2 ：1 】一【1 2 2 】1 1 ，1 】 以e 这些性质使得所有区间组成的集合i r 对加法和乘法不能构成一个 环关于，冀的代数性质的详细讨论请参阅相关参考文献( 【1 4 2 3 9 】) 实际上，如果按式1 2 2 进行浮点运算，则不能保证边界的舍入数据能 完全落在区f 日j 内浮点数在计算机里足有固定的长度的，表示浮点数的字节 数依赖f 变量的精度例如，采用i e e e 标准，一个双精度的数有6 4 位，8 个字节长，以一二进制存储，( 士) m 2 “p ，其中m 足尾数( o 5sm 1 ) ， c x p 为指数若工和z 7 是连续的正的舣精度的数，它“j 的差( 称为“咖( 最 后一一位的学位) ，f = 25 3 矿2 p = 2 e x p 一” 加入舍入误差后，运算的结果就町以保蹦：落入最后的区间内 舍入区阳j 算法( r i a ) r b j 一一川= h + ，一( 、b + d + f j t f rd j = ! d d f 6 r + f i m 州h ( f j = f r a i n a t ，a d k b d j e m a x i a d b c b d ) 十f 1( 1 , 2 7 ) “一r 川= ! m i w ：；，一m a x i ；：；d b ) + ，】。f ，卅 j ：面公式中， t = 2 ”一曲3 ，其中“p 足每个参加计蘑的数的上界或下 2 0 0 5 年中国科学技术大学博士学位论文第9 页 第一章绪论1 3 区间多项式 1 3 区间多项式 区间多项式是指系数是闭区间的多项式我们可以在多项式的各种基 ( 较常见的有幂基和b e r n s t e i n 基等) 下讨论，本文主要讨论幂基下的区间 多项式区问多项式可以看作是多项式的集合 m ，= 莓吲x o = 莓斛：厶叱1 ) s ， 口oj 这里x = ( x 1 2 7 2 ，z 。) ，q = ( q 1 ，n 2 ，o 。) 是多重指标，【，0 l 是实闭 区间，我们只考虑有界的情形 区间多项式【，( x ) 的宽度定义为 u 州，】( x ) ) = m d x ”( 魄i )( 1 3 2 ) o 这里1 , ( 瞻】) 足指实闭区间的宽度 两个区问多项式 ，】( x ) 和【9 1 ( x ) 的加、减法和乘法很自然的定义为 ，j ( x ) 士洲x ) = 】4 - ) x 。 f i ( x ) 恻x ) ：e 。( i ，0 1 。州 1 舢 n 矗 这望我f | j 需嘤注意，对f l x ：f h 3 多项式的加法，若h ( x ) 肌x ) + m ( x ) ， 则存在f ( x ； 门x ) 9 i x j 翻f x ) 使得，( x j 十v ( x ) = h ( x ) 也就是说，如 果我们记 p i l l 、( 【f i ( x j ：1 f x j ) ：= f ( x ) 斗9 ( x ) ：厂( x ) f ，】( x ) o ( x ) b ( xj ) 则有 p l u s ( ! 一x j ( x 1 卜f f r x ) + 引( x ) ( 1 34 ) f q 样的，这条性瞬z i k 问彩巧i 式的减法也成。z 化对乘法，卜述性质不再成 迂我们记 p r o d ，r _ l x q i x ；j ：一 厂i x ) - 9 i x l ，f x j ：f j ( x ) 9 f x ) j i x ) ) 2 0 0 5 年中国科学技术大学博士学位论文第1 0 页 第一章绪论 13 区间多项式 则有 p r o d ( i f ( x ) 【9 】( x ) ) c 【y l ( x ) - 【9 j ( x )( 1 3 5 ) 反方向的包含关系通常不再成立例如设 f ，j ( z ) = ( 1 ，2 i x + 【3 ，4 】 【引( z ) = 0 ，1 i x + f 1 ，2 】 则 【h l ( x ) ：= 【，1 ( z ) 【9 l ( x ) = 【o ，2 1 2 2 + 【1 ，8 i x + 【3 ，8 1 易知若 ( z ) 是p r o d ( f ( x ) ，【引( z ) ) 中的一个线性多项式，则有 h ( x ) ，j ( z ) 1 ，2 】= 【l ，4 】。+ f 3 8 】 故8 z 十8 【，】( z ) 【9 1 ( z ) 但8 z + 8 p r o d ( f l ( x ) m ( z ) ) 这种单方向的 包含关系将导致区间运算过程中宽度的扩张不过不难征明，f 麒x ) 引( x ) 足包含p 1 ( 【州x ) m ( x ) ) 的“最小”区间多项式也就足说若区| 日】多项式 旧f x ) 包含p r o d ( f ( x ) 引( x ) ) ，则必有 【，】( x ) 【9 】( x ) c ( x ) 另外区f b i 多项式的加法满足结合律 ( f ， ( x ) + 【g l ( x ) ) 4 - 昨l ( x ) = 【f i ( x ) + ( ：q x l 。f j ( x ) j 但一般来说，乘法的结合律不再成立乘法对加法的分配律也只有单方向的 包含关系 点l x j ( ! 棘x ) 十胁】( x ) ) c 【h c x ) ：f i i x ) 斗：h i l x 矾x ) 请看f 例l 文献i 7 7 ) 例1 3 给定三个一无区i 司多项式 f f ) x i = f 12 37 奠4 ： b 】( ，) = 【一1 2 j 3 + 1 2 3 ： ( z ) = f 1 3 i x 2 0 0 5 年中国科学技术大学博士学位论文第1 1 页 第一章绪论14 区问隐式曲线 按照上面定义的区间多项式运算法则，有 ( 【，】( z ) 9 】( z ) ) 【州( z ) = ( 一6 ，1 2 x 3 + 【6 ，4 2 z 2 + f 6 ，3 6 】 【，】( z ) ( 9 】( z ) 【州( z ) ) = 一6 ，1 2 x 3 + 卜t 0 ，4 2 z 2 + f 6 ，3 6 】 可以看到，( f l ( x ) ( z ) ) 【州扛) f t ( x ) ( m ( x ) 【脚( z ) ) ，即乘法无 结合律另外。 【 】( 卫) x ( i ，】( t ) + 【9 】( z ) ) = 【0 ，1 2 x 2 + f 5 ，2 1 x 【 】( z ) 【，】( z ) + 【 】( z ) b 】( z ) = f 一2 ，1 2 1 2 2 + 1 5 ，2 1 z 即乘法对加法不满足分配率 所有区间多项式组成的集合记作i r x 】由于r 不是环，1 r x 】也不 是环事实上，从上面的讨论我们可以看到l r x 1 对乘法甚至不能构成一个 半群这使得关于多项式的很多概念不能直接推广到区间多项式，例如多项 式的困子分解和最犬公【天l 子等这些我们将在后面的章爷中讨论 1 4 区间隐式曲线 1 4 1区间代数曲线 平面区同代数f l 扦线足指系数含问的代数曲线 m 1 ：= z 2 矿= = f 1 ) 】 ( 1 _ 4 1 ) 0 1 t + j m 这晕f ，t ，j = 匕，7 叫足嘲问，i o i 足指任意的含【) 区问。 区间代数曲线。，以再作是区问多项式的零点囊 z ( ! ，n j ，= t m 叫n _ 二，lj j f ，】( z ) ht “聃1 j = o ( 1 4 2 ) 由于二对f e 卷的t 1 ：l 常数0 ，* ry ) = 卡盱，i ，v ) = f o j 表示的足 同一区f i t 匕数曲线，孜对区l h j 代数曲线作规范化使得 。，i ，i u i x ，。：c ：工，】) ! = 1 ( 1 4 3 ) 2 0 0 5 年中国科学技术大学博士学位论文 第1 2 页 第一章绪论 l4 区间隐式曲线 这里c ( 阢，1 ) 表示闭区间【厶】的中点 区间代数曲线( 1 4 1 ) 的宽度定义为 ”( 1 1 1 ) 2 两蒜。t + j m 州伽 这里 ( 】) 表示闭区间 厶j 的宽度 区间代数曲线( 1 4 1 ) 的中心曲线定义为 ( c ，1 ) ( 啪) ：= c ( ) 矿= 0 ( 1 4 4 ) ( 1 4 5 ) 易知区间代数茁线( 1 4 1 ) 在四个象限中的边界线分别是不同的代数曲 线例如它在第二象限的两条边界为 ，z 2 矿+7 一! ，= 0 o j2 + j m ti se v e n 0 1 i + 3 1 t r i ，2bo d d - - h z 7 矿+ 驴矿= 0 0 1 2 十j ! t n tl se v e n 0 1 l 十j m ，li so d d 在其他三个象限中的边界线也具有相似的表达式由于区间代数嗌线( 1 4 1 ) 的边界比较复杂，所以我们寻求用其他的基函数形式表示的区问代数曲线( 衄 线段) 在计算机辅助j l l q 设i 十中，多项式的b e n l s t e i n 基荫敬足较常用的基 两数，相比幂基它有很多优点所以我们考虑b t ，r n s t e l ng - 函数下的间代 数f l f 线段和参数b 以j f ，r 曲面类似，b e r n s t e m 荩函数f 的代数瞧线段也分 为矩形域 - 6 j 张壁墓表示和三角域上的霞心坐标表示两种形式 1 4 2 矩形域上的区间代数曲线段 张酵肇衷，的脚隐式b d z i e l 瞌线段足指 豫丁，j 这翌1 7 = z ，。，j ，。j 是b e r n s ”i ，- 蘑函数 州牡蕊高州1 叫一t ( 1 4 6 ) o = 彩 哆 r 蟛， 。舢 。 2 0 0 5 年中国科学技术大学博士学位论文 第1 3 页 第一章绪论1 4 区问隐式曲线 一般b e r n s t e i n 基函数的自变量取值范围都是在f 0 ，1 1 内，所以这里的代数 曲线段f ，】( ，y ) 也是在f 0 ，1 】x 0 1 】上考虑的其他范围内的曲线段通常需 要作平移和伸缩使它落在这个范围内 和幂基表示下的区间代数瞳线一样，我们也可以定义区间隐式b 6 z i e r 曲 线段( 1 4 6 ) 的规范化，宽度，中心曲线等 。垡m 椰a x j 。厶】) l = 1 叭【，】) 2 两赤面萎叫1 ) e c ( 圳) ：= r ( ) 刀( z ) 骘( ”) = 0 由于b ，( z ) 叼【可) 0 ，区闻隐式b 6 z i e r 曲线段( 1 4 6 ) 的边界线足下 面两条代数曲线 l = 0 0 t 一0j = 0 f - - 。3 卵( z ) 譬( 弘) = 0 _ ，。蟛“( 丁) 碍( 9 ) = 0 这里我们注意到，如果在( 1 46 j 中我们用其他基卤数替换b e r n s t e i n 基 函数，则可以得到各种类型的问隐式曲线例如如果我们采用b 样条基， 则可以得到l h j 隐式b 样条f 线我仃】在第四章中将利用这种区间曲线来 做参数b 样条衄线的区间隐式化刚题 1 4 3三角域上的区间代数曲线段 给定乎面 ：的一个三角形t = a t l t 2 t 3 ，设( m ”) 是这个三角形 卜的重l - 坐标，在二角形t 内定义的区问隐式b 6 z i e r 曲线段足指 叭川u ) * 渺a i 删，u ) = ( 1 4 7 ) 一 一一 这咀， j = z ，啪：) & l 魂i x ! h j ，口墨? ”n “) 是b e r n s t t i n 基蛹数 口飘f u u j 一1 1 1 。u t 2 ，u 2 + j + 七= r n r