现代数值计算方法第一章

第一章数值计算的基本概念计算不仅仅只是作为验证理论模型的正确性的手段，大量的事实表明它已成为重大科学发现的一种重要手段。科学计算与实验、理论三足鼎立，相辅相成，成为当今科学活动的三大方法。石钟慈：《第三种科学方法----计算机时代的科学计算》（2000）1.数学的一个分支、数学与其它应用学科的桥梁；其具有悠久的历史。2.其它学科发展迫切需要进行数值计算与仿真;科学计算已成为平行于理论分析和科学实验的第三种科学研究手段。3.计算机软、硬件的发展为数值方法的实现提供环境，也促进它的快速发展。1、数值计算简介2、数值计算的研究对象和内容数值分析输入由实际问题建立起来的数学模型计算机近似解课本P1，倒数第二行开始，关于数值算法的定义。基本的数学问题(研究的主要对象与内容):1.大型线性代数方程组Ax=b求解;2.矩阵A的特征值和特征向量计算;3.非线性方程求解(求根);4.积分计算;5.常微分方程初值问题求解;6.函数插值与逼近7.其它。0)(xfdxxfba)(具体例子：（1）求的正实根；29sinxx（2）求一阶微分方程初值问题：(,),(0)1dyfxyydx的解，其中：2(,)sin9fxyxx（3）解线性代数方程组：11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb（4）求积分：10sinxdxx注1：求精确解(值)一般非常困难。例如：1.形式复杂时求根和求积分很困难。2.线性微分方程易解，如非线性方程难解，如)(xf12'yyy1)0()0('yy1sin2yyyey1)0()0('yy注2：若所用的方法不恰当，问题无法解决。例如：方程组阶数n很大，例如n=20。计算机运算速度10亿次/秒,用不好的方法,大约需算3万年;好方法不到一分钟(可见书P2)。希望：好的算法应该具有以下性质:(1)结构简单,易于编程;(2)理论上有(全局)收敛性与稳定性;(3)效率高(运行速度与存储量);(4)经过检验,行之有效.1.3.1来源与分类/*Source&Classification*/从实际问题中抽象出数学模型——模型误差/*ModelingError*/(P2)通过测量得到模型中参数的值——观测误差/*MeasurementError*/(P3,下同)求近似解——方法误差(截断误差/*TruncationError*/)机器字长有限——舍入误差/*RoundoffError*/3、误差的基本理论dxex102近似计算:例大家一起猜？dxe2x1011/e解法之一：将作Taylor展开后再积分2xe91!4171!3151!21311)!4!3!21(10864210dxxxxxdxe2xS4R4/*Remainder*/,104Sdxe2x取则111!5191!414R称为截断误差/*TruncationError*/005091!414.R这里7430024010333014211013114....S0010200050..|舍入误差/*RoundoffError*/|≈0.743由截去部分/*excludedterms*/引起由留下部分/*includedterms*/引起006000100050102...dxe-x的总体误差计算1.3.2误差与有效数字/*ErrorandSignificantDigits*/绝对误差/*absoluteerror*/xx(x)*其中x为精确值，x*为x的近似值。(x)10006074302..dxex*xx，例如：工程上常记为，称为绝对误差限/*accuracy*/，的上限记为注：理论上讲是唯一确定的，可能取正，也可能取负。0不唯一，当然越小越具有参考价值。(x)相对误差/*relativeerror*/)*)(()()(xxxxxr实际总取为x的相对误差上限/*relativeaccuracy*/定义为使的。|)(|xr注：从的定义可见，实际上被偷换成了。那么这样的偷换是否合法？严格的说法是，与是否反映了同一数量级的误差？有兴趣的同学可查阅相关书籍。)(xrxx)(*)(xxxx)(*)(xx向量的误差2112)*(||*||niiixxxx对于n维欧氏空间中的任一向量,),,,(21nTnRxxxxx设是的近似向量，则可利用的欧氏范数Tnxxxx*),*,*,(*21*xx*x1n来表示，它实际上向量与在上的欧氏距离，用的值表示的绝对误差，类似地用表示的相对误差。特别地，当时，就化成前述通常的单个数的误差了。nRx||*||xx*x||||/||*||xxx*x有效数字/*significantdigits*/)(1416.3五位有效数字)(14.3三位有效数字定义(可见书P5,定义1.1):设数是数的近似值，如果的绝对误差限是它的某一数位的半个单位，并且从左起第一个非零数字到该数共有n位，则称这n个数字为的有效数字，也称用近似时具有n位有效数字。x*x*x*x*x*xx00016.0d250.0b1357.24a例1.2已知下列近似数（书P5）的绝对误差限都是0.0005，问它们具有几位有效数字。用科学计数法，记（其中）。若（即的截取按四舍五入规则），则称为有n位有效数字，精确到。mnaa.ax10021*01anm.xx1050||*na*xnm101415.3*;8979321415926535.3例：问：有几位有效数字？请证明你的结论。**10501050*and103141504131..π||π,.π*证明：有位有效数字，精确到小数点后第位。43注：0.2300有4位有效数字，而00023只有2位有效。12300如果写成0.123105，则表示只有3位有效数字。数字末尾的0不可随意省去！例2设=0.0270是某数经“四舍五入”所得，则误差不超过末位的半个单位，即：又,故该不等式又可写为由有效数字定义可知,有3位有效数字，分别是2,7，0。*xx)(x*x41021*xx110270.0*x311021*xx*x例3=32.93,=32.89,故有3位有效数字，分别是3,2，8。x1102105.004.0*xx321021*xx*x*x有效数字与相对误差的关系有效数字相对误差限11111021101021|*||*||)(|nmnmraaxxxx已知x*有n位有效数字，则其相对误差限为相对误差限有效数字nmmnraaxxεxx102110)1(10)1(21|*||)(||*|11)1(1反之，由得可见x*至少有n位有效数字。)1(110)1(21|)(|nraxε例：为使的相对误差小于0.001%,至少应取几位有效数字？*π解：假设*取到n位有效数字，则其相对误差上限为111021|)(|nraxε要保证其相对误差小于0.001%，只要保证其上限满足%001.01021|)(|11nraxε已知a1=3，则从以上不等式可解得n6log6，即n6，应取*=3.14159。例1.3为使的近似值的相对误差小于0.1%，问至少应取几位有效数字.26%,1.010521|)(|)1(nrx)3.1(1021|)(|11nrax.51a26解的近似值的首位非零数字是假设应取n位有效数字，则由(1.3)式有099.52626,3n解之得故取n=4即可满足要求。也就是说只要的近似值具有4位有效数字，就能保证的相对误差小于0.1%。),1lg(4lg5,10)1(41101411anan,0002.010)1(21|)(|)1(1nrax)4.1(10)1(21|)(|)1(1nraxε,911a*x解由于首位数未知，但必有则由(1.4)式有.3n,0969.43979.3,8lg54lg4nn得得*x例1.4已知近似数的相对误差界为0.0002，问至少有几位有效数字*x1.4数值算法设计的若干原则/*Remarks*/1.避免相近二数相减(详细分析请参阅教材p.7-8)几种经验性避免方法：;xεxεxεx;1lnlnlnxεxεx当|x|1时：;2sin2cos12xx...6121112xxxex例：a1=0.12345，a2=0.12346，各有5位有效数字。而a2a1=0.00001，只剩下1位有效数字。2.避免小分母:分母小会造成浮点溢出/*overflow*/3.避免大数吃小数例：用单精度计算的根。010)110(992xx精确解为110291x,x算法1：利用求根公式aacbbx242在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1的指数部分须变为1010，则：1=0.00000000011010，取单精度时就成为：-b=109+1=0.100000001010+0.000000001010=0.100000001010大数吃小数024,102422921aacbbxaacbbx算法2：先解出再利用9211024)(aacbbsignbx11010991221xacxacxx注：求和时从小到大相加，可使和的误差减小。例：按从小到大、以及从大到小的顺序分别计算1+2+3+…+40+1094.尽量简化计算步骤，减少乘除运算的次数,避免误差积累.例如，计算多项式通常运算的乘法次数为若采用递推算法,则乘法次数仅为n.又如nnnxaxaaxp......)(102)1(......21nnn01)()0121(uxp,,,,n-n-kaxuuaunkkknn100111)111()1(11000110001nnnnnn5.选用数值稳定性好的算法，以控制舍入误差高速增长一个算法，如果在执行它的过程中舍入误差在一定条件下可以得到控制（或者说初始误差和舍入误差的增长不影响产生可靠的结果），则称它是数值稳定的，否则称该算法数值不稳定.传播与积累/*Spread&Accumulation*/例：蝴蝶效应——纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！NYBJ以上是一个病态问题/*ill-posedproblem*/关于本身是病态的问题，我们还是留给数学家去头痛吧！......210110,,,n,dxexeIxnn例：计算11nnInI公式一：注意此公式精确成立632120560111100.edxeeIx记为*0I80001050.IIE则初始误差111111110010nI)e(ndxexeIdxexennnn391414231519594249414122764807131632896000121030592000111088128000101............367879440111415*13*14*12*13*11*12*10*11*9*10*0*1.II.II.II.II.II.II.II????!!!Whathappened?!考察第n步的误差nE|)1()1(|||||*11*