第二章-插值法-数值分析.课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第二章-插值法-数值分析.课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 插值法 数值 分析 课件
- 资源描述:
-
1、第二章第二章 插值法插值法/* Interpolation */Interpolation_introduction1 引引 言言1.1.函数表达式过于复杂不便于计算函数表达式过于复杂不便于计算, , 而又需要计算许而又需要计算许多点处的函数值多点处的函数值2.2.仅有几个采样点处的函数值仅有几个采样点处的函数值, , 而又需要知道非采样而又需要知道非采样点处的函数值点处的函数值 v上述问题的一种上述问题的一种解决思路:解决思路:建立复杂函数或者未建立复杂函数或者未知函数的一个便于计算的近似表达式知函数的一个便于计算的近似表达式. .v解决方法解决方法插值法插值法 1. 1. 插值概念插值概念
2、求插值函数求插值函数 ( (x) )的问题的问题( (方法方法) )称为称为插值问题插值问题( (方法方法) )。2. 2. 几何意义、内插法、外插法几何意义、内插法、外插法内插外插niixM0maxniixm0min,Mmx,Mmxbutbax2 拉格朗日多项式拉格朗日多项式 /* Lagrange Polynomial */niyxPiin,., 0,)( 求求 n 次多项式次多项式 使得使得nnnxaxaaxP 10)(条件:无重合节点,即条件:无重合节点,即jixx ji l0(x)l1(x)2 Lagrange Polynomial多项式插值是数值分析的基本工具,常用来计算被插函数多
3、项式插值是数值分析的基本工具,常用来计算被插函数的近似的近似函数值函数值,零、极点零、极点,导数、积分导数、积分(第四章(第四章 数值积数值积分和数值微分),分和数值微分),解微分方程解微分方程(第五章)、(第五章)、积分方程积分方程x0 x1x2x3x4xPn(x) f(x)解 几何上看,即求几何上看,即求多项式曲线多项式曲线与与被插值函数曲线被插值函数曲线间满足:间满足:特点:插值曲线插值曲线Pn(x)过被插值曲线过被插值曲线f (x)的上给定的的上给定的n+1个点。个点。n = 1已知已知 x0 , x1 ; y0 , y1 ,求,求xaaxP101)( 使得使得111001)(,)(y
4、xPyxP 可见可见 P1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。)()(0010101xxxxyyyxP- - - - 101xxxx- - -010 xxxx- - -= y0 + y1l0(x)l1(x) 10)(iiiyxl称为拉氏基函数称为拉氏基函数 满足条件满足条件 li(xj)= ij 2 Lagrange Polynomial 提问:上面所提的多项式提问:上面所提的多项式Pn(x)是否存在?是否存在? 若存在,是否唯一?如何求?若存在,是否唯一?如何求?证明证明 插值条件插值条件(2.2)(2.2)等价于线性方程组等价于线性
5、方程组200021112111nnnnnnxxxxxxxxx定理定理1 1 满足插值条件满足插值条件(2.2)(2.2)的不超过的不超过n次的插值次的插值多项式多项式唯一存在。唯一存在。0()0jiij nxx -系数行列式(系数行列式(n+1+1阶范德蒙行列式)阶范德蒙行列式)由克莱默法则知,方程组有唯一解由克莱默法则知,方程组有唯一解20102000201121112012nnnnnnnnnnaa xa xa xyaa xa xa xyaa xa xa xy 01,.na aa2-1 插值多项式的存在唯一性插值多项式的存在唯一性 唯一性的另一证明唯一性的另一证明 满足满足 的的 n 阶插阶
6、插值多项式是唯一存在的。值多项式是唯一存在的。niyxPii,., 0,)( 证明证明 ( 前面已利用前面已利用Vandermonde 行列式论证行列式论证)反证:若不唯一,则除了反证:若不唯一,则除了Ln(x) 外还有另一外还有另一 n 阶多项阶多项式式 Pn(x) 满足满足 Pn(xi) = yi 。考察考察 则则 Qn 的阶数的阶数, )()()(xLxPxQnnn- - n而而 Qn 有有 个不同的根个不同的根n + 1x0 xn注:若不将多项式次数限制为注:若不将多项式次数限制为 n ,则插值多项式不唯一。,则插值多项式不唯一。例如例如 也是一个插值也是一个插值多项式,其中多项式,其
7、中 可以是任意多项式。可以是任意多项式。 - - niinxxxpxLxP0)()()()()(xp2 Lagrange PolynomialInterpolation polynomial 2-2 线性插值与抛物插值线性插值与抛物插值 x0 x1(x0 ,y0)(x1 ,y1)P1(x)f (x) 可见可见 P1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。)(001010 xxxxyyyy-直线方程为直线方程为:等价变形为等价变形为:10100101yxxxxyxxxxy-记为记为:)(1xL1. 线性插值线性插值引入记号引入记号:,)(10
8、10 xxxxxl-0101)(xxxxxl-则则:11001)()()(yxlyxlxL分析两个基函数有分析两个基函数有:0)(1)(1000 xlxl1011()0( )1l xl x对于三个点对于三个点,类似有类似有:2211002)()()()(yxlyxlyxlxL称为插值基函数称为插值基函数0)(0)(1)(201000 xlxlxl0)(1)(0)(211101xlxlxl1)(0)(0)(221202xlxlxlx0 x1x2P2(x) f(x)f(x)2. 抛物线抛物线(二次二次)插值插值 将以上思路推广到将以上思路推广到n+1个节点情形,即可得到类似的个节点情形,即可得到类
9、似的插值基函数和插值多项式表示形式。插值基函数和插值多项式表示形式。P2(x)xn 1希望找到希望找到li(x),i = 0, , n 使得使得 li(xj)= ij ;然后令;然后令,则显然有,则显然有Pn(xi) = yi 。li(x)每个每个 li 有有 n 个根个根 x0 xi xn jiC0 - -nj i jxx)(- - - -inxxixxxxC0).().(ixl)( - - j i jxixiC)(1 iixl1)( - - - njijjijixxxxxl0)()()( niiinyxlxL0)()(Lagrange Polynomial与节点有关,而与与节点有关,而与
10、f无关无关 niinxlxP0)()(yi 基函数法(基函数法(n=1情形的推广情形的推广)2 Lagrange Polynomial2-3 Lagrange插值多项式插值多项式 2-4 插值余项插值余项 /* Remainder */设节点设节点)1( nf在在a , b内存在内存在, 考察截断误差考察截断误差)()()(xLxfxRnn- - , baCfn bxxxan 10,且,且 f 满足条件满足条件 ,Rolles Theorem: 若若 充分光滑,充分光滑, ,则,则存在存在 使得使得 。)(x 0)()(10 xx ),(10 xx 0)( 推广:推广:若若0)()()(210
11、 xxx ),(),(211100 xxxx 使得使得0)()(10 ),(10 使得使得0)( 0)()(0 nxx 存在存在),(ba 使得使得0)()( nRn(x) 至少有至少有 个根个根n+1 - - niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 - - - niixtxKtRnt0)()()()( (x)有有 n+2 个不同的根个不同的根 x0 xn x),(, 0)()1(baxxn !)1()()()1(-nxKRxnn 注意这里是对注意这里是对 t 求导求导 - - - !)1)()()()1()1(nxKLfxnnxn
12、!)1()()()1( nfxKxn - - niixnnxxnfxR0)1()(! ) 1()()( 2 Lagrange Polynomial1 Lagrange Polynomial注:注: 通常不能确定通常不能确定 x , 而是估计而是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限。1)1()( nnMxf - - niinxxnM01|)!1(当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时,时, , 可知可知 ,即插值多项式对于次数,即插值多项式对于次数 n 的的多项多项式是式是精确精确的。的。0)()1( xfn0)( xRnQuiz: 给定给
13、定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是下面哪个是 l2(x)的图像?的图像? y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x ABC 1 Lagrange Polynomial例:例:已知已知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解:解:0 x1x2x185500
14、 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)()(,23sin21)2(1 - - - xxfxRxx00762. 0)185(01319. 01- - - - Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的实际误差的实际误差 - -0.010010.010013,421 xx利用利用sin
15、50 0.76008, 00660. 018500538. 01 R内插内插 /* interpolation */ 的实际误差的实际误差 0.005960.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点,插值效果较好。端点,插值效果较好。1 Lagrange Polynomialn = 223)()(21)()(21)()()(4363463464363646342 - - - - - - - - - - - - - - - xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2
16、- - - - - xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.000610.00061高次插值通常优于高次插值通常优于低次插值低次插值但绝对不是次数越但绝对不是次数越高就越好,嘿高就越好,嘿嘿嘿 When you start writing the program, you will find how easy it is to calculate the Lagrange polynomial.Oh yeah? What if I find the current interpolation not
17、 accurate enough? Then you might want to take more interpolating points into account.Right. Then all the Lagrange basis, li(x), will have to be re-calculated. Excellent point !We will come to discuss this problemnext time.1 Lagrange Polynomial练习:练习: 设设f(x)=x4,利用利用 Lagrange 插值写出以插值写出以-1,0,1,2为节点为节点 的
18、插值多项式。的插值多项式。 练习:练习:已知插值节点满足已知插值节点满足xi-xi-1=h,i=1,2,3, 证明三次插值证明三次插值多项式多项式L3(x)与被插函数与被插函数f(x)的差有如下关系:的差有如下关系:03034431max |( )( )|max |( )|24xx xxx xf xL xhfx -1 Lagrange Polynomial练习:练习:证明证明0010(1)( ),0,1,2,(2)()( )0,0,1,2,(3) ( )n+1( )() ( )()nkkiiinkiiinniiiiix l xxknxxl xknp xp xp x l xxx-是任一最高次项系
19、数为1的次多项式,则Interpolation_introduction问题的提出:问题的提出: 如果需要增加精度,一般采用增加插值节点来实如果需要增加精度,一般采用增加插值节点来实现。但是由于插值基函数的性质,使得计算新的插值现。但是由于插值基函数的性质,使得计算新的插值多项式时,原来的计算量不能很好地利用,造成计算多项式时,原来的计算量不能很好地利用,造成计算的浪费,为了克服这一缺点,我们将要介绍下面的逐的浪费,为了克服这一缺点,我们将要介绍下面的逐步线性插值和步线性插值和Newton插值。插值。3 逐次线性插值逐次线性插值 /* Lagrange Polynomial */3 逐次线性插
20、值法逐次线性插值法 /* Lagrange Polynomial */ 0,1010011100,100100,202200,200200,20,10,1 20,1121:1Lagrange,;:1LagrangeIxx xxf xx f xf xf xIxf xxxxxIxx xf xf xIxf xxxxxIxIxIxIxxxxx-,以 ,为节点的 次插值公式,实际上是过,点的直线,采用点斜式以 ,为节点的 次插值公式,同理有仿上,令易证 0,200,100,1 200,10010,100210,210,110,1 210,11110,111210,220,120,1 220,12210,
21、222210,1 20122IxIxIxIxxxIxf xxxIxIxIxIxxxIxf xxxIxIxIxIxxxIxf xxxIxx x x-,由插值公式的唯一性知,是以 ,, 为节点的 次Lagrange插值多项式。以此 0,12,0,110,10,111101kkkkkkkkkIxIxIxIxxxxxx xxk-,类推,是以 ,, , 为节点的 次Lagrange插值多项式。 10,10,110,12,11kkkkkkkkkkx xx xIxIxIxxxxx-,实际上实际上,是对两个低次插值的线性插值,这种通过低次插值再作是对两个低次插值的线性插值,这种通过低次插值再作线性插值生成高次
22、插值的方法称为线性插值生成高次插值的方法称为逐次线性插值逐次线性插值。 Aitken法法(按下表计算按下表计算) 0,12,0,110,10,1111kkkkkkkkIxIxIxIxxxxx-,线性插值基函数线性插值基函数 0,0,1,0,1,2,0,1,2,3,00110,10220,20,1,2 kkkkkkxf xIxIxIxIxxf xxf xIxx xxf xIxIx- 1330,30,1,30,1,2,32440,40,1,40,1,2,40,1,2,3,43 x xxf xIxIxIxx xxf xIxIxIxIxx x-0123 x xx xx xx x-增加增加如果精度不够,
23、增加节点如果精度不够,增加节点x4, ,同时表中增加一行,三同时表中增加一行,三角形斜边上即为所要求的各次插值多项式。角形斜边上即为所要求的各次插值多项式。k1k0k2k3k4 Neville法法(按下表计算按下表计算) 1,1, ,11, ,11, ,1,200110,10221,20,1,2 kkkkkk kkk kkk kkxf xIxIxIxIxxf xxf xIxx xxf xIxIx- 0332,31,2,30,1,2,30443,42,3,40,1,2,40,1 x xxf xIxIxIxx xxf xIxIxIxI- ,2,3,401111 kkkkxx xx xx xx xx
24、 x-增加增加如果精度不够,增加节点如果精度不够,增加节点x4, ,同时表中增加一行,三角形斜边上同时表中增加一行,三角形斜边上即为所要求的各次插值多项式。即为所要求的各次插值多项式。k1k0k1k1k1 11,0,110,10,1100kkkkkkIxIxIxIxxxxx-,HW: 用类似于前面的方法用类似于前面的方法构造构造Neville计算公式计算公式注:注:Atkin方法和方法和Neville方法与方法与Lagrange公式相比,当公式相比,当需要增加节点时,很容易由低次插值构造高次插值,而需要增加节点时,很容易由低次插值构造高次插值,而Lagrange插值公式中,每个基函数都需要作适
25、当变化。插值公式中,每个基函数都需要作适当变化。误差估计:误差估计:由插值多项式的存在唯一性知,仍有由插值多项式的存在唯一性知,仍有 - - niixnnxxnfxR0)1()(! ) 1()()( 但这里可采用一种更简便的方法。当但这里可采用一种更简便的方法。当f (n+1)(x)在插在插值区间变化不大时,设值区间变化不大时,设f (n+1)(x)L,则有则有 0,110-10,12,0-2-!-!kkkkkkLf xIxx xx xkLf xIxx xx xx xk-, 10,110,12,0,1110,12,0,11 if kkkkkkkkkkxxf xIxIxIxxxIxIx-, 0,
展开阅读全文