资源预览内容
第1页 / 共90页
第2页 / 共90页
第3页 / 共90页
第4页 / 共90页
第5页 / 共90页
第6页 / 共90页
第7页 / 共90页
第8页 / 共90页
第9页 / 共90页
第10页 / 共90页
亲,该文档总共90页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第二章第二章 插值法插值法/* Interpolation */Interpolation_introduction1 引引 言言1.1.函数表达式过于复杂不便于计算函数表达式过于复杂不便于计算, , 而又需要计算许而又需要计算许多点处的函数值多点处的函数值2.2.仅有几个采样点处的函数值仅有几个采样点处的函数值, , 而又需要知道非采样而又需要知道非采样点处的函数值点处的函数值 v上述问题的一种上述问题的一种解决思路:解决思路:建立复杂函数或者未建立复杂函数或者未知函数的一个便于计算的近似表达式知函数的一个便于计算的近似表达式. .v解决方法解决方法插值法插值法 1. 1. 插值概念插值概念求求插值函数插值函数 ( (x) )的问题的问题( (方法方法) )称为称为插值问题插值问题( (方法方法) )。2. 2. 几何意义、内插法、外插法几何意义、内插法、外插法内插外插2 拉格朗日多项式拉格朗日多项式 /* Lagrange Polynomial */niyxPiin,., 0,)(= = =求求 n 次多项式次多项式 使使得得条件:无重合节点,即条件:无重合节点,即l0(x)l1(x)2 Lagrange Polynomial多项式插值是数值分析的基本工具,常用来计算被插函数多项式插值是数值分析的基本工具,常用来计算被插函数的近似的近似函数值函数值,零、极点零、极点,导数、积分导数、积分(第四章(第四章 数值积数值积分和数值微分),分和数值微分),解微分方程解微分方程(第五章)、(第五章)、积分方程积分方程x0 x1x2x3x4xPn(x) f(x)解 几何上看,即求几何上看,即求多项式曲线多项式曲线与与被插值函数曲线被插值函数曲线间满足:间满足:特点:插值曲线插值曲线Pn(x)过被插值曲线过被插值曲线f (x)的上给定的的上给定的n+1个点。个点。n = 1已知已知 x0 , x1 ; y0 , y1 ,求求使得使得111001)(,)(yxPyxP= = =可见可见 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)等价于线性方程组等价于线性方程组定理定理1 1 满足插值条件满足插值条件(2.2)(2.2)的的不超过不超过n次的插值次的插值多项式多项式唯一存在。唯一存在。系数行列式(系数行列式(n+1+1阶范德蒙行列式)阶范德蒙行列式)由克莱默法则知,方程组有唯一解由克莱默法则知,方程组有唯一解2-1 插值多项式的存在唯一性插值多项式的存在唯一性 唯一性的另一证明唯一性的另一证明 满足满足 的的 n 阶阶插值多项式是唯一存在的。插值多项式是唯一存在的。证明证明 ( 前面已利用前面已利用Vandermonde 行列式论证行列式论证)反证:若不唯一,则除了反证:若不唯一,则除了Ln(x) 外还有另一外还有另一 n 阶多阶多项式项式 Pn(x) 满足满足 Pn(xi) = yi 。考察考察 则则 Qn 的阶的阶数数 n而而 Qn 有有 个不同的根个不同的根n + 1x0 xn注:若不将多项式次数限制为注:若不将多项式次数限制为 n ,则插值多项式不唯一。则插值多项式不唯一。例如例如 也是一个插也是一个插值多项式,其中值多项式,其中 可以是任意多项式。可以是任意多项式。2 Lagrange PolynomialInterpolation polynomial 2-2 线性插值与抛物插值线性插值与抛物插值 x0 x1(x0 ,y0)(x1 ,y1)P1(x)f (x) 可见可见 P1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。直线直线方程为方程为:等价变形为等价变形为:记为记为:1. 线性插值线性插值引入记号引入记号:则则:分析两个基函数有分析两个基函数有:对于三个点对于三个点,类似有类似有:称为插值基函数称为插值基函数x0 x1x2P2(x) f(x)f(x)2. 抛物线抛物线(二次二次)插值插值 将以上思路推广到将以上思路推广到n+1个节点情形,即可得到类似的个节点情形,即可得到类似的插值基函数和插值多项式表示形式。插值基函数和插值多项式表示形式。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)(Lagrange Polynomial与节点有关,而与与节点有关,而与 f无关无关 = = =niinxlxP0)()(yi 基函数法(基函数法(n=1情形的推广情形的推广)2 Lagrange Polynomial2-3 Lagrange插值多项式插值多项式 2-4 插插值余值余项项 /* Remainder */设节点设节点在在a , b内存在内存在, 考察截断误差考察截断误差,且,且 f 满足条件满足条件 ,Rolles Theorem: 若若 充分光滑,充分光滑, ,则,则存在存在 使得使得 。推广:推广:若若使得使得使得使得存在存在使得使得Rn(x) 至少有至少有 个根个根n+1 = = = =niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 = = = =niixtxKtRnt0)()()()( (x)有有 n+2 个不同的根个不同的根 x0 xn x!)1()()()1(+-+nxKRxnn 注意这里是对注意这里是对 t 求导求导= =+ + + + +!)1)()()()1()1(nxKLfxnnxn !)1()()()1(+ += =+ +nfxKxn 2 Lagrange Polynomial1 Lagrange Polynomial注:注: 通常不能确定通常不能确定 x , 而是估计而是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限。当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时,时, , 可知可知 ,即插值多项式对于次数,即插值多项式对于次数 n 的的多多项式是项式是精确精确的。的。Quiz: 给定给定 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例:例:已知已知分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解:解:n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算利用利用这里这里而而sin 50 = 0.7660444)185(50sin10 p pL0.77614外外推推 /* extrapolation */ 的实际误差的实际误差 0.010010.01001利用利用sin 50 0.76008, 内插内插 /* interpolation */ 的实际误差的实际误差 0.005960.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点,插值效果较好。端点,插值效果较好。1 Lagrange Polynomialn = 2)185(50sin20 p pL0.76543sin 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 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为节点为节点 的插值多项式。的插值多项式。 练习:练习:已知插值节点满足已知插值节点满足xi-xi-1=h,i=1,2,3, 证明三次插值证明三次插值多项式多项式L3(x)与被插函数与被插函数f(x)的差有如下关系:的差有如下关系:1 Lagrange Polynomial练习:练习:证明证明Interpolation_introduction问题的提出:问题的提出: 如果需要增加精度,一般采用增加插值节点来实如果需要增加精度,一般采用增加插值节点来实现。但是由于插值基函数的性质,使得计算新的插值现。但是由于插值基函数的性质,使得计算新的插值多项式时,原来的计算量不能很好地利用,造成计算多项式时,原来的计算量不能很好地利用,造成计算的浪费,为了克服这一缺点,我们将要介绍下面的逐的浪费,为了克服这一缺点,我们将要介绍下面的逐步线性插值和步线性插值和Newton插值。插值。3 逐次线性插值逐次线性插值 /* Lagrange Polynomial */3 逐次线性插值法逐次线性插值法 /* Lagrange Polynomial */实际上实际上,是对两个低次插值的线性插值,这种通过低次插值再作是对两个低次插值的线性插值,这种通过低次插值再作线性插值生成高次插值的方法称为线性插值生成高次插值的方法称为逐次线性插值逐次线性插值。 Aitken法法(按下表计算按下表计算)线性插值基函数线性插值基函数增加增加如果精度不够,增加节点如果精度不够,增加节点x4, ,同时表中增加一行,三角同时表中增加一行,三角形斜边上即为所要求的各次插值多项式。形斜边上即为所要求的各次插值多项式。k1k0k2k3k4 Neville法法(按下表计算按下表计算)增加增加如果精度不够,增加节点如果精度不够,增加节点x4, ,同时表中增加一行,三角形斜边上同时表中增加一行,三角形斜边上即为所要求的各次插值多项式。即为所要求的各次插值多项式。k1k0k1k1k1HW: 用用类似于前面的方法类似于前面的方法构造构造Neville计算公式计算公式注:注:Atkin方法和方法和Neville方法与方法与Lagrange公式相比,当公式相比,当需要增加节点时,很容易由低次插值构造高次插值,而需要增加节点时,很容易由低次插值构造高次插值,而Lagrange插值公式中,每个基函
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号