佛大数值分析2.doc

第1章 插值法1.1 引言实验中常常碰到这样的问题：某一函数y = f(x)在一系列点（x0，x1，xn）处的值为（y0，y1，yn）(测量得出)。其中f(x)未知或f(x)知道，但是计算复杂，不便计算，我们就用较易计算的函数p(x)去近似代替f(x)。其p(x)满足p(xi)=y i(i=0，1，n)，此类问题就称为插值问题一般地，设函数y = f(x)在区间a，b上有定义，且已知在ax0x1xnb点上的值为y0，y1，yn，若存在一简单函数p(x)，使p(xi)=y i(i=0，1，n)，则称函数p(x)为f(x)的插值函数，点x0，x1，xn为插值节点，a，b为插值区间，求插值函数p(x)的方法称为插值法，若p(x)是次数不超过n的代数多项式，即 为实数，则称p(x)为插值多项式。1.2 拉格朗日(Lagrange)插值 1.21线性插值与抛物插值 1. 线插（两点一次插值） 对于，当n=1时，假定给定区间x0，x1及端点的函数值y0，y1，要求线性插值多项式P1(x)满足P1(x0) = y0，P1(x1) = y1，P1(x)的几何意义就是过两点(x0，y0)，(x1，y1)的直线。 （点斜式） （两点式 或 对称式）由两点式看出，P1(x)是由两个线性函数： ， 的线性组合得到，其系数分别为及。即显然，及也是线性插值多项式，在节点x0，x1 满足 ，； ，；我们称及为线性插值基函数。2. 抛物线插值（三点二次插值）线性插值仅仅用两个节点以上的信息，精确度较差。为了提高精确度，我们进一步考察以下三点的插值问题，即当n2时，假设插值节点为x0，x1，x2 要求二次插值多项式P2(x)满足 （i0，1， 2）我们知道在几何意义上就是过三点(x1，y1)的抛物线，为了求出，可以采用基函数方法。设 此时基函数、及是二次函数，且在节点上满足条件； ， （i=1， 2）； ， （i=0， 2）；， ， （i=0， 1） ；现在来求。有两个0点设 同理 ，将、及的值分别代入 ，有 1.22拉格朗日(Lagrange)插值设有n1个节点，x0x1xn 的n次插值多项式Pn(x)，假定它满足 （i0，1，n）基本思想：构造n+1个插值“基函数” li(x) (j=0，1，n)，如果满足： 就称这n+1个n次多项式li(x)为节点(x0，x1，xn)上的n次插值基函数。则所求插值多项式即为：。并称该式为拉格朗日插值多项式，线性插值及抛物线插值仅是该式的当n1及n2的特例。拉格朗日插值基函数构造 ( i=0，1，n )基函数构造简记法：若记则 注意1：n次插值多项式Pn(x)通常是最高次数为n的多项式，特殊情况下，次数可能小于n例 求过这三个点 (0，1)，(1，2)，(2，3)的拉格朗日插值多项式。解： 此为一条直线，其原因在于(0，1)，(1，2)， (2，3)三点共线注意2：1.23 Lagrange插值的截断误差(插值余项)与误差估计若在区间a，b上用Pn(x)近似f(x)，则其截断误差为：Rn(x)= f(x)Pn(x)，或称插值余项。定理 设f(n)(x)在a,b上连续，f(n+1)(x)在(a,b)内存在，则(其中依赖于x)：由于余项中含有，如果插值点偏离插值点xi较远则插值效果就可能不太理想，通常如果插值节点位于插值区间内，就称为内插，否则称为外插。由上述定理表面外插是不可靠的。插值的截断误差限估计式： 三、例题：例1 已知函数y=f(x)的观察数据为下表，试构造拉格朗日多项式Ln (x)， 并计算L(1)。xk2045yk5131解： 先构造基函数 所求三次多项式为L3(x)L3(1)例2 已给sin0.32=0.314567,sin0.34=0.333487, sin0.36=0.352274, 用线性插值及抛物插值计算 sin0.3367 的值并估计截断误差。解： 由题意取x0=0.32, y0=0.314567 , x1=0.34 ,y1=0.333487 , x2=0.36 , y2=0.352274 。用线性插值及抛物插值计算，取 x0=0.32 及 x1=0.34 , 又由公式得 sin0.3367L1(0.3367)= = =0.330365 .其截断误差得其中 ，因 f(x)=sinx，f/(x)= -sinx，可取，于是R1(0.3367)=sin 0.3367 L1(0.3367)1/2(0.3335)(0.0167)(0.0033)0.92105，若取x1=0.34，x2=0.36为节点，则线性插值为 ，其截断误差为，其中于是 用抛物插值计算 sin0.3367时，可得这个结果与六位有效数字的正弦函数表完全一样，这说明查表时用二次插值精度已相当高了。其截断误差得 其中 于是练习：已知函数y=ln x的函数表如下：1011121314y=ln x2.30262.39792.48492.56492.6391分别用Lagrange线性插值和抛物线插值求ln 11.5 的近似值，并估计误差。解 线性插值。取两个节点，插值基函数为 由式（1-4）得将代入，即得按式（1-12）得因为，在与之间，故=于是抛物线插值。取，插值多项式为所以因为，于是因此用抛物线插值计算的误差为查表可得。1.3 牛顿(Newton)插值牛顿插值基本思想： 拉格朗日插值的每一基函数lk(x)都依赖于全部n+1个插值节点，增加节点时每一基函数lk(x)都要改变，不能利用已有插值节点的推值表达式结果推出增加一个新节点后的插值表达式。 牛顿插值法即为了改善这一缺点而设计的。牛顿插值多项式的形式牛顿插值法即求形式 Nn(x)= a0+a1(x-x0)+a2(x-x0)(x-x1)+ + an(x-x0)(x-x1)(x-xn-1)的满足插值条件的便于计算的插值多项式。便于计算的两个含义：Nn(x)(本身)的形式便于利用未增加插值节点前的已有插值多项式计算增加后的插值多项式；Nn(x)的系数a0，a1，an便于计算。牛顿插值系数与差商的联系令Nn(x0)= f0，得a0 =f0 ;令Nn(x1)= f1，得令Nn(x2)= f2，得差商定义，称为f(x)关于点x0，x1的一阶差商；，称为f(x)关于点x0，x1，x2的二阶差商；，称为f(x)关于点x0，x1 ，xn的k阶差商。规定0阶差商为函数值本身即计算差商按照差商定义，用两个k-1阶差商的值计算k阶差商，通常用差商表的形式计算和存放（见表1-4）。计算均差时通常要构造形如表1-4所示的均差表。表 4-1 差商表xkf(xk)一阶差商二阶差商三阶差商n阶差商x0x1x2x3xnf(x0)f(x1)f(x2)f(x3)f(xn)fx0,x1fx1,x2fx2,x3fxn-1,xnfx0,x1,x2fx1,x2,x3fxn-2,xn-1,xnfx0,x1,x2,x3fxn-3,xnfx0,x1,xn例 给定函数的函数表-2012171217写出函数的差商表。解 差商表如下：1阶差商2阶差商3阶差商-2012171217-8115371差商性质11. K阶差商可表示为f0，f1， fk的线性组合：对差商阶数k用数学归纳法证明。 n=1时，即为欲证形式。 假设n=k-1是性质1成立，则n=k时，说明：证明中等式(1)为k阶差商的定义；等式(2)为对两个k-1阶差商应用归纳假设；等式(3)为取出两个和式中的公有项(j=0,1,k-2)一起放在花括号内，而把第一和式中j=k项，第二和式中j=k-1项放在花括号外；等式(4)为合并、整理花括号内两项后形成最终和式的相应项j=0,1,k-2，再加上j=k项，j=k-1项即为最终和式。此式即说明差商具有对称性差商性质2N阶差商与导数的关系：牛顿插值公式把x也看作一固定点，把差商展开有 f(x)=f(x0)+fx, x0(x- x0) fx, x0=fx0, x1 +fx, x0 , x1(x- x1) fx, x0, , xn-1= fx0, , xn+ fx, x0, , xn(x- xn)后一式逐次代入前一式得：f(x)=f(x0)+fx0, x1(x- x0) +fx0,x1,x2(x- x0)(x- x1)+fx0, x1 ,xn (x- x0)(x- xn-1) +fx,x0, ,xn(x- x0)(x- xn-1)(x- xn) =Nn(x)+ Rn(x)其中，Nn(x)= f(x0)+fx0, x1(x- x0) +fx0,x1,x2(x- x0)(x- x1)+fx0, x1 ,xn (x- x0)(x- xn-1)Rn(x)= f(x0)- Nn(x)= fx,x0, ,xn(x- x0)(x- xn-1)(x- xn)= fx,x0, ,xnn+1(x)我们称为牛顿(Newton) 差商插值多项式.系数就是差商表1-4中加横线的各阶差商，它比拉格朗日插值计算量省，且便于程序设计；称Rn(x)为牛顿插值公式的插值余项。 当时，Rn(x)0，即Nn(xi)=yi当时，一般有Rn(x)0，其误差为Rn(x)小结：牛顿(Newton) 差商插值多项式次数不超过n，项数不超过n+1，各项系数是是各阶差商； 节点上 ，即增加一个节点时，只须在得名基础上再增加最后一项，其余各项不变。例如当n=1时，取进行插值，有N1(x)= f(x0)+fx0, x1(x- x0) 当n=2时，取进行插值，有N2(x)= f(x0)+fx0, x1(x- x0) +fx0,x1,x2(x- x0)(x- x1) N1(x)+ fx0,x1,x2(x- x0)(x- x1)练习：试列出f(x)=x3 在节点x =0，2，3，5，6上的各阶差商值。例 对上例的中的，求节点为的一次插值多项式，节点为的二次插值多项式和节点为的三次插值多项式。解 差商表如下：1阶差商2阶差商3阶差商-2012171217-8115371由上例知，于是有练习已知函数表(见下表)，试用牛顿插值公式求，并计算的近似值。x132f(x)121解：列出差商表：xi0阶差商1阶差商2阶差商11320.52132.5已知函数表 xi012yi8-7.5-18求函数yf(x)在0，2上零点的近似值解：由于yi是严格单调的，可用反插值求其零点。可先求出插值多项式，并令y0yi8-7.5-18xi012116. 给定单调连续函数yf(x)的函数值表如下x-2-1123f(x)-10-511118求方程f(x)0的根的尽可能好的近似值解：利用函数值表f(x)-10-511118xf -1(y)-2-1123建立差商表ykf -1(yk)一阶差商二阶差商三阶差商四阶差商102510.2110.3333330.0121211120.10.0145830.0012721830.1428570.0025210.0007440.000072得到牛顿插值例. 给定单调连续函数yf(x)的函数值表如下x-2-1123f(x)-10-511118求方程f(x)0的根的尽可能好的近似值解：分析如果直接运用插值公式，可以求得4次插值多项式。从而可以得到一元4次方程。然而我们没有可靠的办法直接解高次方程。因为函数yf(x)单调连续，所以f(x)必存在反函数xf -1(y)利用已知函数值表可知y=f(x)-10-511118xf -1(y)-2-1123建立差商表ykf -1(yk)一阶差商二阶差商三阶差商四阶差商102510.2110.3333330.0121211120.10.0145830.0012721830.1428570.0025210.0007440.000072得到牛顿插值特别注意：反插值只有在y = f (x)为单调函数才能使用。练习 已知函数表 xi012yi8-7.5-18求函数yf(x)在0，2上零点的近似值解：由于yi是严格单调的，可用反插值求其零点。可先求出插值多项式，并令y0yi8-7.5-18xi012例. 给定函数yf(x)的函数值表如下，已知该函数是一个多项式，试求其次数及x的最高幂的系数x012345f(x)-7-452665128解：构造差商表如下xkf (xk)一阶差商二阶差商三阶差商四阶差商0714325933262161465399105128631210由表知，函数的三阶差商均为1，故多项式的最高次数为3由牛顿插值公式得f (x)73（x-0）+3（x-0）(x-1)+（x-0）(x-1) (x-2) x3+2x-7故 x3的系数为1例 求一个次数不高于3的多项式P3(x)满足下列插值条件x123f(x)2412f(x)3解：设P2(x)满足 P2(1)2，P2(2)4，P2(3)12，则有P2(x)3x2-7x+6为求得P3(x)，根据插值条件知，P3(x)应具有下面的形式P3(x)P2(x)k(x-1) (x-2) (x-3)，这样的P3(x)自然满足：P3(xi)= f (xi)由P3(2 )=3P3(2 )= P2(2 )+k(2-2) (2-3)+ (