数值分析期末复习总结

1期末复习总结计算方法董君良北京工业大学/应用数理学院[e-mail]2第一章数值计算的误差计算方法3绝对误差：绝对误差**exxx—精确值x*—近似值则称*为绝对误差限/误差限若存在一个正数*，使得工程上通常记为：x=x**|e*|=|x*-x|*绝对误差可能取正，也可能取负绝对误差越小越具有参考价值但绝对误差却不能很好地表示近似值的精确程度4相对误差相对误差：x*-xer*=x若存在正数r*，使得|er*|r*，则称r*为相对误差限由于真值难以求出，通常也使用下面的定义作为相对误差x*-xer*=x*近似值的精确程度取决于相对误差的大小实际计算中我们所能得到的是误差限或相对误差限5有效数字有效数字：若近似值x*的误差限是某一位的半个单位（即截取按四舍五入规则），且该位到x*的第一位非零数字共有n位，则称x*有n位有效数字x*=a1.a2···an10m(a10)且有|x-x*|0.510m-n+1则x*有n位有效数字设x*为x的近似值，若x*可表示为等价描述6有效数字例：=3.14159265···，近似值x1=3.1415，x2=3.1416问：x1,x2分别有几位有效数字？例：写出下列各数的具有5位有效数字的近似值187.9325，0.03785551，2.7182828，8.000033187.93，0.037856，2.7183，8.0000注：0.2300有4位有效数字，而0.23只有2位有效数字12300如果写成0.123105，则表示只有3位有效数字。数字末尾的0不可以随意添加或省略！7有效数字定理：设近似值x*可表示为x*=a1.a2···al10m(a10)，若x*具有n位有效数字，则其相对误差限满足1r*2a110-(n-1)反之，若x*的相对误差限满足则x*至少有n位有效数字。1r*2(a1+1)10-(n-1)有效位数越多，相对误差限越小8第二章插值法计算方法9插值基本概念已知函数y=f(x)在[a,b]上有定义，且已经测得在点ax0x1···xnb处的函数值为y0=f(x0)，…，yn=f(xn)什么是插值如果存在一个简单易算的函数P(x)，使得P(xi)=f(xi)，i=1,2,...,n则称P(x)为f(x)的插值函数插值区间插值节点求插值函数P(x)的方法就称为插值法插值节点无需递增排列，但必须确保互不相同！插值条件10基函数插值法基函数法通过基函数来构造插值多项式的方法就称为基函数插值法Zn(x)={次数不超过n的多项式的全体}记n+1维线性空间设z0(x),z1(x),...,zn(x)构成Zn(x)的一组基，则插值多项式P(x)=a0z0(x)+a1z1(x)+···+anzn(x)①寻找合适的基函数②确定插值多项式在这组基下的表示系数基函数法基本步骤11Lagrange插值Lagrange插值基函数设lk(x)是n次多项式，在插值节点x0,x1,…,xn上满足1,()0,kjjklxjk则称lk(x)为节点x0,x1,…,xn上的拉格朗日插值基函数单项式基函数利用线性无关的单项式族：21,,,,nxxx构造n次多项式：2012()nnfxaaxaxax12线性与抛物线插值两种特殊情形n=10110011010110()()()xxxxLxylxylxyyxxxx线性插值多项式（一次插值多项式）n=2020112012010210122021()()()()()()()()()()()()xxxxxxxxxxxxyyyxxxxxxxxxxxx抛物线插值多项式（二次插值多项式）2()Lx13插值举例例：已知函数y=lnx的函数值如下解：x0.40.50.60.70.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231试分别用线性插值和抛物线插值计算ln0.54的近似值线性插值：取x0=0.5,x1=0.6得将x=0.54代入可得：011010110()0.18231.6046xxxxLxyyxxxxxln0.54L1(0.54)=-0.6202为了减小截断误差，通常选取插值点x邻接的插值节点14插值举例抛物线插值：取x0=0.4,x1=0.5,x2=0.6,可得ln0.54L2(0.54)=-0.6153在实际计算中，不需要给出插值多项式的表达式ex21.mln0.54的精确值为：-0.616186···可见，抛物线插值的精度比线性插值要高Lagrange插值多项式简单方便，只要取定节点就可写出基函数，进而得到插值多项式，易于计算机实现。15Lagrange插值l0(x),l1(x),…,ln(x)构成Zn(x)的一组基性质注意l0(x),l1(x),…,ln(x)与插值节点有关，但与函数f(x)无关lk(x)的表达式0110111,()()()()()()()()()kknkkkknjjjkkknjkkxxxxxlxxxxxxxxxxxxxxxx由构造法可得16误差估计如何估计误差)()()(xLxfxRnn插值余项定理设f(x)Cn[a,b](n阶连续可微)，且f(n+1)(x)在(a,b)内存在，则对x[a,b]，有(1)1()()()()()(1)!nxnnnfRxfxLxxn其中x(a,b)且与x有关,101()()()()nnxxxxxxx证明：（板书）17插值余项余项公式只有当f(x)的高阶导数存在时才能使用几点说明计算插值点x上的近似值时，应选取与x相近插值节点10()(1)!nnniiMRxxxn如果，则(1)1()nnfxMx与x有关，通常无法确定,实际使用中通常是估计其上界18插值误差举例例：已知函数y=lnx的函数值如下x0.40.50.60.70.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231试估计线性插值和抛物线插值计算ln0.54的误差解线性插值(2)2()4f(2)101()()()()2fRxxxxx1(0.54)2(0.540.5)(0.540.6)0.0048Rx0=0.5,x1=0.6,(0.5,0.6)19Newton插值为什么Newton插值Lagrange插值简单易用，但若要增加一个节点时，全部基函数lk(x)都需重新计算，不太方便。设计一个可以逐次生成插值多项式的算法，即n次插值多项式可以通过n-1次插值多项式生成——Newton插值法解决办法20新的基函数设插值节点为x0,…,xn，考虑插值基函数组010201011()1()()()()()()()()nnxxxxxxxxxxxxxxxx当增加一个节点xn+1时，只需加上基函数10()nniixx21Newton插值此时f(x)的n次插值多项式为10102010()()()()()nnnkkpxaaxxaxxxxaxx问题如何从pn-1(x)得到pn(x)?怎样确定参数a0,…,an?需要用到差商（均差）22差商什么是差商设函数f(x)，节点x0,…,xn()()[,]jiijjifxfxfxxxxf(x)关于点xi,xj的一阶差商[,][,][,,]jkijijkkifxxfxxfxxxxxf(x)关于点xi,xj,xk的二阶差商101010[,,][,,][,,,]kkkkfxxfxxfxxxxxk阶差商差商的一般定义23差商的性质k阶差商与k阶导数之间的关系：若f(x)在[a,b]上具有k阶导数，则至少存在一点(a,b)，使得()01()[,,,]!kkffxxxk24差商的计算如何巧妙地计算差商差商表xiƒ(xi)一阶差商二阶差商三阶差商…n阶差商x0x1x2x3xnƒ(x0)ƒ(x1)ƒ(x2)ƒ(x3)ƒ(xn)ƒ[x0,x1]ƒ[x1,x2]ƒ[x2,x3]ƒ[xn-1,xn]ƒ[x0,x1,x2]ƒ[x1,x2,x3]ƒ[xn-2,xn-1,xn]ƒ[x0,x1,x2,x3]ƒ[xn-3,xn-2,xn-1,xn]……ƒ[x0,x1,…,xn]25差商举例例：已知y=(x)的函数值表，试计算其各阶差商i0123xi-2-112f(xi)531721解：差商表如下xiƒ(xi)一阶差商二阶差商三阶差商-2-112531721-2743-1-1ex24.mex23.m26Newton插值公式Newton插值公式由差商的定义可得000()()()[,]fxfxxxfxx1],,[)(],[],[101100xxxfxxxxfxxf2……],...,,[)(],...,[],...,,[0010nnnnxxxfxxxxfxxxfn11+(xx0)2+……+(xx0)…(xxn1)n1...))(](,,[)](,[)()(102100100xxxxxxxfxxxxfxfxf))...(](,...,[100nnxxxxxxf))()...(](,...,,[100nnnxxxxxxxxxfNn(x)Rn(x)27Newton插值公式f(x)=Nn(x)+Rn(x)10102011()()()()()nniinaaxxaxxxxaxNxx001[,,...,]()...()(())nnnnfxxxxRxxxxxxNn(x)是n次多项式Nn(xi)=f(xi)，i=0,1,2,…,n重要性质Nn(x)是f(x)的n次插值多项式nixxfaxfaii,,2,1],,,[),(000其中28Newton/LagrangeNewton插值多项式与Lagrange插值多项式f(x)在x0,x1,…,xn上的n次插值多项式是唯一的！Nn(x)Ln(x)余项也相同(1)000()[]()()(1)!nnnxniiiifξfx,x,...,xxxxxn(1)0()[](1)!nxnfξfx,x,...,xn!)(][)(0kfx,...,xfkk将x看作节点29插值举例例：已知函数y=lnx的函数值如下解：取节点0.5,0.6,0.4作差商表试分别用牛顿线性插值和抛物线插值计算ln0.54的近似值x0.40.50.60.70.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231xiƒ(xi)一阶差商二阶差商0.50.60.4-0.6931-0.5108-0.91631.82302.0275-2.0450N1(x)=-0.6931+1.8230(x-0.5)N1(0.54)=-0.6202N2(x)=-0.6931+1.8230(x-0.5)-2.0450(x-0.5)(x-0.6)N2(0.54)=-0.6153ex25.m插值节点无需递增排列，但必须确保互不相同！30第三章函数逼近与FFT计算方法31函数逼近三个问题问题一已知一个函数的数值表xx1x2……xnyy1y2……yn能否找到一个简单易算的p(x)，使得p(xi)=yi。问题二函数f(x)的表达式非常复杂，能否找到一个简单易算的p(x)，使得p(x)是f(x)的一个合理的逼近。问题三问题一的表中的数值带有误差，能否找到一个简单易算的p(x)，可以近似地表示这些数据。插值数值逼近32赋范线性空间赋范线性空间C[a,b]线性空间C[a,b]，f(x)C[a,b]①1-范数：1()()dbafxfxx22()()dbafxfxx()max()axbfxfx②2-范数：③-范数：33逼近标准度量p(x)与f(x)的近似程度的常用两种标准使