数值分析期末复习总结.ppt

1期末复习总结数值分析2第一章数值计算的误差计算方法数值计算中的误差来源及种类---模型误差、参数误差、截断误差、舍入误差。1.模型误差（也称描述误差）模型误差是在建立数学模型时，由于忽略了一些次要因素而产生的误差，它是数学建模阶段要考虑的误差，不是计算方法可以解决的。2.参数误差（也称观测误差）测量已知参数时，数据带来的误差，它也不是计算方法能解决的问题。数值计算中的误差3.截断误差（也称方法误差）截断误差是对参与计算的数学公式做简化可行处理后所产生的误差（用有限过程代替无限过程或用容易计算的方法代替不容易计算的方法），是计算方法关注的内容。4.舍入误差（也称计算误差）舍入误差是由于计算机只能表示有限位数字，因而只能取有限位数进行计算所得的误差，它也是计算方法关注的内容。5绝对误差：绝对误差**exxx—精确值x*—近似值则称*为绝对误差限/误差限若存在一个正数*，使得工程上通常记为：x=x**|e*|=|x*-x|*绝对误差可能取正，也可能取负绝对误差越小越具有参考价值但绝对误差却不能很好地表示近似值的精确程度6相对误差相对误差：x*-xer*=x（精确）若存在正数r*，使得|er*|r*，则称r*为相对误差限由于真值难以求出，通常也使用下面的定义作为相对误差x*-xer*=x*（近似）近似值的精确程度取决于相对误差的大小实际计算中我们所能得到的是误差限或相对误差限7有效数字有效数字：若近似值x*的误差限是某一位的半个单位（即截取按四舍五入规则），且该位到x*的第一位非零数字共有n位，则称x*有n位有效数字x*=a1.a2···an10m(a10)且有|x-x*|0.510m-n则x*有n位有效数字设x*为x的近似值，若x*可表示为等价描述8有效数字（与相对误差限的关系）定理：设近似值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)有效位数越多，相对误差限越小问题的敏感性与数值稳定性对于一个问题，所使用的数据集记作D，所得的解集为S，于是问题简记为S＝f(D)。然而在实际中，使用的数据为D*且有一定误差，从而所得解集S*＝f(D*)也将不会精确地为S(不考虑输入误差及公式误差)。一个重要的问题是：当数据集D*很接近精确值D时，其解集是否也一定很接近精确解S呢？这就是“解对数据的敏感性”问题。定义：对问题f(*)，如数据集非常接近精确值D时，相应解集S*＝f(D*)也非常接近精确解S＝f(D)，则称问题f(*)是良态的，或解对数据不敏感；否则，称f(*)是病态的，或解对数据敏感。描述问题的敏感性，常采用“条件数”这一概念。对不同的问题，条件数的具体定义及计算也不尽一样。作为实例，后面将讨论求解线性方程组问题。需要指出，这种变化并不是由舍入误差引起，也不是计算公式造成，而是由问题本身对系数的敏感性决定的。求高阶多项式的零点问题往往是病态的。对于良态问题，原则上讲可以求得满足精度要求的解。但输入误差不可避免，因而还应保证所使用的算法不会扩展误差在计算结果中的影响，否则计算结果仍不可信。定义：对于一个由多阶段运算组成的算法，若每经过一个阶段的运算，原有的初值误差或舍入误差的影响不增长，则称这个算法是数值稳定的。数值计算中应注意的几个问题某些原则---１．使用数值稳定的计算方法；２．小心处理病态的数学问题；３．注意简化计算步骤，减少算术运算的次数；４．避免两个相近的数相减，避免绝对值太小的数作除数；５．防止大数“吃掉”小数．6.简化计算步骤以节省计算量（秦九韶算法）7.减少有效数字的损失计算机运算时，绝对值很小的数作除数会溢出停机，而且当绝对值很小的除数稍有一点误差时，对计算结果影响很大，例如2.71822.71822718.2;2471.10.0010.00.00001112第二章插值法计算方法13插值基本概念已知函数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)的方法就称为插值法插值节点无需递增排列，但必须确保互不相同！插值条件14基函数插值法基函数法通过基函数来构造插值多项式的方法就称为基函数插值法Ln(x)={次数不超过n的多项式的全体}记n+1维线性空间设l0(x),l1(x),...,ln(x)构成Ln(x)的一组基，则插值多项式P(x)=f0l0(x)+f1l1(x)+···+fnln(x)①寻找合适的基函数②确定插值多项式在这组基下的表示系数基函数法基本步骤15Lagrange插值Lagrange插值基函数设lk(x)是n次多项式，在插值节点x0,x1,…,xn上满足1,()0,kjjklxjk则称lk(x)为节点x0,x1,…,xn上的拉格朗日插值基函数单项式基函数利用线性无关的单项式族：21,,,,nxxx构造n次多项式：2012()nnfxaaxaxax16线性与抛物线插值两种特殊情形n=10110011010110()()()xxxxLxylxylxyyxxxx线性插值多项式（一次插值多项式）n=2020112012010210122021()()()()()()()()()()()()xxxxxxxxxxxxyyyxxxxxxxxxxxx抛物线插值多项式（二次插值多项式）2()Lx17Lagrange插值l0(x),l1(x),…,ln(x)构成Ln(x)的一组基函数性质注意l0(x),l1(x),…,ln(x)与插值节点有关，但与函数f(x)无关lk(x)的表达式0110111,()()()()()()()()()kknkkkknjjjkkknjkkxxxxxlxxxxxxxxxxxxxxxx由构造法可得18误差估计如何估计误差)()()(xLxfxRnn插值余项(1)1()()()()()(1)!nxnnnfRxfxLxxn定理设f(x)Cn[a,b](n阶连续可微)，且f(n+1)(x)在(a,b)内存在，则对x[a,b]，有其中x(a,b)且与x有关,101()()()()nnxxxxxxx19插值余项余项公式只有当f(x)的高阶导数存在时才能使用几点说明计算插值点x上的近似值时，应选取与x相近插值节点10()(1)!nnniiMRxxxn如果，则(1)1()nnfxMx与x有关，通常无法确定,实际使用中通常是估计其上界20Newton插值为什么Newton插值Lagrange插值简单易用，但若要增加一个节点时，全部基函数lk(x)都需重新计算，不太方便。设计一个可以逐次生成插值多项式的算法，即n次插值多项式可以通过n-1次插值多项式生成——Newton插值法解决办法21新的基函数设插值节点为x0,…,xn，考虑插值基函数组010201011()1()()()()()()()()nnxxxxxxxxxxxxxxxx当增加一个节点xn+1时，只需加上基函数10()nniixx22Newton插值此时f(x)的n次插值多项式为10102010()()()()()nnnkkpxaaxxaxxxxaxx问题如何从pn-1(x)得到pn(x)?怎样确定参数a0,…,an?需要用到差商（均差）23差商什么是差商设函数f(x)，节点x0,…,xn()()[,]jiijjifxfxfxxxxf(x)关于点xi,xj的一阶差商[,][,][,,]jkijijkkifxxfxxfxxxxxf(x)关于点xi,xj,xk的二阶差商101010[,,][,,][,,,]kkkkfxxfxxfxxxxxk阶差商差商的一般定义24差商的性质k阶差商与k阶导数之间的关系：若f(x)在[a,b]上具有k阶导数，则至少存在一点(a,b)，使得()01()[,,,]!kkffxxxk25差商的计算如何巧妙地计算差商差商表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]26差商举例例：已知y=(x)的函数值表，试计算其各阶差商i0123xi-2-112f(xi)531721解：差商表如下xiƒ(xi)一阶差商二阶差商三阶差商-2-112531721-2743-1-1ex24.mex23.m27Newton插值公式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)28Newton插值公式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其中29Newton/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看作节点30插值举例例：已知函数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插值节点无需递增排列，但必须确保互不相同！31第三章函数逼近与曲线拟合计算方法32函数逼近三个问题问题一已知一个函数的数值表xx1x2……xnyy1y2……yn能否找到一个简单易算的p(x)，使得p(xi)=yi。问题二函数f(x)的表达式非常复杂，能否找到