（计算数学专业论文）连分式中若干问题的研究.pdf

连分式若干问题的研究 摘要 本文分为三个部分，具体情况如下： 在第一章中，讨论t h i e l e 型有理插值的存在性问题。逆差商是t h i e l e 型 有理插值算法中的一个重要构成部分，我们分析了逆差商在什么情况下是存在 的，并分析了在逆差商存在的基础上，什么时候下会出现不可达点，而且所得 的结论具有很明显的几何意义。 c b r e z i n s k i 和a l e m b a r k i 曾经给出了极限周期连分式的收敛性定理 并给出了相应的截断误差分析，w j t h r o n 也给出了在某些假定条件下的改进 的截断误差分析，赵欢喜和朱功勤提出了向后三项递推关系式。在此基础上， 本文的第三章利用向后三项递推关系式给出了一类极限周期连分式的截断误差 分析。 在c a g d 中，曲线和曲面的表示一般有两种：参数表示，隐式表示；相对 于参数表示，隐式表示有着独特的优点。在第四章中，提出一种新的隐式化算 法。 关键词：t h i e l e 型有理插值、极限周期连分式、隐式化算法 o ns e v e r a lq u e s t i o n sa b o u tc o n t i n u e d f r a c t i o n s a b s t r a c t m a i nc o n t e n t so ft h i st h e s i sa r el i s t e da sf o l l o w s ： i nc h a p t e ro n e ，t h er e l e v a n t1 i t e r a t u r ei s b r i e f l ys u r v e y i n c h a p t e rt w o ，w ed i s c u s st h ee x i s t e n c eq u e s t i o n so ft h i e l e t y p er a t i o n a l i n t e r p o l a n t s o n e o f i m p o r t a n tc o n s t r u c t i n g e l e m e n t so f t h i e l e t y p e r a t i o n a l i n t e r p o l a t i n ga l g o r i t h mi s i n v e r s ed i f f e r e n c e ，t h ee x i s t e n c ec o n d i t i o n so fw h i c ha r e a n a l y z e d f u r t h e r m o r e ，w ea n a l y s i st h ea p p e a r a n c eo fu n a t t a i n a b l ep o i n t sw h e n i n v e r s ed i f f e r e n c ee x i s t s ，a n dt h er e s u l t sw e g e ta 比o f c l e a rg e o m e t r i cs i g n i f i c a n c e i nc h a p t e rt h r e e ，t h et r u n c a t i o ne r r o ro fas e to fl i m i t e dp e r i o d i cc o n t i n u e d f r a c t i o n sw a so b t a i n e db yu s eo fb a c k w a r dt h r e et e r m 忙c l i r r e r l c ej e l a t i o n s i nc o m p u t e ra i d e dg e o m e t r i c d e s i g n ，c u r v e sa n ds u r f a c e sg e n e r a l l yh a v et w o k i n d so fr e p r e s e n t a t i o n s ：p a r a m e t r i co n ea n di m p l i c i t o n e c o m p a r i n gw i t h t h e f o r m e r ，t h e l a t t e rh a s s p e c i a la d v a n t a g e s i nc h a p t e rf o u r ，w ep r e s e n tan e w i m p l i c i t i z i n ga l g o r i t h m ，w h i c hi sa l s or e l i a b l et os u r f a c ew i t hb a s ep o i n t k e y w o r d s ：t h i e l e t y p er a t i o n a li n t e r p o l a n t s l i m i tp e r i o d i cc o n t i n u e df r a c t i o n s i m p l i c i t z i n ga l g o r i t h m 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕士 学位论文质量要求。 答辩委员会签名：( 工作单位、职称) 主席：咖殇 委员： 蒙矽勃 发哳段 刷瓢 乃 今多六 詹步久 旅旋 放镳 秘，久铍位 a 胁似互二私以、 独创性声明 本人声明所呈交的学位论文是本人在导师指导r 进行的研究工作及取得的研究成果。据我所 知除了文中特j ；| j 加以标忐和致谢的地方外论文中不包含其他人已彝技表或撰写过的研究成果 也不包含为获得 佥壁工业盔堂或其他教百机构的学位或证书而使用过的材料。与我一同t 作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明井表而谢意。 学位论文作者签字：刍他李箍字日期：刀眄年# 月日 学位论文版权使用授权书 本学位论文作者完全r 解佥墨兰些盘堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送芟论文的复印件和磁盘，允许论文被查阅或借阅。本人授权盒里兰些厶 ! 鲞可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论史在解密后适用奉授权书) 学位论文者签名 刍枢绪 导师签名 忍节驴 签字日期：掬群6 月f 日 签字日期：时月日 学位硷文作者毕业后去向 工作单协： 通讯地址： 电话 邮编 致谢 在论文完成之际，首先感谢合肥工业大学给我这个学习和提高的机会，特别是我 的导师唐烁副教授多年来对我的悉心指导，借此机会向他们表示衷心的感谢! 在学习和论文的写作过程中，唐烁老师给予了我极大的关怀和帮助，从论文题目 的确定、实施方案的制定、具体工作的进展以及最后论文的撰写与修改，无不渗透着 导师的智慧和心血。 同时还要感谢檀结庆教授，黄有度教授的教诲。盛后要感谢赵前进博士，王强博 士及1 0 0 3 室的同学们，感谢他们无私的帮助。 作者：土旭辉 2 0 0 5 年5 月 第一章绪论 函数的近似表示通常就是设法把它写成自变量的多项式的形式，虽然多项式 是函数一种非常好的逼近工具，但多项式也有它的不足之处。主要因为多项式是 幂级数的特殊情况，其在一点附近的性质就确定它在整个实数轴上的性质，而这 种特性恰好是许多物理现象所不具备的，这导致了1 9 4 6 年i j s c h o e n b e r g 开 创了样条这个新的逼近工具。但对于具有极点的函数来说，采用多项式、甚至多 项式样条作为逼近工具，显然都是不大合适的，可以想象采用多项式的另一种最 简单的推广一一有理函数作为逼近工具是恰当的。不仅如此，而且用有理分式逼 近去求所给函数的零点与极点是很方便的，因为这时所要解的那些代数方程的次 数比用多项式逼近时更低一些。还有，在用有理分式通分时，无需计算自变量的 高次幂。然而对于有理函数而言，也存在一些局限性。如：事先任意给定的插值 条件，有理插值函数并不总是存在的，而其他结果，诸如唯一性、算法、误差估 计等，在叙述其结论时也总是假定所讨论的有理插值函数是存在的，如果存在性 问题得不到很好的解决，势必影响这些结果在使用上的确定性。因此无论从理论 上还是从实际应用上，有理插值函数存在性的研究都显得至关重要。而t h i e l e 型连分式有理插值作为一种特殊的、便于计算的有理插值方法。在实际中的应用 越来越广泛，因此更有必要分析一下他的存在性问题。 在很多数学分支中，连分式有着很广的应用背景，而连分式的诸多应用都与 连分式的收敛性联系在一起，从中可看出连分式的收敛性在连分式理论中的地 位。另一方面跟随而来的一个重要问题就是连分式的截断误差分析。讨论连分式 收敛性的最一般的方法是基于值域技术，有三种常见方法，一种方法可导出截断 误差界，即它的收敛证明是构造性的另外二种方法不能给出连分式的收敛速 度，即它的收敛证明是存在性的。作为一种特殊形式的连分式一一极限周期连分 式有着它本身的收敛特点，在 1 4 中，c b r e z i n s k i 和a l e m b a r k i 给出了相应 的结论。w j t h r o n 也给出了在某些假定条件下的改进的截断误差分析。本文则 是从另外一个角度给出了截断误差分析，从而构造地说明了极限周期连分式的收 敛域。 在c a g d 中，曲线和曲面的表示一般有两种：参数表示，隐式表示。而这两 种表示方法也各有其优越性。相对于参数曲面，隐式曲面具有很多优点，除了在 概述中已提到的之外，隐式曲面还具有简单灵活的表现形式，更易于表现立体形 状，比如，基本的三维形体，其外形，包括各类二次曲面，都可以用简单的代数 曲面来表示。而且，用于进行造型设计的代数曲面次数较低。由于隐式曲线曲面 的使用率越来越高，因此，参数曲线曲面的隐式化就成为了引人关注的问题。现 行的隐式化方法有：结式方法，g r o e b n e r 基方法，w u r i t t 方法，动曲线和动曲 面方法，基方法等。结式方法是一种有效的方法，但遗憾的是，当曲面具有基 点的时候这种方法，该方法失效。g r o e b n e r 基方法，w u r i t t 方法虽然对任何的 曲线和曲面都适用，但他们的效率不是很高。动曲线和动曲面方法的效率虽然比 结式高，但如何选取相应的混合函数还没有自动的方法。基方法是建立在动曲 线和动曲面方法的基础上的，是一种十分有效的方法。 本文主要分为三个部分，具体情况如下： 在第一章中，我们讨论了t h i e l e 型有理插值的存在性问题。逆差商是t h i e l e 型有理捅值算法中的一个重要构成部分，我们分析了逆差商在什么情况下是存在 的，并分析了在逆差商存在的基础上，在什么时候下会出现不可达点。而且所得 的结论具有很明显的几何意义。 在第二章中，针对极限周期连分式，本章利用向后三项递推关系式给出了一 类极限周期连分式的截断误差分析。这样我们就补充了文 1 7 】中的一些结论。 在第三章中，对于隐式化问题，我们提出了一种隐式化算法来进行参数曲线 和曲面的隐式化。 第二章t h i e l e 型插值的一些分析 本章对t h i e l e 型有理插值的构造元素一一逆差商进行了相应的分析，得出 一些判断标准，我们可以用这些标准来判断直接使用t h i e l e 型有理插值是否可 行。 2 1 有理插值的一些背景介绍 插值方法是函数逼近的一种方法，利用它可以通过函数在有限个点的取值 情况，估算该函数在其他点处的值。此外，插值方法还是导出其他许多许多数 值方法的依据( 如数值积分，数值求导) 。多项式插值理论与方法已经相当成熟， 而有理函数插值的理论和方法比多项式插值要复杂得多，其主要表现是有理插 值问题有解是有条件的或者说有理插值并不是总有解的：另一方面有理插值在 处理非线性问题上也有它的特殊的优点。 有理插值问题的一般提法和其存在唯一性 有理插值问题的一般提法： 设( 耳，咒) ，i = 0 ，1 ，聊+ h 是与y = f ( x ) 有关的m + n + l 互异， 儿= ，( t ) ( i = o ，1 ，r e + n ) 。 求有理分式函数 u 加器= 蒂篇 使之满足如下条件 个型值点，其中x ( 2 1 ) ( 咿粼叫砂刚，1 ，肌行 ( 2 2 ) 称而，x i ，+ 。为插值节点，一= f 如) o = o ，】，m + 胛) 为型值。式( 2 2 ) 称为 插值条件， 式( 2 1 ) 中的如。( 工) 称为插值函数，f ( x ) 称为被插函数。 为了简便起见，记n = m + ”，p 表示次数不超过，的多项式集合， o n = ( 而，y j ) i i = 01 ，m + n 分子、分母次数分别不超过m 和h 的有理分式函数 集合记为r ( m ，n ) ，非负数偶( m ，r 1 ) 称为有理插值问题的次数类型。如果有理插值 问题( 2 1 ) 和( 2 2 ) 的解存在且唯一，则称插值问题是适定的，而此时 蕾( f = o ，1 ，n ) 称为适定节点组。 对于有理插值问题( 2 1 ) 和( 2 2 ) 的解需要解如下方程组 怒毗) ( 剐，l i - - ，) 很显然，当如。( x ) = p ( x ) q ( x ) 是插值问题( 2 1 ) 和( 2 2 ) 的解时，q ( 誓) o ，所 以有 q x ：一”( 6 j z ：) = 0 ，( ，= o ，l ，) ( 2 3 ) 定义2 1 【叼 对于两个有理函数马2 云及矗z 一_ 趸p d 丽x ) ，如果存在一个非零 常数口，使得p d x ) = 盯鼻( x ) ，q 2 ( x ) = 盘q l ( x ) ，则称r t ( x ) 与r ：( x ) 恒等，记做 r l ( x ) = r 2 ( 工) ；如果暑( x ) q 2 ( x ) = e ( x ) q l ( x ) ，则称月( x ) 和r ：( x ) 是等价的，记做 r l ( x ) r 2 ( x ) 。 定理2 2 【9 1 若方程组( 2 4 ) 有非平凡解存在，则为使满足插值条件( 2 2 ) 的 最简有理分式函数r 。，( x ) = a ( x ) b ( x ) 存在，必须且只需方程组( 2 3 ) 的任一非 平凡解p ( x ) ，q ( x ) 在约去一切公因子后所 ：导的多项式爿( x ) ，b ( x ) 仍然是方程组( 2 3 ) 的解。 定理2 3 【9 若r 1 ( x ) 与r 2 ( z ) 都是方程组( 2 3 ) 的非平凡解所作成的分式有理 函数，则r i ( x ) r 2 ( x ) 2 2t h i e l e 型插值的存在性分析 在背景介绍中，我们知道要想得到有理插值分式函数的显式表示，需要对 每个具体问题都需要解一个线性齐次方程组。下面来介绍一种有理插值函数算 法一一t h i e l e 型连分式插值算法。作为一种有效的有理插值算法，它被广泛地 应用于数值逼近( 【9 】) ，图象处理( 1 1 】，【1 2 】，【1 3 】) 。但是作为一种有理插值方法， 它也会有本身的局限性一一在某些节点组下，t h i e l e 型插值方法并不能童接得 到我们所要的结论。本章就是基于这种考虑，对t h i e l e 型插值方法在什么时候 是有效的进行了详细的分析，而且所得到的结论具有明显的几何意义。下厩的 讨论分为三个部分：第一部分，介绍了t h i e l e 型连分式插值算法；第二部分， 讨论了在什么情况下，逆差商是不存在的；第三部分，讨论了在什么情况下会 出现不可达点。 2 2 1 l h i e i e 型连分式插值算法 对于给定的数据最= ( t ，m ) i f _ o ，1 ，r 1 ) ，对于任意的f ， o ，1 3 1 - - ， ，i ， 有x i x 。首先介绍一下逆差商的概念： 逆差商可以由以下的方法递归计算， 妒 】= ，( ) ，f = 0 ，1 ，- - - ，h ， z x 毗，x a 2 而寿磊一- ， q o x ， 卜而忑青耘可 4 妒 x ”。一，x ，x t ，x 门2i i ；i ? j ：；i ：i ；i ：；而。 那么t h i e l e 型连分式插值就有如下的形式： 曩( x ) = a o + 垫盟兰血 ( 2 4 ) “i十2 十十 其中口= q ， x o ，薯】，i = o “1 t ，n 。 t h i e l e 型连分式插值具有的性质 ( 1 )r ( 一) = 厂( 一) ( 2 ) b ( 咖眦棚，t 纠n r + l 】，j 【争 我们在背景介绍中了解到，有理分式函数插值并不总是存在的。而作为一 种特殊的有理分式函数插值的方法，它的存在有着一般的共性和其本身的特殊 性。 下面我们就t h i e l e 连分式插值算法来进行分析。为了讨论的方便，我们引 进几个记号： 最一i 皇 ( ，y o ) ，( “) ，k o ，l ，n 插值最一。上的t h i e l e 型有理插值函数记为r 一。( 工) 皇 ( x o ，y o ) ，( t 十y i 1 ) ，( t 儿+ 1 ) ，( ，虬) ) ，f 0 ，1 ，疗) 特别地，有= 鼠一而插值彰上的t h i e l e 型有理函数记为砖( x ) 。 如果在上，能够在通常意义下，计算出慰( x ) ，我们称t h i e l e 型有理插值 函数 ) 是存在的。 2 2 2 逆差商的存在性分析 定理2 4假设t h i e l e 型有理插值函数咒一。( x ) 和群。1 ( x ) 存在，则点( ，n ) 在 曲线y = b 一( x ) 上科，x 1 ，矗 是以詈形式出现的( 其中a 为非零常数) 。 证明：( j ) 由于( x n ，儿) 在y = r 一( x ) 上，我们有 轧c 咿酬+ 赫矗景蒜 2 儿 而同时在群= ( ，) ，( 矗。一：) ，( 吒，n ) ) 上，群。1 ( 吒) = 虬。即 蟛n - 1 ( 咖】+ 赫+ 。儿 比较上面两个式子，显然有 x n x 2 + a x o ，x l ，矗_ 2 矗】 烈 + 石x 丽n - - x 0 + 所以有 x n x n 一2 + 诃，矗一1 = 讲 + 丽x n - - x 0 + p x o ，x l ，一x 。一2 ，矗一】j 2 ( p x o ，五，。一2 ，x nj 故 纠，薯，“。m 矗 2 石i i i _ i i j 彳i 葺专j i 雨2 罟 ( 仁) ( p x o ，h 】是以罟形式出现的，即 妒【，而，x n 一2 ，x n = 伊【，x i ，矗书一1 ， 所以有 u x ) 2 尹m + 瓦x - - 而x 0 + 故有儿= g n 一( ) 。证毕 ! 二生= 2 + 纠，。l j ，矗- 2 ，x n 】 酬+ x - - x 币o + 伊i ，玉i + 兰= 兰! = 2 + p x o ，。l i - 矗一2 ，x n 】 如果妒，而，矗】是以- 4 d 形式出现的，在通常的计算机计算过程中是没有意 义的，此时我们简单的称q , x o ，_ ，】此时是不存在的；反之，我们称之为存 在的。 定理2 5 设插值最一。上的r 一。( z ) 存在，如果点( 矗，) 在曲线y = r 一。( z ) 上， k ( 1 ，疗) ，那么烈，矗 也是不存在的。 证明：由于 妒，一x a2 而万磊= 焉x n 鬲- - x 而n _ k 了i 而 类似于定理2 4 的证明，我们知道， q ， x o ，x n 吒】= 昙， ( b 为不为零的常数 而且由于逆差商的递归算法，有 伊【，矗一t ，一“，矗】。i 瓦j _ j ：i i x n f - - i x i n _ k i + i _ j ：而 所以，烈，x l ，一，矗】也是不存在的。 如果我们把y = 月。( x ) k = 1 ，”看作在x o y 平面上的一簇曲线，那么如果 点p ( l ，) 恰好落在这簇曲线上的话，在不改变节点的次序的情况下，那么 t h i e l e 型插值算法中的逆差商的计算这个环节就不能被执行下去。 下面我们来讨论在什么情况下，t h i e l e 型插值算法中的逆差商的计算这个环 节是可以执行的。 定理2 6设烈，x l ，矗一1 】是存在的，如果( x 。，儿) 不在任何一条曲线 6 y = r i ( x ) 上，k = 1 ，2 ，r t ，则c p x o ，x i ，x n x n 】也是存在的。 证明：由于我们假设t p x o ，一，矗一1 】是存在的，其实也包含了 讲x o ，尹，五】，纠x o ，x i ，x n 一2 】 都是存在的。 由于( x 。，虬) 不满足f ( x ) = r 一。( x ) = r o ( z ) = y o ，即虬y o 。我们知道 妒，矗】i ? 挚是存在的。由于( ，n ) 不满足厂( x ) = r 巾- 1 ) ( x ) = 墨( x ) ，而 ，n，0 p ，x l ，矗 = j 二普二b ，由定理2 4 ，我们知道q x o ，卜p x o ，一 0 ，所以 纠，矗j 一纠x o ，x ij 妒，葺，x n 也是存在的。 类似地，我们可以递推出l j p x o ，。i i 一，吒+ x n 】也是存在的。证毕! 这个定理也就意味着，如果只要点p ( 屯，儿) 不落在这簇曲线上的话，在 不改变节点的次序的情况下，那么t h i e l e 型插值算法中的逆差商的计算这个环 节是可以被执行下去。 2 2 3 不可达点的分析 我们首先来看一个例子来说明：什么是不可达点? 并指出分析它的必要性。 例已知数据s = ( 一2 ，一i 3 ) ，( 一l ，一；) ，( o ，0 ) ( 1 ，3 ) ，( 2 ，了7 ) ，( 3 ，导) ) ，构造逆差商表【9 】 l 薯y 。研，玉】研，葺，葺】p f 而，葺，而，葺】烈，x 3 ，置】纠，x 4 ，鼍】 023 5 11。l 31 5 4 2001 0 31 2 5 3l35 62 4 3 57 1 2 427 31 5 1 14 4 3 57 46 7 531 3 52 5 1 66 4 3 52 l 43 77 3 孙卜；+ 高+ 去+ 斋+ 崭+ 崭 z 2 + x + 1 2 x l 显然有r ，( o ) 0 ，即b ( x ) 只满足部分插值条件。为什么会出现这种情况呢? 其 实在计算中恐( x ) = 气熹器。也就是说在分子和分母中出现了形式为 一t ) 的公因式。我们也就称这样形式的插值节点为不可达点。 下面来分析一下在什么样的情况下t h i e l e 型有理插值会出现不可达点。 定理2 7 设f j p x o ，一，矗】存在和蟛一。( x ) 存在，如果点( 矗，h ) 在曲线y = 彤一( x ) 7 上，i 1 ，2 ，一，”一2 ) ，贝0 有 妒【，一，t 一，矗 2 伊 ，一一t ，t + 】+ 石i j + + 尹，x i - i ，x ，x n 一1 】 证明：由于我们假设p x o ，而，靠 存在和月：一。( x ) 存在，所以下面的讨论才有意义。 由于 ( 班龇】+ 丽x n - - x o 忘+ 磊专羔而 x n x n i + f p x o ，。一，t l ，t + 】，。，】 2 儿 又虬2 p x a 刊朴丽x n - - x 0 忘雩蒜+ 面之去而+ 益二生= 3 + q , x o ，t ，t l ，t ，x n i 】 比较上面的两个式子，我们有 x n x h 妒 ，一一1 ，一“，西+ 2 】+ 蔓二益= ! ： 盘二苎 + 妒 ，蕾一l ，墨+ l ，一，x n 】e x o ，t 一1 ，薯，t “】+ 玉二玉= ! + , p x o ，一，一1 】 而 _ 芷b 芏玉l _ = , p x o ，钆，h 】 烈，t 小x i ，薯+ 1 】+ + q , x o ，蕾小，吒一l 】 + 一”1 所以有 科，蕾一，x o 2 妒 ，。一，一- ，薯“】+ ；i i + + ；i i _ 了i j i 证毕! 定理2 8 设t p x o ，x 1 ，矗】存在和e 一( x ) 存在，如果( ，m ) 在曲线y = 一l ( x ) 上，i l ，2 ，n 一2 ，贝0 有 。p x o ，t _ i ，+ l ，一2 ，矗一l 】= 研x o ，t _ ”x i ，一2 ，】 证明：由定理2 7 ，我们有 烈v m _ 】= 研w m 机】+ 瓦畿十 所以有 x h x n 一2 十p x o ，蕾一，x l + l ，一l 】 诃，。一，t 一- ，卜妒【，t 一一，t “】2 ；i i _ 萱：+ + ；五：_ _ i 乏j ；五i _ i j ；= i ：j 三专篙i 而2 伊【，t 一一，葺“，薯+ ：】+ ；i i i i ：三i i ：j i ：j i j + 十诃，薯州t 十1 ，2 ，矗一1 】 x 。一矗一 e x o ，x i - i 誓一h 】= 烈，x h ，x i + l , x m 】+ _ 立生三_ p l z o 一，工- i 工f + 1 ，z f + 2 x i + 3j 墨二! ! = 2 + + 研，一_ l ，x i 小，x n i 】 重复上面的步骤，可以得到 ( p x o ，x h ，x n 一2 ，矗一1 】= t p x o ，一十x f + l ，x n - 2 , x 。j 证毕! 我们也可以在另外一个角度来理解这个推论，在定理2 4 中，我们得到的结 论是： 在最= ( x o ，y o ) ，( ，虬) ) 的基础上，如果( x n ，乩) 满足方程f ( x ) = r 。( x ) q ， x o ，x i i i n 一2 ，k 1 = o x o ，五，x n 一2 ，x n 】。 而现在如果假设插值的节点组是 邑= ( x o ，) ，- ，( 一l ，m 一1 ) ，( + 1 ，y i + i ) ，( x 。，“) 那么我们会得到结论， p x o ，t m t ，x n 一2 ，一l 】= 研，一x ，i n 一2 ，x n 】。 f 面给出一点说明：在t h i e l e 型有理插值算法中，在所有的逆差两都被 计算出来后，e ( x ) ：+ 逊墨x - - x n _ 1 ，这是我们一般会对它进行化 a i十c 1 2 卞。十 “ 简，但化简的过程中分子和分母会出现公因式。如果我们保留了出现的公因式， 称这种形式的结果为未约化的；反之，称之为约化的。如果出现了形式为0 一耳) 的公因式( 其中札 x o ，一，) ) ，我们称这样的公因式为平凡公因式。 定理2 9 未约化的r ( x ) 的分子和分母中有平凡公因式0 一h ) 的充分必 要条件是 伊【，一，“】+ ；i ：筠+ + ；i 畿2 。 证明：( ；) 由于r ( x ) 的分子和分母有平凡公因式( x - - x k ) ，则意味着r ( ) 在通 常情况下是没有意义的。所以我们不能得到r ( x d = 虮。 用反证法来说明 妒 ，而，一，坼“】+ ；i i 飘+ + ；畿x o 2 0 。 研，而，矗+ 2 j + + 烈，而，矗j 如果妒 ，而，。一，坼“】+ ；i ：筠+ + ；i 畿。，我竹 有 讹脚m + 丽x k - x o 赫十忘詈南赫 = 研廿瓦x , - 而x o + + 蕞景筠 = 诃】- n 稆品然县与颢设是矛盾的，所以有 伊【，_ ，吨“ + i i ：x i + + ；i x 畿0x i x 2 0 妒【，一，耳+ 2j + 。+ 妒【，。，。j ( 仁) 记_ ，( z ) = c , o x o ，一，+ ， + ；i i + n p x o ，。一，x n 由十 伊xo,_，“+。o：xo巍xk+；ix畿ox n = 。，+ 2 j + 一十p 【，z i ，j 所以厂( x ) = 一杖) 石( x ) ，故 驰却m + 丽x - x o 赫+ 而景而赫 2 妒【】+ i 丽x - - x 0 + + ；i 赢+ i i 。二x j - 丽x k 如果我们在化简的过程中保留了 一x k ) ，则很显然未约化的r 。( x ) 的 分子和分母中有平凡公因式o 一) 。证毕! 引理2 1 0 ( 唯一性定理) 在保证逆差商存在的前提下，如果改变瓯的节点 次序，所得到的未约化的t h i e l e 型有理插值函数是唯一的。 注：在保证逆差商存在的前提下，最为一个变化过次序的节点组。最上对应的 插值函数为r ( x ) ，而毫上对应的插值函数为 ) ，其中r ( x ) 和，：t ( z ) 都是未约 化的。那么砖( x ) = ( x ) 定理2 1 1设r 一。( x ) 存在，如果( 矗，儿) 满足方程，( x ) = 碍一( x ) ， i o ，1 ，竹一2 ) ， 则有妒 ，而，一，_ “ + ；西i j 亲+ + ；i 淼2 0 证明：在定理2 8 中，我们知道如果( ，乩) 满足方程厂( x ) = 群一，( x ) ，则有 o x o ，x ，墨“，x 。一，工一】= 诃，- 一，墨l ，一+ i ，x n 一2 ，】。 当i = 即一2 时，我们有 伊【知，矗- 3 ，一1 】= 矿【，x n - 3 ，x n 】 这时，我们有 o x o ， 一卜最荨南 ： 昱= ! 二墨= 2 + ! ! = 2 二! = ! g x o ，_ 3 ，k l 】一妒 ，矗- 3 ，x n 一2 】t p x o ，而，矗】 ：益= l = ! ! = z+ ! ! = 2 = ! a = ! 研x o ，“，x n - o x o ，h _ 3 ，吒一2 】讲，巧， 】 ： 叠= l 二益= 2 + 玉= 2 二! ! = ! 纠x ，x n 一3 ，矗卜纠，h _ 3 ，矗一2 】 玉二! = ! 科，x n 。2 ，】一妒【，h 一2 ，一i 】 1 0 = ! 叠上二! 些曼_ 一 妒，矗x 。卜q ， x o ，x n _ 1 ，x n 一2 + x q x h 一 墨二墨= ! 一 研，矗一3 ，矗】一研，- 3 ，矗一2 】 ：! ! = ! 二量= 2 q x o ，t ，x n 】一o x o ，吒矗一2 】 墨= ! 二墨= ! e x o ，x n 9 x n 一1 卜q ， x o ，h _ 3 ，x n 一2 】 + 曼生_ = 二兰! l 一x n x r i 玉二! ! = 2 一 ! n = ! 二! = 2 q ， x o ，x n 卜( a x o ，_ 3 ，一2 】6 p x o ，矗_ 3 x n 一q ， x o ，。一2 =兰2 = ! 二兰= 2j 兰! = 2 二兰2 ：! q ， x o ，一h ， 一妒 ，矗口矗一2 】p 【，x n 一3 ，x n 一妒 ，x n _ 3 ，x n 一2 】 = 0 当i o ) ，我们称连分式6 0 + k ( 吼一，1 ) 为一_ 正项极限周期连分式。 3 2 正项极限周期连分式的误差分析 定理3 5 对于正项极限周期连分式的最( w ) 和r ( 0 ) ，有下面的结论成立 l 最( w ) 一s ( o ) i 0 ，则连分式( 3 1 ) 收敛，而且作者还给出了它的截断误差分析结果： j 厂一最( 0 ) 庠m i n ( 占i ，巳)( 3 1 4 ) 其中 q ：_ 地生翌l _ 矿一 p ”1 l 钆l + 击( 1 9 a 2 i + c 2 l a 2 q l + + c 2 ”4 l 吼一。吼1 ) ) 兀1 阮一i 吼l c ) q = 下地譬导l 一 丌( 1 以一l a k e 1 1 ) 兀1 以一i a ki c ) 我们可以得出，对于本章中所研究的极限周期连分式而言，条件( 3 13 ) 就变成 了 以+ 停引 这样的话，结论( 3 1 4 ) 只适用于d 满足口( 一，1 ) 的一类极限周期连分式。而本 4 章对所有口 0 的极限周期连分式，在适当的处理后，都可以用定理3 6 做出相 应的截断误差分析。 第四章曲线和曲面隐式化一个算法 在c a g d 中，曲线和曲面的表示一般有两种：参数表示，隐式表示：而这两 种表示方法也各有其优越性。如果能够同时拥有这两种表示形式将是极为方便 的事。从经典的代数几何可知，任何有理表示一定可以转化为隐式表示，这一 转化过程称为隐式化。相对于参数曲面，隐式曲面具有很多优点，除了在概述 中已提到的之外，隐式曲面还具有简单灵活的表现形式，更易于表现立体形状， 比如，基本的三维形体，其外形，包括各类二次曲面，都可以用简单的代数曲 面来表示。而且，用于进行造型设计的代数曲面次数较低。由于隐式曲线曲面 的使用率越来越高，因此，参数曲线曲面的隐式化就成为了引人关注的问题。 4 1 问题的提出 问题的提出 在本章中，我们用r t 】，r s ，f 】，r x ，y 】，r x ，y ，z 】等表示实数域上的多项式 环。 曲线的隐式化问题 给定有理曲线的齐次表示 p ( t ) = 0 ( ，) ，6 ( f ) ，c ( f ) ) ，( 4 1 ) 其中口( ，) ，6 ( f ) ，c ( t ) r t 】都是次数不超过n 的多项式，其最大的次数为，z ，且 g c d ( a ，b ，c ) = 1 ，d ( f ) ，6 ( f ) ，c ( t ) 可以表示为 口o ) = q 一，6 ( f ) = g t ，c ( f ) = q ， l = oj - 0i = o 求不可约多项式f ( x ，y ) = g x ，y 】，使得 f 0 ( f ) c ( t ) ，6 ( ，) c o ) ) ；0( 4 2 ) 曲面的隐式化问题 给定有理曲线的齐次表示 p ( s ，r ) = ( 口( j ，f ) ，b ( s ，r ) ，c ( s ，) ，d ( s ，r ) ) ， 其中口，b ，c ，d r t 】都是次数为( m ，珂) 的多项式，且g e d ( a ，b ，c ，d ) = 1 式f ( x ，y ，= ) = r x ，y ，z 】，使得 f ( a ( s ，t ) d ( s ，) ，b ( s ，t ) d ( s ，) ，c ( j ，t ) d ( s ，f ) ) z0 ( 4 3 ) 求不可约多项 ( 4 4 ) 4 2 已有的一些隐式化方法 结式方法 定理4 1 【4 5 1 令f = 口( f ) 一c ( t ) x ，g = 6 ( f ) 一c ( t ) y ，则有理曲线( 4 1 ) 的隐式方程 为 f ( x ，y ) = r e s ( f ，g ，f ) = 0 根据结式的s y l v e s t e r 表示，有f ( x ，y ) = d e t ( s y l ( f ，g ，f ) ) ，其中 s y l ( f ，g ，f ) = d 0 一c o 工 a n c h z 一c o xa l c i x一c x b o c o y a n c y 6 0 - c o y6 l - c i y吼一c y 这黑1 4 嚣2 ad 蕊髫觏a cc a 且a 一脯料i a d c b 引理，为同阶方阵，若 = 且。1 存在则有i 1 = i l 。 若厂和g 的形式为 。 f = ( a o - c o x ) + ( a 一c x ) t ” g = ( b o c o 石) + ( 吒一c x ) t ” 则 d e t ( s y l ( f ，g ，f ) ) = d e t a o c o x 0 0 “一c n x 一c o x 6 0 一c o y 0 0 b o c o y o n n c n y 0 0 o a n c n x 0 口。一c 。y = i 一c o x 喁一c 。j 1 一g x q q j r c 。y 玩一岛j r 一矗y 根据结式的b e z o u t 表示，有f ( x ，y ) = d e t ( b e z ( f ，g ，f ) ) ，b e z ( f ，g ，t ) 是一个n 阶 矩阵，它的每个元素都是墨y 的一次多项式。 对于曲面的隐式化而言，我们需要涉及有理曲面的基点。如果存在( s o ，t o ) 满 足 a ( s o ，t o ) = b ( s o ，t o ) = c ( s o ，t o ) = d ( s o ，t o ) = 0 则称( s o ，t o ) 为p ( s ，f ) 的基点。对于没有基点的有理曲面，可以通过d i x o n 结式计 算。 对于有基点的有理曲面，不能够直接使用d i x o n 结式来计算，但我们可以 用摄动法【2 0 1 来解决。 8 r o e b n e r 基方法 g r o e b 即e r 基是一种处理多元多项式的有效工具，利用它用可以求得有理曲 线与曲面的隐式方程。我们来介绍一下g r o e b n e r 基的背景知识。 引理4 3 3 4 1 若石，正【一，矗】，则 埘 m ， ，l川卜卜h = ( 置1 ，吃h 毛，h 】) i = l 是k x l ，_ 】中的理想，并称 为由| ，i ，f 生成的理想。 定义4 4 【3 4 1 k x l ，】中单项式，的任意全序关系卜称为e 。l ，一，k 】上单项 式的序，如果 1 ) 卜是k x i ，矗】上是相容的，即当x 。卜x 4 且x 7 为任意单项式，有 x 4 工，= x c t + ， x 卢石，= x 卢+ r ： 2 ) 卜为良序的，即在序 _ 下每个非空单项式集都有最小元。 下面是一些我们常用到的单项式的序。 定义4 5 设扩，为k x l ，矗】上的单项式， 1 ) ( 字典序) ，k ，如果a - p = ( 吼一层，一属) 的第一个非零元为正； 2 ) ( 逆字典序) x “ r t e xx ，如果口一= ( q 一尼，a 。一成) 的最后一个非零 元为负： 3 ) ( 分次字典序) x 4 mx 4 ，如果i 口p i 卢1 或i 口削l 时，x 。k 妒； 4 ) ( 分次逆字典序) r k 。，如果l 口p i i 或i 口 i l 时，x “ r l e x x 4 。 定理4 6 3 4 1 ，。以及均为单项式序。 给定的这些单项式的序 - 的目的在于；我们可以在它的基础上给出 k x j ，x n 】上的除法。 下面给出一些记号 设厂= 。a a x “是研五，矗】上非零多项式且 _ 是一个单项式序 1 ) m u l t i d e g = m a x e z ：oi o ， - ) 2 ) l c ( f ) = a m 。l i i d ( ，) k 3 ) z m ( f ) = z ”“”门 4 ) l t ( f ) = l c ( f ) l m ( f ) 下面来介绍单项式理想 定义4 7 i c ，】称为一个单项式理想，如果存在a 仁z i 。使得 ，= ( 吃r 1 九七，、】) ) 、d e ， 记为= 引理4 8 t 3 4 1 设1 = 为单项式理想，则对卢z i 。有 x 卢i 当且仅当j 盯a ，x 。i x p x 卢1 2 定理4 9 1 ( d i c k s o n 引理) j = ( 扩i 口a ) ( c z 刍) 为单项式理想，则，有 有限基： ，= ( 矿。1 ，x 州”)