计算方法复习重点1.

一、误差、有效数字定义1绝对误差，简称误差：.*,**的近似值为准确值其中xxxxe误差限：.|*|*的一个上界e相对误差：,**xeer相对误差限：.||**的一个上界rre.***xeer或5.0765x例如，毫米尺5.10001,10yx例如，0.5%.||%,10||**yxyx引论引论定义2.**,*有效数字位有位，就说的第一位非零数字共有到该位的半个单位的误差限是某一位数字若近似值nxnxx(2.2)1021*.0(2.1))1010(10*11)1(121nmnnmxxaaaax并且其中即，例142.195,0.0375551,8.00033,2.71828,按四舍五入写出上述各数具有四位有效数字的近似数.引论1(1)121*(1)1**10(1010)(2.1)0.*1102mnnnrxxaaaaxna设近似数表示为其中若具有位有效数字，则其相对误差限为；定理１*(1)11*10*2(1).nrxxan反之，若的相对误差限为，则至少具有位有效数字200.1%要使的相对误差限小于，要取几位有效数字？例3111102na1*111204.4,41100.125100.1%42nnrana只要取解：设取n位有效数字，相对误差限*r=，引论二、数值运算的误差估计**1212,,,xxxx四则运算，设为准确值为近似值，则：误差限.||)(||)(||)/(),(||)(||)(),()()(2*2*1*2*2*1*2*1*1*2*2*1*2*1*2*1*2*1xxxxxxxxxxxxxxxxx,*,,*)(*)*)((*)()(,*,)(22)(之间在公式由为近似值为准确值，一元函数xxxxxxxfxfxfTaylorxxxff*).(|*)(|*))((*)(xxfxfxf的误差限得).(*)(),,(,,,,,),,(*1***11**11knkknnnnxxffxxfxxxxxxf的误差限同理得的近似值为准确值，多元函数**(8)(*)(*)(*).sldsssldld场地面积：书上第页例6引论三、病态问题与条件数.,,)()()()(*)(条件数称为计算函数值问题的考虑计算函数值问题ppxfxfxxxxfxfxfCC%.24%,2,24.1)02.1(,1)1(,10,)(10函数值相对误差为误差为自变量相对例如ffCxxfppC10.一般认为是病态.,考虑是否病态条件数其他计算问题也要考虑引论四、算法的数值稳定性考虑初始数据误差在计算中的传播问题.1107d,0,1,,.nxnIexexn计算并估计误差例,,,.舍入义一个算法若输入数据有误差而在计算过程中不增长则称此算法是数值稳定的否则是不误差稳定的定3,,2,1,11nnIInn.,2,1,1,6321.0)(10nInIIAnn.110eI.1,,8,9),1(,0684.0)(*1*1*9nIIIBnnn)0684.0)10101(21(19eI引论引论五、避免误差危害的若干原则1.避免‘大数’除以‘小数’绝对值太小的数不宜做除数4()()10()0.14560.14550.0001分子分子分子这里分子的误差被扩大104倍,再如若将分母变为0.0011,即分母只有0.0001的变化时,计算结果却有了很大变化3.14153141.50.0019.28550011.01415.32、两个相近的数相减，会严重损失有效数字例如x=1958.75，y=1958.32都具有五位有效数字，但x-y=0.43只有两位有效数字通常采用的方法是改变计算公式,例如当很接近时,由于2121lglglgxxxx用右端代替左端公式计算,有效数字就不会损失引论xxxx111)1(11)1(xxarctgarctgxxarctg则用右端来代替左端。当x很大时可作相应的变换引论2121610.x863,863xxx求解例972A101cos2.1cos2sin2xx。计算（）例10xxxx111引论12301.001.001.001.001.001.0123100100项项３、防止‘大数’吃‘小数’引论六、简化计算步骤，减少运算次数例：x255=xx2x4x8x16x32x64x128原先要做254次乘法现只需14次即可例：如计算多项式p(x)=anxnan-1xn-1…a1xa0的值若直接计算akxk,再逐项相加，一共要做n+(n-1)+…+2+1=n(n+1)/2次乘法和n次加法引论如果将前n项提出x，则有p(x)=（anxn-1an-1xn-2…a1）xa0=((anxn-2an-1xn-3…a2)xa1）xa0=(…(anxan-1)x…a2)xa1)xa0写成递推公式nknkkabnkaxbb01),,2,1(于是,这种多项式求值的算法称为秦九韶算法,只做n次乘法和n次加法,程序实现简单nbxP)(引论插值法问题的提出•函数解析式未知,通过实验观测得到的一组数据,即在某个区间[a,b]上给出一系列点的函数值yi=f(xi)•或者给出函数表xx0x1x2……xnyy0y1y2……yny=f(x)y=p(x)定理1n次代数插值问题的解是存在且惟一的单项式：)()()(01111011111100011010nnnnnnnnnnnnnnnnxfaxaxaxaxfaxaxaxaxfaxaxaxa拉格朗日插值：nkjjjkjnkjjjknkjjjkxxxxxxxxxl000)()()(nkkkyxlxP0)()((2.10))())(()(101nnxxxxxxx引入记号)()!1()()()()()1(xnfxpxfxRnab且依赖于x对于线性插值，其误差为对于抛物插值（二次插值），其误差为01221()()()()()(),21()-)8（RxfxPxfxxxxabRxbaMbaxxxxxxfxPxfxR,)())()((61)()()(210(1)11n1max|()|,|()||()|,(1)!nnaxbnnfxMMRxxn若则34)()()()()(2333221100xxyxlyxlyxlyxlxp例已知f(x)的观测数据x1234f(x)0-5-63构造插值多项式解:四个点可以构造三次插值多项式,将数据代入插值公式，有例已知=100,=121,用线性插值估计在x=115时的截断误差xxf)(0x1x解:由插值余项公式知)()(21)(1xfxR2341)(xxf))((81)(10231xxxxxR因为)121115)(100115(81)115(231R23121,100max)121115)(100115(81)121115)(100115(1081301125.010615813520123450(-)()(),,,,,iiiixxlxlxxxxxxx例如：p28页的例1证明=0,其中是关于的插值基函数。均差与牛顿插值：)())((,),)((,,1110100nxxxxxxxxxxxxxif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]f[xi,xi+1,xi+2]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]………f[x1,x2]-f[x0,x1]x2–x0)())((,,)(,)()(110100100nnnxxxxxxxxxfxxxxfxfxNxif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]114293N2(7)=1+(7-1)*0.33333+(7-1)*(7-4)*(-0.01667)=2.6999233333.014122.0492301667.01933333.02.0+(x-x0)(x-x1)f[x1,x0,x2]+(x-x0)f[x1,x0]=f(x0)N(x)例2.12已知x=1,4,9的平方根值，求解：7)!()(],...,,[)(10nfxxxfnn例2.14已知f(x)=x7+x4+3x+1求f[20,21,…27]及f[20,21,…27,28]解:由差商与导数之间的关系()01(7)(8)(7)017(8)01781,,,()!()7!,()0()7!2,2,,217!7!()02,2,,2,208!8!nnfxxxfnfxfxffff及知埃尔米特插值：)()!22()()()()(2)22(1212xnfxHxfxRnnn例6P36例：已知函数y=f(x)的数据如下表所示,求次数不超过三次的Hermite的插值多项式H3(x)使H3(xi)=yi(i=0,1,2)H´3(xi)=y´i101()101()0xyfxyfx分段线性插值三次样条插值：)0()0(1,,2,1)0()0()0()0(iiiiiixSxSnixSxSxSxS函数逼近三种常用范数：，有上的向量例如，对),,(1TnnxxxR.2d)(||||,1d|)(||||||)(|max||||)(],[21221范数称为，范数称为，范数，称为，：，可定义三种常用范数上的类似地，对bababxaxxffxxffxffxfbaC范数或最大范数，称为，||max||||1inixx,1||||||11范数称为，niixx.2||||21122范数称为，niixx正交多项式：勒让德多项式(2.7).,122,,0d)()(11nmnnmxxPxPnm正交性(1)(2.8).)()1()(xPxPnnn奇偶性(2).n)1,1()(个互异的实零点内部有在xPn(3)(2.9)),2,1(),(1)(112)(,)(,1)(1110nxPnnxxPnnxPxxPxPnnn递推关系(4)),35(21)(),13(21)(3322xxxPxxP可得切比雪夫多项式切比雪夫多项式.次称为正交化所得正交多项式，序列权函数为区间为n},,,1{11)(],1,1[2nxxxxnnT(x)cos(narccosx),(1x1,n0,1,2,)(2.10)xcosT(x)cos(n),0.若令，则,34)(,12)arccos2cos()(,)cos(arccos)(,1)0cos()(332210xxxTxxxTxxxTxT:切比雪夫多项式的性质(2.11)).()(2)(,)(,1)()1(1110xTxxTxTxxTxTnnn递推关系1).(n,2)(1nnnxxT的系数为的最高次幂.,cos.1,)1cos(coscos2)1(c