计算方法期末复习

第一章引论1、误差来源及分类1.模型误差——从实际问题中抽象出数学模型2.观测误差——通过测量得到模型中参数的值（通常根据测量工具的精度，可以知道这类误差的上限值。）3.截断误差——当数学模型得不到精确解时，要用数值计算方法求它的近似解，由此产生的误差称为（截断误差）或（方法误差）4.舍入误差——由于计算机字长有限，原始数据的输入及浮点数运算过程中都有可能产生误差，这样产生的误差称为舍入误差2、五个关于误差的概念1.绝对误差(*)ex2.绝对误差限*3.相对误差(*)rex4.相对误差限(*)rx（1）定义：设某一量的准确值为x，近似值为x*，则x*与x之差叫做近似值x*的绝对误差(简称误差)，记为*(*)*eexxx（2）性质：(1)绝对误差e(x*)可正可负(2)|e(x*)|的大小标志着x*的精确度(3)绝对误差e(x*)未知（3）判断：绝对误差是误差的绝对值？（错）（1）定义：若指定一个适当小的正数，使|(*)||*|*exxx则称*为近似值x*的绝对误差限。(有时用*xx表示近似值x*的精度或准确值的所在范围。)（2）性质：(1)在实际问题中，绝对误差一般是有量纲的，绝对误差限也是有量纲的。(2)绝对误差限是正的，有无穷多个【则比*大的任意正数均是绝对误差限】（1）定义：绝对误差与准确值之比*(*)*(*),0rrexxxeexxxx称为x*的相对误差。（2）性质：(1)相对误差是个无量纲量。值小者精度高。(2)由于准确值x未知，故实际问题中，当|(*)rex|较小时，常取(*)(*)*rexexx（1）定义：若指定一个适当小的正数(*)rx，使|(*)||(*)|(*)||rrexexxx则称(*)rx为近似值x*的相对误差限。（2）性质：当||(*)|rex较小时，可用下式计算(*)(*)||rxxx3.有效数字（1）定义：若近似值x*的绝对误差限是某一位的半个单位，该位到x*的第一位非零数字一共有n位，则称近似值x*有n位有效数字，或说x*精确到该位。注意：近似值后面的零不能随便省去！（2）例题：取x1*=3作为π的近似值，则011||0.1415102e：一个有效数字取x2*=3.14作为π的近似值，则221||0.00159102e：三个有效数字取x3*=3.1416作为π的近似值，则431||0.00000734102e：五个有效数字它们的误差都不超过末位数字的半个单位。（3）性质：(1)有效数字越多，则绝对误差越小(2)有效数字越多，则相对误差越小有效数字的位数可刻画近似数的精确度！4、一元函数的误差估计问题：设y=f(x)，x的近似值为x*，则y的近似值y*的误差如何计算？(*)(*)(*)(*)eydyfxdxfxex(*)(*)(*)eyfxex*(*)(*)(*)(*)rrxeyfxexfx故相应的误差限计算如下(*)(*)(*)yfxx*(*)(*)(*)(*)rrxyfxxfx5、算法的数值稳定性概念及运算（1）定义：初始数据的误差或计算中的舍入误差在计算过程中的传播，因算法不同而异。一个算法，如果计算结果受误差的影响小，就称该算法具有较好的数值稳定性6、设计算法的五个原则(一)要避免相近两数相减;εxεxxεxlnlnln1;εxεxxsin()sin2cos()sin22xxx2311126xexxx(二)要防止大数“吃掉”小数，注意保护重要数据(*)(*)*(*)(*)(*)(*)(*)rrdyfxexxeyfxexyfxfx291()4102bsignbbacxa91229110110ccxxxaax求和时从小到大相加，可使和的误差减小。若干数相加，采用绝对值较小者先加的算法，结果的相对误差限较小000054321100.4100.3100.41054322y(三)注意简化计算步骤，减少运算次数，避免误差积累（秦九韶）4324()0.06250.4251.2151.9122.1296(((0.06250.425)1.125)1.912)2.1296Pxxxxxxxxx(四)要避免绝对值小的数作除数21121222()()()xxxxxxx1cossinsin1cosxxxx(1)1xxxxxx(五)设法控制误差的传播许多算法具有递推性。递推法运算过程较规律，但多次递推必然导致误差的积累。1112,3,,91/nnEnEnEe111()()(1)!()nnneEneEneE11nnEEn11|()||()|nneEeEn11|()||()|!neEeEn第三章插值问题1，函数逼近1、插值问题：求一条曲线严格通过数据点2、曲线拟合问题：求一条曲线在一定意义下靠近数据点2，插值问题1、定义：求一个简单函数φ(x)作为f(x)的近似表达式，以满足(),0,1,,iixyin我们称这样的问题为插值问题；并称φ(x)为f(x)的插值函数；f(x)为被插函数，x0,x1,x2,…,xn是插值节(基)点；(),0,1,,iixyin是插值原则.3，插值多项式1、定义：求一个次数不超过n的多项式2012()nnnPxaaxaxax使满足插值原则(条件)(),0,1,,niiPxyin称Pn(x)为f(x)的n次插值多项式2、定理：在n+1个互异节点处满足插值原则且次数不超过n的多项式Pn(x)存在并且唯一。注：若不将多项式次数限制为n，则插值多项式不唯一。0()()()()nniiPxPxpxxx也是一个插值多项式，其中()px可以是任意多项式。4,插值问题拉格朗日差值牛顿插值000()()()()nnnniiiLxylxylxylx0010001()()[,]()...[,...]()...()nnnNxfxfxxxxfxxxxxx二次插值基函数02110120122021()()()()()()()()()()xxxxlxxxxxxxxxlxxxxx一阶差商()()[,]jiijjifxfxfxxxxk阶差商01020111[,,...,][,...,,][,,...,]kkkkkkfxxxfxxxfxxxxx零阶差商0110110()()()()()()()()()iiiniiiiiinnjjijjilxxxxxxxxxxxxxxxxxxxxx()1,()0,iiijlxlx[]()iifxfx1.差商与节点的排列次序无关，称为差商的对称性2.高阶差商可由低阶差商反复作一阶差商得到，计算具有递推性3.若f(x)在[a,b]上存在n阶导数，则()01()[,,,],[,]!nnffxxxabn()()()nnRxfxLx(1)1101()()()(1)!()()()()nnnnnfRxxnxxxxxxx为了使得|ωn+1(x)|尽可能小一些，插值基点的选取原则是：使x尽可能位于区间Ix的中部，这里Ix是包含x以及所用基点的最小闭区间。(1)10100()()()(1)![,,...,]()=[,,...]()...()nnnnnnnfRxxnfxxxxfxxxxxxx1.计算量省，便于程序设计2.具有承袭性的插值公式，便于理论分析埃尔米特差值插值条件中除函数值插值条件外，还有导数值插值条件，即已知：2n+2个条件求:一个次数不超过2n+1的多项式H2n+1(x)解法1：基函数法解法2：承袭法分段低次插值原因：当插值基点无限加密时，Pn(x)也只能在很小范围内收敛，这一现象称为龙格(Runge)现象，它表明通过增加基点来提高逼近程度是不宜的。定义：设在[a,b]上给出插值条件：求一个折线插值函数Ih(x)满足xix0x1…xnf(xi)f0f1…fn1°Ih(x)是[a,b]上的连续函数2°Ih(xk)=fk，k=0,1,…,n3°Ih(x)在每个小区间[xk,xk+1]上是线性函数则称Ih(x)为分段线性插值函数数学表达：1111kkhkkkkkkxxxxIffxxxx1()kkxxx性质：1°分段线性插值多项式是分段函数；2°可以预见，但n充分大时，Ih(x)能很好逼近f(x)。3°Ih(x)有一个缺点：在插值点处有尖点，即一阶导数不连续，不够光滑。解决办法：三次埃尔米特插值三次样条插值两种构造方法5，最小二乘法1、定义：已知：一组实验数据（xi，yi）(i=0,1,…,m)，且观测数据有误差求：自变量x与因变量y之间的函数关系y=F(x)，不要求y=F(x)经过所有点，而只要求在给定点上误差()(0,1,...,)iiiFxyim按某种标准最小。2、度量标准：(1)使残差的最大绝对值为最小maxmax()miniiiiieyFx(2)使残差的绝对值之和为最小miniie(3)使残差的平方和为最小2miniie3、最小二乘法——多项式拟合01()...()nnFxaaxaxnm已知：一组数据（xi，yi）(i=0,1,…,m)求：在次数不超过n的多项式中找一个函数()yFx，使误差平方和最小，即22()00[()]min[()]mmiiiiFxniiFxyFxy是次多项式这里：01()...()nnFxaaxaxnm解：32010(())(,)iiiFxyaa故：010011(,)0(,)0aaaaaa解得：01,aa4、最小二乘法—非多项式拟合—参数线性0011(1)()()()...()()nnFxaxaxaxnm①已知：一组数据（xi，yi）(i=0,1,…,m)求：在函数类01{(),(),...,()}nspanxxx中找一个函数()ySx，使误差平方和最小，即22()00[()]min[()]mmiiiiSxiiSxySxy这里：0011()()()...()()nnSxaxaxaxnm②已知：一组数据（xi，yi），且每个点对应权因子wi0,(i=1,2,…,m).求：在函数类01{(),(),...,()}nspanxxx中找一个函数()ySx，使误差平方和最小，即22()00[()]min[()]mmiiiiiiSxiiwSxywSxy这里：0011()()()...()()nnSxaxaxaxnm最小二乘法—非多项式拟合—参数非线性01010101343(2)()()()...()()()(),(!!)()naaanaaaFxxxxxxFxNOax或第四章数值积分1，求解定积分问题方法：（求曲边梯形面积）旧：（1）牛顿—莱布尼兹公式()()()bafxdxFbFa【需要寻求原函数的困难】【已知点离散】新：（2）机械求积公式0()()nbkkakfxdxAfx【多项式机械求积公式】***【解决原函数的困难】()()()2baabfxdxbaf【中矩形公式】***【解决原函数的困难】()[()()]2babafxdxfbfa【梯形公式】***【解决原函数的困难】0()()()()nbbbnkkaaakfxdxLxdxfxlxdx【插值型求积公式】***【解决离散问题】2，代数精度（1）目的：数值求积方法是近似方法，为了保证精度，我们自然希望公式能对“尽可能多”的函数准确成立，这就提出了所谓代数精度的概念。（2）定义：①若某