拉格朗日插值和逐次线性插值课件

2.5 Hermite插值多项式插值多项式2.4 Newton插值多项式插值多项式2.3 逐次线性插值法逐次线性插值法2.2 Lagrange插值多项式插值多项式2.1 引言与问题引言与问题特例特例第二章第二章 插值法插值法2.6 分段低次插值分段低次插值2.7 三次样条插值三次样条插值2.1 引言与问题引言与问题特例特例例例2.1例例2.2问题问题插值插值-定义定义2.12.2 Lagrange插值多项式插值多项式例例2.1 在统计中会遇到概率积分在统计中会遇到概率积分的计算。为便于应用，有概率积分表的计算。为便于应用，有概率积分表2-1x0.5200.5210.5220.524f(x)0.537 900.538 760.539 620.540 48求求 f(0.52136)或或f(0.52218).(数据表中没有）。数据表中没有）。解法：解法：用插值法求。用插值法求。2.1 引言与问题引言与问题特例特例例例2.2 由化学实验得到某种物质浓度由化学实验得到某种物质浓度yi与时间与时间ti的的关系如表关系如表2-2.ti0.0 0.51.01.52.0yi0.0 0.190.260.290.31求其它时间的物质浓度。求其它时间的物质浓度。解法：解法：建立时间与物质浓度的简单数学模型，建立时间与物质浓度的简单数学模型，或或用插值法用插值法。求求y=f(x)在在 a,b 上的近似曲线？上的近似曲线？问题：问题：基于未知函数或复杂函数的某些已知信息，基于未知函数或复杂函数的某些已知信息，如何构造这些函数的近似表达式如何构造这些函数的近似表达式?x0 x1x2x3x4 xf(x)(x)曲线曲线 (x)近似近似 f(x)从代数上看，看从代数上看，看 (x)满足以下代数条件满足以下代数条件 (xi)=yi i =0,1,2,n这就是所谓的插值这就是所谓的插值然后计算然后计算 (x)在在a,b 上其它点上其它点x 处的函数值作处的函数值作为原来函数为原来函数 f(x)在此点函数值的近似值。在此点函数值的近似值。代数多项式、三角多项式、有理函数或样条函数代数多项式、三角多项式、有理函数或样条函数(2.1)式称为式称为插值条件插值条件，x2 xn b 点上的值点上的值 y0,y1,yn.若存在一简单若存在一简单 函数函数 (x),使得使得 (xi)=yi i =0,1,2,n (2.1)定义定义2.1f(x)称为称为被插值函数被插值函数，a,b 称为称为插值区间插值区间，称为称为插值节点插值节点，求求 (x)的方法就是的方法就是插值法插值法。设函数设函数 f(x)在在a,b上有定义，且已知在上有定义，且已知在 a x0 x1成立成立,则称则称 (x)为为 f(x)的的插值函数插值函数。近似计算近似计算 f(x)的值、零点、极的值、零点、极值点、导数、积分，值点、导数、积分，插值点在插值区间内的称为插值点在插值区间内的称为内插内插,否则称否则称外插外插.x0 x1x2x3x4f(x)(x)曲线曲线 (x)近似近似 f(x)研究问题：研究问题：（1）满足插值条件的）满足插值条件的 (x)是否是否存在唯一存在唯一？（2）若满足插值条件的）若满足插值条件的 (x)存在，存在，如何构造如何构造(x)？（3）如何如何估计估计用用 (x)近似替代近似替代 f(x)产生的产生的误差误差？2.2 Lagrange2.2 Lagrange插值多项式插值多项式2.2.1 2.2.1 多项式插值问题多项式插值问题2.2.2 2.2.2 LagrangeLagrange插值插值2.2.3 Lagrange2.2.3 Lagrange插值余项插值余项问题插值多项式的存在唯一性问题插值多项式的存在唯一性定理定理2.1 线性（一次）插值线性（一次）插值例例2.3 n次次Lagrange 插值多项式插值多项式n=2n=1n=2例例2.2*Lagrange插值多项式的另一种形式插值多项式的另一种形式定理定理2.2定理定理2.3 Lagrange插值算法实现插值算法实现练习练习1-32.3 逐次线性插值法逐次线性插值法例例2.4算例算例1-22.2 Lagrange2.2 Lagrange插值多项式插值多项式2.2.1 2.2.1 多项式插值问题多项式插值问题用代数多项式作为插值函数的插值法称为用代数多项式作为插值函数的插值法称为多项式插值法。多项式插值法。可设可设 (x)=a0 +a1 x+a2x 2+ai x i+,问题：问题：插值多项式插值多项式 (x)是几次多项式？系数是几次多项式？系数ai=？插值多项式插值多项式 (x)唯一吗？唯一吗？可设可设 (x)=a0 +a1 x+an x n要求插值多项式要求插值多项式 (x)，可以通过求，可以通过求n+1个方程的解个方程的解:得到。但这样做不但计算复杂，得到。但这样做不但计算复杂，而且难于得到而且难于得到 n(x)的简单表达式。的简单表达式。确定多项式确定多项式 (x)的次数的次数方法：待定系数法方法：待定系数法结论：结论：n+1个插值节点产生的插值多项式的次数不个插值节点产生的插值多项式的次数不超过超过n次次问题插值多项式的存在唯一性问题插值多项式的存在唯一性 设设 n(x)是是 f(x)的插值多项式，的插值多项式，Hn表示次数不超过表示次数不超过n 的所有多项的所有多项且且 n(x)Hn.称插值多项式存在且唯一，就是指在称插值多项式存在且唯一，就是指在由由(2.1)可得可得(2.2)方程组方程组(2.2)有唯一解有唯一解插值多项式的唯一性插值多项式的唯一性0(xixj)定理定理2.1 满足条件满足条件(2.1)的插值多项式存在且唯一。的插值多项式存在且唯一。范德蒙行列式范德蒙行列式a0,a1,a2,an存在唯一存在唯一(xi)=yi i =0,1,2,nHn 中有且仅有一个中有且仅有一个 n(x)满足插值条件满足插值条件(2.1)式。式。式的集合。式的集合。n+1个节点互异当当n=1n=1时，要构造通过两点时，要构造通过两点(x0,y0 )和和(x1,y1)的不超过的不超过1 1次的多项式次的多项式 1(x)(后面记后面记作作L1(x)，使得，使得2.2.2Lagrange插值插值y 0 x y=f(x)y=L1(x)x0 x1 y 0 x y=f(x)y=L1(x)x0 x1 称为线性（一次）插值称为线性（一次）插值（两点式）（两点式）（点斜式）（点斜式）或或L1(x)是两个线性函数是两个线性函数的线性组合的线性组合称为节点称为节点x0 0,x1 1上上线性插值基函数线性插值基函数-线性线性Lagrange插值多项式形式插值多项式形式(2.3)y10 x0 x1 x l0(x)l1(x)节点上的节点上的线性线性 插值基函数：插值基函数：满足满足 y10 x0 x1 xx0 x1l0(x)10l1(x)01例例2.32.3 已知已知 ,解解:这里这里x0 0=100=100，y0 0=10=10，x1 1=121=121，y1 1=11,=11,利用线利用线性插值性插值 利用线性插值利用线性插值求求 先求先求 插值基函数插值基函数 l 0(x),l1(x),l 2(x),它们满足它们满足 (1)都是二次函数；都是二次函数；(2)在节点满足在节点满足x0 x1x2l0(x)100l1(x)010l2(x)001y 1 0 xy 1 0 xy 1 0 xx0 x1 x2 先求先求 l0(x):待定系数待定系数x0 x1 x2x0 x1 x2 由由l0(x)满足的两个条件满足的两个条件类似地类似地,可得可得知知l0(x)中含有两个因子中含有两个因子(x-x1)(x-x2)，且是二次的，且是二次的再由再由l0(x)满足的条件满足的条件即得即得所以有所以有 L2(x)=y0 l0 0(x)+y1 l1(x)+y2 l2(x)例例2.2*已知已知 ,解解:这里这里x0 0=100=100，y0 0=10=10，x1 1=121=121，y1 1=11,=11,x2 2=144=144，y2 2=12=12，利用抛物线插值公式利用抛物线插值公式 利用抛物线插值利用抛物线插值求求n次次Lagrange 插值多项式插值多项式求通过求通过n+1个节点的个节点的n 次插值多项式次插值多项式Ln(x)：先求插值基函数先求插值基函数然后构造插值多项式然后构造插值多项式设设Ln(x)=满足插值条件：满足插值条件：L n(xj)=y j ,j=0,1,n定义定义2.2 若若n 次多项式次多项式 lk(x)(k=0,1,n)在各节点在各节点i,k=0,1,n (2.4)上满足条件上满足条件 则称这则称这n +1个个n 次多项式为这次多项式为这n+1个节点上的个节点上的n 次插次插值基函数值基函数。先求先求 插值基函数插值基函数，k=0,1,n.k=0,1,n.L2(x)=y0 l0(x)+y1 l1(x)+y2 l2(x)（类似于前面讨论（类似于前面讨论n n=1,2 =1,2 时的情形）时的情形）(2.5)再构造再构造插值多项式插值多项式（Ln(x)是是n+1个插值基函数的线性组合）个插值基函数的线性组合）定理定理2.2（Lagrange）插值多项式插值多项式通常次数通常次数=n,但特殊情形次数可但特殊情形次数可 x=0.4，0.5,0.7，0.8;y=-0.916291,-0.693147,-0.356675,-0.223144;lagrange(x,y,0.6)ans=-0.509 975 （精确解-0.510 826)算例算例2给出函数为给出函数为f(x)=1/(1+x2)，它在区间，它在区间-5，5上各导数上各导数存在，但是在此区间上取存在，但是在此区间上取n个节点构造的个节点构造的Lagrange插值多项插值多项式在全区间内并非都收敛的，而且分散得很厉害式在全区间内并非都收敛的，而且分散得很厉害。x=-5:1:5;y=1./(1+x.2);x0=-5:0.1:5;y0=lagrange(x,y,x0);y1=1./(1+x0.2);绘制图形 plot(x0,y0,-r)插值曲线 hold on plot(x0,y1,-b)原曲线v为解决Rung问题，引入分段插值。LagrangeLagrange插值插值采用插值基函数的线性组采用插值基函数的线性组合来构造插值多项式合来构造插值多项式含义直观含义直观形式对称形式对称优点：优点：缺点：缺点：计算量大计算量大求二次插值多项式。求二次插值多项式。解解 按按Lagrange方法，有：方法，有：练习练习1 练习练习2 给定数据表给定数据表 xi 0 1 2 3 yi 0 1 5 14求三次求三次Lagrange插值多项式插值多项式L3(x).练习练习3 要制作三角函数要制作三角函数sin sin x的值表，已知表值有四位小数，的值表，已知表值有四位小数，要求用线性插值引起的截断误差不超过要求用线性插值引起的截断误差不超过表值的舍入误差表值的舍入误差，试，试确定其最大允许的步长。确定其最大允许的步长。解解 f(x)=sin x,设设xi,xi为任意两个插值节点，最大允许步为任意两个插值节点，最大允许步长记为长记为 h=hi=xi xi，2.3 逐次线性插值法逐次线性插值法 在许多情况下，当函数的高阶导数未知时，直接用插值余项公式在许多情况下，当函数的高阶导数未知时，直接用插值余项公式（2.102.10）来估计误差是困难的。下面以线性插值为例，介绍另一种估计误）来估计误差是困难的。下面以线性插值为例，介绍另一种估计误差的方法。差的方法。此两式分别给出了此两式分别给出了L1(x)和和L1(x）作近作近似计算时的实用误似计算时的实用误差估计式。而不需差估计式。而不需要计算高阶导数，要计算高阶导数，也不用顾忌插值区也不用顾忌插值区间上高阶导数的界。间上高阶导数的界。已知已知 f(0)=2，f(1)=3,f(2)=12利用利用Lagrange插值计算未知函数插值计算未知函数y=f(x)在在x=1.2078处处的函数值的函数值f(1.2078)，并估计误差，并估计误差.解：在区间解：在区间0,1上的上的1次次Lagrange插值多项式为插值多项式为在区间在区间1,2上的上的1次次Lagrange插值多项式为插值多项式为例例2.5而而x=1.20781,2 基于以上分析，为更好的近似计算基于以上分析，为更好的近似计算f(x*)，可以，可以考虑把考虑把 ，即，即 2次的次的 上面的例题可以克服这一缺点，即使用逐次上面的例题可以克服这一缺点，即使用逐次线性插值方法求得高次插值。线性插值方法求得高次插值。2.2.3Aitken 逐次线性插值法逐次线性插值法计算时应尽量多地利用靠近计算时应尽量多地利用靠近x的节点信息，即先对所有节点重的节点信息，即先对所有节点重新排序，与新排序，与x接近的点排在前面，接下来计算接近的点排在前面，接下来计算f(x)的近似值。的近似值。计算过程如下计算过程如下 从表上看每增加一个节点就计算一行，斜线上是从表上看每增加一个节点就计算一行，斜线上是1 1次到次到4 4次插值多项式的值，如精度不满足要求，再增加一个节点，次插值多项式的值，如精度不满足要求，再增加一个节点，前面计算完全有效，这个算法适用于计算机上计算，且具有前面计算完全有效，这个算法适用于计算机上计算，且具有自动选节点并逐步比较精度的特点，程序也比较简单。算例自动选节点并逐步比较精度的特点，程序也比较简单。算例见教材见教材(略）。略）。下面介绍的牛顿插值多项式就克服了这个缺点。它能下面介绍的牛顿插值多项式就克服了这个缺点。它能根据插值条件构造一个插值多项式，它既有具体的表达根据插值条件构造一个插值多项式，它既有具体的表达式，又很容易用它计算任何点的函数值。式，又很容易用它计算任何点的函数值。逐次线性插值法的优点是能够最有效地计算逐次线性插值法的优点是能够最有效地计算任何给定点任何给定点的函数值，而不需要写出各步用到的插值多项式的表达式。的函数值，而不需要写出各步用到的插值多项式的表达式。但如果解决某个问题是但如果解决某个问题是需要插值多项式的表达式需要插值多项式的表达式，那么，那么，它的这个优点就成了它的缺点了。它的这个优点就成了它的缺点了。由插值多项式存在唯一性的定理说明，满足插值条由插值多项式存在唯一性的定理说明，满足插值条件的多项式存在，并且插值多项式与构造方法无关。然而，件的多项式存在，并且插值多项式与构造方法无关。然而，直接求解方程组直接求解方程组(1.3)(1.3)的方法，不但计算复杂，而且难于的方法，不但计算复杂，而且难于得得到到p(x)的简单表达式。类似于的简单表达式。类似于LagrangeLagrange插值，我们还可插值，我们还可以给出不同形式的便于使用的其它插值多项式。以给出不同形式的便于使用的其它插值多项式。基本思想基本思想：在：在n n次多项式空间次多项式空间Pn中找一组合适的中找一组合适的基函数基函数 0 0(x),),1 1(x),),n n(x),),使使pn(x)=b0 0(x)+b1 1(x)+bn n(x)(bi 为常数为常数)不同的基函数的选取导致不同的不同的基函数的选取导致不同的插值方法插值方法Lagrange插值插值Newton插值插值