计算方法--第二章插值法

第二章插值法如果可以将一个实际问题用函数来描述，那么对这个函数性质以及运算规律的研究，就是对这一实际问题的某些内在规律的理性揭示。在工程实践和科学实验中，经常需要建立函数关系，即y=f(x)。虽然从原则上说，它在某个区间[a,b]上是存在的，但通常只能观测到它的部分信息，即只能获取[a,b]上一系列离散点上的值，这些值构成了观测数据。这就是说，我们只知道的一张观测数据表，而不知道函数在其他点x上的取值，这时只能用一个经验函数y=g(x)对真实函数y=f(x)作近似。xix1x2…xnf(xi)f(x1)f(x2)…f(xn)下面两种办法常用来确定经验函数y=g(x)（1）插值法（2）拟合法根据问题的不同，有时要用插值技术来解决，有时则应该采用拟合的方法才合理。已知数据表下面两种办法常用来确定经验函数y=g(x)（1）插值法（2）拟合法根据问题的不同，有时要用插值技术来解决，有时则应该采用拟合的方法才合理。（1）插值法的基本思想求一个经验函数y=g(x)，使g(xi)=f(xi),i=1,…n.xix1x2…xnf(xi)f(x1)f(x2)…f(xn)插值的任务就是由已知的观测点(xi,yi)为物理量(未知量),建立一个简单的、连续的解析模型g(x)，以便能根据该模型推测该物理量在非观测点处的特性。oxy●●●●●y0x1x2xny1y2ynx0y=f(x)g(x)插值法:由实验或测量的方法得到所求函数y=f(x)在互异点x0,x1,...,xn处的值y0,y1,…,yn,构造一个简单函数F(x)作为函数y=f(x)的近似表达式y=f(x)F(x)使F(x0)=y0,F(x1)=y1,,F(xn)=yn,(a)这类问题称为插值问题。f(x)称为被插值函数，F(x)称为插值函数，x0,x1,...,xn称为插值节点。(a)式称为插值条件。第一节函数插值的基本问题插值函数的类型()()()ixFxcxnii=0nii=0在函数类中，选取若干个函数，以作为插值函数。21110()1,,,,()()nnnnnspanxspanxxxFxPxaxaxaxanii=0n取=，插代值函数为=数插值：()sin,cos,sin2,cos2,,sin,cosspanxspanxxxxnxnxnii=0取三：=角插值sin,cos,()sincosspanxxFxaxbx例取：(),()()ispanxFxcxnniii=0i=0即：()sin1,,sin,Fxabxcxspanxx例：()()()PxFxQxmn有理插值：=2012230123()aaxaxFxbbxbxbx例：()()iFxcxnii=0一般地：当插值函数是代数多项式时，插值问题称为代数插值。代数插值定理1设x0,x1,…,xn是n+1个互异节点,函数f(x)在这组节点的值yk=f(xk)(k=0,1,…,n)是给定的，那么存在唯一的次数≤n的多项式Pn(x)满足Pn(xk)=yk,k=0,1,…,n。设Pn(x)=a0+a1x+…+anxn,…...(1)n次代数插值问题为:求次数≤n的多项式Pn(x),使满足插值条件Pn(xi)=yi,,i=0,1,2,…，n,……(2)只要求出Pn(x)的系数a0,a1,…,an即可由插值条件(2)知Pn(x)的系数满足下列n+1个代数方程构成的线性方程组a0+a1x0+a2x02+…+anx0n=y0a0+a1x1+a2x12+…+anx1n=y1…………………….a0+a1xn+a2xn2+…+anxnn=yn证明ai(i=0,1,2,…,n)的系数行列式是Vandermonde行列式2n0002n111101n102nnnn1...1...V(,,,)()(4)...............1...niijijxxxxxxxxxxxxxx(3)由于xi互异，所以(4)右端不为零，从而方程组(3)的解a0,a1,…an存在且唯一。2n0002n111101n102nnnn1...1...V(,,,)()(4)...............1...niijijxxxxxxxxxxxxxx但遗憾的是方程组(3)是病态方程组,阶数n越高，病态越严重。为此我们从另一途径寻求获得Pn(x)的方法----Lagrange插值和Newton插值。（这两种方法称为基函数法）证毕插值误差估计0()()()()()njjjRxfxFxfxcx第二节Lagrange插值线性插值(n=1)求次数≤1的多项式L1(x).满足条件L1(x0)=y0,L1(x1)=y1,1010010011010110()()()yyLxyxxxxxxxxLxyyxxxx点斜式对称式y=f(x)y=L1(x)x0x1xy0101()(),lxlxxx称和为以为节点的插值基函数01010110(),()xxxxlxlxxxxx记10011()()()Lxlxylxy00011011()1()0()0()1lxlxlxlx011010110()xxxxLxyyxxxx令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.二次插值(n=2)求次数≤2的多项式L2(x),使其满足条件L2(x0)=y0,L2(x1)=y1,L2(x2)=y2l0(x)含有x-x1,x-x2两个因子，令l0(x)=λ(x-x1)(x-x2)利用l0(x0)=1确定其中的系数λ，得到：类似的可以得到l1(x),l2(x)0211012()()()()()xxxxlxxxxx0122021()()()()()xxxxlxxxxxl0(x),l1(x),l2(x)称为以x0,x1,x2为节点的插值基函数。0212201012200110120122))))((((()))))(((())(())((xxxxxxxxLxyyxxxxxxxxxxxxyxxxx1200102()()()()()xxxxlxxxxx0,()1,jiijxlij0110,011()()()()()()()()()njjnijiijjjjjjjnjixxxxxxxxxxlxxxxxxxxxxx令Ln(x)=l0(x)y0+l1(x)y1+…+ln(x)yn求n次多项式lj(x),(j=0,1,…,n)使其满足条件n次插值多项式:求次数≤n的多项式Ln(x),使其满足Ln(x0)=y0,Ln(x1)=y1,......,Ln(xn)=yn..(7)容易求得lj(x)(j=0,1,…,n)称为以x0,x1,...,xn为节点的Lagrange插值基函数。0001110011100()()()()()()()...()()...()()()...()()...()()njjnjjnnjjjnjjnjjjjjjjjnnnijijjiijxxxLyllxxylLxxxxxxxxxxyxxxxxxxxxxjxxyxx将代入得....(9)公式（9）就是n次Lagrange插值多项式.特点：构造容易，L-型插值基函数理论上有意义，但增加节点要重新计算，不适合编程计算。实际应用：只用低次插值。定理2:设Ln(x)是过点x0，x1，x2，…xn的f(x)的n次插值多项式，f(x)∈Cn+1[a,b]，其中[a，b]是包含点x0，x1，x2，…,xn的区间，则对任意给定的x[a，b]，总存在一点（a，b）（依赖于x）使(1)1()()()()()(1)!nnnnRxfxLxxnf101()()()...()nnxxxxxxxLagrange插值的截断误差…(10)其中罗尔定理设f(x)在[a,b]内连续，在(a,b)内可导，且有f(a)=f(b)；则在(a,b)内一定存在一点ξ，使得f’(ξ)=0。证明:显然Rn(xi)=f(xi)-Ln(xi)=0,i=0,1,…,n,现在任意固定一点x∈[a,b],x≠xi(i=0,1,…,n),设Rn(x)=K(x)n+1(x),引进辅助函数g(t)=f(t)-Ln(t)-K(x)n+1(t),(*)则g(t)在[a,b]上具有n+1阶连续导数，在t=x0,x1,…,xn,x诸点处函数值皆等于零。即g(t)在[a,b]中有n+2个零点。由罗尔定理知g’(t)在[a,b]中有n+1个零点。如此反复，最后可推知g(n+1)(t)在[a,b]中有1个零点，即有g(n+1)()=0,ab.因为n+1(t)是n+1次多项式，n+1(n+1)(t)=(n+1)!,又因为Ln(t)是次数为n的多项式,因此Ln(n+1)(t)=0。这样，由(*)式便有(1)(1)(1)(1)()()()()()()(1)!nnnngtftKxtftKxn代入Rn(x)=K(x)n+1(x),即得结论(1)(1),()()()(1)!0nntgfKxn令(1)()()(1)!nfKxn由此得(1)1()()()()()(1)!nnnnRxfxLxxnf证毕上式称为带余项的Lagrange插值公式,只要f(x)具有n+1阶导数,就有上式成立,其余项为1(1)()(1)!()()()nnfnnfxLxxab(1)()1(1)!()()nfnnnRxx12()()()2!fRxx22()(1)xtth|)(|max8|)(|''2110xfhxRxxx令x1-x0=b-a=h,x=x0+th,0t1则特别，当n=1时，取x0=a,x1=b，则有易证，当0t1时,|t(1-t)|的最大值为1/4，应当指出，余项表达式只有在f(x)的高阶导数存在时才能应用。在（a，b）内的具体位置通常不可能给出，如果我们可以求出，那么插值多项式Ln(x)逼近f(x)的截断误差是…(11)(1)1()maxnnaxbxfMnnnMRxxn11()()(1)!-1125-77-435ixiy23()105102pxxxx【例2-1】对于函数表求次数不超过3的拉氏插值多项式。在MATLAB中，输入命令formatrat%使数据格式采用有理数形式。x=[-1,1,2,3]’,y=[-7,7,-4,35]’%输入列向量%利用MATLAB矩阵拼装运算方法,构造出方程组(2.2)的系数矩阵A=[x.^0,x.^1,x.^2,x.^3]A\y%求解可得到ans=[10,5,-10,2]’这表明第三节Newton插值本节介绍Newton插值多项式，该公式是一种具有承袭性的插值多项式，且在后续章节有重要应用。为了使Newton插值多项式具有承袭性，令0100011011()1()()()()()()()()()0,1,2,...,iiiiNewtxxxxxxxxxxxxxxxxxinon插值基函数取为nniiionnNxcxccNxxcxewxxxxxton010011()()()()()()插值多项式为式中c0,c1,…,cn为插值多项式系数。为便于表示Nn(x),引出差商概念.差商及其性质定义1给定一个函数表0101...()()...()nnxxxfxfxf