（计算数学专业论文）插值的一般框架研究.pdf

插值的一般框架研究 摘要 本文主要讨论了二元插值的一般框架问题，其主要内容包括二元插值一般 框架的一个注记、对称型有理插值的框架以及基于块的混合有理插值的一般结 构。 通过引进新的参数将檀结庆和方毅研究的二元插值的一般框架做进一步 的推广和改进，使之可以用来处理带不可达点和逆差商不存在的插值问题，并 将其推广至多元情形和基于块的混合有理插值情形，包含近年来人们研究的多 种插值格式，如修正t h i e l e 型连分式混合插值，基于块的牛顿型混合有理插值， 基于块的t h i e l e 型混合有理插值等。 通过引进新的参数将檀结庆和方毅研究的二元对称型插值的一般框架做 进一步的推广和改进，包含近年来赵前进、王家正、k h i k u c h m i n s k a ，s m v o n z a 等人所研究的几种对称插值格式，并给出了几种新形式的对称型混合有理插值 格式。 将s w k a h n g 研究的插值的一种显示表达式进行改进和推广，构造了基于 块的一元插值函数的一般结构，这种插值结构不仅包含了s w k a h n g 研究的显 示公式，而且包含基于块的牛顿型混合有理插值，基于块的t h i e l e 型混合有理 插值以及t h i e l e w e r n e r 型切触有理插值，此外还可以通过对参数的选取获得其 它类型的插值函数。此外还推广s 。w k a h n g 研究的显示公式到多元情形，研究 了二元情形的插值框架，插值定理，对偶插值格式，包括的特殊插值格式，并 给出了这种插值框架的误差估计。 关键词：n e w t o n 插值，关联连分式插值，一般框架，块混合有理插值 r e s e a r c ho ng e n e r a lf r a m e so fi n t e r p o l a n t s 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 so ng e n e r a lf l a m e so f b i v a r i a t ei n t e r p o l a n t ，w h i c hi n c l u d en o t eo ng e n e r a lf r a m e so fb i v a r i a t ei n t e r p o l a n t ， g e n e r a lf l a m e so fs y m m e t r yr a t i o n a li n t e r p o a l t i o na n dg e n e r a ls t r u c t u r e so fb l a c k b a s e di n t e r p o l a t i o n a lf u n c t i o n 。 an e wg e n e r a lf l a m ei se s t a b l i s h e db yi n t r o d u c i n gm u l t i p l ep a r a m e t e r s ， w h i c hi se x t e n s i o n sa n di m p r o v e m e n t so ft h o s ef o rt h eg e n e r a lf l a m e ss t u d i e db y t a na n df a n g ，a n dc a nb eu s e dt od e a lw i t ht h ei n t e r p o l a n tp r o b l e mw h e ni n v e r s e d if f e r e n c e sa r en o n e x i s t e n to rm e e t i n gu n a t t a i n a b l ep o i n t s 。w ee x t e n dt h eg e n e r a l f l a m e st om u l t i v a r i a b l ec a s ea n db l o c kb a s e db l e n d i n gr a t i o n a li n t e r p o l a t i o nc a s e 。 m o d i f yt h i e l e t y p ec o n t i n u e df r a c t i o nb l e n d i n gi n t e r p o l a t i o n ，b l o c kb a s e db l e n d i n g r a t i o n a li n t e r p o l a t i o na r es p e c i a lc a s e so ft h eg e n e r a lf l a m e s 。n u m e r i c a le x a m p l e s a 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 er e s u l t s 。 an e ws y m m e t r yg e n e r a lf l a m ei se s t a b l i s h e db y i n t r o d u c i n gm u l t i p l e p a r a m e t e r s ，w h i c hi se x t e n s i o n sa n di m p r o v e m e n t so ft h o s ef o rt h eg e n e r a lf l a m e s s t u d i e db yt a n a n df a n g ，t h es y m m e t yi n t e r p o l a t i o nf o r m u l a es t u d i e db y k h i k u c h m i n s k a ，s m v o n z a ，z h a oq i a n ji n ，w a n gj i a z h e n ge t c a r es p e c i a lc a s e s o ft h es y m m e t r yg e n e r a lf l a m e ，a n dg i v es e v e r a l s y m m e t r yb l e n d i n g r a t i o n a l i n t e r p o l a t i o n so fn e wf o r m w ee x t e n da n di m p r o v e dt h er e s u l t so fs w k a h n g ，c o n s t r u c tg e n e r a ls t r u c t u r e o fo n ev a r i a b l e i n t e r p o l a t i o nf u n c t i o n ，w h i c hn o to n l yi n c l u d et h er e s u l t so f s w k a h n g ，b u t a l s oe m b o d yb l o c k b a s e dn e w t o n l i k eb l e n d i n gr a t i o n a l i n t e r p o l a t i o n ， b l o c kb a s e dt h i e l e - l i k e b l e n d i n g r a t i o n a l i n t e r p o l a t i o n ， t h i e l e - w e r n e ro 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 ds o m eo t h e rc l a s si n t e r p o l a t i o n f u n c t i o n 。w ea l s oe x t e n dt h eg e n e r a ls t r u c t u r et om u l t i v a r i a t ec a s e ，d i s s c u s sg e n e r a l s t r u c t u r eo fb i v a r i a t ei n t e r p o l a t i o nf u n c t i o n ，i n t e r p o l a t i o nt h e o r e m ，s p e c i a lc a s e ， d u a li n t e r p o l a t i o nf l a m e sa n de r r o re s t i m a t i o n 。c l e a r l y ，o u rm e t h o do f f e r sm a n y f 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 s 。 k e y w o r d s ：n e w t o ni n t e r p o l a t i o n ， 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 i n t e r p o l a t i o n ， g e n e r a lf r a m e s ，b l o c kb a s e db l e n d i n gr a t i o n a li n t e r p o l a t i o n 表1 1 表3 1 表3 2 表3 3 表5 1 表5 2 表5 3 表格清单 有理逼近与部分和逼近的效率比较2 插值数据表2 5 调动节点后插值数据表2 5 插值数据表2 6 插值数据表4 4 z ，选取数据表4 4 a i 选取数据表4 4 v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 金魍王些太堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者签字；都签字日期；阳，年乡月 日 学位论文版权使用授权书 本学位论文作者完全了解 金壁王些太堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 金胆至些太堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：邹 t 于， 签字日期；矽占年乡月7 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日期： 电话： 邮编： 忽义童 。亳年毛旯7 日 致谢 时光飞逝，转瞬己到毕业之际。回顾这三年的生活，往事历历在目。在老 师和同学们的帮助下，自己顺利度过了紧张、忙碌而又快乐的三年研究生生活， 同时，在学习和为人处事方面，自己也取得了一定的进步。这三年的生活，将 是我人生中的宝贵财富，在此，我要向所有帮助过我的人表示由衷的谢意! 值此论文完成之际，我要向我的导师唐烁教授致以最衷心的感谢。他不仅 学识渊博，治学态度严谨，更有着博大的胸，环，在做学问、做人和生活上都给 予了我很大的帮助。三年里，他不断的鼓励给了我信心，在他的亲切的指导下， 我顺利地完成了论文的写作，并在此过程中受益非浅，深刻体会到了学习的乐 趣。 在学习期间和论文的撰写过程中，还受到了檀结庆教授、苏化明教授、黄 有度教授、邬弘毅教授、林京教授、朱功勤教授、朱晓临教授等老师所给予的 关心、支持和帮助。他们的教学思想、教学作风和高尚的品德都给我留下了深 刻的印象，同时也是我学习的楷模，我在此十分感谢与敬佩他们! 感谢3 4 班的全体同学，大家共同学习、激烈讨论，度过了难忘的三年时光， 在此感谢他们。 感谢评阅、评议硕士论文和出席硕士论文答辩会的各位专家学者，感谢他 们在百忙中给予的批评指正和宝贵意见。 最后，感谢我的父母在我研究生学习阶段对我提供的物质帮助和精神鼓励。 正是有了家人无私的帮助和奉献，我才能在研究生阶段全身心地投入到学习之 中。 邹乐 2 0 0 8 年4 月 第一章绪论 1 1 多项式插值研究背景 函数逼近论有着悠久的历史，而插值问题又是其古老而经典的一项内容， 同时也是计算数学中的一个基本问题。插值概念最早是在5 4 4 6 1o 年间由我国隋 朝数学家刘焯首先提出的【l1 1 ，这比西欧学者在16 5 5 年发表的结果早一千多年【6 6 1 所谓插值问题是指从给定的离散点的值去构造一个连续定义的( 简单) 函数， 使得它与被逼近的函数在给定点的值完全一致。在信息的存储、处理、分析、 传输日益数字化的今天，插值问题无处不在：通过离散点作一条光滑曲线、读 表【l 】、由给定数据求数值微分和数值积分、计算函数值、用简单函数代替复杂 函数等。更复杂的插值问题可能会附加导数插值条件【1 , 2 , 9 , 1 1 , 1 6 】、增加额外约束， 如单调性、凸性、周期性等，以及多元函数插值问题。插值方法的目的就是寻 求简单函数来近似代替复杂函数，选择简单函数的过程中，通常应注意以下几 个问题： 根据实际问题的需要，选择恰当的插值函数类型。 插值结点之间具有什么内在性质( 单调性、凸性、周期性等) ? 是需要插值函数的表达式还是它在指定点处的函数值? 如何构造插值函数及考虑相应的插值余项估计问题。 常用的插值函数有多项式、分段多项式、有理函数、分段有理函数、样条 函数、三角函数、指数函数。多项式作为一种最简单的函数类，是整个数值逼 近的基础，能令人满意的解决一系列有实际应用价值的重要问题，特别是在数 值微分和数值积分方面。关于代数插值的研究已有很多，例如有l a g r a n g e 插值 公式，a i t k e n 逐步插值法，n e v i l l e 算法，n e w t o n 插值公式，h e r m i t e 插值公式 等。代数多项式的特点是运算简单，不论是函数值的计算、微分、积分都能方 便地运算，它的另一特点是在整个数轴上有任意阶导数。因此，在某种意义下， 代数多项式是逼近光滑函数的重要工具。此外，计算插值的算法包括系数算法 和求值算法，其中系数算法用于得到插值函数的表达式，而求值算法用于求插 值函数在不同于插值点的任意点处的值【1 ，1 6 】。 多项式插值与逼近是整个数值逼近的基础，它被广泛应用于方程求根、曲 线曲面拟合、近似计算函数值、函数逼近、数值微分、数值积分、积分和微分 方程数值解等。多项式插值与逼近的广泛应用是基于它们结构最简单，易于构 造，便于利用。常用的一元多项式插值方法是n e w t o n 插值【l 2j 、l a g r a n g e 插值 j 和带导数插值条件的h e r m i t e 插值、b i r k h o f f 插值【5 2 1 。 1 2 有理插值研究背景及现状 在自然科学与技术科学领域中存在着大量的需要解决的非线性问题，它们 已成为科学技术领域研究的热点。诚如英国哲学家和数学家罗素( b e r t r a n d r u s s e l l ) 所说：“确实，所有的非线性科学也己受到，并将继续受到非线性逼近 的思想的渗透和影响”。作为非线性逼近的典型之一的有理函数插值与逼近，越 来越引起人们的关注。近年来人们在数值与函数逼近、计算机辅助几何设计中 偏爱有理函数，因为有理函数仍属简单函数类，用它来近似表示函数时，比用 多项式更灵活、更有效，且能反映函数的一些固有特性，如极性等。有理分式 函数由于其自身的特点，使得它不但可以在极点附近取得很好的逼近效果，而 且又能保证当x o o 时，有理逼近函数趋于某一定值的性能。 先看下面的例子【4 】： 设函数f ( x ) = l n ( 1 + 石) ，它的泰勒级数展开式为 h c - + x ，= x 一萼+ 手一等+ + c 一- 广1 鲁+ = 乙( x ) + 6 t ( x ) ， 其中瓦( x ) 是上述级数的h 次部分和，e t ( x ) 表示l ( x ) 和i n ( 1 + x ) 之间的误差。当 x = 1 时，上述级数的收敛速度是非常慢的。可是将函数h a o + x ) 用连分式展开， 得到 1 1 1 ( 1 + x ) ：一x 堡垒生垒 ， l + 2 + 3 + 4 + 5 + 取它的第玎阶渐近分式b ( x ) ，则得l n ( 1 + x ) 的逐次有理逼近式 r 。( x ) = 羔， r 2 ( 加蔫等， r 3 ( 班尝卷筹骞， g加j坐笪坐兰坐墼，4( 7 4 2 0 + 8 4 0 x + 5 4 0 x 2 + 1 2 0 x 3 + 6 x 4 。 容易验证，r ( x ) 与泰勒展开的前2 刀项正。( z ) 完全相同，然而两者的逼近效 率则大不相同。下表列出两者在x = 1 及x = 2 时的数值比较( i n2 = 0 6 9 3 1 4 7 1 8 ， i n3 = 1 0 9 8 6 1 2 2 8 9 ) 。 表1 1 有理逼近与部分和逼近的效率比较 玎 r 。( 1 ) 靠( 1 ) 互。( 1 )9 7 ，( 1 ) 砖( 2 )岛( 2 ) 1 0 6 6 7 0 0 2 6 0 5 0o 191 0 0 0 0 0 9 9 2 0 6 9 3 20 0 0 0 8 40 5 8o 1 11 0 9 20 0 6 6 30 6 9 3 1 2 20 0 0 0 0 2 50 6 1 70 0 7 61 0 9 8 00 0 0 0 6 1 4 0 6 9 31 4 6 40 0 0 0 0 0 0 7 60 6 3 40 0 5 81 0 9 8 5 7 0 0 0 0 0 4 2 ( ( x ) 表示e ( x ) 和l n ( 1 + x ) 之间的误差) 由上表可以看到，心( 1 ) 与瓦( 1 ) 的精度相差竟达10 万倍。更令人惊奇的是， 当x = 2 时函数i n ( 1 + x ) 的泰勒级数展开式发散，然而由上表知，r 。( 2 ) 趋向于 2 h 13 = 1 0 9 8 6 1 2 2 8 9 。所以，开展有理函数逼近的研究是十分有意义的。 另外，19 6 4 年d j n e w m a n 指出，可以找到一个分子、分母皆为 次的有 理分式序列，：，( x ) ，使得 一( x ) b3 p 一，一1 z 1 它显然比通常的，2 次多项式的最佳逼近阶0 ( 1 刀) 优越得多。 这些事实说明，开展函数的有理分式逼近问题的研究是十分有意义的。作 为有理逼近研究的重要组成部分，有理函数插值的理论及其应用一直是计算数 学领域中引入注目的课题。 有理插值问题的研究多起源于对连分式的研究。在有理函数插值格式的构 造方法中，最常用的是基于t h i e l e 型连分式的插值方法。连分式理论迅速发展 的时间虽然仅有三百多年，但其思想方法可以追溯到公元前3 0 0 年，在公元前 3 0 0 年至公元2 0 0 年期间，连分式主要用来表示数值和解方程。借助于连分式 研究有理逼近问题的历史也不算长，荷兰数学家和天文学家c h r i s t i a a n h u y g e n s ( 16 2 9 16 9 5 ) 首次将连分式用于解决有理逼近问题。e u l e r ( 1 7 0 7 17 8 3 ) ， l a g r a n g e ( 1 7 3 6 1 8 1 3 ) ，g a u s s 等都为连分式地发展做出了重大贡献，特别是e u l e r 所著的连分式一书；g a u s s 于1 8 7 2 年给出了t a n h x 的连分式表示，借助于 连分式证明了f e r m a t 猜想；兰伯特( h e i n r i c hl a m b e r t ) ( 1 7 2 8 1 7 7 7 ) 于1 7 7 0 年给 出了a r c t a nx 的连分式表示；l i o u v i l l e 则利用正则连分式展开证明了超越数的存 在性，这些都是连分式在数值近似方面的例子，直到十八世纪，连分式理论应 用还仅限于数学领域。到了二十世纪初，连分式开始越来越多的出现在其它应 用领域，如r o b e r tm c o r l e s s 用连分式研究混沌理论【5 1 】。二十世纪六十年代以 后，俄罗斯数学家v y a s k o r o b o g a t k o 将分支思想应用于连分式理论，开创了 连分式理论与方法研究的新纪元，多元分叉连分式插值与逼近受到西方各国学 者的广泛关注。比利时学者a c u y t ，b v e r d o n k l 2 u 。2 3 】通过定义多元逆差商和多 元偏倒差商构造了一种对称型的二元分叉连分式展开和逼近；波兰学者 w s i e m a s z k o t 3 0 , 4 6 】提出了不同类型的二元分叉连分式插值格式；乌克兰学者k h i k u c h m i n s k a 、d i b o d a r 和o m s u s 研究了多元分叉连分式的性质和收敛性等问 题。法国学者c c h a f f y 和乌克兰学者t s s v y d a ，m m p a h i r y a s s 等均在二元连 分式插值与展开方面作了大量工作。向量有理插值是由p w y n n 4 9 1 - 于6 0 年代率 先提出的，为解决多元或向量值函数的数值有理逼近问题提供了一个新思路。 与此同时，连分式理论与方法也不断被扩展到实际应用领域，并在实际应用中 得到发展。如i j g o o d 将连分式理论应用于控制领域，解决传递函数的l a p l a c e 变换问题；g r a v e s m o r r i s 2 4 - 2 6 从机械振动中有关“振动模”这一实际问题出发， 借助于一元t h i e l e 型连分式和s a m e l s o n 逆变换，建立了一元向量值连分式插值 的理论，证明了这种向量值有理插值函数的特征定理和唯一性定理，从此开创 了向量值函数的有理插值与逼近研究的新纪元。而对切触有理插值问题的研究 最早是由h e s a l z e r l 2 9 j 于19 6 2 年在“n o t eo no 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 ” 一文中提出的。l w u y t a c k t3 8 j 在1 9 7 5 年发表的“o nt h eo s c u l a t o r yr a t i o n a l i n t e r p o l a t i n gp r o b l e m ”一文中给出了类似于q d 算法的方法来计算切触有理插 值，但这种算法仅适用与正规切触有理插值表。苏家铎和黄有度【8 】在1 9 8 7 年发 表的“切触有理插值的一个新算法”一文中给出了一种兀f 算法来计算非正规 n e w t o n p a d e 表，即非正规的切触有理插值表。朱晓临l l8 j 曾在其博士论文中对 已知在各插值点一阶导数和二阶导数值的一元函数的切触有理插值的有解条件 及解的表达式给出了具体证明。 目前，连分式方法不仅在数值积分、微分方程数值求解、积分计算、积分 方程、数学物理中特殊函数的渐进展开、数论、信息安全、马尔可夫过程理论、 矩量问题和生死过程、混沌、理论物理等领域得到了广泛的应用，而且还在控 制理论、统计力学、机械振动、模分析、信号处理等工程技术领域有显著的应 用。 从1 9 9 0 年开始，朱功勤，檀结庆，顾传青，朱晓临，赵前进等人系统的研 究了向量值和矩阵值有理插值与逼近，得到许多美妙的结果。朱功勤、顾传青 把数量值连分式的思想引入到向量值连分式中，给出了向量的s a l z e 定理及 t h i e l e 型向量值连分式的收敛性定理，并将著名的p r i n g s h e i m 定理拓广至向量 值的形式彤7 ， 】；檀结庆等提出了二元t h i e l e 型向量连分式有理插值方法，建立 了多元分叉连分式的特征定理、唯一性定理、边界插值定理和对偶定理等，研 究了具有洞形结构的矩形网格上的多元连分式插值问题，通过划分等价类的方 法得到了特征拓扑不变性等优美结果【3 , 7 , 1 7 , 1 9 , 3 2 , 3 3 】；檀结庆对n e w t o n 插值多项 式和t h i e l e 型插值连分式巧妙地进行糅性加工得到了几种混合有理插值格式， 通过引进混合差商的概念，解决了混合有理插值的有效计算问题【l7 , 3 2 , 3 3 ；檀结 庆和唐烁针对病态数据构造了复合型的多元连分式插值框架，并研究了这种插 值的误差估计【3 4 , 3 5 , 4 2 】：檀结庆等提出了多元向量值函数连分式插值的矩阵算法 1 3 , 17 】，利用行向量列展开技巧揭示了向量值连分式插值与矩阵值连分式插值之 间的必然联系，指出矩值阵连分式插值可由向量值连分式插值转换而得【3 引。近 年来，赵前进提出了两种新形式的对称型混合有理插值；王家正构造了一种 s t i e l t j e s - - n e w t o n 型有理插值1 6 5j ；k h i k u c h m i n s k a 和s m v o z n a 建立了一种 n e w t o n t h i e l e 1 i k e 插值格式【5 6 , 5 7 1 。此外，赵前进利用分块的思想得到一系列新 的插值形式，大大丰富了有理插值的成果【1 5 , 17 , 5 4 , 5 9 】。檀结庆、朱晓临、胡敏等 在连分式插值理论应用方面也进行了卓有成效的尝试，提出了利用连分式进行 有理曲面的重建【3 】，快速构造圆弧和圆弧样条以及生成空间任意形状旋转曲面 i7 1 ，数字图象压缩与重建7 】的新方法等。 1 3 插值框架的研究现状 s w k a h n g 将一元n e w t o n 插值法推广并将其应用于逼近问题，这种推广 拓展了多项式函数和有理函数及它们的变换和一些非线性函数的插值应用问 题，并且推广的公式使我们可以用一种统一的格式处理插值问题。s w k a h n g 4 4 】 于1 9 6 9 年在文献“o s c u l a t o r yi n t e r p o l a t i o n ”中构造了一元切触插值的一种显示 表示公式，使得h e r m i t e 插值和连分式切触有理插值均为其特殊形式。陈金环 【7 6 】对n e w t o n 插值多项式进行推广得到广义n e w t o n 插值，从而将h e r m i t e 插 值，l a g r a n g e 插值，n e w t o n 插值都归结为“广义n e w t o n 插值”的特殊格式。檀结 庆和方毅【5 3 】通过引进参数构造了矩形网格上的二元插值的一般框架。通过对参 数的选取，使得二元n e w t o n 多项式插值，二元n e w t o n t h i e l e 型混合有理插值， 二元t h i e l e n e w t o n 型混合有理插值，二元分叉连分式插值及对称连分式插值 格式均为其特殊形式。檀结庆和朱功勤在文献“g e n e r a lf r a m e w o r kf o rv e c t o r - v a l u e d i n t e r p o l a n t s ”中研究了向量值插值的一般框架问题。檀结庆在专著连分式理论及 其应用 17 】中将矩形网格推广到更一般的插值节点，得到了更一般网格上插值 的一般框架。 1 4 本文的主要内容 在已有成果的基础上，本文推广了檀结庆等提出的一元及二元插值的一般 框架及s w k a h n g 构造的统一插值格式。全文内容安排如下，其中从第三章开 始是作者的主要研究结果。 第一章介绍了多项式插值和有理插值的研究背景，以及有理逼近、连分式 和插值框架在国内外的发展概况。 第二章对一元多项式插值、多元多项式插值、一元有理函数插值、一元切 触有理插值、多元有理函数插值、基于块的混合有理插值问题以及前 人构造的插值框架进行了综述。 第三章通过引进新的参数将檀结庆和方毅研究的二元插值的一般框架做进 一步的推广和改进，使之可以用来处理带不可达点和逆差商不存在的 插值问题。 第四章通过引进新的参数将檀结庆和方毅研究的二元对称型插值的一般框 架做进一步的推广和改进，使之包含今年来所研究的几种对称插值格 式，并给出几种新形式的对称型混合有理插值格式。 第五章 将s w k a h n g 研究的插值的一种显示表达式推广，构造了一种不依 赖于差商或逆差商的一元插值函数的一般框架，这种插值框架提供了 多种可选择的插值格式，且给出了这种插值框架的误差分析，并将其 推广至多元情形，研究了二元情形的插值框架，插值定理，包括的特 殊插值格式及误差估计。 第六章 对全文的工作、创新点和理论、实际意义做总结，对今后的研究工作提出 了浅显的想法。 第二章插值法 插值方法是数值分析的一个古老分支，它有着悠久的历史。插值的使用最 早可追溯到公元6 世纪，隋朝数学家刘焯( 公元5 4 4 6 l0 ) 用等距二次插值法 束计算天文学公式：而唐朝的数学家张遂( 公元6 8 3 7 2 7 ) 则提出了不等距结 点内插公式，这比西方学者发现的相应结论早一千多年。到微积分创立的牛顿 时代，插值方法又得到了进一步的研究。插值的方法有很多种，主要分为多项 式插值、有理插值、三角插值、样条函数插值等，本章以多项式插值、有理插 值【1 ，2 ，3 ，16 l 为主要内容进行介绍，不讨论三角插值和样条函数插值。 2 1 多项式插值 若通过某种方法己知函数y = f ( x ) 在区间【口，b 】上的一组对应关系 ( ，儿) ，( ，y ，) ，( ，n ) ，插值的目的是根据给定数据，寻找一个解析函数p ( 工) 近 似地代替f ( x ) 。函数p ( x ) 的类型有很多选择，若采用代数多项式则该插值函数称为 多项式插值或代数插值。以下简单介绍l a g r a n g e 插值、牛顿插值以及h e r m i t e 插值。 2 1 1 l a g r a n g e 插值 在区间【口，b 】上，己知函数y = ( z ) 的n + 1 个点的函数值 ( ，甄) ，( 五，y 。) ， ，( 矗，y 。) ，要构造一个多项式p ( x ) 使之满足条件： 1 ) 尸( x ) 是不超过疗次的多项式， 2 ) 尸( 薯) = 厂( 薯) = 咒( f = o ，1 ，甩) ， p ( x ) 称为插值函数，薯称为插值节点，条件1 ) 、2 ) 称为插值条件，【口，b 】称为 插值区间。 l a g r a n g e 在1 7 9 5 年证明了下面的定理： 定理2 1 1 满足上述插值条件的插值多项式( x ) 存在且唯一。 形如 只( x ) = 只7 f ( x ) ( 2 1 1 ) 的聆次多项式。 ，( 工) ：竖型蔓玉l 坠立丛血上堕兰上( 2 1 2 ) ”7 ( 一) ( 一一五) ( 葺- x , 一1 ) ( t 一+ 1 ) ( 薯一) 、 引进记号c o ( x ) = ( x - x o ) ( x - x , ) ( x - - x i 1 ) 一靠1 ) ( x - - x n ) ，上式可以简写 为 t a x ) _ 燕) c o ， ( 2 1 3 ) 【x 一l 一) 其中国，( 一) ：i 掣l 。 l a x j x = x , 多项式( 2 1 1 ) 即为l a g r a n g e 插值多项式。定理2 1 1 也可以描述性的叙述 6 为，有且仅有一个胛次多项式( x ) 与已知函数f ( x ) 在n + 1 个不同点上取相同的 数值。它的几何意义是，有且仅有一条行次代数曲线通过平面上预先给定的1 7 + 1 个点( 薯，y ，) ( f = 0 ，l ，玎) ( 当i _ ，时，五t ) 。 l a g r a n g e 插值公式结构紧凑、思想清晰，所以至今在理论分析上仍有重要价值。 2 1 2n e w t o n 插值 l a g r a n g e 插值公式虽然构造简单，但缺点是当插值结点的个数有变动时( 例 如，为了提高精度，有时需要增加插值结点的个数) ，l a g r a n g e 基函数 f j ( x ) ( f = 0 ，1 ，z ) 就要随之发生变化，需要重新构造，从而整个公式的结构也要 发生变化，这在实际计算中是不方便的。为了克服上述缺点，在这一节中我们 介绍n e w t o n 型插值公式。 以功+ f ：x o 冀x l n 譬x o h ) ( x 二印”x n _ 1 ) ， ( 2 ) ，一， 】( x 一 一而) ( x 一一1 ) ， 、。 其中系数f ( x o ) ，i x o ，五】，j x o ，x i ，】即是厂( x ) 的各阶差商。这就是 n e w t o n 插值公式。 因为在刀+ 1 个点x o ，x 1 ，上取给定值的次数不超过胛的多项式是唯一的，所以 次数相同的n e w t o n 插值多项式与l a g r a n g e 插值多项式是恒等的，它们的差异仅是书 写形式而己。但是，这种差异为计算实践带来了很大的方便。实际上，对于n e w t o n 插值公式来说，当需要增加一个插值结点时，只需在原插值多项式的后面再添加一个 新项就可以了。 2 1 3h e r m i t e 插值 h e r m i t e 插值是指具有重结点的多项式插值方法，其构造方法类似于 l a g r a n g e 插值中构造基本多项式的方法，这里我们仅给出其插值公式，就不具 体介绍它的构造过程了。 设已知x o x l x ，厂( z ，) = z ，k = o ，l ，s 一1 ；i = 1 ，2 ，若存在一个 n ( n + i = j ，) 次多项式日( x ) ，满足插值条件 日( ) = z ，k = 0 ，l ，一l ，f = 0 ，1 ， ( 2 1 5 ) 则m ( x ) 就是所要求的h e r m i t e 插值多项式。其表达式为 姒加器咩 等搿1 ， m ， 、， x ，l ， 似 z 脚，瑚 = xh 中其 w = 驴扩，去 等c - 1 ) 表和数去哥协棚训。惭的前 _ 一意项和。 2 1 4 多元插值多项式 现在我们讨论多元多项式插值，为记号简单且不失一般性我们讨论二元情 形。同一元多项式插值类似，二元多项式插值也有l a g r a n g e 方法，a i t k e n 方法， 牛顿插值法等等，本节仅介绍二元牛顿插值法。 令是r 2 上的有界闭区域，f ( x ，y ) 是定义在a 上的连续函数，厂( ，y j ) = z ， i = 0 ，1 ，玎，歹= 0 ，1 ，m 。取定a 中的结点组( 可整序格点网) f i = ( 薯，y j ) 10 js 啊，0 is 聊) ， 其中 ? 1 0 强n 2 ，2 m 这种网格上的牛顿插值格式如下 n ( x ，y ) = ( x - x o ) ( x - x 。) ( x - - x 川) ( y - y o ) ( y - y 。) ( y - y 。一，) 工。 ( 2 1 7 ) 其中工。= f ( x o ，而，_ 一1 ；y o ，y t ，y u j ) 为二元牛顿差商。 易证 ( ，y j ) = ，j i = 0 ，i 1 一，m ，= o ，l ，1 一， ( 2 1 8 ) 2 2 有理函数插值 2 2 1 有理函数插值的一般提法 设( ，只) ，( f - o ，1 ，m + r 1 ) 是与y = f ( x ) 有关的m + n + 1 个型值点，其中x j ， ( 扛0 ，1 ，聊+ 功互异，y j = 厂( ) ，o = o ，1 ，研+ ，2 ) ；以力= q 一，9 = 匆一，所谓有 理插值问题，就是寻找有理分式函数 ，= 器= 筹舞， 亿2 使之满足 u = 器坝= 0 ，1 ，肌以 ( 2 2 2 ) 此时，称x o ，五，+ 。为插值节点，咒= 厂( 薯) ，( f = 0 ，1 ，坍+ 玎) 为型值，( 2 2 2 ) 式为插值条件，r i l l , t 7 ( x ) 称为插值函数，厂( x ) 称为被插函数。r ( x ) = f ( x ) - r m 。( x ) 称 为插值余项。 对于有理插值问题( 2 2 1 ) ，( 2 2 2 ) 的解，人们往往通过求解下列线性方程组 得到： 口0 + 口l + + 口。一“- y , ( b o + 6 l + + 巩葺”) = o ，( f = 0 ，1 ，m + 甩) ( 2 2 3 ) 然而，有理插值问题( 2 2 1 ) ，( 2 2 2 ) 的解不一定总是存在的，而且满足( 2 2 3 ) 的 解不一定满足插值条件( 2 2 2 ) 。大量的文献对于有理插值问题( 2 2 1 ) ，( 2 2 2 ) 解的存在 唯一性给予了研究，如n m a c o n ，和d e d u p r e e 在【3 中研究了有理插值问题( 2 2 1 ) ， ( 2 2 2 ) 的解的存在唯一性；在文献【1 9 】中利用n e w t o n 插值多项式，给出判别有理插值 问题( 2 2 1 ) ，( 2 2 2 ) 的解是否存在的另一个方法。 2 2 2 一元t h i e l e 型插值连分式 由2 2 。1 的介绍可知，要想得到有理插值函数的显示表示，需要对于每个 具体问题解一个齐次线性方程组。下面介绍一种有理插值函数算法t h i e l e 型连分式插值算法，作为一种有效的有理插值算法，它被广泛地应用于数值逼 近【1 1 、图像处理【7 , 1 7 , 2 7 。 定义2 2 1 称下述形式的连分式： + 寻+ 寻等+ 眨2 为t h i e l e 型连分式【1 6 , 1 7 , 2 8 , 5 1 1 定义2 2 2 设x = b ，1i 1 n 是复平面上一点集，f ( x ) 是定义在g ( g3x ) 上 的函数。令 烈一】= f ( x ，) ，i = 0 ，1 ，2 ，( 2 2 5 ) 烈引= 赫， ( 2 2 6 ) 研，一，吒】= _ j _ 等i _ ， ( 2 2 7 ) o l x o ，一，x k 一2 ，坼j 一烈x o ，五，坼一lj 称由上述公式确定的研，而，】为函数厂b ) 在点x 0x 1 ，x 2 ，x 女处的k 阶逆差 商。 定理2 2 1 设 帕m + 寻+ 寻+ + 芋= 器 2 则d e g = 孚 ，d e g q = 三 。其中d e g 表示多项式的最高次数，【】表示不超 过“的最大整数。 定理2 2 2 设 兄( z ) 。妒 】+ 丽x - - x 0 + ；毛；x 而- - x 1 + + i i 畿， ( 2 2 9 ) 其中( p x o ，五， o ，o o ；k = 0 ，1 ，n 为f ( x ) 在x 0 x 1 ，一，魂处的k 阶逆差商，则 有 民( 誓) = 厂( 誓) ，i = o ，1 ，刀。 定义2 2 3 如果连分式 9 r n ( 加+ 寻+ 寻一半 满叫小胞) ，f - o ，l ，嗍，则称该连分式为函姒舳 丁n + 1 互n 型, e l e 定眦3 函姒蚰 丁n + 1 互n 型, t h i e l e 插值连分式是唯吨 定理2 , 2 4 设 x o ，五，艺 c a ，6 】c 瓞，厂( x ) 在k ，6 】上有直到拧+ l 阶的导数， 若 呻) = 6 ：0 + 寻+ 寻一等= 器 满足兄( 一) = 厂( 一) ，i = o ，1 ，刀，则眠【o r b 】，均j 孝i ( x o ，而，x nx ) ，此处 i ( x 出x r 1 表示旬。含x z x 及x 的最小- y f 区间，使得 m h = 鬻 其中+ ( x ) = ( x - x o ) ( x 一五) ( x x n ) 。 2 2 3t h i e l e w e r n e r 型有理插值 h w e r n e r ( 19 7 9 ) 提出了一种有效、司靠的有理插值方法，即将n e w t o n 插值 思想和t h i e l e 型连分式结合起来，构造出了灵活而