计算方法第四章

第4章插值法和曲线拟合4.1插值法的基本理论4.2拉格朗日插值多项式4.3牛顿均差插值多项式4.4三次样条插值4.5曲线拟合的最小二乘法}4.1.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次插值多项式。这样的插值多项式是否存在、唯一？}定理4.1在n+1个互异基点处满足插值原则且次数不超过n的多项式Pn(x)是存在并唯一的。证得由niyxPiin,,1,0,)(nnnnnnnnnnyxaxaxaayxaxaxaayxaxaxaa22101121211000202010其系数行列式),,,(10nxxxVnnnnnnxxxxxxxxx2121102001110)(0nijjixx因此方程组存在唯一的解naaa,,,10，因此Pn(x)存在并唯一。}4.1.2插值多项式的误差截断误差：)()()(xPxfxRnn也称为Pn(x)的余项。定理4.2设函数f(x)在包含基点x0,x1,…,xn的区间[a,b]上连续，在(a,b)上具有n+1阶导数，Pn(x)为满足插值原则的n次插值多项式，则对任一点x∈[a,b]，总存在相应的点ξ∈(a,b)，使)()!1()(1)1(xnfxRnnn其中)(1xn)())((10nxxxxxx)(0inixx证当x=xi(i=0,1,…,n)时，由插值条件知Rn(xi)=0，故结论显然成立。当x是[a,b]上任一个固定点，但不是插值基点时，}作辅助函数)()()()()()(11txxRtPtftFnnnn根据罗尔定理，在F(t)的两个零点之间至少有一点使导数为0，即F(t)在区间[a,b]上至少有n+2个互异的零点x,x0,x1,…,xn。F(n+1)(ξ)=f(n+1)(ξ)=0从而结论成立。依此类推，可知F(n+1)(t)在(a,b)内至少有一个零点ξ，则F(t)在(a,b)内至少有n个互异零点F(t)在(a,b)内至少有n+1个互异的零点}}推论当f(x)是次数不超过n的多项式时，其n次插值多项式就是f(x)本身。证明因为f(n+1)(x)=0，从而Rn(x)≡0，Pn(x)≡f(x)。误差公式的用法：Mtfnbta)(max)1(，则截断误差估计为如果)!1()(nMxRn)(1xn设min{x0,x1,…,xn}=a，max{x0,x1,…,xn}=b当插值点x∈(a,b)时称为内插，否则称为外插。}例若利用在100和144的值，对做一次插值，估计误差是多少？x110解插值基点x0=100,x1=144,插值点110.)(!2)(2)2(1xfxR)144)(100(!2)2(xxf,)(xxf,21)('21xxfxxxxf4141)(''23)(max)2(144100f144100maxx4000141|)(|1xR|)144)(100(|4000121xx|)110(|1R|)144110)(100110(|800010425.0400174.2拉格朗日插值多项式4.2.1线性插值和二次插值4.2.2n次拉格朗日插值}4.2.1线性插值和二次插值}1线性插值----n=1时的代数多项式插值已知f(x0)=y0，f(x1)=y1,x0≠x1xx0x1yy0y1要构造线性函数P1(x)=a0+a1x,使满足插值条件P1(x0)=y0,P1(x1)=y1.)()(0010101xxxxyyyxP)()()(1100010110101xlyxlyxxxxyxxxxyxP（线性插值多项式）（拉格朗日线性插值多项式）公式的结构：它是两个一次函数的线性组合01011010)(,)(xxxxxlxxxxxl（线性插值基函数）}基函数的性质1,0,,)(0)(,1)(jiijxlxljiii}线性插值多项式的截断误差为))((!2)('')()()(1011xxxxfxPxfxRξ是在包含x,x0,x1的区间内某数。例1给定函数y=lnx在两点10、11的值如下表，试用线性插值求ln10.5的近似值，并估计截断误差。1110115.10303.2解f(x)=lnx,x0=10,x1=11,x=10.5ln10.5≈P1(10.5)=1011105.10398.25350.2010110101)(xxxxyxxxxyxP,1)(xxf21)(xxf01.010/1)(max21110f25001.0)115.10)(105.10(!201.0)5.10(1Rx1011y2.3032.398}2二次插值----n=2时的代数多项式插值已知f(x)在三个互异点x0,x1,x2的函数值y0,y1,y2xx0x1x2yy0y1y2要构造次数不超过二次的多项式22102)(xaxaaxP使满足插值条件)2,1,0(,)(2iyxPii公式的构造：先对每个基点xi构造二次插值基函数li(i=0,1,2)，使满足21001,,ji,i)(j)(xl,)(xljiii、))(())(()(2010210xxxxxxxxxl))(())(()(2101201xxxxxxxxxl))(())(()(1202102xxxxxxxxxl})()()()(2211002xlyxlyxlyxP))(())(())(())(())(())((120210221012012010210xxxxxxxxyxxxxxxxxyxxxxxxxxy（拉格朗日二次插值多项式）P2(x)的截断误差为))()((!3)(''')()()(21022xxxxxxfxPxfxRξ是包含x0,x1,x2,x的区间内某数。}例2已知函数y=f(x)的观测数据如表所示，试求其拉格朗日插值多项式，并计算f(1.5)的近似值。x012y2-14解)20)(10()2)(1(2)(2xxxP)12)(02()1)(0(4xx2742xx5.025.175.14)5.1()5.1(22Pf)21)(01()2)(0()1(xx}二次插值也称之为抛物插值。当三点(x0,y0),(x1,y1),(x2,y2)位于一条直线上时，显然插值函数的图形是直线。}4.2.2n次拉格朗日插值作基点xi的n次插值基函数(i=0,1,…,n)：nixxxxxxxxxxxxxxxxxxxxxxxxxljijnijjniiiiiiiniii,,1,0)())(())(()())(())(()(011101110基函数具有性质:n,ji,i)(j)(xl,)(xljiii,,1001、)()()()(1100xlyxlyxlyxPnnnninijjjijixxxxy00n次拉格朗日插值多项式}计算框图：}}高次代数多项式插值的龙格（Runge)现象所以，七、八次以上的代数多项式插值很少使用。}4.3牛顿均差插值多项式4.3.1均差及均差表4.3.2牛顿均差型插值多项式}目的：构造具有如下形式的插值多项式：)())(())(()()(110102010nnnxxxxxxaxxxxaxxaaxP它满足递推性：)())(()()(1101nnnnxxxxxxaxPxP4.3.1均差及均差表一阶均差ijijjixxxfxfxxf)()(],[二阶均差ikjikjkjixxxxfxxfxxxf],[],[],,[例如设9)4(,5)2(,1)0(fff2)02())0()2((]2,0[fff2)24())2()4((]4,2[fff0)04(])2,0[]4,2[(]4,2,0[fff则}k阶均差kiiikikiiikiikikixxxxxfxxxfxxxf],,,[],,,[],,,[11111105]4,2,0[]5,4,2[]5,4,2,0[fff例如零阶均差定义为函数值本身，即)(][iixfxf均差具有对称性：任意改变基点的次序后其值不变。例如f[0,2,4]=f[2,0,4]=f[4,2,0]等等。}均差表xif(xk)1阶2阶3阶4阶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)x4f(x4)f(x3,x4)f(x2,x3,x4)f(x1,x2,x3,x4)f(x0,x1,x2,x3,x4)┊┊┊┊┊┊……计算规律：任一个k(≥1)阶均差的数值等于一个分式的值，其分子为所求均差左侧的数减去左上侧的数，分母为所求均差同一行最左边的基点值减去由它往上数第k个基点值。243243432],[],[],,[xxxxfxxfxxxf143214324321],,[],,[],,,[xxxxxfxxxfxxxxf注意：均差表中，对角线上的均差是构造牛顿型插值公式的重要数据。粗线框出的部分在计算机上可存入二维数组}均差表的数据构成一个矩阵F：F00=f(x0)F10=f(x1),F11=f[x0,x1]F20=f(x2),F21=f[x1,x2],F22=f[x0,x1,x2]F30=f(x3),F31=f[x2,x3],F32=f[x1,x2,x3],F33=f[x0,x1,x2,x3]Fi,j-1=f[xi-j+1,…,xi]Fi-1,j-1=f[xi-j,,…,xi-1]计算机上计算均差表的公式njjinjxxFFFnixfFjiijijijiii,...,1,.,...,2,1),/()(,...,1,0,)(1110一般有Fi,j=f[xi-j,xi-j+1,…,xi-1,xi]}例4.4已知函数y=f(x)的观测数据如表，试构造均差表，并求f[2,4,5]及f[2,4,5,6]的值。x02456f(x)159-413解n=4,构造均差表xif(xi)1阶2阶3阶4阶0245621159-4132-13170-515-15526)5(151756)4(132021522459134594105051546)13(1700422525213106)1(5f[2,4,5]=-5f[2,4,5,6]=5}4.3.2牛顿均差型插值多项式根据线性插值的点斜式)()()()()(