（计算数学专业论文）基于连分式的二元有理插值的算法研究.pdf

基于连分式的二元有理插值的算法研究 摘要 连分式插值是一种非线性插值，它不仅在数值积分、微分方程数值求解、 积分计算、积分方程、数学物理中特殊函数的渐近展开、数论、马尔可夫过程 理论、矩量问题和生死过程、混沌、理论物理等领域得到了广泛的应用，而且 还在控制理论、统计力学、机械振动、模分析、信号处理等工程技术领域有显 著的应用。本文主要讨论了基于连分式的二元有理插值的算法，分别介绍了二 元n e w t o n t h i e l e 型混合连分式插值的算法，t h i e l e n e w t o n 型混合连分式插值的 算法，t h i e l e t h i e l e 型混合连分式插值的算法，经过分析后不难发现，这几种二元 有理插值格式是利用一元n e w t o n 型插值多项式和一元t h i e l e 型插值连分式按 照某种方式嵌套生成的，将这几种二元插值格式统一在一个框架之中，在基于连 分式的二元有理插值的一般框架的基础上，本文给出了其相应的矩阵算法。利用 牛顿多项式插值和关联连分式插值构造出的二元牛顿关联连分 式插值，本文给出了递推算法的等价算法一一矩阵算法，数值例子表明该算法 的有效性。 关键词：插值；矩阵算法；关联连分式 a l g o r i t h mr e s e a r c ho fb i v a r i a t er a t i o n a li n t e r p o l a t i o n b a s e do nc o n t i n u e df r a c t i o n a bs t r a c t c o n t i n u e df r a c t i o ni n t e r p o l a t i o ni san o n l i n e a ri n t e r p o l a t i o n ，i ti sn o to n l y h a v eb e e nw i d e l yu s e di nt h en u m e r i c a l i n t e g r a t i o n ，n u m e r i c a l s o l u t i o no f d i f f e r e n t i a le q u a t i o n s ，i n t e g r a lc a l c u l a t i o n ，i n t e g r a le q u a t i o n s ，s p e c i a lf u n c t i o n so f m a t h e m a t i c a lp h y s i c si nt h ea s y m p t o t i ce x p a n s i o n ，n u m b e rt h e o r y ，m a r k o vp r o c e s s t h e o r y ，m o m e n tp r o b l e m sa n dd e a t hp r o c e s s ，c h a o s ，t h e o r e t i c a lp h y s i c sa n do t h e r f i e l d s ，b u ta l s oi nc o n t r o lt h e o r y ，s t a t i s t i c a lm e c h a n i c s ，m e c h a n i c a lv i b r a t i o n ， m o d e a n a l y s i s ，s i g n a lp r o c e s s i n ga n do t h e re n g i n e e r i n gt e c h n o l o g i e sh a v e s i g n i f i c a n ta p p l i c a t i o n s t h i sp a p e rc h i e f l yd i s c u s s e st h ea l g o r i t h mp r o b l e mo f b i v a r i a t er a t i o n a li n t e r p o l a t i o nb a s e do nc o n t i n u e df r a c t i o n ，t h ea l g o r i t h md e s c r i b e d h e r ei n c l u d er e c u r s i v ea l g o r i t h ma n dm a t r i xa l g o r i t h m ，t h em a i nc o n t e n ti n c l u e d s b i v a r i a t en e w t o n t h i e l e - l i k e b l e n d i n g c o n t i n u e df r a c t i o n i n t e r p o l a t i o n a l g o r i t h m ，t h i e l e - n e w t o n l i k eb l e n d i n gc o n t i n u e df r a c t i o ni n t e r p o l a t i o na l g o r i t h m ， i ti sn o td i f f i c u l tt of i n dt h a t ，t h e s et y p e so fr a t i o n a li n t e r p o l a t i o na r eg e n e r a t e di n o n ew a yo ra n o t h e rb yi n t e r p o l a t i o no fu n v a r i a t en e w t o n l i k ep o l y n o m i a l sa n d u n v a r a i t et h i e l e - l i k ec o n t i n u e df r a c t i o ni n t e r p o l a t i o n s e v e r a lb i v a r i a t ei n t e r p o l a t i o n f o r m a tc a nb ee x p r e s s e si nau n i f i e df r a m e w o r k ，t e a c h e rj i e q i n gt a ng i v e st h eg e n e r a l f r a m e w o r ko fb i v a r i a t er a t i o n a li n t e r p o l a t i o nb a s e do nc o n t i n u e df r a c t i o n ，t h i sp a p e r g i v e st h ec o r r e s p o n d i n gm a t r i xa l g o r i t h m i nt h i sp a p e r ，an e wb i v a r i a t ec o n t i n u e d f r a c t i o ni n t e r p o l a t i o ni s c o n s t r u c t e d b yt h en e w t o ni n t e r p o l a t i o np o l y n o m i a l i n t e r p o l a t i o na n da s s o c i a t e dc o n t i n u e df r a c t i o ni n t e r p o l a t i o n ，a tt h es a m et i m e ，w e a l s og i v ean e we q u i v a l e n tm e t h o d m a t r i xa l g o r i t h m ，n u m e r i c a le x a m p l e ss h o w t h ee f f e c t i v e n e s so ft h ea l g o r i t h m k e y w o r d s ：i n t e r p o l a t i o n ；m a t r i xa l g o r i t h m ；a s s o c i a t e dc o n t i n u e df r a c t i o n s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得 金胆王些太堂 或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 2 0 日 学位论文作者签字：粳明娟 签字日期：矽7d 年中月 扬明娇 学位论文版权使用授权书 本学位论文作者完全了解金胆兰些太堂 有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借 阅。本人授权 金起王些太堂 可以将学位论文的全部或部分论文内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：桶阴娟 签字日期：2 0 l o 年年月z o 日 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日期：矽co 年 电话： 邮编： 乒月 致谢 学位论文是在我的导师唐烁教授的亲切关怀和悉心指导下完成的。他严肃 的科学态度，严谨的治学精神，精益求精的工作作风，深深地感染和激励着我。 从课题的选择到项目的最终完成，唐烁老师都始终给予我细心的指导和不懈的 支持。唐烁教授不仅在学业上给我以精心指导，同时还在思想、生活上给我以 无微不至的关怀，在此谨向唐烁老师致以诚挚的谢意和崇高的敬意。 在此，我还要感谢在一起愉快地度过研究生生活的各位同学们，正是由于 你们的帮助和支持，我才能克服一个一个的困难和疑惑，直至本文的顺利完成。 在论文即将完成之际，我的心情无法平静，从开始进入课题到论文的顺利完成， 有多少可敬的师长、同学、朋友给了我无言的帮助，在这里请接受我诚挚的谢 意! 感谢父母对我二十多年来辛勤的养育，并让我获取了一定的知识并最终走 向社会，为社会贡献自己! 最后，我要向在百忙之中抽时间对本文进行审阅、评议和参加本人论文答 辩的各位老师表示感谢! 作者：杨明娟 2 0 10 年4 月 第一章绪论 1 1多项式插值研究背景 函数逼近论有着悠久的历史，而插值问题又是其古老而经典的一项重要内 容，同时也是计算数学中的一个基本问题。插值概念最早是在5 4 4 6 l0 年间 由我国隋朝数学家刘悼首先提出的p j ，这比西欧学者在16 5 5 年发表的结果早 一千多年。所谓插值问题是指从给定的离散点的值去构造一个连续定义的( 简单) 函数，使得它与被逼近的函数在给定点的值完全一致。在信息的存储、处理、 分析、传输日益数字化的今天，插值问题无处不在：通过离散点作一条光滑曲 线、读表1 、由给定数据求数值微分和数值积分、计算函数值、用简单函数代 替复杂函数等。插值方法的目的就是寻求简单函数来近似代替复杂函数，选择 简单函数的过程中，通常应注意以下几个问题： 根据实际问题的需要，选择恰当的插值函数类型。 插值结点之间具有什么内在性质( 单调性、凸性、周期性等) ? 是需要插值函数的表达式还是它在指定点处的函数值? 如何构造插值函数及考虑相应的插值余项估计问题。 常用的插值函数有多项式、分段多项式、有理函数、分段有理函数、样条 函数、三角函数、指数函数。多项式作为一种最简单的函数类，是整个数值逼 近的基础，能令人满意的解决一系列有实际应用价值的重要问题，特别是在数 值微分和数值积分方面。关于代数插值的研究已有很多，例如有l a g r a n g e 插值 公式，n e v i l l e 算法，n e w t o n 插值公式，h e r m i t e 插值公式等。代数多项式的 特点是运算简单，不论是函数值的计算、微分、积分都能方便地运算，它的另 一特点是在整个数轴上有任意阶导数。因此，在某种意义下，代数多项式是逼 近光滑函数的重要工具。此外，计算插值的算法包括系数算法和求值算法，其 中系数算法用于得到插值函数的表达式，而求值算法用于求插值函数在不同于 插值点的任意点处的值一j 。 多项式插值与逼近是整个数值逼近的基础，它被广泛应用于方程求根、曲 线曲面拟合、近似计算函数值、函数逼近、数值微分、数值积分、积分和微分 方程数值解等。多项式插值与逼近的广泛应用是基于它们结构最简单，易于构 造，便于利用。常用的一元多项式插值方法是n e w t o w 插值l i 一1 、l a g r a n g e 插 值【l 】o 1 2 有理插值研究背景 在自然科学与技术科学领域中存在着大量的需要解决的非线性问题，它们 已成为科学技术领域研究的热点。作为非线性逼近的典型之一的有理函数插值 与逼近，越来越引起人们的关注。近年来人们在数值与函数逼近、计算机辅助 几何设计中偏爱有理函数，因为有理函数仍属简单函数类，用它来近似表示函 数时，比用多项式更灵活、更有效，且能反映函数的一些固有特性，如极性等。 有理分式函数由于其自身的特点，使得它不但可以在极点附近取得很好的逼近 效果，而且又能保证当工专o o 时，有理逼近函数趋于某一定值的性能。这些事 实说明，开展函数的有理分式逼近问题的研究是十分有意义的。作为有理逼近 研究的重要组成部分，有理函数插值的理论及其应用一直是计算数学领域中引 入注目的课题。 在有理函数插值格式的构造方法中，最常用的是基于t h i e l e 型连分式的插 值方法。连分式理论迅速发展的时间虽然仅有三百多年，但其思想方法可以追 溯到公元前3 0 0 年，在公元前3 0 0 年至公元2 0 0 年期间，连分式主要用来表示 数值和解方程。借助于连分式研究有理逼近问题的历史也不算长，荷兰数学家 和天文学家首次将连分式用于解决有理逼近问题。g a u s s ，于18 7 2 年给出了t a n h x 的连分式表示，借助于连分式证明了f e r m a t 猜想，兰伯于17 7 0 年给出了a r c t a n x 的连分式表示，l i o u v i l l e 则利用正则连分式展开证明了超越数的存在性，这是 连分式在数值近似方面的例子，直到十八世纪，连分式理论应用还仅限于数学 领域。到了二十世纪初，连分式开始越来越多的出现在其它应用领域，如r o b e r t m c o r l e s 用连分式研究混沌理论。二十世纪六十年代以后，俄罗斯数学家v y a s k o r o b o g a t k o 将分支思想应用于连分式理论，开创了连分式理论与方法研究的 新纪元，多元分叉连分式插值与逼近受到西方各国学者的广泛关注。 目前，连分式方法不仅在数值积分、微分方程数值求解、积分计算、积分 方程、数学物理中特殊函数的渐近展开、数论、信息安全、马尔可夫过程理论、 矩量问题和生死过程、混沌、理论物理等领域得到了广泛的应用，而且还在控 制理论、统计力学、机械振动、模分析、信号处理等工程技术领域有显著的应 用。 1 3本文的主要内容 在已有成果的基础上，本文利用檀结庆教授等提出的二元分叉连分式插值 的矩阵算法思想，给出了二元连分式插值的统一描述的信息矩阵算法，并且受到 这种思想的启发，根据二元牛顿关联连分式插值的递推算法，本文给出了其相应 的矩阵算法。全文内容安排如下： 第一章介绍多项式插值和有理插值的研究背景，以及有理逼近、连分式 的发展状况。 第二章对一元多项式插值、一元有理函数插值、多元有理函数插值进行 了综述。 第三章对几种常见的二元混合连分式的递推算法以及矩阵算法作了介 绍，在基于连分式的二元有理插值的一般框架的基础上，本文给出了其相应的 2 矩阵算法。 第四章对于利用牛顿多项式插值和关联连分式插值构造出的二元牛顿 关联连分式插值，利用类似的思想，给出了递推算法的等价算法一矩阵算法， 数值例子表明该矩阵算法的有效性。 第二章插值法 2 1 多项式插值【1 】 若通过某种方法己知函数y = f ( x ) 在区间【口，b 】上的结点x 0 而，x 。处的函 数值分别为y 。，y l 一，y 。，插值的目的是根据给定数据，寻找一个解析函数p ( x ) 近 似地代替f ( x ) 。函数p ( x ) 的类型有很多选择，若采用代数多项式则该插值函数 称为多项式插值或代数插值。 2 1 1 l a g r a n g e 插值 在区f 刚陋，b e 己知函数y = f ( x ) 7 在- 区间 口，6 上的结点x 0 x l ，一，x 。处的函数 值分别为y 。，y i ，一，y 。构造多项式p ( x ) 使之满足插值条件： 1 ) p ( x ) 是不超过n 次的多项式 2 ) p ( x ，) = f ( x ，) = y ，o = o ，l ，2 ) ， p ( x ) 称为插值函数，x ，称为插值结点，条件1 ) 、2 ) 称为插值条件，【日，b 】称为 插值区间。l a g r a n g e 在17 7 5 年证明了下面的定理： 定理2 1 1 1 】满足上述插值条件的插值多项式p 。( z ) 存在且唯一。 构造 n ( x ) = y ，如) ( 2 1 1 ) 的即次多项式。 其中 ，“) ：j 竺玉堑! 止尘二苴坚! 生蔓! 上 ( 2 1 2 ) 、7 ( x ，x o ) ( x f x 1 ) ( x ，一x f 一1 ) ( x ，一x ，+ i ) ( x f x ”) 多项式( 2 1 1 ) 即为l a g r a n g e 插值多项式。 l a g r a n g e 插值公式结构紧凑、思想清晰。 2 1 2n e w t o n 插值公式 l a g r a n g e 插值公式虽然结构简单，但是有很大缺点，当插值节点的个数有 变动时，其基函数，( x ) ( f _ o ，1 ，船) 就要随之发生变化，需要重新构造，使得整 个公式的结构也要发生变化，在实际计算中有很大不便。为了克服这一缺点， 我们介绍n e w t o n 型插值公式。 p 。( x ) = f ( x o ) + f x o ，x 1 ( x x o ) + + f x o ，x 1 ，x 。】( x x o ) ( x x 1 ) ( x x 。一1 ) 4 其中系数f ( x 。) ，f x 。，而】，f i x 。，z l 一，x 。 是厂( x ) 的各阶差商。差商除了可以进 行递推计算外，还有一个有趣的性质就是差商的行列式表示： 1 z ：。1 厶 厂tx。，x。，x。，=嚼1 ix 。x fz x 1 x ? x 。z ： 其中z = f ( x ) ，f - o ，1 ，以差商的上述性质告诉我们差商有很好的对称性质，即 差商与插值节点的排序无关。 由于在玎+ 1 个节点，x 1 一，x 。上取给定值的次数不超过，z 的多项式是唯一 的，所以次数相同的n e w t o n 插值多项式和l a g r a n g e 插值多项式是相同的，仅 仅是书写形式不同而已。但是却给实践的计算带来极大的方便。因为增加一个 节点只需要在原插值多项式的后面再添一项就可以了。 2 2 一元t h i e l e 型有理插值【1 2 】 已经知道，构造一般的有理插值函数需要求解线性方程组，这无疑给有理插 值的表示和计算带来不便。然而借助于带变量的连分式可以实现一种特殊形式 的有理插值，其表达式简单、计算方便。 定义2 2 1 称下述形式的连分式 b 。+ ! 玉兰玉盟 ” b 1 + b 2 + +b + 为t h i e l e 型连分式。 定义2 2 2 设x = 上的t h i e l e - n e w t o n 型混合差商。 从上述定义可以看出，蛳k 口，x q ；y ，y s ，y k ，乃 关于变量x 的递推关系类 似于一元逆差商，而关于变量y 的递推关系类似于一元差商。 定理3 3 1 对i = 0 , 1 ，m ；j = 0 ，l ，n ，令 d ，= 妒7 i x o ，x l ，x ，；y o ，y l ，y 】， 则所定义的r 肌n j t ( x ，少) 满足插值条件： r m l ? ，f ( x 叫y ) = 厂( x 叫y ) ，v ( x ，y ) 兀z 3 4 二元t h i e l e n e w t o n 型混合连分式插值的矩阵算法【l 纠 与二元t h i e l e n e w t o n 型混合连分式插值类似，二元t h i e l e n e w t o n 型混合 连分式插值连分式插值除了可以用t h i e l e n e w t o n 型混合差商进行计算外，还 可以通过下述所谓的信息矩阵方法来计算。 算法3 4 1 第一步：初始化。令 z = f ( x ，y ，) ，f _ o ，1 ，m ；j = 0 , 1 ，z 并定义如下初始信息矩阵： 船0 第二步：x 方向t h i e l e 递推 魁0 以， 对，= 0 , 1 ，n ；p = 1 , 2 ，m ；i = p ，p + 1 ，m ，令 厂( p ，o ) = ji 。j x i xp 一1 ，了q 0 一c 豺 上述递推过程旨在通过m ( m + 1 ) ( 甩+ 1 ) 2 次乘法运算( 列变换) 将初始信息矩阵 m 转换为 f ( o ，o )厂( 1 ， f ( m ，o ) - ，0 ，露，l 。, d 脚押 第三步：y 方向n e w t o n 递推 i = 0 , 1 ，m ；q = 1 , 2 ，n ；i = g ，q + l , - - n ，令 ，( f ，g ) 一 ji 。j y j 。y q - i ，( i , q - d，( f q - 1 ) ji 。jji , q 一1 上述递推过程旨在通过n ( n + 1 ) ( 朋+ 1 ) 2 次乘法运算( 行变换) 将信息矩阵m 进 一步变换为 m 2 = 宽一 z 硝1 ： z 以 以p 以y 第四步：利用m ：的第i + 1 列元素：乡门，= 0 , 1 ，2 构造关于y 的n e w t o n 型连分 式z ，( y ) ，即令 z ，( y ) = z 譬聊+ ，：1 ( y - y o ) + ：譬2 ( y - y o ) ( y y 1 ) + + 第五步：令 譬( y - y o ) ( y y 1 ) ( y y 。一1 ) ，i = 0 , 1 ，m r 篡l ( x ，少) = l o ( y ) + x x 0x z l x x ，一i 厶( y ) + 1 2 ( y ) + + + ，。( 少) 1 8 啪一叩j 疋露； 一j 石工； ” m m j 以以； 则r 哪n , r ( 、x ，y ) 即为在矩形网格兀m , n 上给定函数f ( x ，y ) 的二元n e w t o n t h i e l e 型 混合有理插值函数。 对于t h i e l e - t h i e l e 型分支连分式插值的递推算法和矩阵算法文献 1 2 中做 了说明，对于n e w t o n t h i e l e 型混合连分式插值，t h i e l e n e w t o n 型混合连分式插 值和t h i e l e t h i e l e 型分支连分式插值，仔细分析后不难发现，这几种二元有理插 值格式是利用一元n e w t o n 型插值多项式和一元t h i e l e 型插值连分式按照某种 方式嵌套生成的，下面将上述三种二元插值格式统一在同一个框架之中。 3 5二元连分式插值的统一描述 1 2 】 设兀i ；= 兀二兀：= ( 薯，y j ) l i = 0 ，1 ，m ；j = 0 ，1 ，z ) 对汪0 ，1 ，m ，令 s 。( 少；6 ，r ) = c i 。( 6 ，r ) ， s 女( y ；f i ，r ) = 呸，女( 万，刁) + ( y 一败) s ，+ l ( y ；万，刁) 6 ，n - 1 ，1 ，o ； s ( 少；万，r 1 ) = s o ( j ，；万，7 7 ) ， 乩，( x ，y ；8 ，r 1 ) = s m ( 夕；6 ，蟹) ， ( z ，y ；8 ，r 1 ) = s ( y ；万，刁) + ( x 一薯) + l ( x ，y ；8 ，7 7 ) 】”，f = m - 1 ，1 ，0 ， ( 3 5 1 ) ( 3 5 2 ) ( 3 5 3 ) ( 3 5 4 ) ( 3 5 5 ) 其中，7 和万取1 和- 1 定义3 5 1令 胪驯i x , ，y 】= 厂( x ，y j ) ，v ( x 州y ) 兀训m , l ， ( 3 5 6 ) 刖睇m ，_ ( 盟掣y ky j 6 n 5 。 i j 胪， x j ；y r , , y s , y k , y 1 ：f ，竺堕生业止丝竖趔l 栅，_ ( 坐一厂 1 9 ( 3 5 8 ) ( 3 5 9 ) f 占 w i x 尹，五，；以】 ：f ，! 堕立型型竺型趔卜 。 1 0 i石，一蕾j f 占4 x p ，x q ；y r ，只，y k ，乃】 = ( 盥型出等等竖型r y l y k ( 3 5 1 1 ) 其中7 7 和万取1 和一1 ，则称由式( 3 5 1 ) 一一( 3 5 1 1 ) 定义的f j ”i x , ，；”，只】 为函数f ( x ，y ) 在网格点 ，x q y r ，y a 上的( 万，t 1 ) 差商。 不难看出，t h i e l e t h i e l e 型偏逆差商型、n e w t o n t h i e l e 混合差商型、 t h i e l e n e w t o n 型混合差商均是( 万，r 1 ) 差商的特殊情形，实际上我们有 f ( - 1 , - o x p ，；”，y , = q a r r x p ，x q ；y r ，y s ， f 。1 1 讳，x q ；y , ，虬】= 纨r x p ，x q ；y r ，以】， f 1 一1 x p ，；”，y , = t p r n x p ，x q ；y r ，咒】， 另外，我们还不难发现f ( 1 ，i _ p ，x g ；”，”】是二元n e w t o n 差商【l ，2 9 1 。 定理3 5 1 3 0 1 设厂( x ，y ) 在gd 兀z 上有定义，令 q ( 万，7 7 ) = f 5 ，训 x o ，x j ；y o ，”】，i = o ，1 ，聊；= o ，1 ，z ， 且所有( 万，r ) 差商均存在，则由式( 3 5 1 ) 一一( 3 5 11 ) 定义的( z ，y ；8 ，7 7 ) 满足 条件 一般框架包含了四种二元有理插值格式： 插值格式l二元n e w t o n 插值格式 在式( 3 5 1 ) 一( 3 5 5 ) 中令万= r = 1 ，我们得到 ( x ，y ；1 ，1 ) = s o ( y ；1 ，1 ) + ( x x o ) s 1 ( y ；1 ，1 ) + ( x x o ) ( x 一五) s 2 ( y ；1 ，1 ) + ( x x o ) ( x 一为) ( x x m - 1 ) s 。( y ；1 ，1 ) 其中，对f = o ，1 ，m ， s i ( y ；l ，1 ) = a i ，o ( 1 ，1 ) + ( y y o ) a f 1 ( 1 ，1 ) + ( y y o ) ( y m ) q ，2 ( 1 ，1 ) + ( y y o ) ( y y 1 ) ( y 一一1 ) 口抽( 1 ，1 ) 插值格式2二元t h i e l e n e w t o n 型混合连分式插值格式 2 0 在式( 3 5 1 ) - ( 3 5 5 ) 中令万= 1 ，r = 一1 ，我们得到 ( x ，少；l ，一1 ) 2 ( j ，；l ，一1 ) + ：飞x 而- x o + ：i 石x 而- x 1 + j ：x 石- - 而x m _ i 其中，对i = 0 ，1 ，r n ， ( y ；1 ，一1 ) = q 。o ( 1 ，一1 ) + ( y y o ) 口i ，l ( 1 ，一1 ) + ( y y o ) ( y y 1 ) a ，2 ( 1 ，一1 ) + ( j ，一y o ) ( y 一乃) ( 少一一1 ) q 。( 1 ，- 1 ) 插值格式3二元n e w t o n t h i e l e 型混合连分式插值格式 在式( 3 5 1 ) - ( 3 5 5 ) 中令万= 一1 ，r = 1 ，我们得到 砜( z ，y ；- 1 ，1 ) = s o ( 少；一1 ，1 ) + ( x x o ) ( y ；一1 ，一1 ) + ( x - - x o ) ( x 一五) j 2 ( y ；一1 ，- 1 ) + ( x x o ) ( x 一) ( x x m 1 ) s m ( y ；- 1 ，- 1 ) 其中，对i = o ，1 ，m ， s ，( y ；- 1 , 1 ) 2 q ，。( 一1 ，1 ) + 乙而y - y o + 乙而y - y l + + 乙y 而一y n - - i 插值格式4 二元t h i e l e t h i e l e 型混合连分式插值格式 在式( 3 5 1 ) 一( 3 5 5 ) 中令万= 一1 ，r = 一1 ，我们得到 砜( x ，y ；一1 ，一1 ) = s o ( y ；一1 ，一1 ) + x 一x 一五 墨( j ，；一1 ，一1 ) + s 2 ( y ；一1 ，一1 ) x x n ，一i ( y ；一1 ，一1 ) 其中，对i = 0 ，1 ，m ， _ ( y ；- 1 , - 1 ) 。q ，。( 一1 ，一1 ) + 丢：y 而- y o + 乙乏鼍三z 兰酉+ + 三：y 而- - y n - 1 3 6 二元连分式插值一般框架的信息矩阵算法 算法3 6 1 第一步：初始化。令 蝣0 叩) = f 川i x , ，乃】= 厂( 薯，乃) ，v ( 一，y j ) e 兀： 并定义如下初始信息矩阵 2 l m = 【础0 】( 万，7 ) 篇0 】( 占，7 7 ) 馏0 】( 万，刁) 【彳】( 万，叩) 以抑( 万，7 ) 彳】( 万，r ) 【以抑( 万，7 7 ) ：； e y , ! o 川 ( 万，7 ) l 名! ：；o 】( 艿，7 7 ) 第二步z 方向递推 对= 0 , 1 ，n ；e = 1 , 2 ，m ；i = p ，e + 1 ，m ，令 眈m 荆_ ( 型号警麴卜 上述递推过程旨在通过m ( m + 1 ) ( ，z + 1 ) 2 次乘法运算( 列变换) 将初始信息矩阵 m 转换为 m l = 矗：0 ( 万，刁) 【z 告o 】( 万，7 7 ) 【以各。】( 万，7 7 ) 嚣0 ( 万，7 7 ) z 3 o 】( 万，7 7 ) 【以： ( 万，7 7 ) ；! t ：o t 】( 万，7 ) 【z 曼】( 万，7 ) 以： ( 万，刁) 第三步：y 方向n e w t o n 递推 i = 0 , 1 ，m ；l = 1 , 2 ，n ；j = ，+ 1 ，n ，令 蟛门砌= 丝等警塑r 上述递推过程旨在通过n ( n + 1 ) ( m + 1 ) 2 次乘法运算( 行变换) 将信息矩阵m 1 进 一步变换为 m 2 = 矗：0 】( 万，r 1 ) ；】( 万，7 7 ) 晚 ( 万，7 7 ) 石器1 ( 万，7 7 ) ；： m 】( 万，刁) 以：朋 ( 万，7 7 ) ： ： 丘：一】( 万，7 7 ) l 譬】( 万，7 7 ) 一： ( 万，7 7 ) 第四步：利用m 2 的第i + 1 列元素；! ，j = o ，1 ，z 构造关于y 的连分式s ，( y ) ，即 令 s ，。( y ；万，r ) = z 譬一( 万，刁) ， s ，( 少；万，矽) = z 鬟( 万，7 ) + ( y 一以) s + l ( y ；万，刁) 】占，k = 行一1 ，1 ，0 ， s ( y ；万，7 7 ) = 墨o ( y ；万，7 1 ) ， 其中i = 0 ，l ，m 第五步：构造关于x 的连分式 u - 坍( x ，y ；8 ，7 7 ) = 最( y ；万，7 7 ) ， v ( z ，y ；8 ，r 1 ) = s ( y ；万，r 1 ) + ( x 一薯) 【+ l ( x ，y ；8 ，刁) 】9 ，i = m 一1 ，1 ，0 ， 则v o ( x ，y ；8 ，r 1 ) 满足条件 ( 薯，y j ；8 ，刁) = 厂( t ，乃) ，( 一，乃) 兀= 证明对任意的( 一，乃) 兀：，i = 0 ，1 ，肌，由式( 3 5 2 ) 式( 3 5 3 ) 式( 3 5 11 ) 知 s ，q ( ；万，r ) = q g= z 譬9 ( 万，7 7 ) ， s ，。一l ( ；万，r 1 ) = q 叮一1 ( 万，刁) + ( j ，一一1 ) s ，g ( ；万，刁) 】声 = z 笃彳 ( 万，7 7 ) + ( 一一。) = ：1 ( 万，玎) d 】( 万，7 ) - - ，( i , q - 1 ( 万，刁) y q y q 一1 s ，g 一2 ( 均；万，r ) = q 。g 一2 ( 万，7 7 ) + ( y 一一1 ) s ，g l ( ；万，7 7 ) 】艿 =，g写2(万，刁)+(一一：)上互竺=二!至；掣 = 睹扩2 ( 万，7 7 ) s ，。( 托；万，7 7 ) = z 譬9 _ 1 】( 万，矽) s ( ；万，r ) = s ，o ( ；j ，1 7 ) = z g m 】( 万，r ) 由式( 3 5 4 ) ( 3 5 5 ) ( 3 5 1 0 ) ( 讳，；万，7 7 ) = & ( ；万，刁) = 刀与o 】( 万，7 7 ) 一l ( 讳，；万，7 7 ) = & 一l ( ；万，7 ) + ( 一讳一1 ) u p ( 石p ，y q ；8 ，7 7 ) 】叩， - f ，z - 1 o 】( 万，7 7 ) + ( 一x p 一，) 乃乒k o ( 万，7 ) _ 【刀w p - i o 】( 万，叩) x p xp 一1 一2 ( ，；万，1 7 ) 2 讳一2 ( ；j ，7 7 ) + ( 一讳一2 ) 一1 ( x p ，y q ；8 ，7 7 ) ” = 【乃互】( 万，7 7 ) + ( 一一：) = 名乒2 0 】( 万，7 7 ) u ( 讳，y q ；8 ，7 7 ) = 乃? ( 艿，7 7 ) 乒2 0 】( 万，7 7 ) 一【z 墨翔( 艿，7 7 ) x p xp 一2 乃乒1 0 】( 万，7 ) ( x p ，；万，7 7 ) = 孓( ；6 ，7 7 ) + ( x p - x o ) t ：；l ；o ( 万，刁) ：蟛】( 8 , r 1 ) + ( x p - x o ) 丝鲨业麴 工j 口一工0 = 名：】( 万，7 7 ) = f p 刃 x p ，】_ f ( x p ，凡) 显然，令万= r = 1 时，此时的算法是二元n e w t o n 插值格式的矩阵算法。 令万= 1 ，r = 一1 时，得到3 4 节的二元t h i e l e n e w t o n 型混合连分式插值 格式的矩阵算法。 令万= 一1 ，r = 1 时，得到3 2 节的二元n e w t o n t h i e l e 型混合连分式插值 格式的矩阵算法。 令万= 一1 ，r = 一1 时，得到二元t h i e l e t h i e l e 型混合连分式插值格式的矩 阵算法【1 2 】。 2 4 第四章二元牛顿关联连分式插值的矩阵算法 对于t h i e l e t h i e l e 型分支连分式插值、n e w t o n t h i e l e 型混合连分式插值、 t h i e l e n e w t o n 型混合连分式插值，不难发现，这几种二元有理插值格式是利用 一元n e w t o n 型插值多项式和一元t h i e l e 型插值连分式按照某种方式嵌套生成 的。本章利用牛顿多项式插值和关联连分式插值构造出的二元牛顿关联连分式 插值，给出了其递推算法的等价算法一矩阵算法，数值例子表明该算法的有效 性。 众所周知，二元分叉连分式( b b c f ) 最为常用的形式为四种： 第一种形式的b b c f 可写成以下形式( 3 7 】、 3 8 】) ： 旦(x，y)。+：_：j；焉x-xo+：-：乏兰蕊y-yo 第二种形式的b b c f ( 我们称之为s t i e i o e s 型二元分叉连分式) 可以写成以下 形x - ( 3 7 】、 3 9 】、 4 0 】) ： 驰y ) = + i ( x - 霉x o ) ( y - y o ) 第三种形式的b b c f 可以写成以下形式( 4 1 】) ： b ( x ，y ) = k o + 岛+ 号厶+ 謦 其中对k = o ，l ， ：b k o 坠掣( 趔+ 坠每必 + 1 ，1+ 2 。2 厶：b o k + 坠之蛙盟+ 坠遵划 岛，t + 2 第四种形式的b b c f 可写成以下形式( 我们称之为二元t h i e l e 型分叉连分式) ( 3 8 】、 4 2 、 4 3 ) ： 驰川= 瓦+ t x - x o + 寻+ 其中瓦= 。+ 上 丝 2 + 差商和逆差商是构造矩形网格上连分式插值函数的一种有效方法，为此我 们期望通过确定一种混合差商构造二元有理函数。令点集如下： 五m l + 1 = x o ，毛，妇眦】+ 1 ) c 口，b cr 艺【胁，2 】+ l = 蜘，y l ，y 2 【州4 2 j “，) c 【c ，d 】cr 兀：置m ：卜t 定义二元函数厂( x ，j ，) 在d = 口，b l c ，d 】上。 定义4 1 1形如 r ( x ，y ) = k o ( y ) + t q ( y ) ( x - x o ) + 如( y ) ( x x o ) ( x 一) + + 乞【。2 】+ l ( 力( x x o ) ( x x 。) ( z 一砭【。，2 】) ( 4 1 1 ) p ( x ，y ) q ( x ，j ，) 其中 砖( y ) = 组，五，x j ；y o 】+ 矽【，五，x ，；y o ，m 】( y y o ) f 。，：卜。! ! 二丝! ! 羔二羔! i ! ! ! + i 【，五，x , ；y o ，m ，t + 2 】+ 矽 ，五，x , ；y o ，m ，儿女+ 3 ( y - y 2 t + 2 ) k = o i = 1 ，2 ，2 胁2 + 1 ( 4 1 2 ) 的表达式称之为二元牛顿关联连分式。 近二十年来，国内外众多学者主要针对t h i e l e 型、s t i e i t j e s 型二元分叉连 分式插值进行了详细的研究，取得了大量的研究成果( 6 】、 8 】、 1o 】一 2 0 等) 。 对其它两种形式的b b c f 几乎很少研究，本文给出了一种混合差商的递推算法 以及借用线性代数中初等变换的思想，给出其矩阵算法，来处理二元牛顿关联 连分式的插值问题。 4 2 递推算法 设f ( x ，y ) 中的每个分量均有限，构造递推算法如下： ( 算法一)令 ；y 】= f ( x j ；x ，】 i = 0 ，1 ，2 咒2 1 + 1 歹= 0 , 1 ，2 m