数值分析第二章ppt课件

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

2、方法、理论及其实现的方法、理论及其实现. . 近似代替又叫做逼近近似代替又叫做逼近 . .( )x ( )f x被逼近的函数被逼近的函数 或被近似的函数或被近似的函数 逼近的函数逼近的函数 或近似的函数或近似的函数 即即上一页上一页下一页下一页函数逼近是数值分析的许多分支的理论基础函数逼近是数值分析的许多分支的理论基础. . 例如例如: : 数值积分数值积分; ; 数值微分数值微分; ; 微分方程数值解微分方程数值解; ;曲线曲面拟合曲线曲面拟合; ;函数值近似计算函数值近似计算; ;等等等等上一页上一页下一页下一页从逼近论的观点，通常有两种意义下的逼近：从逼近论的观点，通常有两种意义下的逼近

3、：局部逼近局部逼近整体逼近整体逼近1 1、局部逼近、局部逼近所谓局部逼近就是求函数所谓局部逼近就是求函数( )f x在某点附近的近似在某点附近的近似 最常用的逼近方法：最常用的逼近方法： Taylor逼近方法逼近方法 理论依据：理论依据： Taylor定理定理 上一页上一页下一页下一页( )f x0 x00(,)Ixx 1n ,xI 定理定理1.11.1设设n n为一非负整数，为一非负整数，在点在点某一邻域某一邻域有有阶连续导数，阶连续导数，有有 则对则对的的( )( )( )nnf xpxR x( )npx( )nR x这里，这里，n n次次TaylorTaylor逼近多项式逼近多项式和误差

4、余项和误差余项分别为分别为( )00000()()( )()()() ,1!nnnf xfxp xf xxxxxn 0(1)(1)101( )( )()( )(),!(1)!nxnnnnxfR xxtft dtxxnn (1.1) (1.2) (1.3) 上一页上一页下一页下一页注意：注意：( )npx1 1、TaylorTaylor逼近多项式逼近多项式满足以下逼近要求满足以下逼近要求 00()(), 0,1, .kknkkd p xd f xkndxdx ( )f x0 x2、Taylor逼近是一种局部逼近逼近是一种局部逼近在一点在一点处的信息处的信息. .仅利用了被逼近的函数仅利用了被逼近

5、的函数下面举例说明下面举例说明TaylorTaylor多项式的逼近效果多项式的逼近效果. . 上一页上一页下一页下一页解解 由由(1.2)(1.2)式和式和(1.3)(1.3)式易求得式易求得 ( )00000()()( )()()() ,1!nnnf xfxp xf xxxxxn 0(1)(1)101( )( )()( )(),!(1)!nxnnnnxfR xxtft dtxxnn (1.2) (1.3) 1( )1,p xx 22( )1,2xp xx12111( )( ),2xR xep xx e 23221( )( ),6xR xep xx e 直观理解可以参见下图。直观理解可以参见下

6、图。 上一页上一页下一页下一页(a)xe的一次和二次的一次和二次TaylorTaylor逼近函数逼近函数 (b)xe的一次和二次的一次和二次TaylorTaylor逼近误差逼近误差 (a)(b)上一页上一页下一页下一页因而，因而，TaylorTaylor逼近适合作函数的局部逼近逼近适合作函数的局部逼近. .由此可见：误差不是均匀分布的由此可见：误差不是均匀分布的. . 当当x x越偏离越偏离x0 x0误差就越大误差就越大即当即当x x越接近越接近x0 x0误差就越小；误差就越小；我们将主要讨论整体逼近问题我们将主要讨论整体逼近问题: :即对定义域上的所有点即对定义域上的所有点. .近似函数对被

7、逼近函数的逼近近似函数对被逼近函数的逼近函数曲线对样本数据的拟合函数曲线对样本数据的拟合考虑考虑: :上一页上一页下一页下一页(0.5, 0)(1, 0.25) (1.5, 1).ABC、和和例例2 2 求区间求区间0,1.50,1.5上的二次抛物曲线上的二次抛物曲线, ,要求要求该曲线过样本点该曲线过样本点 解解 设所求抛物线的方程为设所求抛物线的方程为2,yabxcx 利用待定系数法，可得利用待定系数法，可得21.4yxx 此例将引出所谓的此例将引出所谓的 Lagrange Lagrange 型多项式插值问题型多项式插值问题, , 这时给定这时给定的样本数据仅包含函数值的样本数据仅包含函数

8、值. . 上一页上一页下一页下一页例例3 3 求区间求区间0,10,1上的三次曲线，要求该函数曲线过上的三次曲线，要求该函数曲线过且其一阶导函数曲线过样本点且其一阶导函数曲线过样本点(0,0)(1,1)和和( (即函数曲线在即函数曲线在0,10,1点处的斜率分别为点处的斜率分别为0 0和和1).1).(0,1)A(1,0),B和和样本点样本点23,yabxcxdx 23143.yxx 解解 设所求的三次曲线为设所求的三次曲线为类似于例类似于例2 2的计算，可得的计算，可得上一页上一页下一页下一页上例将引出所谓的上例将引出所谓的HermiteHermite型多项式插值问题型多项式插值问题此时样本

9、数据包含：此时样本数据包含：1 1、函数值、函数值2 2、一阶导数值、一阶导数值. . 更广泛的还有所谓的更广泛的还有所谓的BirkhoffBirkhoff插值问题插值问题. . 注意：注意：上一页上一页下一页下一页1,0,1 121( 2,0)( 1, )(0, )(1, )636ABCD、(2,0)E 2,2 例例4 4 求区间求区间上的二阶连续可微的分段三次多项式上的二阶连续可微的分段三次多项式），要求该曲线过点），要求该曲线过点和和，且在，且在A、E两点的导数为两点的导数为0. 曲线其内部段点分别为曲线其内部段点分别为解解 注意所求函数为偶函数，注意所求函数为偶函数，利用待定系数法，利

10、用待定系数法，0,2x 上的表示式为上的表示式为 可得该函数在可得该函数在y 3212, 0123xxx 32142, 1263xxxx上一页上一页下一页下一页其图形如下图所示其图形如下图所示. .此例将引出所谓的样条插值问题：此例将引出所谓的样条插值问题： 即求满足一定的即求满足一定的整体光滑或连接条件的分段插值多项式整体光滑或连接条件的分段插值多项式. . 上一页上一页下一页下一页 1,1 ( ),f x2|arctan1sin, 1,0)(0,1,( )40, 0,xxxxf xxx 1( ),p x111max|( )( )|xf xp x 1211( ( )( ) f xp xdx

11、例例5 5 如下图，如下图， 上的函数上的函数达到最小达到最小. . 给定区间给定区间其表达式为其表达式为求一直线求一直线使误差使误差或或上一页上一页下一页下一页上例将引出所谓的最佳一致和最佳平方逼近问题。上例将引出所谓的最佳一致和最佳平方逼近问题。 x01234567y27.0 26.8 26.5 26.3 26.1 25.7 25.3 24.8例例6 6 给定离散数据下表），给定离散数据下表），数据，使误差平方和最小。数据，使误差平方和最小。125.273036. 0 xy此例将引出所谓的此例将引出所谓的最小二乘逼近问题。最小二乘逼近问题。 用一直线拟合这组用一直线拟合这组上一页上一页下一

12、页下一页(0,0.1)( )f xsin3sin4( )0.12sin2,23xxf xx 301sin,2kkabkx 例例7 7 如下图，如下图，满足满足(1)(1)最佳平方逼近于最佳平方逼近于f(x);f(x);或或(2)(2)拟合图中实心点所示拟合图中实心点所示对称的周期为对称的周期为22的曲线的曲线( (或样本点或样本点) )求三角多项式求三角多项式给定关于给定关于的所有样本点，使误差平方和最小的所有样本点，使误差平方和最小. . 上一页上一页下一页下一页上例将引出所谓的周期函数的最佳平方逼近问题及上例将引出所谓的周期函数的最佳平方逼近问题及快速快速FourierFourier变换。

13、变换。 逼近问题主要由以下三个要素构成：逼近问题主要由以下三个要素构成：(1) (1) 被逼近函数或样本数据）被逼近函数或样本数据）(2) (2) 逼近函数空间逼近函数空间简单函数：主要是指可以用四则运算进行计简单函数：主要是指可以用四则运算进行计算的函数，通常为代数或三角多项式、算的函数，通常为代数或三角多项式、分段多项式和有理多项式函数分段多项式和有理多项式函数. .简单函数所属的函数空间简单函数所属的函数空间上一页上一页下一页下一页 逼近问题主要由以下三个要素构成：逼近问题主要由以下三个要素构成：(1) (1) 被逼近函数或样本数据）被逼近函数或样本数据）(2) (2) 逼近函数空间逼近

14、函数空间简单函数：主要是指可以用四则运算进行计简单函数：主要是指可以用四则运算进行计算的函数，通常为代数或三角多项式、算的函数，通常为代数或三角多项式、分段多项式和有理多项式函数分段多项式和有理多项式函数. .简单函数所属的函数空间简单函数所属的函数空间上一页上一页下一页下一页(3) (3) 逼近方式逼近方式插值逼近：要求逼近函数曲线通过样本数据点插值逼近：要求逼近函数曲线通过样本数据点( (有时还要求在样本数据点处，等于给定的导数值有时还要求在样本数据点处，等于给定的导数值) )本章将在插值逼近方式下，讨论相应的逼近问题本章将在插值逼近方式下，讨论相应的逼近问题. .上一页上一页下一页下一页

15、插值问题涉及的基本内容：插值问题涉及的基本内容：1.1.问题提法问题提法 2.2.问题的适定性问题的适定性( (解的存在、唯一性解的存在、唯一性) )3.3.解的构造解的构造 ( (或表示或表示 ) )及其相关算及其相关算法法 4.4.误差分析误差分析( (逼近度刻化逼近度刻化) )及稳定性分析及稳定性分析 首先首先, ,对逼近函数取为代数多项式，样本数据对逼近函数取为代数多项式，样本数据仅包含被逼近函数的函数值的情形，讨论相应的仅包含被逼近函数的函数值的情形，讨论相应的插值问题插值问题. . 上一页上一页下一页下一页2 Lagrange2 Lagrange插值插值 一、问题的提法一、问题的提

16、法 二、适定性和二、适定性和LagrangeLagrange插值公式插值公式 三、三、NewtonNewton插值公式插值公式 上一页上一页下一页下一页一、问题的提法一、问题的提法(),0,1, ,iif xyin ,),(baIxxf 1 n知：知： 或其或其 个样本值个样本值nxxx,10且且彼此互异。彼此互异。01nnaa xa x 记所有次数不超过记所有次数不超过n n的代数多项式的代数多项式.nP的全体为的全体为上一页上一页下一页下一页插值问题：插值问题： 求求,nnPp 满足满足(),0,1, .niipxyin 00,x y ,iix y ,nnxy( )f x( )npx01,

17、nxxx称称为被插函数，为被插函数，为为n n次多项式插值函数，次多项式插值函数，为插值节点，为插值节点，的的LagrangeLagrange插值问题。插值问题。 并称并称而上述问题被称为而上述问题被称为 01,nxxx关于节点关于节点上一页上一页下一页下一页二、适定性和二、适定性和LagrangeLagrange插值公式插值公式 定理定理 2.1 2.1 插值问题的解是存在且唯一的插值问题的解是存在且唯一的. . 证明：（构造性证明）证明：（构造性证明）（1 1存在性存在性 首先构造特殊插值多项式首先构造特殊插值多项式,)(niPxl , 1, 0)(,kikixlkiki ., 1 , 0

18、,nki 克罗内克尔克罗内克尔(Kronecker)(Kronecker)符号符号. .:,ki (2.1) 上一页上一页下一页下一页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)( njijjijixxxxxl0)()()( niiinyxlxL0)()(Lagrange 多项式多项式与与 有关，而与有关，

19、而与 无关无关节点节点f上一页上一页下一页下一页(2) (2) 唯一性唯一性设设n n次多项式次多项式( )( )nnL xQx和和()()()0,1,2,niiniL xf xQ xin ( ):( )( ),nnnG xL xQxP记记()()()0,0,1,.ininiG xL xQ xin 且且均为插值问题的解均为插值问题的解, ,则有则有由高等代数基本知识知，由高等代数基本知识知，若一个若一个n n次代数多项式至少次代数多项式至少存在存在n+1n+1个根，则它一定恒为零个根，则它一定恒为零. . ( )0,( )( ).nnG xL xQx故故即即唯一性得证唯一性得证. . 上一页上

20、一页下一页下一页称为称为f(x)f(x)的的n n次多项式插值的次多项式插值的 Lagrange Lagrange 公式公式也称为也称为Lagrange Lagrange 插值多项式插值多项式. . 0( )( )nni iiL xy l x 称为称为n n次多项式插值问题的基函数次多项式插值问题的基函数(Lagrange (Lagrange 因子因子) )()()()(ininixxxxxl 其中其中0( )().nnjjxxx 上一页上一页下一页下一页例例 当当n=1n=1时，线性插值公式时，线性插值公式11001()( )()xxL xyxx 0110()()xxyxx 上一页上一页下一

21、页下一页当当n=2n=2时，抛物插值公式时，抛物插值公式12200102()()( )()()xxxxL xyxxxx 0211012()()()()xxxxyxxxx0122021()()()()xxxxyxxxx 上一页上一页下一页下一页 插值余项插值余项 设节点设节点)1( nf在在(a , b)内存在内存在, 考察截断误差考察截断误差)()()(xLxfxRnn , baCfn bxxxan 10，且，且 f 满足条件满足条件 ,Rolles Theorem: 假设假设 充分光滑，充分光滑， ，那么，那么存在存在 使得使得 。)(x 0)()(10 xx ),(10 xx 0)( 推广

22、：假推广：假设设0)()()(210 xxx ),(),(211100 xxxx 使得使得0)()(10 ),(10 使得使得0)( 0)()(0 nxx 存在存在),(ba 使得使得0)()( nRn(x) 至少有至少有 个根个根n+1 niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考考察察 niixtxKtRnt0)()()()( (t)有有 n+2 个不同的根个不同的根 x0 xn x),(, 0)()1(baxxn !)1()()()1(nxKRxnn 注意这里是对注意这里是对 t 求导求导 !)1)()()()1()1(nxKLfxnnxn

23、 !)1()()()1( nfxKxn niixnnxxnfxR0)1()(! ) 1()()( 上一页上一页下一页下一页niyxPiin,., 0,)( 求求 n 次多项式次多项式 使得使得nnnxaxaaxP 10)(条件：无重合节点，即条件：无重合节点，即jixx ji 首先找到首先找到li(x)，i = 0, , n 使得使得 li(xj)=ij ；然后；然后令令 niiinyxlxP0)()(，则显然有，则显然有Pn(xj) = yj 。定理定理 (唯一性唯一性) 满足满足 的的 n 阶插值多阶插值多项式是唯一存在的。项式是唯一存在的。niyxPii,., 0,)( 上一页上一页下一

24、页下一页li(x)每个每个 li 有有 n 个根个根 x0 xi-1 xi+1 xn njj i jiixxCxl0)()( j i jiiiixxCxl)(11)( njijjijixxxxxl0)()()( niiinyxlxL0)()(Lagrange 多项式多项式与与 有关，而与有关，而与 无关无关节点节点f上一页上一页下一页下一页000010( )()().()()( )( )()()()ninnniinnnjjjjijijiijxxxxxxxxxxLxyyxxxxxxx 若若上上式式可可改改成成( )jlx上一页上一页下一页下一页设节点设节点)1( nf在在(a , b)内存在内存

25、在, 其截断误差其截断误差)()()(xLxfxRnn , baCfn bxxxan 10，且，且 f 满足条件满足条件 , niixnnxxnfxR0)1()(! ) 1()()( 插值余项插值余项 /* Remainder */上一页上一页下一页下一页注：注： 通常不能确定通常不能确定 x , 而是估计而是估计 , x(a,b) 将将 作为误差估计上限。作为误差估计上限。1)1()( nnMxf niinxxnM01|)!1(当当 f(x) 为任一个次数为任一个次数 n 的多项式的多项式时，时， , 可知可知 ，即插，即插值多项式对于次数值多项式对于次数 n 的多项式是精的多项式是精确的。

26、确的。0)()1( xfn0)( xRn上一页上一页下一页下一页10010, 12111, 14412,125例例1 1 知知线性插值和抛物插值公式求线性插值和抛物插值公式求的近似值的近似值. . 试分别用试分别用01121,144,xx 0111,12,yy 解解 （1 1选取选取利用线性插值公式，利用线性插值公式，011010110()()( )()()xxxxL xyyxxxx 1144( )11121144xL x 可得可得 12112,144121x 于是于是 1125(125)L 11.17391. 上一页上一页下一页下一页012100,121,144,xxx 01210,11,1

27、2,yyy 解解 （2 2选取选取利用抛物插值公式，利用抛物插值公式，可得可得 0212201010210120122021()()()()( )()()()()()() ()()xxxxxxxxL xyyxxxxxxxxxxxxyxxxx 2(121)(144)( )10(100121) (100144)xxL x (100)(144)11(121100) (121144)xx (100)(121)12,(144100) (144121)xx 于是于是 2125(125)L 11.18107. 上一页上一页下一页下一页注意：注意：12511.1803398 则线性插值公式所得近似值有则线性插

28、值公式所得近似值有3 3位有效数字位有效数字 抛物插值公式所得近似值有抛物插值公式所得近似值有4 4位有效数字位有效数字 上一页上一页下一页下一页 例例 知知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x185500 n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 xx利用利用216/4/6/214/6/4/)(1 xxxL这里这里)3,6(,sin)(,sin)()2( xxxfxxf而而)4)(6(!2)()(

29、,23sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的实际误差的实际误差 0.010103,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R内插内插 /* interpolation */ 的实际误差的实际误差 0.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点，插值效果较好。端点，插值效果较好。上一页上一页下一页下一页 n =

30、 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.00061高次插值通常优于高次插值通常优于低次插值低次插值上一页上一页下一页下一页计算机上算法实现计算机上算法实现在计算机上实现：在计算机上实现：001(1)(0,1,2,. )02(0,1,2,. )niiiniiipapppainsbsssbin （ ） 上一页上一

31、页下一页下一页Lagrange插值算法。输出做对输入插值点计算插值输入vuylvvxxxulnjvuuLniyxjjnjiiijiiii,:4);2);/()(10,1,.,3)0;2);1);()2();,.,2 , 1 , 0(,:) 1 (o0o上一页上一页下一页下一页上一页上一页下一页下一页Lagrange插值公式的优缺点：插值公式的优缺点：优点：公式的形式对称，结构紧凑，优点：公式的形式对称，结构紧凑， 容易编写计算程序，便于理论分析和许多容易编写计算程序，便于理论分析和许多 数值计算公式的推导。数值计算公式的推导。缺点：没有承袭性，缺点：没有承袭性， 即当增加新的节点时，所有即当增

32、加新的节点时，所有LagrangeLagrange因子因子必须重新计算，这就会造成计算量的浪费。必须重新计算，这就会造成计算量的浪费。上一页上一页下一页下一页作业作业:P56-57:P56-571 1题题(1), 2(1), 2题题,3,3题题上一页上一页下一页下一页三、三、 牛顿插值公式牛顿插值公式 Lagrange 插值虽然易算，但若要增加一个节点时，插值虽然易算，但若要增加一个节点时，全部基函数全部基函数 li(x) 都需重新算过。都需重新算过。将将 Ln(x) 改写成改写成.)()(102010 xxxxaxxaa).(10 nnxxxxa的形式，希望每加一个节点时，的形式，希望每加一

33、个节点时，只附加一项上去即可。只附加一项上去即可。? 差商差商),()()(,jijijijixxjixxxfxfxxf 1阶差商阶差商 )(,kixxxxfxxfxxxfkikjjikji 2阶差商阶差商上一页上一页下一页下一页一般地，一般地，nnnnnnxxxxxfxxxfxxxf 01112010, 称为称为f (x)f (x)在在x0 , x1 , , xnx0 , x1 , , xn点的点的 n n 阶阶差商。差商。上一页上一页下一页下一页重节点差商重节点差商 其定义式为其定义式为 100010,lim,xxf x xf x x 1010010()()lim().xxf xf xfx

34、xx 一般地，可定义一般地，可定义 0101, , , .nndf xxxx xf xxxxdx 上一页上一页下一页下一页010(),()nknknkf xf xxxx 此性质表明差商与节点的排列次序无关。此性质表明差商与节点的排列次序无关。 f x0 , x1 , x2 , ., xn=性质性质1 1 差商可以表示为函数值的线性组合，即差商可以表示为函数值的线性组合，即差商的性质差商的性质: : 性质性质2 (2 (差商的对称性差商的对称性) )f x1 , x0 , x2 , ., xn= = fx1 , x2 , ., xn , x0 上一页上一页下一页下一页( )f x性质性质3 3

35、假设假设是一个是一个m m次代数多项式，次代数多项式， 那么那么1m 次代数多项式次代数多项式. . x0 x关于点关于点和任一已知和任一已知点点的一阶差商是的一阶差商是( )f x事实上，由差商的定义有事实上，由差商的定义有 000( )( ) ,f xf xf x xx x 上式右端的分子为上式右端的分子为m m次代数多项式次代数多项式, , 并且当并且当0 xx 时为零时为零, ,因此分子包含了因此分子包含了0 xx 因子刚好和分母约去因子刚好和分母约去, ,1m 次代数多项式次代数多项式. . 故右端为故右端为 上一页上一页下一页下一页 性质性质4 4 若若f(x)f(x)在在a,ba

36、,b上存在上存在n n阶导数阶导数, , 且节点且节点x0, x0, x1 , xnx1 , xn a,b, a,b,则至少存在一点则至少存在一点a, b a, b 满满足下式足下式!)(,)(10nfxxxfnn 解解 f (8)(x)=-68 !, f 1,2, ,9=-6, f (9)(x)=0, f 1,2, ,10=0.例例1 f (x)=-6x8+7x5-10,1 f (x)=-6x8+7x5-10,求求f 1,2, ,9f 1,2, ,9及及f 1,2, ,10.f 1,2, ,10.上一页上一页下一页下一页 牛顿插值牛顿插值 / /* * Newtons Newtons Int

37、erpolation Interpolation * */ /).(.)()()(10102010 nnnxxxxaxxxxaxxaaxN?上一页上一页下一页下一页010 ,.,.,0 ,.,nnnf x xxf xxnx xf x xx ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf （n+1） 上一页上一页下一页下一页 牛顿插值牛顿插值 ,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf ).(.)()()(10102010 nnnxxxxaxxxxaxxaaxN12 n+

38、11+ (x x0) 2+ + (x x0)(x xn1) n+1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)ai = f x0, , xi 上一页上一页下一页下一页57 注：注： 由唯一性可知由唯一性可知 Nn(x) Ln(x)， 只是算法不同，故只是算法不同，故其余项也相同，即其余项也相同，即)(!)1()()(,.,1)1(10 xnfxxxxfnxnnn),(,!)(,.,maxmin)(0 xxkfxxfkk 实际计算过程实际计算过程为为f (x

39、0)f (x1)f (x2)f (xn1)f (xn)f x0, x1f x1, x2 f xn1, xnf x0, x1 , x2 f xn2, xn1, xnf x0, , xn f (xn+1) f xn, xn+1 f xn1, xn, xn+1 f x1, , xn+1 f x0, , xn+1上一页上一页下一页下一页差商表上一页上一页下一页下一页59上一页上一页下一页下一页60上一页上一页下一页下一页上一页上一页下一页下一页上一页上一页下一页下一页xk f(xk)一阶均差一阶均差 二阶均差二阶均差三阶均差三阶均差 四阶均差四阶均差0.400.550.650.800.900.4107

40、50.578150.696750.888111.026521.116001.186001.275731.384100.280000.358930.433480.197330.213000.03134例例2 已知已知f(x)的函数表的函数表, 求二次牛顿插值多项式求二次牛顿插值多项式, 并由并由此计算此计算f(0.596)的近似值。的近似值。 2( )0.41075 1.11600(0.40)N xx 解解 由上表可得过前三点的由上表可得过前三点的2 2次次NewtonNewton插值多项式为插值多项式为0.28000(0.40)(0.55)xx 上一页上一页下一页下一页632010. 0)59

41、6. 0()596. 0(2 Nf又又0123,0.19733f x x xx 可得过前四点的可得过前四点的3次次Newton插值多项式插值多项式32( )( )0.19733(0.40)(0.55)(0.65)NxNxxxx故故3(0.596)(0.596)0.6319145fN 故故2( )0.410751.11600(0.40)0.28000(0.40)(0.55)N xxxx 04,0.03134f xx 又又上一页上一页下一页下一页可得过前五点的可得过前五点的4次次Newton插值多项式插值多项式43( )( )0.03134(0.4)(0.55) (0.65)(0.80),N xN

42、xxxxx 于是于是4(0.596)(0.596)fN 0.63195. 当插值节点等距分布时，上述基于差商的当插值节点等距分布时，上述基于差商的NewtonNewton插值插值公式可以得到进一步简化。公式可以得到进一步简化。上一页上一页下一页下一页作业作业:P57-58:P57-586 6题题, 7, 7题题上一页上一页下一页下一页 等距节点公式等距节点公式 向前差分向前差分 iiifff 1ikikikikffff1111)( 向后差分向后差分 111 ikikikfffi1iifff 中心差分中心差分 1122112211iiikkkiiiffffffdddd+-+-=-=-其中其中)(

43、221hiixff 当节点等距分布时当节点等距分布时:),.,0(0nihixxi 上一页上一页下一页下一页 差分的重要性质：差分的重要性质： 线性：例如线性：例如gbfaxgbxfa )()( 假设假设 f (x)是是 m 次多项式，那么次多项式，那么 是是 次多项式，而次多项式，而 )0()(mkxfk km )(0)(mkxfk 差分值可由函数值算出：差分值可由函数值算出： njjknjknfjnf0)1( njnjkjnknfjnf0) 1(!)1).(1(jjnnnjn 其中其中 函数值可由差分值算出：函数值可由差分值算出：kjnjknfjnf 0kkkhkfxxf!,.,00 kn

44、kknnnhkfxxxf!,.,1 kkkhff0)()( 由由 Rn 表达式表达式上一页上一页下一页下一页 牛顿公式牛顿公式).(,.,.)(,)()(1000100 nnnxxxxxxfxxxxfxfxN 牛顿向前插值公式牛顿向前插值公式 牛顿向后插值公式牛顿向后插值公式 将节点顺序倒置：将节点顺序倒置：).(,.,.)(,)()(101xxxxxxfxxxxfxfxNnnnnnnn 设设htxx 0，那，那么么)()()(000 xfkthtxNxNknknn ),(,).(1()!1()()(01)1(nnnnxxhntttnfxR 设设htxxn ，那，那么么)() 1()()(0n

45、knkknnnxfkthtxNxN 注：一般当注：一般当 x 靠近靠近 x0 时用牛顿向前插值公式，靠近时用牛顿向前插值公式，靠近 xn 时用牛顿向后插值公式。时用牛顿向后插值公式。上一页上一页下一页下一页例例3 3 设设 y=f(x)=ex, xi=1, 1.5, 2, 2.5, 3, y=f(x)=ex, xi=1, 1.5, 2, 2.5, 3, 用三用三次插值多项式求次插值多项式求f(1.2) f(1.2) 及及f(2.8)f(2.8)的近似值的近似值. .解解 相应的函数值及差分表如下相应的函数值及差分表如下: :0.48146 0.74210 1.22356 1.14396 1.8

46、86063.10962 1.76341 2.90347 4.793437.90305 2.71828 4.481697.28906 12.1824920.08554四阶差分四阶差分三阶差分三阶差分二阶差分二阶差分一阶差分一阶差分函数值函数值上一页上一页下一页下一页函数值函数值一阶差分一阶差分二阶差分二阶差分三阶差分三阶差分四阶差分四阶差分2.71828 4.481697.28906 12.1824920.08554 1.76341 2.90347 4.793437.90305 1.14396 1.886063.10962 0.74210 1.223560.48146求求f(1.2)用用Newt

47、on前插公式前插公式, 且由且由 1.2=1+0.5t, 得得t=0.431.14396(1.2)(1.2)2.71828 1.76341 0.40.4 (0.4 1)2!0.742100.4 (0.4 1)(0.4 2)3!fN 3.3338632. 上一页上一页下一页下一页求求f(2.8)用用Newton后插公式后插公式,且由且由 2.8=3+0.5t, 得得 t=-0.43(2.8)(2.8)fN 15.7680872. 20.085547.90305 ( 0.4) 3.10962( 0.4)( 0.41)2! 1.22356( 0.4)( 0.41)( 0.42)3! 上一页上一页下一

48、页下一页 3 3 埃尔米特插值埃尔米特插值 不仅要求函数值重合，而且要求若干阶导数也重合。不仅要求函数值重合，而且要求若干阶导数也重合。即：要求插值函数即：要求插值函数 (x) 满足满足 (xi) = f (xi), (xi) = f (xi), (mi) (xi) = f (mi) (xi).注：注： N 个条件可以确定个条件可以确定 阶多项式。阶多项式。N 1要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数阶导数都重合的插值多项式即为都重合的插值多项式即为Taylor多多项式项式00)(!)(.)()()(000)(000mmxxmxfxxxfxfx 其余项为其余项为)1(00)

49、1(00)()!1()()()()(mmxxmfxxfxR 一般只考虑一般只考虑 f 与与f 的值。的值。上一页上一页下一页下一页 例：设例：设 x0 x1 x2, 知知 f(x0)、 f(x1)、 f(x2) 和和 f (x1), 求多求多项式项式 P(x) 满足满足 P(xi) = f (xi)，i = 0, 1, 2，且，且 P(x1) = f (x1), 并估计误差。并估计误差。模仿模仿 Lagrange 多项式的思想，设多项式的思想，设解：首先，解：首先，P 的阶数的阶数 = 3213)()()()()(0iiixhx1f xhxfxP h0(x)有根有根x1, x2，且，且 h0(

50、x1) = 0 x1 是重根。是重根。)()()(22100 xxxxCxh 又又: h0(x0) = 1 C0 )()()()()(202102210 xxxxxxxxxh h2(x)h1(x)有根有根 x0, x2 )()()(201xxxxBAxxh 由余下条件由余下条件 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, (x

51、1) = 1 h1 h1),()()()()()(221033xxxxxxxKxPxfxR !4)()()4(xfxK 与与 Lagrange 分析分析完全类似完全类似上一页上一页下一页下一页 一般地，知一般地，知 x0 , , xn 处有处有 y0 , , yn 和和 y0 , , yn ，求，求 H2n+1(x) 满足满足 H2n+1(xi) = yi ， H2n+1(xi) = yi。解：设解：设ni)()()(0iixhxhyixH2n+1 n0iyi其中其中 hi(xj) = ij , hi(xj) = 0, (xj) = 0, (xj) = ij hi hihi(x)有根有根 x0

52、 , , xi , , xn且都是且都是2重根重根 )()()(2xlBxAxhiiii ijjijixxxxxl)()()(由余下条件由余下条件 hi(xi) = 1 和和 hi(xi) = 0 可解可解Ai 和和 Bi )()(21 )(2xlxxxlxhiiiii (x) hi有根有根 x0 , , xn, 除了除了xi 外都是外都是2重根重根 hi)()(iili2(x)xxCx hi又又: (xi) = 1 Ci = 1 hi)(x)(ili2(x)xx 设设,.210baCfbxxxann 那那么么20)22()()!22()()( niixnnxxnfxR 这样的这样的Hermi

53、te 插值唯插值唯一一上一页上一页下一页下一页 求求Hermite多项式的基本步骤：多项式的基本步骤： 写出相应于条件的写出相应于条件的hi(x)、 hi(x) 的组合形式；的组合形式； 对每一个对每一个hi(x)、 hi(x) 找出尽可能多的条件给出的根；找出尽可能多的条件给出的根； 根据多项式的总阶数和根的个数写出表达式；根据多项式的总阶数和根的个数写出表达式； 根据尚未利用的条件解出表达式中的待定系数；根据尚未利用的条件解出表达式中的待定系数； 最后完整写出最后完整写出H(x)。上一页上一页下一页下一页作业作业:P57-58:P57-588 8题题, 10, 10题题上一页上一页下一页下

54、一页 4 分段低次插值分段低次插值 例：在例：在5, 5上考察上考察 的的Ln(x)。取。取211)(xxf),., 0(105niinxi -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) 上一页上一页下一页下一页 )1(! 2! 1)(0200ttftffxp)1()1(!0 ntttnfnthxx 0 ,kfkf )1(! 2! 1)(0200ttftffxpNewtonNewton向前插值多项式：向前插值多项式：，那么：，那么：假设假

55、设不精确，成为不精确，成为上一页上一页下一页下一页这时这时 ikfikffkkk, ikikffRkkk, 0 knknknffR假设：假设：那么：那么：. . 得表：得表：)1()1(!0 ntttnfn上一页上一页下一页下一页 61520156 5 10105 46 4 3 3 2 kR 2 3 4 5 6 上一页上一页下一页下一页分段低次插值分段低次插值 算法数值稳定性得不到保证算法数值稳定性得不到保证舍入误差严重影响高阶差商或差分的准确性舍入误差严重影响高阶差商或差分的准确性最终严重影响到插值结果的精度最终严重影响到插值结果的精度. .上一页上一页下一页下一页 分段线性插值分段线性插值

56、 在每个区间在每个区间 上，用上，用1阶多项式阶多项式 (直线直线) 迫近迫近 f (x):,1 iixx11111)()( iiiiiiiiyxxxxyxxxxxPxf,for 1 iixxx记记 ，易证：当，易证：当 时，时，|max1iixxh 0h)()(1xfxPh一致一致| )(|max8| )()(|max 21xfhxPxfbxabxa上一页上一页下一页下一页( )f x假设假设在在a,ba,b上二阶连续可微，上二阶连续可微，ixe 时，时，则当则当有有111( )( )( )()(), ,2!iiiiiiff xp xxxxxxx 从而从而iiiiiixx xxx xf xp

57、 xxxxxfx11111|( )( )|max ()() max( ) ,2 上一页上一页下一页下一页iiiiiixx xxx xf xp xxxxxfx11111|( )( )|max ()() max( ) ,2 由于由于1211max |()()|, 4iiiiixx xhxxxx 11,iiihxx 于是，在整个区间于是，在整个区间a,ba,b上有上有 21|( )( )|max( ) ,8a x bhf xp xfx 其中其中1max.ii nhh 上一页上一页下一页下一页失去了原函数的光滑性。失去了原函数的光滑性。上一页上一页下一页下一页 分段分段Hermite插值插值 给定给定

58、nnnyyyyxx ,.,;,.,;,.,000在在 上利用两点的上利用两点的 y 及及 y ，可构造，可构造3次次Hermite函数函数.,1 iixx, max1inihh 1iiixxh其误差估计：其误差估计：记记有：有：|,)(|max384| )()(|max)4(4xfhxHxfbxabxa上一页上一页下一页下一页( )f x假设假设在在a,ba,b上四阶连续可微，上四阶连续可微，ixe 时，时，则当则当有有(4)2211( )( )( )() () , (,),4!iiiiiiff xH xxxxxxx 从而在整个区间从而在整个区间a,ba,b上有上有 4(4)|( )( )|m

59、ax( ) ,384a x bhf xH xfx 其中其中1max.ii nhh 上一页上一页下一页下一页 5 样条函数插值样条函数插值 定义定义设设 。三次样条函数。三次样条函数 , 且在每个且在每个 上为三次多项式上为三次多项式 /* cubic polynomial */。若它。若它同时还满足同时还满足 ，则称为，则称为 f 的三次样条插值的三次样条插值函数函数 .bxxxan .10,)(2baCxS ,1 iixx),., 0(),()(nixfxSii 注：三次样条与分段注：三次样条与分段 Hermite 插值的根本区别在于插值的根本区别在于S(x)自自身光滑，不需要知道身光滑，不

60、需要知道 f 的导数值除了在的导数值除了在2个端点可能需个端点可能需要）；而要）；而Hermite插值依赖于插值依赖于f 在所有插值点的导数值。在所有插值点的导数值。f(x)H(x)S(x)上一页上一页下一页下一页 构造三次样条插值函数的三弯矩法构造三次样条插值函数的三弯矩法 在在 上，记上，记,1jjxx ,1 jjjxxh,for )()(1jjjxxxxSxS 对每个对每个j, 此为此为3次多项式次多项式那么那么 Sj”(x) 为为 次多项式，需次多项式，需 个点的值确定之。个点的值确定之。12设设 Sj”(xj1) = Mj1， Sj”(xj) = Mj 对于对于x xj1, xj 可