第1节课第一章插值法拉格朗日插值分段插值

第一章插值方法李书杰合肥工业大学计算机学院提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值插值的基本概念例.某地区某年夏季时节间隔30天的日出日落时间为5月1日5月31日6月30日日出5：515：175：10日落19：0419：3819：50任意一天的日照时间？日照时间的变化设为y(x)=a0+a1x+a2x2,6614616135143131211322102210210.)(.)(.aaaaaaaaa求出a0，a1，a2，即可得到5、6月份的日照时间的变化规律。根据三组数据:(1,13.21)，(31,14.35)，(61,14.66)导出关于a0，a1，a2的线性方程组什么是插值?插值法是函数逼近的一种简单但又十分重要的方法，实际中，f(x)是复杂多样的，通常只能观测到一些离散数据；或者f(x)过于复杂而难以运算。这时我们要用近似函数φ(x)来逼近f(x)。自然地，希望φ(x)通过所有的离散点x3x4xφ(x)f(x)x0x1x2定义1:函数y=f(x)给出一组函数值nixfyii,,1,0),(x:x0x1x2……xny:y0y1y2……yn其中x0,x1,x2,…,xn是区间[a,b]上的互异点,要在函数类Φ中求一个简单的函数φ(x)作为f(x)的近似表达式。使满足niyxii,,1,0,)((插值原则、插值条件)这类问题称为插值问题。)(x-----f(x)的插值函数;f(x)-----被插值函数;x0,x1,x2,…,xn-----插值节点;求插值函数的方法称为插值法。若x∈[a,b],需要计算f(x)的近似值φ(x),则称x为插值点。函数类Φ-----插值函数类;一、定义：当选择代数多项式作为插值函数类时，称为代数多项式插值问题:代数多项式插值问题:设函数y=f(x)在[a,b]有定义,且已知在n+1个点a≤x0x1……xn≤b上的函数值y0,y1,……,yn.,要求一个次数不高于n的多项式nnnxaxaxaaxP2210)(使满足插值原则niyxPiin,,1,0,)(称Pn(x)为f(x)的n次插值多项式。这样的插值多项式是否存在、唯一？设Pn(x)=a0+a1x+a2x2+……+anxn是y=f(x)在[a,b]上的n+1个互异节点x0,x1,…,xn的插值多项式，则求Pn(x)问题归结为求系数a0,a1,…,an。nnnnnnnnnyxaxaayxaxaayxaxaa101111000010定理n次插值问题的解是存在而且唯一的。证明：由插值条件：Pn(xk)=yk(k=0,1,…,n)得关于a0,a1,…,an的n+1阶线性方程组故Pn(x)存在且唯一。njinjinnnnnnnxxxxxxxxxxxxxxV121211020010)(111),,()(jixxji因故上式不为0。据Cramer法则，方程组解存在且唯一。是Vandermonde行列式.其系数行列式提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值拉格朗日插值线性插值抛物插值一般情形给定插值节点x0,x1，y0=f(x0)，y1=f(x1).求线性插值多项式L1(x)=a0+a1x，使满足:L1(x0)=y0,L1(x1)=y1.线性插值y=L1(x)的几何意义就是过点(x0,y0)，(x1,y1)的直线。)()(0010101xxxxyyyxL001110101yxxxxyxxxxxL)(L1(x)的表达式：点斜式:变换可得:可以看到，L1(x)是由两个线性函数01010110xxxxxlxxxxxl)(,)(11001)()()(yxlyxlxL的线性组合得到，其系数分别为y0，y1。即kjkjxljk01)(l0(x)及l1(x)在节点x0,x1上满足条件：l0(x0)=1,l0(x1)=0.l1(x0)=0,l1(x1)=1.称l0(x)及l1(x)为线性插值基函数。(j,k=0,1)即n=1时的一次基函数为:0x1xy1Ox)(0xly10x1x)(1xlOx.)(,)(01011010xxxxxlxxxxxl抛物插值假定插值节点为x0,x1,x2，求二次插值多项式L2(x)，使L2(xj)=yj(j=0,1,2)y=L2(x)的几何意义就是过(x0,y0)，(x1,y1)，(x2,y2)三点的抛物线。采用基函数方法，设L2(x)=l0(x)y0+l1(x)y1+l2(x)y2此时基函数l0(x),l1(x),l2(x)是二次函数.l0(x0)=1,l0(x1)=0,l0(x2)=0.l1(x0)=0,l1(x1)=1,l1(x2)=0.l2(x0)=0,l2(x1)=0,l2(x2)=1.基函数l0(x),l1(x),l2(x)在节点上满足：满足上式的插值基函数很容易求出。kjkjxljk01)(即(j,k=0,1,2)))((12010xxxxC))(())(()(2010210xxxxxxxxxl故其中C为待定系数，由l0(x0)=1,得如求l0(x):因x1,x2为其零点，故可表为))(()(210xxxxCxl))(())(()(2101201xxxxxxxxxl同理显然L2(x)=l0(x)y0+l1(x)y1+l2(x)y2满足条件L2(xj)=yj(j=0,1,2)))(())(()(1202102xxxxxxxxxl2120210121012002010212yxxxxxxxxyxxxxxxxxyxxxxxxxxxL))(())(())(())(())(())(()(将l0(x),l1(x),l2(x)代入得1200102()()(),()()xxxxlxxxxxn=2时的二次基函数为:0211012()()(),()()xxxxlxxxxx0122021()()().()()xxxxlxxxxx设有n+1个互异节点x0x1…xn，且yi=f(xi)(i=0,1,2…,n)构造Ln(x)，使Ln(xj)=yj(j=0,1,2,…,n)kjkjxljk01)(一般情形定义若n次多项式lj(x)(j=0,1,…,n)在n+1个节点x0x1…xn上满足条件(j,k=0,1,…,n)则称这n+1个n次多项式l0(x),l1(x),…,ln(x)为节点x0,x1,…,xn上的n次插值基函数。由条件lk(xj)=0(j≠k)知x0,x1,…,xk-1,xk+1…,xn都是n次多项式lk(x)的零点，故可设lk(x)=Ak(x-x0)(x-x1)…(x-xk-1)(x-xk+1)…(x-xn)其中Ak为待定系数。再由lk(xk)=1有1=Ak(xk-x0)(xk-x1)…(xk-xk-1)(xk-xk+1)…(xk-xn)由x0,x1,…,xk-1,xk+1…,xn互异，解出Ak0111()()()()kkkkkkknAxxxxxxxx从而得Lxlxylxylxynnn()()()()0011nkiiikikxxxxxl0)()()()())(()()())(()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl(k=0,1,2,…,n)或记为(k=0,1,2,…n)次数不高于n的多项式在x0,x1,…,xn上的值分别为y0,y1,…,ynn次插值基函数Lxlxylxylxynnn()()()()0011)())(()()())(()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl(k=0,1,2,…,n)Lagrange插值多项式n=1时,线性插值n=2时,二次插值或抛物插值11001)()()(yxlyxlxL2001122()()()()Lxlxylxylxy取x0=4,y0=2，x1=9,y1=3，x2=16,y2=4.416,39,24734942949)(1xxxL6251347537952771.)()()(L例1已知求解（1）线性插值：取x0=4,x1=94)916)(416()97)(47(3)169)(49()167)(47(2)164)(94()167)(97()7(72L6286.2)6458.27(取x0=4,x1=9,x2=16（2）抛物插值：4,3,1,13210xxxx)4)(3)(1(401)41)(31)(11()4)(3)(1()(0xxxxxxxl)4)(3)(1(121)41)(31)(11()4)(3)(1()(1xxxxxxxl)4)(1)(1(81)43)(13)(13()4)(1)(1()(2xxxxxxxl)3)(1)(1(151)34)(14)(14()3)(1)(1()(3xxxxxxxl例2求过点(-1,-2),(1,0),(3,-6),(4,3)的三次插值多项式解以以为节点的基函数分别为:)()()()()(332211003xlyxlyxlyxlyxL)3)(1)(1(1513)4)(1)(1(81)6()4)(3)(1(1210)4)(3)(1(401)2(xxxxxxxxxxxx)3)(1)(1(51)4)(1)(1(43)4)(3)(1(201xxxxxxxxx3423xx()则拉格朗日的三次插值多项式为00110()()()()()nnnniiiLxylxylxylxylx使其满足利用拉格朗日基函数li(x),构造次数不超过n的多项式njyxLjjn,,1,0)()()(xLxPnn称为拉格朗日插值多项式。由插值多项式的唯一性,得特别地,当n=1时又叫线性插值,其几何意义为过两点的直线.当n=2时又叫抛物（线）插值,其几何意义为过三点的抛物线.注意:(1)对于插值节点,只要求它们互异,与大小次序无关;(2)插值基函数li(x)仅由插值节点xi(i=0,1,…,n)确定,与被插函数f(x)无关;(3)插值基函数li(x)的顺序与插值节点xi(i=0,1,…,n)的顺序一致.提纲插值的基本概念拉格朗日插值逐步插值插值余项分段插值逐步插值•拉格朗日插值公式计算函数的近似值若对原先选定的n+1个节点所得结果精度不够，需要增加节点怎么办？•给定区间[a,b]上一组插值节点x0,x1,…,xn,…及对应的函数值y0,y1,…,yn,…把k+1个节点，，…，所确定的不高于k次插值多项式记作，则1）(r=0,1,…,k)2）0ix1ixikx01iiikxP01iiikiriryxP1201(1)0010iiikiiikiikiiikikixxxxxxxPPPxxNeville算法•算法步骤如下表•例如K=0123x0y0=p0(x)x1y0=p1(x)p01(x)x2y0=p2(x)p12(x)p012(x)x3y0=p3(x)p23(x)p123(x)p0123(x)……………23121312331xxxxxxxPPPxxAitken算法•算法步骤如下表•计算公式x0y0=p0(x)X1y0=p1(x)p01(x)X2y0=p2(x)p02(x)p012(x)x3y0=p3(x)p03(x)p013(x)p0123(x)x4