数值分析第二章

《数值分析第二章》由会员分享，可在线阅读，更多相关《数值分析第二章（114页珍藏版）》请在金锄头文库上搜索。

1、上一页上一页下一页下一页第二章第二章 函数基本逼近（一）函数基本逼近（一） 插值逼近插值逼近 1湘潭大学数学与计算科学学院上一页上一页下一页下一页1 1 引引 言言 函数逼近函数逼近: : 数学中的基本问题数学中的基本问题, , 最活跃的研究领域之一最活跃的研究领域之一 数值计算中函数表示的重要方法数值计算中函数表示的重要方法 讨论如何用讨论如何用 简单函数近似代替复杂函数简单函数近似代替复杂函数 简单函数曲线拟合离散数据简单函数曲线拟合离散数据 的的方法、理论方法、理论及其及其实现实现。2湘潭大学数学与计算科学学院上一页上一页下一页下一页讨论如何用简单的函数讨论如何用简单的函数一个复杂的函数

2、一个复杂的函数近似地代替近似地代替的的方法方法、理论理论及其及其实现实现. . 近似代替又叫做近似代替又叫做逼近逼近 .被逼近的函数被逼近的函数 或或被近似的函数被近似的函数 逼近的函数逼近的函数 或或近似的函数近似的函数 即即3湘潭大学数学与计算科学学院上一页上一页下一页下一页函数逼近函数逼近是数值分析的许多分支的理论基础是数值分析的许多分支的理论基础. . 例如例如: : 数值积分数值积分; ; 数值微分数值微分; ; 微分方程数值解微分方程数值解; ;曲线曲面拟合曲线曲面拟合; ;函数值近似计算函数值近似计算; ;等等等等4湘潭大学数学与计算科学学院上一页上一页下一页下一页从从逼近论逼近

3、论的观点，通常有两种意义下的逼近：的观点，通常有两种意义下的逼近：局部局部逼近逼近整体整体逼近逼近1 1、局部逼近、局部逼近所谓局部逼近就是求函数所谓局部逼近就是求函数在某点附近的近似在某点附近的近似 最常用的逼近方法：最常用的逼近方法： Taylor逼近方法逼近方法 理论依据：理论依据： Taylor定理定理 5湘潭大学数学与计算科学学院上一页上一页下一页下一页定理定理1.1设设n为一非负整数，为一非负整数，在点在点某一邻域某一邻域有有阶连续导数，阶连续导数，有有 则对则对的的这里，这里，n次次Taylor逼近多项式逼近多项式和误差余项和误差余项分别为分别为(1.1) (1.2) (1.3)

4、 6湘潭大学数学与计算科学学院上一页上一页下一页下一页注意：注意：1 1、Taylor逼近多项式逼近多项式满足以下逼近要求满足以下逼近要求 2、Taylor逼近是一种局部逼近逼近是一种局部逼近在一点在一点处的信息处的信息. .仅利用了被逼近的函数仅利用了被逼近的函数下面举例说明下面举例说明Taylor多项式的逼近效果多项式的逼近效果. . 7湘潭大学数学与计算科学学院上一页上一页下一页下一页解解 由由(1.2)式和式和(1.3)式易求得式易求得 (1.2) (1.3) 直观理解可以参见下图。直观理解可以参见下图。 8湘潭大学数学与计算科学学院上一页上一页下一页下一页(a)的一次和二次的一次和二

5、次Taylor逼近逼近函数函数 (b)的一次和二次的一次和二次Taylor逼近逼近误差误差 (a)(b)9湘潭大学数学与计算科学学院上一页上一页下一页下一页因此，因此，Taylor逼近逼近适合适合作函数的局部逼近作函数的局部逼近. .由此可见：误差由此可见：误差不是均匀分布不是均匀分布的的. . 当当x越偏离越偏离x0误差就误差就越大越大即当即当x越接近越接近x0误差就误差就越小越小；我们将主要讨论我们将主要讨论整体逼近整体逼近问题问题: :即对定义域上的即对定义域上的所有点所有点. .近似函数近似函数对对被逼近函数被逼近函数的逼近的逼近函数曲线函数曲线对对样本数据样本数据的拟合的拟合考虑考虑

6、: :10湘潭大学数学与计算科学学院上一页上一页下一页下一页例例2 求区间求区间0,1.5上的二次（抛物）曲线上的二次（抛物）曲线, ,要求要求该曲线过样本点该曲线过样本点 解解 设所求抛物线的方程为设所求抛物线的方程为 利用待定系数法，可得利用待定系数法，可得此例将引出所谓的此例将引出所谓的 Lagrange 型型多项式插值问题多项式插值问题, , 这时给定的这时给定的样本数据样本数据仅仅包含函数值包含函数值. . 11湘潭大学数学与计算科学学院上一页上一页下一页下一页例例3 求区间求区间0,1上的三次曲线，要求该函数曲线过上的三次曲线，要求该函数曲线过且其一阶导函数曲线过样本点且其一阶导函

7、数曲线过样本点和和( (即即函数曲线在函数曲线在0,1点处的斜率分别为点处的斜率分别为0和和1).).和和样本点样本点解解 设所求的三次曲线为设所求的三次曲线为类似于例类似于例2的计算，可得的计算，可得12湘潭大学数学与计算科学学院上一页上一页下一页下一页上例将引出所谓的上例将引出所谓的Hermite型型多项式插值问题多项式插值问题此时样本数据包含：此时样本数据包含：1 1、函数值、函数值2 2、一阶、一阶导数值导数值. . 更广泛的还有所谓的更广泛的还有所谓的Birkhoff插值问题插值问题. . 注意：注意：13湘潭大学数学与计算科学学院上一页上一页下一页下一页例例4 求区间求区间上的二阶

8、连续可微的分段三次多项式上的二阶连续可微的分段三次多项式），要求该曲线过点），要求该曲线过点和和，且在，且在A、E两点的导数为两点的导数为0. . 曲线（其内部段点分别为曲线（其内部段点分别为解解 注意所求函数为偶函数，注意所求函数为偶函数， 利用待定系数法，利用待定系数法，上的表示式为上的表示式为 可得该函数在可得该函数在14湘潭大学数学与计算科学学院上一页上一页下一页下一页其图形如下图所示其图形如下图所示. .此例将引出所谓的此例将引出所谓的样条样条插值问题：插值问题： 即即求满足一定的求满足一定的整体光滑整体光滑（或（或连接连接）条件的分段插值多项式）条件的分段插值多项式. . 15湘潭

9、大学数学与计算科学学院上一页上一页下一页下一页 逼近问题主要由以下三个要素构成：逼近问题主要由以下三个要素构成：(1)(1) 被逼近函数（或样本数据）被逼近函数（或样本数据）(2)(2) 逼近函数空间逼近函数空间简单函数：简单函数：主要是指可以用四则运算进行计主要是指可以用四则运算进行计算的函数，通常为（算的函数，通常为（代数或三角）多项式、代数或三角）多项式、分段多项式分段多项式和有理多项式函数和有理多项式函数. .简单函数所属的函数空间简单函数所属的函数空间20湘潭大学数学与计算科学学院上一页上一页下一页下一页(3)(3) 逼近方式逼近方式插值逼近插值逼近：要求逼近函数曲线通过样本数据点：

10、要求逼近函数曲线通过样本数据点( (有时还要求在样本数据点处，等于给定的导数值有时还要求在样本数据点处，等于给定的导数值) )本章本章将在插值逼近方式下，讨论相应的逼近问题将在插值逼近方式下，讨论相应的逼近问题. .21湘潭大学数学与计算科学学院上一页上一页下一页下一页插值问题涉及的基本内容：插值问题涉及的基本内容：1.1.问题问题提法提法 2.2.问题的问题的适定性适定性( (解的存在、唯一性解的存在、唯一性) )3.3.解的构造解的构造 ( (或表示或表示 ) )及其相关及其相关算法算法 4.4.误差误差分析分析( (逼近度刻化逼近度刻化) )及及稳定性稳定性分析分析 首先首先, ,对逼近

11、函数取为对逼近函数取为代数多项式代数多项式，样本数据样本数据仅包含被逼近函数的仅包含被逼近函数的函数值函数值的情形，讨论相应的的情形，讨论相应的插值问题插值问题. . 22湘潭大学数学与计算科学学院上一页上一页下一页下一页2 2 Lagrange插值插值 一、问题的提法一、问题的提法 二、适定性和二、适定性和Lagrange插值公式插值公式 三、三、Newton插值公式插值公式 23湘潭大学数学与计算科学学院上一页上一页下一页下一页一、问题的提法一、问题的提法已知：已知： 或其或其 个样本值个样本值且且彼此互异。彼此互异。 记所有次数不超过记所有次数不超过n n的代数多项式的代数多项式的全体为

12、的全体为24湘潭大学数学与计算科学学院上一页上一页下一页下一页插值问题插值问题： 求求满足满足称称为为被插函数被插函数，为为n次次多项式插值函数多项式插值函数，为为插值节点插值节点，的的Lagrange插值问题。插值问题。 并称并称而上述而上述问题问题被称为被称为 关于节点关于节点25湘潭大学数学与计算科学学院上一页上一页下一页下一页二、适定性和二、适定性和Lagrange插值公式插值公式 定理定理 2.1 2.1 插值问题的解是插值问题的解是存在且唯一存在且唯一的的. . 证明：（证明：（构造性构造性证明）证明）（1 1）存在性）存在性 首先构造特殊插值多项式首先构造特殊插值多项式克罗内克尔

13、克罗内克尔( (Kronecker) )符号符号. .(2.1) 26湘潭大学数学与计算科学学院上一页上一页下一页下一页 n 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后然后令令 = = =niiinyxlxP0)()(，则显然有，则显然有Pn(xj) = yj 。li(x)每个每个 li 有有 n 个根个根 x0 xi-1 xi+1 xn = = = =njj i jiixxCxl0)()( = = =j i jiiiixxCxl)(11)(Lagrange 多项式多项式与与 有关，而与有关，而与 无关无关节点节点f27湘潭大学数学与计算科学学院

14、上一页上一页下一页下一页(2) (2) 唯一性唯一性设设n次多项式次多项式记记且且均为插值问题的解均为插值问题的解, ,则有则有由高等代数基本知识知，由高等代数基本知识知，若一个若一个n次代数多项式至少次代数多项式至少存在存在n+1+1个根，则它个根，则它一定恒为零一定恒为零. . 唯一性得证唯一性得证. . 28湘潭大学数学与计算科学学院上一页上一页下一页下一页称称为为f(x)的的n次多项式插值的次多项式插值的 Lagrange 公式公式也称为也称为Lagrange 插值多项式插值多项式. . 称称为为n次多项式插值问题的次多项式插值问题的基函数基函数( (Lagrange 因子因子) )其

15、中其中29湘潭大学数学与计算科学学院上一页上一页下一页下一页例例 当当n=1时，线性插值公式时，线性插值公式30湘潭大学数学与计算科学学院上一页上一页下一页下一页当当n=2时，抛物插值公式时，抛物插值公式31湘潭大学数学与计算科学学院上一页上一页下一页下一页 插插值余值余项项 设节点设节点在在(a , b)内存在内存在, 考察截断误差考察截断误差，且，且 f 满足条件满足条件 ,Rolles Theorem: 若若 充分光滑，充分光滑， ，则，则存在存在 使得使得 。推广：推广：若若使得使得使得使得存在存在使得使得Rn(x) 至少有至少有 个根个根n+1 = = = =niinxxxKxR0)

16、()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 = = = =niixtxKtRnt0)()()()( (t)有有 n+2 个不同的根个不同的根 x0 xn x!)1()()()1(+-+nxKRxnn 注意这里是对注意这里是对 t 求导求导= =+ + + + +!)1)()()()1()1(nxKLfxnnxn !)1()()()1(+ += =+ +nfxKxn 32湘潭大学数学与计算科学学院上一页上一页下一页下一页niyxPiin,., 0,)(= = =求求 n 次多项式次多项式 使使得得条件：条件：无重合节点，即无重合节点，即首先找到首先找到li(x)，

17、i = 0, , n 使得使得 li(xj)= ij ；然后然后令令 = = =niiinyxlxP0)()(，则显然有，则显然有Pn(xj) = yj 。存在性存在性存在性存在性定理定理 (唯一性唯一性唯一性唯一性) 满足满足 的的 n 阶插值阶插值多项式是唯一存在的。多项式是唯一存在的。33湘潭大学数学与计算科学学院上一页上一页下一页下一页li(x)每个每个 li 有有 n 个根个根 x0 xi-1 xi+1 xn = = = =njj i jiixxCxl0)()( = = =j i jiiiixxCxl)(11)(Lagrange 多项式多项式与与 有关，而与有关，而与 无关无关节点节

18、点f34湘潭大学数学与计算科学学院上一页上一页下一页下一页35湘潭大学数学与计算科学学院上一页上一页下一页下一页设节点设节点在在(a , b)内存在内存在, 其截断误差其截断误差，且，且 f 满足条件满足条件 , 插插值余值余项项 /* Remainder */36湘潭大学数学与计算科学学院上一页上一页下一页下一页注：注： 通常不能确定通常不能确定 x , 而是估计而是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限。当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时，时， , 可知可知 ，即插值多项式对于次数，即插值多项式对于次数 n 的的多多项式是项式是精确

19、精确的。的。37湘潭大学数学与计算科学学院上一页上一页下一页下一页例例1 1 已知已知线性插值和抛物插值公式求线性插值和抛物插值公式求的近似值的近似值. . 试分别用试分别用解解 （1 1）选取）选取利用线性插值公式，利用线性插值公式，可得可得 于是于是 38湘潭大学数学与计算科学学院上一页上一页下一页下一页解解 （2 2）选取）选取利用抛物插值公式，利用抛物插值公式，可得可得 于是于是 39湘潭大学数学与计算科学学院上一页上一页下一页下一页注意：注意：则线性插值公式所得近似值有则线性插值公式所得近似值有3 3位位有效数字有效数字 抛物插值公式所得近似值有抛物插值公式所得近似值有4 4位位有效

20、数字有效数字 40湘潭大学数学与计算科学学院上一页上一页下一页下一页 例例 已知已知分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算利用利用这里这里而而sin 50 = 0.7660444)185(50sin10 p pL0.77614外外推推 /* extrapolation */ 的实际误差的实际误差 0.010100.01010利用利用sin 50 0.76008, 内插内插 /* interpolation */ 的实际误差的实

21、际误差 0.005960.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点，插值效果较好。端点，插值效果较好。41湘潭大学数学与计算科学学院上一页上一页下一页下一页 n = 2)185(50sin20 p pL0.76543sin 50 = 0.76604442次次插值的实际误差插值的实际误差 0.000610.00061高次插值通常优于高次插值通常优于低次插值低次插值42湘潭大学数学与计算科学学院上一页上一页下一页下一页计算机上算法实现计算机上算法实现在计算机上实现在计算机上实现：43湘潭大学数学与计算科学学院上一页上一页下一页下一页L

22、agrange插值算法44湘潭大学数学与计算科学学院上一页上一页下一页下一页45湘潭大学数学与计算科学学院上一页上一页下一页下一页Lagrange插值公式的优缺点：插值公式的优缺点：优点：公式的形式对称，结构紧凑，优点：公式的形式对称，结构紧凑， 容易编写计算程序，便于理论分析和许多容易编写计算程序，便于理论分析和许多 数值计算公式的推导。数值计算公式的推导。缺点：没有承袭性，缺点：没有承袭性， 即当增加新的节点时，所有即当增加新的节点时，所有Lagrange因子因子必须重新计算，这就会造成计算量的浪费。必须重新计算，这就会造成计算量的浪费。46湘潭大学数学与计算科学学院上一页上一页下一页下一

23、页作业作业:P56-57:P56-571 1题题(1), 2(1), 2题题,3,3题题47湘潭大学数学与计算科学学院上一页上一页下一页下一页三、三、 牛顿插值公式牛顿插值公式 Lagrange 插值虽然易算，但若要增加一个节点时，插值虽然易算，但若要增加一个节点时，全部基函数全部基函数 li(x) 都需重新算过。都需重新算过。将将 Ln(x) 改写成改写成的形式，希望每加一个节点时，的形式，希望每加一个节点时，只附加一项只附加一项上去即可。上去即可。? 差商差商1阶差商阶差商 2阶差商阶差商48湘潭大学数学与计算科学学院上一页上一页下一页下一页一般地，一般地， 称为称为f (x)在在x0 ,

24、 x1 , , xn点的点的 n 阶差商。阶差商。49湘潭大学数学与计算科学学院上一页上一页下一页下一页重节点差商重节点差商 其定义式为其定义式为 一般地，可定义一般地，可定义 50湘潭大学数学与计算科学学院上一页上一页下一页下一页 此性质表明差商与节点的排列次序无关。此性质表明差商与节点的排列次序无关。 f x0 , x1 , x2 , ., xn=性质性质1 1 差商可以表示为函数值的线性组合，即差商可以表示为函数值的线性组合，即差商的性质差商的性质: : 性质性质2 2 (差商的差商的对称性对称性)f x1 , x0 , x2 , ., xn= = fx1 , x2 , ., xn ,

25、x0 51湘潭大学数学与计算科学学院上一页上一页下一页下一页性质性质3 若若是一个是一个m次代数多项式，次代数多项式， 则则次代数多项式次代数多项式. . 关于点关于点和任一已知点和任一已知点的的一阶差商是一阶差商是事实上，由差商的定义有事实上，由差商的定义有 上式右端的分子为上式右端的分子为m次代数多项式次代数多项式, ,并且当并且当时为零时为零, ,因此因此分子包含了分子包含了因子刚好和分母约去因子刚好和分母约去, ,次代数多项式次代数多项式. . 故右端为故右端为 52湘潭大学数学与计算科学学院上一页上一页下一页下一页 性质性质4 4 若若f(x)在在a,b上存在上存在n阶导数阶导数,

26、, 且节点且节点x0, , x1 , xn a,b, ,则至少存在一点则至少存在一点 a, b 满足下满足下式式 解解 f (8)(x)=- -68 !, f 1,2, ,9=- -6, f (9)(x)=0, f 1,2, ,10=0.例例1 1 f (x)=- -6x8+7x5- -10, ,求求f 1,2, ,9及及f 1,2, ,10.53湘潭大学数学与计算科学学院上一页上一页下一页下一页 牛顿插值牛顿插值 /* Newtons Interpolation */?54湘潭大学数学与计算科学学院上一页上一页下一页下一页（n+1） 55湘潭大学数学与计算科学学院上一页上一页下一页下一页 牛

27、顿插值牛顿插值 12 n+11+ (x x0) 2+ + (x x0)(x xn 1) n+1Nn(x)Rn(x)ai = f x0, , xi 56湘潭大学数学与计算科学学院上一页上一页下一页下一页57 注：注： 由由唯一性可知唯一性可知 Nn(x) Ln(x)， 只是算法不同，故只是算法不同，故其余项也相同，即其余项也相同，即 实际计算过程为实际计算过程为f (x0)f (x1)f (x2)f (xn 1)f (xn)f x0, x1f x1, x2 f xn 1, xnf x0, x1 , x2 f xn 2, xn 1, xnf x0, , xn f (xn+1) f xn, xn+1

28、 f xn 1, xn, xn+1 f x1, , xn+1 f x0, , xn+157湘潭大学数学与计算科学学院上一页上一页下一页下一页差商表58湘潭大学数学与计算科学学院上一页上一页下一页下一页5959湘潭大学数学与计算科学学院上一页上一页下一页下一页6060湘潭大学数学与计算科学学院上一页上一页下一页下一页xk f(xk)一阶均差一阶均差 二阶均差二阶均差三阶均差三阶均差四四阶均差阶均差0.400.550.650.800.900.410750.578150.696750.888111.026521.116001.186001.275731.384100.280000.358930.43

29、3480.197330.213000.03134例例2 已知已知f(x)的函数表的函数表, 求二次牛顿插值多项式求二次牛顿插值多项式, 并并由此计算由此计算f(0.596)的近似值的近似值。 解解 由上表可得过前三点的由上表可得过前三点的2次次Newton插值多项式插值多项式为为63湘潭大学数学与计算科学学院上一页上一页下一页下一页又又可得过前四点的可得过前四点的3次次Newton插值多项式插值多项式故故又又64湘潭大学数学与计算科学学院上一页上一页下一页下一页可得过前五点的可得过前五点的4次次Newton插值多项式插值多项式于是于是当插值节点等距分布时，上述基于差商的当插值节点等距分布时，上

30、述基于差商的Newton插值插值公式可以得到进一步简化。公式可以得到进一步简化。65湘潭大学数学与计算科学学院上一页上一页下一页下一页作业作业:P57-58:P57-586 6题题, 7, 7题题66湘潭大学数学与计算科学学院上一页上一页下一页下一页 等距节点公式等距节点公式 向前差分向前差分 iiifff = = + +1ikikikikffff1111)( + + = = = = 向后差分向后差分 111 = = ikikikfffi 1iifff = = 中心差分中心差分 其中其中当当节点节点等距等距分布时分布时: 67湘潭大学数学与计算科学学院上一页上一页下一页下一页 差分的重要性质：

31、差分的重要性质： 线性：例如线性：例如 若若 f (x)是是 m 次多项式，则次多项式，则 是是 次多次多项式，而项式，而 差分值可由函数值算出：差分值可由函数值算出： = = + + = = njjknjknfjnf0)1( = = + + = = njnjkjnknfjnf0) 1(其中其中 函数值可由差分值算出：函数值可由差分值算出：kjnjknfjnf =+=0kkkhkfxxf!,.,00 = =knkknnnhkfxxxf!,.,1 = = kkkhff0)()( = = 由由 Rn 表达式表达式68湘潭大学数学与计算科学学院上一页上一页下一页下一页 牛顿公式牛顿公式 牛顿向前插值

32、公式牛顿向前插值公式 牛顿向后插值公式牛顿向后插值公式 将节点顺序倒置：将节点顺序倒置：设设，则，则)()()(000xfkthtxNxNknknn = =+ += = = =设设，则，则)() 1()()(0nknkknnnxfkthtxNxN = =+ += = = =注：注：一般当一般当 x 靠近靠近 x0 时用牛顿向前插值公式，靠近时用牛顿向前插值公式，靠近 xn 时时用牛顿向后插值公式。用牛顿向后插值公式。69湘潭大学数学与计算科学学院上一页上一页下一页下一页例例3 设设 y=f(x)=ex, xi=1, 1.5, 2, 2.5, 3, 用三次插值多项用三次插值多项式求式求f(1.2

33、) 及及f(2.8)的的近似值近似值. .解解 相应的函数值及差分表如下相应的函数值及差分表如下: :0.48146 0.74210 1.22356 1.14396 1.886063.10962 1.76341 2.90347 4.793437.90305 2.71828 4.481697.28906 12.1824920.08554四阶差分四阶差分三阶差分三阶差分二阶差分二阶差分一阶差分一阶差分函数值函数值70湘潭大学数学与计算科学学院上一页上一页下一页下一页函数值函数值一阶差分一阶差分二阶差分二阶差分三阶差分三阶差分四阶差分四阶差分2.71828 4.481697.28906 12.182

34、4920.08554 1.76341 2.90347 4.793437.90305 1.14396 1.886063.10962 0.74210 1.223560.48146求求f(1.2)用用Newton前插公式前插公式, 且由且由 1.2=1+0.5t, 得得t=0.471湘潭大学数学与计算科学学院上一页上一页下一页下一页求求f(2.8)用用Newton后插公式后插公式,且由且由 2.8=3+0.5t, 得得 t=- -0.472湘潭大学数学与计算科学学院上一页上一页下一页下一页 3 3 埃尔米特插值埃尔米特插值 不仅要求函数值重合，而且要求若干阶不仅要求函数值重合，而且要求若干阶导数导数

35、也重合。也重合。即：要求插值函数即：要求插值函数 (x) 满足满足 (xi) = f (xi), (xi) = f (xi), (mi) (xi) = f (mi) (xi).注：注： N 个条件可以确定个条件可以确定 阶多项式。阶多项式。N 1要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数都重合的插阶导数都重合的插值多项式即为值多项式即为Taylor多项式多项式其余其余项为项为一般只考虑一般只考虑 f 与与f 的值。的值。73湘潭大学数学与计算科学学院上一页上一页下一页下一页 例：例：设设 x0 x1 x2, 已知已知 f(x0)、 f(x1)、 f(x2) 和和 f (x1),

36、 求多项式求多项式 P(x) 满足满足 P(xi) = f (xi)，i = 0, 1, 2，且且 P(x1) = f (x1), 并估计误并估计误差。差。模仿模仿 Lagrange 多项式的思想，设多项式的思想，设解：解：首先，首先，P 的阶的阶数数 = 3+=213)()()()()(=0iiixhx1f xhxfxP h0(x)有根有根x1, x2，且且 h0(x1) = 0 x1 是重根。是重根。)()()(22100xxxxCxh = =又又: h0(x0) = 1 C0 h2(x)h1(x)有根有根 x0, x2 )()()(201xxxxBAxxh + += =由余下条件由余下条

37、件 h1(x1) = 1 和和 h1(x1) = 0 可可解。解。与与h0(x) 完全类似。完全类似。 (x) h1有根有根 x0, x1, x2 h1)()()(2101xxxxxxCx = = h1又又: (x1) = 1 C1 可解。可解。其中其中 hi(xj) = ij , hi(x1) = 0, (xi) = 0, (x1) = 1 h1 h1与与 Lagrange 分析分析完全类似完全类似74湘潭大学数学与计算科学学院上一页上一页下一页下一页 一般地，已知一般地，已知 x0 , , xn 处有处有 y0 , , yn 和和 y0 , , yn ，求求 H2n+1(x) 满足满足 H

38、2n+1(xi) = yi ， H2n+1(xi) = yi。解：解：设设+=ni)()()(=0iixhxhyixH2n+1 n=0iyi其中其中 hi(xj) = ij , hi(xj) = 0, (xj) = 0, (xj) = ij hi hihi(x)有根有根 x0 , , xi , , xn且都是且都是2重根重根 )()()(2xlBxAxhiiii+ += =由余下条件由余下条件 hi(xi) = 1 和和 hi(xi) = 0 可解可解Ai 和和 Bi (x) hi有根有根 x0 , , xn, 除了除了xi 外都是外都是2重根重根 hi)()(iili2(x)xxCx = =

39、 hi又又: (xi) = 1 Ci = 1 hi)(x)(ili2(x)xx = =设设则则这样的这样的Hermite 插值唯插值唯一一75湘潭大学数学与计算科学学院上一页上一页下一页下一页 求求Hermite多项式的基本步骤：多项式的基本步骤： 写出相应于条件的写出相应于条件的hi(x)、 hi(x) 的组合形式；的组合形式； 对每一个对每一个hi(x)、 hi(x) 找出尽可能多的条件给出的根；找出尽可能多的条件给出的根； 根据多项式的总阶数和根的个数写出表达式；根据多项式的总阶数和根的个数写出表达式； 根据尚未利用的条件解出表达式中的待定系数；根据尚未利用的条件解出表达式中的待定系数；

40、 最后完整写出最后完整写出H(x)。76湘潭大学数学与计算科学学院上一页上一页下一页下一页 4 4 分段低次插值分段低次插值 例：例：在在 5, 5上考察上考察 的的Ln(x)。取。取 -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端点附近抖动端点附近抖动越大，称为越大，称为Runge 现象现象Ln(x) f (x) 78湘潭大学数学与计算科学学院上一页上一页下一页下一页NewtonNewton向前插值多项式：向前插值多项式：，则：，则：若若不精确，成为不精确，成为79湘潭大学数学与计算科学学院上一页上一页下一页下一页这时这

41、时若：若：则：则：. . 得表：得表：80湘潭大学数学与计算科学学院上一页上一页下一页下一页81湘潭大学数学与计算科学学院上一页上一页下一页下一页分段分段低次低次插值插值 算法数值稳定性得不到保证算法数值稳定性得不到保证舍入误差严重影响高阶差商或差分的准确性舍入误差严重影响高阶差商或差分的准确性最终严重影响到插值结果的精度最终严重影响到插值结果的精度. .82湘潭大学数学与计算科学学院上一页上一页下一页下一页 分段线性插值分段线性插值 在每个区间在每个区间 上，用上，用1阶多项式阶多项式 (直线直线) 逼近逼近 f (x):记记 ，易证：当，易证：当 时，时，一致一致83湘潭大学数学与计算科学

42、学院上一页上一页下一页下一页若若在在a,b上二阶连续可微，上二阶连续可微，时，时，则当则当有有从而从而84湘潭大学数学与计算科学学院上一页上一页下一页下一页由于由于于是，在整个区间于是，在整个区间a,b上有上有 其中其中85湘潭大学数学与计算科学学院上一页上一页下一页下一页失去了原函数的光滑性。失去了原函数的光滑性。86湘潭大学数学与计算科学学院上一页上一页下一页下一页 分段分段Hermite插值插值 给定给定在在 上利用两点的上利用两点的 y 及及 y ，可构造可构造3次次Hermite函数函数.其误差估计：其误差估计：记记有：有：87湘潭大学数学与计算科学学院上一页上一页下一页下一页若若在

43、在a,b上四阶连续可微，上四阶连续可微，时，时，则当则当有有从而在整个区间从而在整个区间a,b上有上有 其中其中88湘潭大学数学与计算科学学院上一页上一页下一页下一页 5 5 样条函数插值样条函数插值 设设 。三三次次样样条条函函数数 , 且且在在每每个个 上上为为三三次次多多项项式式 /* cubic polynomial */。若若它它同同时时还还满满足足 ，则则称称为为 f 的的三三次次样样条条插插值函数值函数 .注：注：三次样条与分段三次样条与分段 Hermite 插值的根本区别在于插值的根本区别在于S(x)自自身光滑身光滑，不需要知道，不需要知道 f 的导数值（除了在的导数值（除了在

44、2个端点可能需要）个端点可能需要）；而；而Hermite插值依赖于插值依赖于f 在所有插值点的导数值。在所有插值点的导数值。f(x)H(x)S(x)89湘潭大学数学与计算科学学院上一页上一页下一页下一页 构造三次样条插值函数的构造三次样条插值函数的三弯矩法三弯矩法 在在 上，记上，记,for )()(1jjjxxxxSxS = =对每个对每个j, 此为此为3次多项式次多项式则则 Sj”(x) 为为 次多项式，需次多项式，需 个点的值确定之。个点的值确定之。12设设 Sj”(xj 1) = Mj 1， Sj”(xj) = Mj 对于对于x xj 1, xj 可可得到得到Sj”(x) =jjjjj

45、jhxxMhxxM11 + + 积分积分2次，可得次，可得 Sj(x) 和和 Sj(x) ：jjjjjjjAhxxMhxxM+ + + + 2)(2)(2121Sj(x) =jjjjjjjjBxAhxxMhxxM+ + + + + 6)(6)(3131Sj(x) =利用已知利用已知Sj(xj 1) = yj 1 Sj(xj) = yj 可解可解90湘潭大学数学与计算科学学院上一页上一页下一页下一页jjjjjjjhMMhyyA611 = =jjjjjjjjjjjjhxxhMyhxxhMyBxA12211)6()6( + + = =+ +利用已知利用已知Sj(xj 1) = yj 1 Sj(xj)

46、 = yj 可解可解91湘潭大学数学与计算科学学院上一页上一页下一页下一页 下面解决下面解决 Mj ： 利用利用S 在在 xj 的的连续性连续性xj 1, xj : Sj(x) =jjjjjjjjjjjhMMxxfhxxMhxxM6,2)(2)(112121 + + + + 1111211216,2)(2)(+ + + + + + + + + + + + jjjjjjjjjjjhMMxxfhxxMhxxMxj , xj+1: Sj+1(x) =利用利用Sj(xj) = Sj+1(xj)，合并关于合并关于Mj 1、 Mj、 Mj+1的同类的同类项，并记项，并记 , , , 整理后得到：整理后得到

47、：11jjjjhhh+= 1jj-= ),(6111jjjjjjjxxfxxfhhg-+-+=211gMMMjjjjjj=+- j 1n 1即：有即：有 个未知数，个未知数， 个方程。个方程。n 1n+1还需还需2个个边界条件边界条件92湘潭大学数学与计算科学学院上一页上一页下一页下一页 第第1类边界条件：类边界条件： S(a) = y0， S(b) = yna , x1 : S1(x) =1011012112106,2)(2)(hMMxxfhaxMhxxM + + + + 010110),(62gy0xxfhMM= = = =+ +nnnnnngxxfynhMM= = = =+ + ),(6

48、211类似地利用类似地利用 xn 1, b 上的上的 Sn(x)93湘潭大学数学与计算科学学院上一页上一页下一页下一页 第第2类边界条件：类边界条件： S”(a) = y0” = M0， S”(b) = yn” = Mn这时：这时：94湘潭大学数学与计算科学学院上一页上一页下一页下一页 第第3类边界条件类边界条件 ： 当当 f 为为周期函数周期函数时，时， yn = y0 ， S(a+) = S(b ) ， S” (a+) = S”(b ) M0 = Mn 95湘潭大学数学与计算科学学院上一页上一页下一页下一页例例 给定插值条件给定插值条件 0 01 12 2 3 30 00 00 0 0 0

49、附加边界条件为：附加边界条件为：. .试求试求满足上述条件的三次插值样条函数的分段表达式满足上述条件的三次插值样条函数的分段表达式. .解：（三弯矩方法）解：（三弯矩方法）利用二阶导数利用二阶导数为待定参数为待定参数, ,得得96湘潭大学数学与计算科学学院上一页上一页下一页下一页边界条件方程为边界条件方程为: :97湘潭大学数学与计算科学学院上一页上一页下一页下一页利用公式利用公式求得三次插值样条函数：求得三次插值样条函数：98湘潭大学数学与计算科学学院上一页上一页下一页下一页若利用若利用三转角方法三转角方法, ,选取选取作待定作待定参数，也可获得同样的结果参数，也可获得同样的结果. .99湘

50、潭大学数学与计算科学学院上一页上一页下一页下一页 注：注：另有另有三转角法三转角法得到样条函数，即设得到样条函数，即设 Sj(xj) = mj，则易知则易知xj 1, xj 上的上的Sj(x) 就是就是Hermite函数函数。再利。再利用用S”的连续性，可导出关于的连续性，可导出关于mj 的的方程组，加上边界方程组，加上边界条件即可解。条件即可解。三次样条三次样条 由边界条件由边界条件 唯一唯一确定。确定。收敛性：收敛性：若若 ，且，且 ，则，则一致一致S(x) f(x)即即:提高精度只须提高精度只须增加节点增加节点, 而无须提高样条阶数。而无须提高样条阶数。稳定性：稳定性：只要边界条件保证只

51、要边界条件保证 | 0 |, | 0 |, | n |, | n | 2，则方程组系数阵为则方程组系数阵为SDD阵阵，保证数值稳定。保证数值稳定。100湘潭大学数学与计算科学学院上一页上一页下一页下一页 三次样条算法流程三次样条算法流程: 计算计算 j , j , gj ; 计算计算 Mj (追赶法等追赶法等) ; 找到找到 x 所在区间所在区间 ( 即找到相应的即找到相应的 j ) ; 由该区间上的由该区间上的 Sj(x) 算出算出 f(x) 的近似值。的近似值。101湘潭大学数学与计算科学学院上一页上一页下一页下一页三、三次插值样条函数的基本性质和误差估计三、三次插值样条函数的基本性质和误

52、差估计 主要讨论主要讨论型三次样条插值问题型三次样条插值问题1 1、基本性质、基本性质 引理引理5.1 若若是是型三次插值样条函数型三次插值样条函数, ,有有则对则对证明证明 令令则则且满足且满足102湘潭大学数学与计算科学学院上一页上一页下一页下一页对对利用分部积分及利用分部积分及上述条件，上述条件，有有 其中其中可取为剖分单元中点的函数值可取为剖分单元中点的函数值. . 103湘潭大学数学与计算科学学院上一页上一页下一页下一页两个重要性质：两个重要性质： 定理定理5.2 (最小模性质最小模性质)是是型型若若则则三次插值样条函数，三次插值样条函数，(5.18)而且等号而且等号仅当仅当时成立时

53、成立. . 证明证明 利用引理利用引理5.1，有有特别取特别取104湘潭大学数学与计算科学学院上一页上一页下一页下一页即即 (5.19)利用利用Cauchy-Schwarz不等式，有不等式，有 (5.20)将将(5.20)代入代入(5.19)，两边约去两边约去后再平方后再平方即可得即可得105湘潭大学数学与计算科学学院上一页上一页下一页下一页下面考虑等号成立的情形，即下面考虑等号成立的情形，即 由上式，并利用引理由上式，并利用引理5.1有有 由此知由此知为线性函数为线性函数. .106湘潭大学数学与计算科学学院上一页上一页下一页下一页 又因为所有剖分节点均是又因为所有剖分节点均是的零点。的零点

54、。因此因此在在a,b上上至少至少有两个零点有两个零点所以所以定理定理5.3 (最佳逼近性质最佳逼近性质 )是是型型若若三次插值样条函数，三次插值样条函数，(5.21)则对则对有有 107湘潭大学数学与计算科学学院上一页上一页下一页下一页证明证明 利用引理利用引理5.1及及Cauchy-Schwarz不等式，有不等式，有 108湘潭大学数学与计算科学学院上一页上一页下一页下一页在上式两边约去在上式两边约去后再平方，后再平方，即可得即可得 109湘潭大学数学与计算科学学院上一页上一页下一页下一页2、误差估计误差估计取取为等距剖分，为等距剖分，并对并对定义如下定义如下两种范数两种范数 即即总假设总假

55、设并记并记 110湘潭大学数学与计算科学学院上一页上一页下一页下一页定理定理5.4 设设为为型三次插值样条型三次插值样条问题的误差函数，问题的误差函数，则有则有其中其中111湘潭大学数学与计算科学学院上一页上一页下一页下一页定理定理5.5 设设为为型或型或型三次插值样条函数，型三次插值样条函数， 则则这里这里而而为为剖分网格比剖分网格比. . 112湘潭大学数学与计算科学学院上一页上一页下一页下一页以上定理指出以上定理指出: :便能保证三次插值样条函数便能保证三次插值样条函数及其一、二阶导数一致收敛于及其一、二阶导数一致收敛于及其相应及其相应关于分划关于分划一致有界一致有界. . 1、只要只要

56、的导数的导数. . 对对的一致收敛性，的一致收敛性，2、但但还要求还要求113湘潭大学数学与计算科学学院上一页上一页下一页下一页 插值法小结插值法小结 Lagrange : 给出给出 y0 yn，选基函数选基函数 li(x)，其次数为其次数为 节点数节点数 1。 Newton Ln(x)，只是形式不同；节点等距或渐增节点只是形式不同；节点等距或渐增节点时方便处理。时方便处理。 Hermite： 给出给出 yi 及及 yi ，选选 hi(x) 及及 hi(x) 。 Spline：分段低次分段低次, 自身光滑自身光滑, f 的导数只在边界给出。的导数只在边界给出。 114湘潭大学数学与计算科学学院