函数的插值与最佳平方逼近

1数值计算方法第5章函数的插值与最佳平方逼近2实践中常有这样的问题：(1)由实验得到某一函数f(x)在一系列点x0，x1，…，xn处的值f0，f1，…，fn，其函数的解析表达式是未知的(2)或者f(x)虽有解析式，但计算复杂，不便于使用需要构造一个简单函数y(x)近似地代替f(x)——这就是函数逼近问题35.0基本概念1.逼近函数与被逼近函数函数逼近问题中的函数f(x)称为被逼近函数，y(x)称为逼近函数，其中所谓简单函数指可用四则运算进行计算的函数（如：有理、多项式、分段多项式）2.逼近的度量(1)以为度量的逼近称为一致逼近(2)以为度量的逼近称为平方逼近|)()(|max||||],[xyxfyfbaxbadxxyxfyf22|)()(|||||43.插值与拟合设已知被逼近函数f(x)在离散点xi[a，b]上的值f(xi)=fi，(1)要求y(x)满足（甚至）的问题称为函数插值。(2)要求y(x)满足为最小的问题称为数据拟合（曲线拟合）0|)()(|max0iinixyxf0|)(')('|max0iinixyxfniiixyxf02|)()(|54.简单函数类设φ0，φ1，…，φn线性无关，令Φ=span{φ0，φ1，…，φn}为简单函数类，其中φ0，φ1，…，φn称为Φ的基函数。逼近问题即用y(x)=a0φ0(x)+a1φ1(x)+…+anφn(x)来做逼近，问题归结为求其中的待定系数a0，a1，…，an。65.1多项式插值即：求多项式pn(x)满足插值条件：pn(xi)=f(xi)=fii=0，1，2，…，n(5.1-1)其中点xi[a，b]i=0，1，2，…，n，称为插值节点，区间[a，b]称为插值区间，pn(x)称为插值多项式7定理5.1-1存在唯一pn(x)Pn[x]满足插值条件(5.1-1)pn(xi)=f(xi)=fii=0，1，2，…，n证明：取Pn[x]的一组基{1，x，x2，…，xn}，则pn(x)Pn[x]表为pn(x)=a0+a1x+…+anxn(5.1-2)由(5.1-1)知pn(xi)=a0+a1xi+…+anxin=fi(i=0，1，2，…，n)(5.1-3)(5.1-3)的系数行列式为范德蒙行列式：niijjinnnnnnnxxxxxxxxxxxV110110010)(111),...,,(8(5.1-3)的系数行列式为范德蒙行列式：因为x0，x1，…，xn互异，所以Vn≠0即(5.1-3)存在唯一解，从而存在唯一的pn(x)Pn[x]满足插值条件(5.1-1)。niijjinnnnnnnxxxxxxxxxxxV110110010)(111),...,,(9例1给定数据求次数不小于3的插值多项式p3(x)解：设p3(x)=a0+a1x+a2x2+a3x3依题意有解之得：a0=10，a1=5，a2=–5，a3=2即有p3(x)=10+5x–5x2+2x3注：(1)范德蒙矩阵的条件数很大——误差大计算量大(2)选择适当基函数使插值多项式具有特殊形式xi-1125fi-77-43535)5()5()5(4)2()2()2(7)1()1()1(7)1()1()1(332210332210332210332210aaaaaaaaaaaaaaaa101.Lagrange插值因为所以先考虑特殊的插值问题。求次数不大于n的多项式li(x)满足(5.1-4)100...0100011010nnffffffijijxlijji01)(11由定理5.1-1知，li(x)唯一存在，且有n个零点：x0，...，xi-1，xi+1，...，xn所以li(x)=bi(x–x0)...(x–xi-1)(x–xi+1)...(x–xn)又由li(xi)=1，得即(5.1-5)))...()()...((1110niiiiiiixxxxxxxxbnijjjijixxxxxl0)(12注：(1)易知{l0，...，ln}为Pn[x]的一组基，称为以x0，...，...，xn为节点的Lagrange插值基函数。(2)令(5.1-8)则易知(5.1-8)所示的pn(x)为次数不大于n的多项式，且满足插值条件(5.1-1)(j=0，1，...，n)称pn(x)为Lagrange插值多项式。ninijjjijiniiinxxxxfxlfxp000)()(jnijiijnfxlfxp0)()(13(3)n=1时称为线性插值：，p1(x)=l0(x)f0+l1(x)f1n=2时称为抛物插值：p2(x)=l0(x)f0+l1(x)f1+l2(x)f21010)(xxxxxl0101)(xxxxxl))(())(()(2010210xxxxxxxxxl))(())(()(2101201xxxxxxxxxl))(())(()(1202122xxxxxxxxxl14例2已知离散数据如下：(1)求以x2=0，x3=1为节点的线性插值多项式，并预测x=0.3时f的近似值。(2)求以x1=-1，x2=0，x3=1为节点的二次插值多项式，并预测x=0.3时f的近似值。解:(1)线性插值多项式是：由于p1(0.3)=0.3+1=1.3，所以当x=0.3时f的近似值为1.3。xi-2-1012fi0.250.512412)1(01021011)(232332321xxxxxxxxxfxxxxfxp15例2已知离散数据如下：(2)求以x1=-1，x2=0，x3=1为节点的二次插值多项式，并预测x=0.3时f的近似值。解:(2)二次插值多项式是：由于p2(0.3)=1.2475，所以当x=0.3时f的近似值为1.2475。xi-2-1012fi0.250.5124175.025.0)1()1()1(25.0)01))(1(1()0))(1((2)10))(1(0()1))(1((1)11)(01()1)(0(5.0)(222xxxxxxxxxxxxxxp16Matlab代码：symsxx0=[-1,0,1];y0=[0.5,1,2];n=length(x0);s=0;fork=1:np=1.0;forj=1:nifj~=kp=p*(x-x0(j))/(x0(k)-x0(j));endends=s+p*y0(k);ends=vpa(s,8)s=expand(s);s=simple(s)s=subs(s,'0.3',x);s=vpa(s,8)172.Newton插值L插值的缺点：每增加一个新节点，其插值基函数li(x)要重新计算，能否充分利用已有结果呢？为此作基函数：即将pn(x)表示为：(5.1-10)这样，当增加一个新节点时，只需增加一个新项1,...,2,1,0)()()(1)(10nixxxxxiiiniinnxxcxxxxcxxccxp0102010)(...))(()(1)(niinxxc0)(18利用插值条件(5.1-1)可得c0=f0称为一阶差商称为二阶差商],[10010101011xxfxxffxxcfc],,[],[],[],[))(()(210121020121002021202021022xxxfxxxxfxxfxxxxfxxffxxxxxxccfc19…称为i阶差商(i=1，2，…，n)从而有pn(x)=f0+f[x0，x1](x–x0)+…+f[x0，x1，…，xn](x–x0)(x–x1)…(x–xn-1)(5.1-11)称为Newton插值多项式],...,,[],...,,[],...,,[1011210210iiiiiiiixxxfxxxxxxfxxxxfc20注：差商的基本性质如下：(1)i阶差商f[x0，x1，…，xi]可表为f(x0)，f(x1)，…，f(xi)的线性组合(2)差商具有对称性，即差商与它所含节点的排列顺序无关(3)若f为m次多项式，则i阶差商：mimiimxxxfi0],...,,[21次多项式21(4)差商表例3（p369）求(1)次数不大于3的插值多项式p3(x)通过前四个数据点(2)次数不大于4的插值多项式p4(x)通过所给五个数据点，并计算f(4.0)的近似值。xf(x)一阶差商二阶差商三阶差商…n阶差商x0f(x0)x1f(x1)f[x0，x1]x2f(x2)f[x1，x2]f[x0，x1，x2]x3f(x3)f[x2，x3]f[x1，x2，x3]f[x0，x1，x2，x3]………………xnf(xn)f[xn–1，xn]f[xn-2，xn-1，xn]f[xn-3，xn-2，xn-1，xn]...f[x0，x1，...，xn]xi1.02.73.24.85.6fi14.217.822.038.251.722例3（p369）求(1)次数不大于3的插值多项式p3(x)通过前四个数据点(2)次数不大于4的插值多项式p4(x)通过所给五个数据点，并计算f(4.0)的近似值。解：计算差商表如下：xi1.02.73.24.85.6fi14.217.822.038.251.7xifi一阶差商二阶差商三阶差商四阶差商1.014.22.717.82.1183.222.08.4002.8554.838.210.1250.821-0.5355.651.716.8752.8130.6870.26623解：计算差商表如下：(1)p3(x)=14.2+2.118(x–1.0)+2.855(x–1.0)(x–2.7)–0.535(x–1.0)(x–2.7)(x–3.2)xifi一阶差商二阶差商三阶差商四阶差商1.014.22.717.82.1183.222.08.4002.8554.838.210.1250.821-0.5355.651.716.8752.8130.6870.26624(1)p3(x)=14.2+2.118(x–1.0)+2.855(x–1.0)(x–2.7)–0.535(x–1.0)(x–2.7)(x–3.2)(2)p4(x)=14.2+2.118(x–1.0)+2.855(x–1.0)(x–2.7)–0.535(x–1.0)(x–2.7)(x–3.2)+0.266(x–1.0)(x–2.7)(x–3.2)(x–4.8)={[[0.266(x–4.8)–0.535](x–3.2)+2.855](x–2.7)+2.118}(x–1.0)+14.2f(4.0)p4(4.0)={[[0.266(4.0–4.8)–0.535](4.0–3.2)+2.855](4.0–2.7)+2.118}(4.0–1.0)+14.2=29.355253.插值余项称R(x)=f(x)–pn(x)为插值余项定理5.1-2设f(x)在插值区间[a，b]上存在n+1阶导数，则对于任意x[a，b]，存在=(x)(a，b)，使(5.1-12))()!1()()()()(1)1(xnfxpxfxRnnnn26证明：显然R(xi)=0，(i=0，1，2，…，n)，所以R(xi)至少有n+1个零点故可设作辅助函数则(t)在[a，b]上具有n+1阶导数，且有n+2个互异的零点：x0，x1，...，xn，x由罗尔定理，存在(a，b)使f(n+1)()–K(x)(n+1)!=0)()()()()(10xxKxxxKxRnniinniinxt