（计算数学专业论文）基于块的混合切触插值.pdf

基于块的混合切触插值 摘要 本文主要讨论了基于块的混合切触插值问题，其主要内容包括基于块的 l a g r a n g e - s a l z e r 混合切触有理插值和基于块的n e w t o n 型混合切触插值。 利用分块的思想将连分式切触插值与l a g r a n g e 多项式相结合，构造了一种 基于块的l a g r a n g e - s a l z e r 混合切触有理插值。该有理插值具有更好的灵活性， 传统的s a lz e r 连分式插值则是它的一个特例，同时数值例子表明该插值的有效 性。 借助于n e w t o n 插值的插值格式，构造了一种基于块的n e w t o n 型混合切触插 值。由于采用了分块的方法，该插值提供了多种插值框架可供选择，其中扩展 的n e w t o n 插值则是本文的一个特例。同时讨论了二元情况，给出的数值例子表 明了该插值的有效性。 关键词：l a g r a n g e s a l z e r ， n e w t o n ，混合切触插值，块，有理插值 b l o c kb a s e db l e n d i n go s c u l a t o r yi n t e r p o l a t i o n a b s t r a c t t h es u m m a r i e so ft h i sd i s s e r t a t i o na r et h er e s e a r c h e s o nt h eb l o c kb a s e d b l e n d i n go s c u l a t o r yi n t e r p o l a t i o n ，w h i c h i n c l u d eb l o c kb a s e dl a g r a n g e - s a l z e r b l e n d i n go s c u l a t o r yr a t i o n a li n t e r p o l a t i o na n db l o c kb a s e dn e w t o n - l i k eb l e n d i n g o s c u l a t o r yi n t e r p o l a t i o n w ec o m b i n ec o n t i n u e df r a c t i o no s c u l a t o r yi n t e r p o l a t i o nw i t ht h el a g r a n g e s p o l y n o m i a lb yd i v i d i n gb l o c k sa n dc o n s t r u c tak i n do f b l o c k b a s e dl a g r a n g e 。s a l z e r b l e n d i n go s c u l a t o r yr a t i o n a li n t e r p o l a t i o n t h e n e wc o n s t r u c t i o nm e t h o di sm o r e f l e x i b l ea n dt h et r a d i t i o n a ls a l z e rc 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 sas p e c i a lc a s e s o m en u m e r i c a le x a m p l e sa r eg i v e nt oi l l u s t r a t et h ee f f e c t i v e n e s so ft h em e t h o di n t h i sp a p e r w i t ht h en e w t o n si n t e r p o l a t i n gf o r m a t i o n ，w ec o n s t r u c tak i n do fb l o c k b a s e dn e w t o n 1 i k eb l e n d i n go s c u l a t o r yi n t e r p o l a t i o n t h ei n t e r p o l a t i o np r o v i d e su s w i t hm a n yf l e x i b l ei n t e r p o l a t i o ns c h e m e sf o rc h o i c e sw h i c hi n c l u d et h ee x p a n s i v e n e w t o n sp o l y n o m i a li n t e r p o l a t i o na si t ss p e c i a lc a s e ab i v a r i a t ea n a l o g yi sa l s o d i s c u s s e da n dn u m e r i c a le x a m p l e sa r eg i v e nt os h o wt h ee f f e c t i v e n e s so ft h e i n t e r p o l a t i o n k e y w o r d s ：l a g r a n g e s a l z e r ，n e w t o n ，b l e n d i n go s c u l a t o r yi n t e r p o l a t i o n ，b l o c k ， r a t i o n a li n t e r p o l a t i o n i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金壁王些太堂 或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签字以弓潞 签字日期：矽g 年6 月石日 学位论文版权使用授权书 本学位论文作者完全了解金胆王些太堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被奄阅或借阅。本人 授权金胆：些态堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：刀流参 导师签名： 驰互 签字日期：弘- 孑年月f 日签字日期：砂多年月7 日 学位论文作者毕业后去向： 工作单位： 通讯地址： i 电话： 邮编： 办 致谢 诚挚的感谢导师唐烁教授，是您悉心的教导使我在数值逼近领域有了深刻 的认识，不时的讨论并指点我正确的方向，使我在这三年中获益匪浅。老师对 学问的严谨更是我学习的典范。 感谢系里的老师们，你们不仅勤勤恳恳地传授了我专业知识，同时你们严 谨的治学态度、高尚的教学品德都深深地感染了我，是我学习的楷模；感谢2 0 0 5 级研究生3 4 班的同学们，与你们在一起生活和学习，我是荣幸的，同样也是快 乐的，这将成为我以后美好的回忆；感谢师姊盛敏、梁艳，同学邹乐在论文写 作过程中给予了宝贵的意见。还有9 0 7 机房的全体老师们，在学习期间，你们 也都给了我很多的帮助。 感谢我的父母，二十多年来，对我的生活和学习给予了无私地关爱、支持 和鼓励。 感谢各位评审专家在百忙中抽出时间对论文给予的批评指正和宝贵意见。 i v 李辰盛 2 0 0 8 年4 月 第一章绪论 从给定的离散点值去构造一个连续定义的( 简单) 函数，使得它与被逼近 的函数在给定点的值完全一致，这样的问题称为插值问题。插值问题是计算数 学中的一个基本问题，然而在信息的存储、处理、分析、传输日益数字化的今 天，插值问题却无处不在：通过离散点作一条光滑曲线、读表 5 1 、由给定数据 求数值微分和数值积分、计算函数值、用简单函数代替复杂函数。更复杂的插 值问题可能会附加导数插值条件i l o l 1 3 】f 2 3 i t 2 4 j 3 0 】【“】f 4 6 】【5 1 】、增加额外约束，像单调性、 凸性、周期性等。常用的插值函数有多项式、分段多项式、有理函数、分段有 理函数、三角函数、指数函数。其中多项式和有理函数作为简单函数被广泛关 注。另外，计算插值的算法包括系数算法和求值算法。其中系数算法用于得到 插值函数的表达式，而求值算法用于求值函数在不同于插值点的任意点处的值 1 7 1 3 6 1 。 多项式插值与逼近是整个数值逼近的基础，它被广泛应用于方程求根、函 数逼近、数值微分、数值积分、积分和微分方程数值解等。多项式插值与逼近 的广泛应用是基于它们结构简单，易于构造，便于利用。常用的一元多项式插 值方法是n e w t o n 插值 3 4 1 、l a g r a n g e 插值( 3 5 1 和带导数插值条件的h e r m i t e 插值、 b i r k h o f f 插值 2 7 1 2 9 1 。 有理函数插值与逼近比多项式更灵活、更有效，且能反映函数的一些固有 特性，如奇性等。所以，人们在数值与函数逼近、计算机辅助几何设计中偏爱 有理函数。在有理函数插值格式的构造方法中，最常用的是基于连分式的t h i e l e 型连分式插值方法。连分式是有理逼近的一种有效方法，荷兰数学家和天文学 家c h r i s t i a a nh u y g e n s ( 1 6 2 9 1 6 9 5 ) 首次提出将连分式用于解决有理逼近问题。随 着科学技术的发展，连分式理论的应用范围不断扩大，如r o b e r tm c o r l e s s 用 连分式研究混沌理论1 2 2 1 。二十世纪六十年代后，俄罗斯数学家v s k o r o b o g a t k o 将分支思想应用于连分式理论，开创了连分式理论和方法研究的新纪元。比利 时学者a c u y t 1 4 】【1 5 1 通过定义多元逆差商和多元偏倒插商构造了一种对称型的 二元分叉连分式展开和逼近。波兰学者w s i e m a s z k o 3 1 1 【3 2 1 【3 3 l 提出了不同类型的 二元分叉连分式插值格式。从1 9 9 0 年开始，朱功勤、檀结庆和顾传青等人在基 于连分式的有理插值与逼近方面开展了一些列的研究工作。檀结庆等提出了二 元t h i e l e 型向量连分式有理插值方法，建立了多元分叉连分式的特征性定理、 唯一性定理、边界插值定理和对偶定理等【3 】【4 j 【1 3 】【3 7 1 【4 2 i 1 4 3 】；檀结庆、唐烁等对 n e w t o n 插值多项式和t h i e l e 型插值连分式巧妙地进行糅性加工得到了几种混 合有理插值格式，通过引进混合差商的概念，解决了混合有理插值的有效计算 问题 3 s l 3 9 1 1 4 0 1 。 对于将插值节点分块用于连分式插值的思想出现在上个世纪8 0 年代， 德 国学者h w e r n e r 给出了t h i e l e w e r n e r 插值格式4 5 l 。近年来，由于连分式理 论的快速发展，檀结庆教授等将块插值用于混合型有理插值， 取得了丰富的 成果 2 3 1 1 4 8 】 4 9 】如5 。下面我们简要地介绍多项式插值、有理函数插值和基于块的 混合插值。 1 1 多项式插值【1 】 多项式插值是整个数值逼近的基础，它被广泛应用于方程求根、函数逼近、 数值微分、数值积分、积分和微分方程数值解等。多项式插值与逼近的广泛应 用是基于它结构简单，易于构造，便于利用。常用的多项式插值方法是l a g r a n g e 插值和n e w t o n 插值。 1 1 1多项式插值的一般提法 设( 一， ) ，i = o ，1 ，甩是y = f ( x ) 在区间【口，b 】上的n + 1 个型值点，其中 ( i = 0 ，1 ，拧) 互异，y i = f ( x ，) ，o = o ，1 ，玎) ，所谓多项式插值问题，就是寻找多 项式函数 只( x ) = a 0 + a t x + + a x ”( 1 1 1 ) 使之满足 z ( 而) = 厂( 葺) ，江o ，1 ，9 1 ( 1 1 。2 ) 此时，称x o ，x i ，x 一为插值节点，y f 项x f ) ，o = 9 1 ，刀) 为型值，( 1 1 2 ) 式为 插值条件，( x ) 称为插值函数，火石) 称为被插函数。，( d = 厂( x ) 一( 功称为插值 余项。 为了求插值多项式，只须求出参数a o ，口l ，即可。在( 1 1 1 ) 式中将 a o ，a t ，视为未知量，它就是一个线性代数方程组，因此，我们可以通过求解 方程组来确定己( z ) ，这就是通常所说的待定系数法。由求解方程组( 1 1 1 ) 所确 定的n 次多项式乞( x ) 总是存在唯一的。下面我们介绍l a g r a n g e 于1 7 9 5 年给出 的结果。 1 1 2 l a g r a n g e 多项式插值 记 z j ( x ) = ：，：- 。i 。x 。- x , ，f = ：。，1 ，。，l ， ( 1 1 3 ) 这里的每个l ( x ) 都是n 次多项式，且由( 1 1 3 ) 式容易验证巳( x ) 满足 2 o ( 五) 2 t ：i 二 元- ，= o ，t ，尼( 1 1 4 ) 可以证明函数组 o ) ? 。在插值区间【口，6 】上线性无关，所以这n + 1 个函数 可作为只( x ) 的一组基函数，称为插值基函数。 至此我们得到下面的定理。 定理1 1 1 存在唯一的1 1 次多项式 ( x ) - - 厂( ) ( x ) ( 1 1 5 ) 满足插值条件( 1 1 2 ) 。 称( x ) 为1 1 次l a g r a n g e 插值多项式，( 1 1 5 ) 式为函数弛) 在点 五( i = o ，l ，n ) 的1 1 次l a g r a n g e 插值公式。 用( x ) 作为以x ) 的近似，在区间 口，6 】上有如下误差估计定理。 定理1 1 2 若f o + 9 ( x ) 在区间 口，6 】上存在，则在区间【口，6 】上的n + 1 个互异的点 薯( i = o ，1 ，玎) 对苁x ) 所作的1 1 次l a g r a n g e 插值多项式( x ) 有误差估计为 以m 州= 错冉卜乩 ( 1 1 6 ) 其中孝位于包含，而，毛，z 的最小闭区间的内部。 满足( 1 1 6 ) 式的，( x ) 称为1 1 次l a g r a n g e 插值余项。 1 1 3n e w t o n 多项式插值 l a g r a n g e 插值公式的缺点是，当插值节点的个数有所变动，例如，为了提 高精度，有时需要增加节点的个数，l a g r a n g e 基函数( x ) ( f - o ，1 ，甩) 就需要随 之发生变化，从而整个插值公式也要发生变化，这在实际计算中是不方便的。 为了克服这一缺点，我们介绍n e w t o n 多项式插值。 定义1 1 1 设已知互异点而( 江o ，l ，拧) 上的函数值厂( 薯) ( f = o ，l ，刀) ，我们称 m ：必，f 。 j 一工t 为f ( x ) 在五，x ，处的一阶差商。一阶差商的一阶差商 小刊：盟粤划七 称为二阶差商，一般地，称 厂【而，而，&+，】=2=j鱼鱼!二2三生坚芝兰i二乏鱼浏，七尼+ 为函数f ( x ) 在点x o ，而，坼，x k + 1 上的k + l 阶差商。 定理1 1 3 存在唯一的1 1 次多项式 只( x ) = 厂( x 。) + n 厂 而，而，- n ( x 一毛) ( 1 1 7 ) 满足插值条件( 1 1 2 ) 。 称只( x ) 为r 1 次n e w t o n 插值多项式，( 1 1 7 ) 式为函数以x ) 在点而( i = o ，l ，n ) 的1 1 次n e w t o n 插值公式。 由于理论和实践的需要，有时需要构造一个插值函数，不但在给定点取已 知的函数值，而且还取已知的导数值，使得插值函数和被插值函数贴近程度更 好。这种插值称为h e r i m t e 插值，有时也称为切触插值。 给定互异插值节点为薯( f = o ，1 ，r ) ，相应的函数值为s ( x ，) ( i - 0 ，1 ，) 以及 各阶导数值为厂 ( t ) ( 七= 1 ，2 ，；f = o ，1 ，i ) ，并且( + 1 ) = 拧+ l 。 8 】、【9 】给 出了一种满足插值条件的扩展n e w t o n 插值。 ，o “ - - _ _ _ _ _ ，- _ _ _ 一 只( x ) = 厂( ) + 厂【而，而】( x 一而) + + 九，而】( x 一而户 f o + ll o + i + 【而矗，一 ( x 一粕) “+ 石：磊，x a ，毛】( x 一) t o + 1 ( x 一而) i o + it r + 1 +赢，再矗】(x-fxo x o) 叱( x 一) + + ， ，】() 妒1 ( x 一) 其中九赢，赢】为 ) 在点，墨，而的广义差商。递归定义如 下： 厂c 意，= 制一嘲扎 ，c 靠，袁，：正瑟雩一心慨“ + i- l + 1肺 ，_ ，- - - ，_ 、 厂【， ，气。， ，气1 4 ， ? 1 - l 掣， s lt g i + l m l ， - 一、，- - l - 、，1 ，- _ - ，- k - ，- - _ 一、 ：! 兰：苎：玉：! ：羔：! ：兰：二：兰上z 堕：兰：至j ：- ：兰= ! ：盏：量1 1 朋f 。+ 1 。 x k x i h 1 1 2 有理函数插值1 7 1 1 2 1有理函数插值的一般提法 设( ，乃) ，江o ，1 ，m + n 是与y = a x ) 有关的m + n + 1 个型值点，其中x t ， o = 蜘j m + 功互异，y f 响枷= o ，1 ，聊+ 玎) ：荆= 盈，= e b , e ，所谓有理插 f 0 i = 0 值问题，就是寻找有理分式函数 毛一= 器= 菩舞 n 2 m 使之满足 p ( x 、 如，一( _ ) 2 磊2 f ( x j ) ，j = o 1 ，一，聊慨 ( 1 2 2 ) 此时，称工o ，x i ，+ 撑为插值节点，y ，项x 茂= o ，1 ，m + r t ) 为型值，( 1 2 2 ) 式为插值条件，心一( x ) 称为插值函数，以x ) 称为被插函数。，( x ) = 厂( x ) 一如， ) 称 为插值余项。 对于有理插值问题( 1 2 1 ) ，( 1 2 2 ) 的解，人们往往通过求解下列线性方程 组得到： a o + q 葺+ + a m x f ”一咒( b o + 6 l 而+ + 吃五“) = o ，= o ，1 ，m + 刀) ( 1 2 3 ) 然而，有理插值问题( 1 2 1 ) ，( 1 2 2 ) 的解不一定总是存在的，而且满足( 1 2 3 ) 的解不一定满足插值条件( 1 2 2 ) 。大量的文献对于有理插值问题( 1 2 1 ) ，( 1 2 2 ) 的解的存在唯一性给予了研究。如n m a c o n ，和d e d u p r e e 在 7 】中研究了有 理插值问题( 1 2 1 ) ，( 1 2 2 ) 的解的存在唯一性；在文献【7 中利用n e w t o n 插值多 项式，给出判别有理插值问题( 1 2 1 ) ，( 1 2 2 ) 的解是否存在的另一个方法等。 1 2 2一元t h i e l e 型插值连分式 由1 2 1 的介绍可知，要想得到有理插值函数的显示表示，需要对于每个 具体问题解一个齐次线性方程组。下面来介绍一种有理插值函数算法一一 t h i e l e 型连分式插值算法，作为一种有效的有理插值算法，它被广泛地应用于 数值逼近【7 1 ，图像处理【2 d 6 2 1 】。 定义1 2 1 称下述形式的连分式： 6 b + 寻+ 寻- i - 4 - 字+ ( 1 2 4 ) ” 岛+ 岛 玩 + 一“7 为t h i e l e 型连分式【5 1 定义1 2 2 设z = 扛，ii 删 是复平面上一点集厂 ) 是定义在g ( g3x ) 上的函 数。 令 c a l x , 2 ，【五，；= u ，1 ，2 ， 伊，】2 雨x 再q - - x 而p ， 诃，矿。，吨卜而焉i i x k 再i x k 五_ l x k c p x 磊oi 而， 缈l ，一2 ， j 一 ，而，吒一1 j 称由上述公式确定的q , x o ，毛，政】为函数厂g ) 在点x o ，x l ，x 2 ，以处的k 阶 谫葬商 定理1 2 1 设 驰瑚+ 寻+ 寻+ + 等= 舞 2 渤 贝, l jd e g 只= 剐，d e 咖卧其中d e g 表示多项式的最高溉m 表示不超 过的最大整数。 b ( 功2 驴 殇】+ 丽x - x o + 乏石：x 而- - x i + + ；赢， ( 1 2 6 ) 其中讲，x l ，一，x t 】0 ，k = 0 , 1 ，n 为厂( x ) 在x o ，x l ，- ，x k 处的k 阶逆差商，则 有 民( ) = 厂( t ) ，i = 0 ，i ，i “n 。 定义1 2 3 如果连分式 驰m + 寻+ 寻+ + 等 满足b ( 五) = ( 五) ，f = 。，l ，刀，则称该连分式为函数厂( 力的 孚兰 型t h i e l e 插 值连分式。 定理1 2 - 3 函数厂( x ) 的 竿量 型t h i e l e 插值连分式是唯一的。 定理1 2 4 设 x o ，而，) c 【口，b 】cr ，厂( x ) 在f a , b 1 上有直到n + lf t 的导数，若 6 嘶) 却寻+ 寻+ + 等= 器 满足墨( ) = 厂( ) ，i = 0 ，l ，刀，则v x e a ，b 】，均了孝j k ，x i 一，石。，石) ，此处 ，k ，x l ，矗，x ) 表示包含x 0 而，x 。及x 的最小开区间，使得 m h ( 功= 答， 其中，( x ) = o x o ) ( x 一而) ( x - x n ) 。 1 2 3 切触有理插值 切触有理插值问题最早是由h e r b e r te s a l z e rf 3 0 】于19 6 2 年在“n o t eo n o s c u l a t o r yr a t i o n a li n t e r p o l a t i o n 一文中提出的。近些年来，切触有理插值， 包括有理样条得到了人们的重视【1 3 】f “儿3 0 】i 蚓。在【5 】中较系统的介绍了为解决一元 切触有理插值和样条问题的各种算法，包括s a l z e r 算法，e u l e r m i n d i n g 公式， w u y t a c k 算法等。切触有理插值是类似于多项式插值中的h e r m i t e 插值的一种 插值，即设已知 而 _ ，s = 0 ，1 ，u ， 需要时可先将点重新排序后再进行分块。显然有 ( 以- c , + 1 ) = ，+ 1 ， 记织( 工) = 兀 一而) ，考虑下面的函数 r ( x ) = 足( x ) 鼠( x ) ， ( 2 2 1 ) 其中b a x ) - 1 7 哆( x ) ，以及足( z ) ( s = o ，1 ，材) 为在块f o = o ，1 ，甜) 上的 s a l z e r 插值连分式。如果适当选取( 2 2 1 ) 式中的足( x ) ，使丁( x ) 满足 丁( 葺) = 厂( 毛) = z ，薯z ( 2 2 2 ) 且丁( ) ( 薯) = f ( 薯) = z ，k = 1 ，2 ，f = 0 ，l ，而墨 ( 2 2 3 ) 我们就称( 2 2 1 ) 式所确定的丁 ) 为厂( x ) 的基于块的l a g r a n g e s a l z e r 混合切触有 理插值。 下面我们考虑r ) 如何构造。 对s = o ，l ，“，i = q ，巳+ 1 ，或，= 0 ，1 ，u ，我们有 e ( 而) = e & ，) = o 1 ；二；三：二：；j ：乏+ 1 ，4 c 2 2 4 ， 由( 2 2 1 ) 和( 2 2 4 ) 式得，丁( 葺) = 足( t ) e ( 而) 丁( 五) = 万d k ( 愿( x ) b ( 圳，啊 = 础趟0 ) 摩k - j ) ( 薯) + 趟( 葺) e ( - ) k = l ，2 ， j = o 因而r ( 栌南，f q + 1 ，。，t ，s - o ，”一m 一k - ! 础赵1 葺) 毯h ( 而) 硝( 薯) = 攻葫 一 ( 2 2 5 ) k2 1 ，2 ，l2q ，巳+ 1 ，以，s = 0 ，1 ，甜，( 2 2 6 ) 其中硝( t ) = r s ( x i ) 。 此时的r ) 是在插值节点为群= 毛，i = q ，g + 1 ，) ，函数值及各阶导数 值为f = ( b ( 毛) ，砖( 薯) ，t z $ ( t t ( 葺) ) ，江g ，q + 1 ，以 的s a l z e r 连分式插值，并且 足o ) 满足插值条件( 2 2 5 ) 和( 2 2 6 ) 。 至此我们得到下面的定理： 定理2 2 1如果s a l z e r 插值连分式r ( x ) = 麦是定义在块 群= 薯，i = g ，q + 1 ，t ( s = o ，1 ，“) 上，存在并且满足插值条件( 2 2 5 ) 和 ( 2 2 6 ) ，同时q ( _ ) o ，( 巧墨一 _ ，咆) ) ，那么 r ( 薯) = 厂( 葺) = z ，丁( ) ( 而) = 厂( 再) = z n ，而墨，k = 1 ，2 ，f f 。 证明对q i 以，s = 0 ，l ，u 。通过( 2 2 1 ) ，( 2 2 4 ) ，( 2 2 5 ) 式显然 r ( 再) = r ( 葺) 色( 而) = z ， 州葺) 2 嘉( 足( z ) 最( x ) ) l 石毯， 由( 2 2 6 ) 式得： 丁( ( t ) = 万d k ( r ( x ) e ( x ) ) i = 丢k - i 掣砖气一) 毯纠( t ) + 砖( ) b ( 而) 彳( t ) 一k - ic z 砖7 ( - ) 毯t 一( 薯) e ( 而) 情形1 当1 1 = 1 时，每一个块只含有一个点，那么 忍( x ) = 兀( x ) = 兀( x x 1 ) ， rr + i j sj s j = 0j = 0 1 4 e ( 薯) r ( t ) 2 南， 心( t ) = 一k - i 创砖，( t ) 毯t 一1 气) e ( 墨) ，k = 1 ，2 ，j = o ，1 ，“， 所以 ， 丁( x ) = r ( x 皿( x ) = z ，耋c r ( 瓦) + 耥+ 瓦x - - 雨x s 一赫】。豇( h ) 。 广倒 其中纠，墨 ( k = 1 ，2 ，t s ) 是定义在点( t ，r ( 薯) ) 的带重节点的k 阶 反差商。r 情形2 当甜= 0 时，只有一个块包含所有点，即为s a l z e r 连分式插值。 那么 岛( x ) = 1 ，岛( 而) = z ，硝。( 而) = z ( ，k = l ，2 ，i = 0 ，1 ， t ( x ) = r ( x ) 咖+ 百x - x o 一百x - x o + 百x - x o + 百x - x a 寻 兰二兰= ! 盟兰五 ( 2 2 7 ) 十斗 6 ，o + 6 ，1 4 - , 。斗 b ， 例1 设插值节点集为x 。= o ，3 ，对应的函数值和各阶导数值集为 k = ( 丢 ，( 2 专) 】，构造基于块的l a g r a n g e - s a l z e r 混合切触有理插值。 格式1 取l l = r ，此时将五分成两块f = o ，叫= 3 ) ， 所以丁( x ) = r ( x ) 岛( x ) + r ( x ) 骂( x ) o 其中岛( x ) = ( ) 2 = ( ) 2 ，r ( 而) 2 南2 吉， 她) = 譬铲= 7 5 4 ， 则民( x ) = r ( 而) + 砭( ) ( z 一而) = 三字， 其中骂( x ) = ( x x o ) 2 彳，局( 而) 2 焉2 吾， 她) = 掣一而1 3 ， 贝0 r i ( x ) = 墨( 五) + 爿( 而) ( x 一西) = - 1 1 3 矿x + 6 3 ， 所以丁( j c ) = i 1 0 8 x _ l 1 2 x 2 + 1 2 x + 1 。 容易验证z ( x ) 满足插值条件。 格式2 取“：0 ，此时只有一个块包含所有点，根据( 2 2 7 ) 式我们得到 r ( x ) = 筹 容易验证丁( x ) 满足插值条件。 例2 设函数厂( x ) = 軎【_ ，且五= o ，1 ，2 ) ，显然有 砭= ( 1 o ) ，( * ) ，( 三，一丢) ) ，删 采用基于块的形式，x 2 分成三块 霹= o ，z = 1 ) ，霹= 2 ) ， 则丁( x ) ：3 x s - 2 2 x 4 + 丽6 0 x 3 - 6 6 x 一2 + 5 0 ， 容易验证丁( 石) 满足插值条件。 通过图像( 图2 1 ) 可知，r ( x ) 具有较好的逼近效果。 注：图2 1 为插值函数7 ( 工) 与被插值函数( j ) = 两1f 逼近效果的图形。 1 6 3 1 引 言 第三章基于块的n e w t o n 型混合切触插值 传统的n e w t o n 插值是基于点的插值。在整个集合z 上的所建立的n e w t o n 插值多项式被降低了灵活性和缺少交互性，因为插值完全由原始的插值节点集 所确定。为得到灵活的混合插值， 4 9 将基于点的n e w t o n 插值推广到基于块的 插值。本章在此基础上，借助于扩展的n e w t o n 插值或s a l z e r 连分式插值将其 推广到切触的形式，构造了一种基于块的n e w t o n 型混合切触插值。 3 2 基于块的n e w t o n 型混合切触插值的构造 3 2 1基本思想 给定插值节点集为z = 薯，i = 0 ，1 ， c 【a , b cr 以及在k ，b 】上的实函数 ( x ) ，对应的函数值和各阶导数值集为 r = ( ( z ，z ，z ( ，彳( ) ) ，f = o ，l ， ， 且( + 1 ) = n + l 将t = 葺，i = o ，1 ，) 分成u + l 块f = ，+ l ，) ，s = o ，1 ，甜， 需要时可先将点重新排序后再进行分块。显然有 ( 吐一q + 1 ) = ，+ 1 s = 0 我们考虑下面这个具有类似n e w t o n 格式的函数 r ( x ) = i o ( z ) + 厶( x ) ( x ) + + l ( x ) ( x ) q 一。( x ) ( 3 2 1 ) 其中 t q ( z ) = 兀。一薯) 州，s = 0 ，l ，甜一1 ， ( 3 2 2 ) 以及( x ) ( s = o ，l ，甜) 是块f ( j = o ，1 ，u ) 上的扩展的牛顿插值或有理函数切 触插值， 如果选定所有上述的l ( x ) ( j = o ，1 ，甜) 使得 丁( t ) = 厂( 五) ，丁( t ) = ( 而) ，而茸，k = l ，2 ，i = 0 ，1 ，。 我们就称由( 3 2 1 ) 和( 3 2 2 ) 所定义的函数r ( x ) 为厂( x ) 的基于块的n e w t o n 型混合切触插值。 3 2 2 分块上插值函数l ( x ) 的构造 假设zc 【口，b cr ，厂( x ) 为一个定义在【口，b 】上的实函数，并且厂( 而) = z ， 厂( ) = ) = z ，j i = 1 ，；f = o ，l ，。 引入下面的记号： ”- f , ， = ，k = 1 ，r j ；i = 0 ，1 ， 1 7 以及对s = 1 ，u ， fiso错，z=c：，c：r， = 万d k ( 掣) l ，呐 ( 3 2 3 ) ，k = l ，；i = q ，乞+ l ， ( 3 2 4 ) 其中f o ( x ) = ( x ) 。 这里的l ( x ) ( s = o ，1 ，“) 是块f ( s = o ，l ，“) 上的扩展的牛顿插值或有理 函数切触插值，并且满足 ( 墨) = z 印，i = 巳，q + l ，或；s = o ，1 ，材 l 。( 而) = z ，七= l ，；j = 乞，c s + 1 ，或；占= o ，1 ，甜 ( 3 2 5 ) ( 3 2 6 ) 定理3 2 1 如果满足( 3 2 5 ) 式和( 3 2 6 ) 式的所有插值l ( x ) ( j = o ，1 ，“) 都存在， 则 t ( x i ) = z ，r ( ( t ) = ，七= 1 ，2 ，；f - o ，1 ， 证明：先证丁( 五) = z ，f = o ，1 ， 对每一个f o ，1 ，) ，存在一固定s o ，1 ，“) ，满足c ss fs 以，由( 3 2 1 ) 式得： 丁( 薯) = l o ( 而) + 五( x , ) c o o ( 而) + + ( 而) ( 五) 致一。( 一) ， 通过( 3 2 5 ) 和( 3 2 3 ) 得到 t ( x , ) c o o ( _ ) 纵一。( 葺) = z 以o c o o ( 而) q 一( 而) ：掣c o o ( 五) ( 而) = i 工- 打，- 工，- q i 【薯j 。 = ( z 卜1 o 一一。( 葺) ) ( 薯) 织一：( t ) 。 因此，通过递推可得 丁( 一) = s o ( 薯) + ( 五) ( 而) + + l ( 而) ( 而) q 一。( 葺) = 厶( 葺) + ( t ) ( _ ) + + ( z 。1 o - l 一。( ) ) ( 薯) q 一：( 墨) = 厶( 薯) + ( 薯) ( 薯) + + z ”k o ( 墨) 织一：( x i ) = = 0 = z 。 再证丁( 2 ) ( t ) = z 2 ，k = 1 ，2 ，；f 0 ，1 ，。 用数学归纳法：对g f 以，s = 0 ，1 ，u 。 当k = l 时，对每一个f o ，l ， ，存在一固定j o ，1 ，“) ，满足c f 以， 由( 3 2 1 ) 式得： 丁( 一) = ( 厶( x ) + ( x ) ( 工) + + l ( x ) ( x ) q 一。( x ) ) i 拈而， 其中 ( l ( 石) ( x ) 致一。( 石) ) k = c ( 薯) ( 五) q 一。( 五) + l ( 薯) ( ( x ) q 一。( x ) ) l ，。而， 讹m 1 = 帮) 。i 州 由( 3 2 5 ) n ( 3 2 3 ) ，我们有 地m 。= 错。 因而我们得到： ( t ( 工) 鳓( z ) q 一。( z ) ) k =(z掣)。i，再()q一。(薯)+错(峨(z)q一。(z)i，叶 一”l - l ( 一) ) q 一。( 薯) 一( z s - i , o _ _ i s 一。( 薯) ) q 一。( ) q 一。2 ( ) ( ) 眈一。( _ ) +错(x)织一：(x)。ij啊q一。(薯)+(而)q一：(薯)q-1(葺) = z ”1 1 c o o ( 薯) q 一：( 而) 一一。( ) ( 薯) q 一：( 而) 一五：二：= 竺= ! ：( 苎) 生f 苎! ：竺= ! ! 苎2 + 生= ! ! 兰! 竺= ! ：【苎! 堕( 兰! ：竺= ! ! 苎! q 一- ( 而) q 一。( 而) + z 卜1 0 ( ( x ) c o , 一：( x ) ) 。i ，叶- l 一。( ) ( ( x ) q 一：( z ) ) 。i j 哟 z 卜1 o q 一。( 薯) ( t ) 致一：( 薯) l 一。( 薯) q 一。( 薯) ( 薯) q 一：( t ) q 一。( 而)噱一。( 而) = ( 厂”1 ( x ) 嘞( x ) q 一：( x ) ) i ，；而一( 一。( x ) 嘞( x ) q 一：( x ) ) 。l ，哟， 所以，通过递推可得 丁。( 薯) = ( 厶( x ) + ( x ) ( x ) + + l ( x ) ( x ) q 一。( x ) ) i ，啊 = ( 厶( x ) + ( x ) ( x ) + + 厂”1 ( x ) ( x ) q 一：( x ) 一l 一。( x ) ( x ) q ：( x ) ) l 必 = ( 厶( x ) + ( x ) ( x ) + + 一：( x ) ( x ) q 一，( x ) + 厂卜1 ( x ) ( x ) q 一：( x ) ) i ，而 = = ( 厂o ( x ) ) k = = z 。 假设k 一1 时成立， 即丁( 扣1 ( 而) = z 扣1 ， 显然r 似( 一) = t ( k - 1 ) ( 而) ) = ( z 扣1 ) = z 所以由数学归纳法知： z ( 。) ( 葺) = 彳，k = 1 ，2 ，f = 0 , i ，。 定理证毕。 3 2 3 特殊情形 情形1 如果所有的( x ) ( s = o ，l ，材) 都是在块f ( j = o ，l ，材) 上的扩展的牛顿 插值多项式只o ) ，则基于块的n e w t o n 型混合切触插值就退化为在整个插值空 间z 上的多项式切触插值 r ( x ) = e o ( x ) + 丑( x ) ( x ) + + ( x ) ( x ) q 一( x ) 。 情形2 如果所有的l ( x ) ( s = o ，l ，u ) 都是在块f ( s = o ，1 ，u ) 上的s a z l e r 插值 r ( x ) ，那么得到 r ( x ) = r ( x ) + 墨( x ) ( x ) + + r ( x ) ( 石) 吼一( 石) 。 特别地，当u = 0 时，整个插值空间被分成一个块，则 t ( x ) = r ( x ) ， 其中r ( x ) 为在整个插值空间z 上的s a z l e r 插值。 3 2 4 数值例于 例1 给定插值节点集为x = 0 , 3 ) ，对应的函数值和各阶导数值集为 x = ( 1 专 ，( 2 ，1 1 ) ，构造满足插值条件的基于块的n e 叭。n 型混合切触插值。 格式1 取u - - - r ，此时将五分成两块：矸= o ) ，爿= 3 ) ， 所以t ( x ) = 厶( x ) + 厶( x ) ( x ) 。 其中( x ) = x 2 ，i o ( x ) = 1 + i 1x ，( 石) = 一壶+ 志x ， 所以丁( x ) = 1 + 丢卜i 1 2x + 1 1 0 8 一 容易验证r ( x ) 满足插值条件。 格式2