插值与逼近

第三章插值与逼近用简单函数P(x)近似代替函数f(x)是数值计算中的基本概念和方法之一.近似代替又叫逼近,f(x)叫做被逼近函数,P(x)叫做逼近函数,f(x)-P(x)叫做逼近的误差或余项.逼近函数P(x)的类别选取:多项式;分段多项式,有理式，三角多项式等这类便于数值计算的函数类(P(x)选择的函数类不同,逼近的效果也不同.根据实际问题选取恰当的函数类).逼近的度量方式的要求：插值,一致逼近,平方逼近(要求必须提得合理否则无解或许多解),如何构造逼近函数P(x).逼近的效果.插值的概念插值是由离散数据来构造一个函数的近似函数的重要方法,插值要求近似函数与被近似函数在一些点处取相同的函数值,甚至导数值.已知函数y=f(x)在[a,b]中n+1个互异点x0,x1,…,xn上的函数值分别为f(x0),f(x1),…,f(xn)，构造一个简单的函数P(x)，满足条件P(xi)=f(xi)(i=0,1,…n)(*)称这类问题为插值问题，称P(x)为函数f(x)的插值函数，f(x)为被插值函数，点x0,x1,…,xn为插值节点，称(*)为插值条件.§3.1多项式插值Lagrange插值公式Lagrange插值问题已知函数y=f(x)在[a,b]中n+1个互异点x0,x1,…,xn上的函数值分别为f(x0),f(x1),…,f(xn)，在次数n的多项式集合Mn中,构造一个Ln(x)Mn，满足条件Ln(x)=f(xi)(i=0,1,…n)(3.1.1)定理3.1满足插值条件(3.1.1)的多项式Ln(x)Mn是存在且唯一的.首先构造n次多项式li(x)(i=0,1,…n)，满足设li(x)=A(x-x0)(x-x1)…(x-xi-1)(x-xi+1)…(x-xn)由插值条件li(xi)=1得从而jijixlji01)()())(())((11110niiiiiiixxxxxxxxxxA)())(())(()())(())(()(11101110niiiiiiiniiixxxxxxxxxxxxxxxxxxxxxl易知(3.1.2)若还有一个次数n的多项式Pn(x)满足插值条件(3.1.1),则r(x)=Ln(x)-Pn(x)是次数n的多项式，且r(xi)=0,(i=0,1,…n),r(x)有n+1个零点,故必有r(x)0，从而Ln(x)=Pn(x),Lagrange插值问题的解存在且唯一.称li(x)(i=1,2,…n)为Lagrange插值基函数．称(3.1.2)为Lagrange插值多项式．记pn+1(x)=(x-x0)(x-x1)…(x-xn)000()()()()nnnjniiiiijijjixxLxfxlxfxxx101()()()()()nnniiinpxLxfxxxpx线性插值（一次插值）已知函数y=f(x)在两点x0,x1上的函数值分别为f(x0),f(x1),构造一个一次式L1(x)，满足条件:L1(x0)=f(x0)，L1(x1)=f(x1).一次Lagrange插值多项式为L1(x)=f(x0)l0(x)+f(x1)l1(x)其中)()()(1010xxxxxl)()()(0101xxxxxl抛物插值（二次插值）已知函数y=f(x)在三个互异点x0,x1,x2上的函数值分别为f(x0),f(x1),f(x2)，构造一个二次式L2(x)，满足条件:L2(x0)=f(x0),L2(x1)=f(x1),L2(x2)=f(x2)二次Lagrange插值多项式为L２(x)=f(x0)l0(x)+f(x1)l1(x)+f(x2)l2(x)其中))(())(()(2101201xxxxxxxxxl))(())(()(1202102xxxxxxxxxl))(())(()(2010210xxxxxxxxxlLagrange插值多项式的余项定理3.2设Ln(x)是满足插值条件(3.1.1)的n次Lagrange插值多项式，若f(x)Cn[a,b],f(x)在(a,b)内存在n+1阶导数，其中[a,b]是包含点x0,x1,…,xn的一区间，则对任意给定的x[a,b]，总存在一点(a,b)(依赖于x)使(1)01()()()()()()()(1)!nnnExfxLxfxxxxxxn证当x为插值节点x0,x1,…,xn中任一点时，结论显然成立.下面设x异于x0,x1,…,xn，由于E(x)=f(x)-Ln(x)满足E(xi)=0,故可设E(x)=K(x)(x-x0)(x-x1)…(x-xn)，其中K(x)为待定函数.固定x，作辅助函数G(t)=f(t)-Ln(t)-K(x)(t-x0)(t-x1)…(t-xn)显然G(t)在[a,b]上有n+2个零点x,x0,x1,…,xn；利用Rolly定理,知G‘(t)在(a,b)内至少有n+1零点;反复利用Rolly定理:G‘’(t)在(a,b)内至少有n零点;……G(n+1)(t)在(a,b)内至少有1零点;即存在一点(a,b)，使G(n+1)()=0.由于G(n+1)(t)=f(n+1)(t)–(n+1)!K(x)，从而所以(1)()()(1)!nfKxn(1)01()()()()()()()(1)!nnnfExfxLxxxxxxxn线性插值多项式的余项抛物插值多项式的余项Lagrange插值公式为101''()()()()()()2!fExfxLxxxxx2101()()()()max''()8axbxxExfxLxfx(3)1012()()()()()()()3!fExfxLxxxxxxx(1)010()()()()()()()(1)!nniiniffxfxlxxxxxxxn1(1)[,]()()()()max()(1)!nnnxabpxRxfxLxfxnNewton插值公式Newton插值问题已知函数y=f(x)在[a,b]中n+1个互异点x0,x1,…,xn上的函数值分别为f(x0),f(x1),…,f(xn)，构造一个多项式Nn(x)Mn，满足条件Nn(xi)=f(xi)(i=0,1,…n)差商的定义规定f(xi)为f(x)在点xi处的零阶差商.称为函数f(x)在点xi，xj处的一阶差商；称为函数f(x)在点xi，xj，xk处的二阶差商；一般地，称为函数f(x)在点x0,x2,…,xk处的k阶差商.()()[,]jiijjifxfxfxxxx[,][,][,,]ikijijkkjfxxfxxfxxxxx012011011[,,,][,,,][,,]kkkkkkfxxxxfxxxfxxxxx差商表xif(xi)一阶差商二阶差商…n阶差商x0x1x2x3¦xnf(x0)f(x1)f(x2)f(x3)¦f(xn)f[x0,x1]f[x1,x2]f[x2,x3]¦f[xn-1,xn]f[x0,x1,x2]f[x1,x2,x3]¦f[xn-2,xn-1,xn]f[x0,x1,x2,…,xn]差商的性质1.差商关于所含节点是对称的,即与节点位置无关.2.f[x0,x1,…,xn]＝，(a,b)3.n次多项式P(x)的k阶差商P[x0,x1,…,xk-1,x,]当kn时为一个n-k次多项式;当kn时恒为零.!)()(nfn由差均的定义f(x)=f(x0)+f[x0,x](x-x0)f[x0,x]=f[x0,x1]+f[x0,x1,x](x-x1)f[x0,x1,x]=f[x0,x1,x2]+f[x0,x1,x2,x](x-x2)……f[x0,x1,…,xn-1,x]=f[x0,x1,…,xn]+f[x0,x1,…,xn,x](x-xn)反复将后一式代入前一式得f(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+…+f[x0,x1,…,xn](x-x0)(x-x1)…(x-xn-1)+f[x0,x1,…,xn,x](x-x0)(x-x1)…(x-xn)记Nn(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+…+f[x0,x1,…,xn](x-x0)(x-x1)…(x-xn-1)E(x)=f(x)-Nn(x)=f[x0,x1,…,xn,x](x-x0)(x-x1)…(x-xn)E(xi)=０(i=0,1,…n)显然,Nn(x)为次数n的多项式,且满足插值条件Nn(xi)=yi(i=0,1,…n)称Nn(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+…+f[x0,x1,…,xn](x-x0)(x-x1)…(x-xn-1)为Newton插值多项式．E(x)=f(x)-Nn(x)=f[x0,x1,…,xn,x](x-x0)(x-x1)…(x-xn)为Newton插值多项式的余项.由定理１知:相同插值节点的Lagrange插值多项式和Newton插值多项式是同一个多项式,故它们的余项相等，即f[x,x0,x1,…,xn](x-x0)(x-x1)…(x-xn)=从而f[x0,x1,…,xn]＝，(a,b)比较Lagrange插值多项式和Newton插值多项式首项系数得证差商性质1.)())(()!1()(10)1(nnxxxxxxnf!)()(nfn一次Newton插值多项式N1(x)=f(x0)+f[x0,x1](x-x0)二次Newton插值多项式N2(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)Lagrange插值多项式形式对称，易于编程，但无继承性。Newton插值多项式则具有继承性.。例已知y=f(x)的函数表xi012yi8-7.5-18求函数f(x)在[0,2]之间的零点近似值.一般情况下，先求出f(x)在[0,2]上的插值函数P(x)，然后求P(x)的零点，把此零点作为f(x)的近似零点.特别地，若f(x)的反函数存在，记为x=g(y)，那么，求f(x)的零点问题就变成求函数值g(0)的问题了.利用插值法构造出g(y)的插值函数，从而求出f(x)的零点g(0)的近似值，这类问题称为反插值问题.利用反插值时，必须注意反插值条件，即函数y=f(x)必须有反函数.本题yi是严格单调下降排列，可利用反插值法.解将原函数表变成反函数表yi8-7.5-18xi012由此反函数表构造y=f(x)的反函数x=g(y)的二次Lagrange插值多项式.函数y=f(x)的近似零点为0201122012010210122021()()()()()()()()()()()()()yyyyyyyyyyyyLyxxxyyyyyyyyyyyy2(07.5)(018)(08)(018)(08)(07.5)(0)012(87.5)(818)(7.58)(7.518)(188)(187.5)0.445232L例已知x=0,2,3,5对应的函数值为y=1,3,2,5，作三次Newton插值多项式.如再增加x=6时的函数数值为6，作四次Newton插值多项式.解首先构造差商表xif(xi)一阶差商二阶差商三阶差商0123132-1-2/3553/25/63/10三次Newton插值多项式为323()1(2)(2)(3)310Nxxxxxxx增加x4=6，f(x4)=6作差商表xif(xi)一阶差商二阶差商三阶差商四阶差商0123132-1-2/3553/25/63/10661-1/6-1/4-11/120四次Newton插值多项为42