数值分析

1数值分析NumericalAnalysis2教材(TextBook)李庆扬、王能超、易大义，数值分析（5版）,北京：清华大学出版社,2008参考书目(Reference)易大义，陈道琦，数值分析引论,浙江大学出版社,2000蔡大用，白峰彬，高等数值分析，清华大学大学出版社，1997J.Stoer&R.Bulirsch，IntroductiontoNumericalAnalysis(SecondEdition)，NewYork:Springer,1993其他（略）3课程简介数值分析是计算数学的一个分支,又称计算方法,它是研究用计算机求解各种数学问题的数值方法及其理论的一门学科,是程序设计和对数值结果进行分析的依据和基础。应用计算机解决科学技术和工程问题的步骤：(1)提出实际问题(2)建立数学模型(3)选用数值计算方法(4)编程上机计算得出数据结果。4提问：数值分析是做什么用的？5由于计算机和科学计算的发展，求解各种数学问题的数值方法也愈来愈应用于科学计算的各个领域，新的交叉学科不断涌现，如计算力学、计算物理、计算生物学、计算经济学等，统称为科学计算。科学计算、理论研究、试验研究6计算数学研究适用于计算机编程的算法基础性、应用性、边缘性面向计算机的算法：串行、并行好的算法的标准：可靠的理论性、计算复杂性好（时间复杂性、空间复杂性）数值分析的特点：面向计算机、有可靠的理论分析、好的计算复杂性、数值试验数学软件软件包LAPACK（EISPACK,LINPACK)、IMSL、NGA(1000多个）、MATLAB7一、误差的来源1.模型误差:在建立数学模型过程中,不可能将所有因素均考虑,必然要进行必要的简化,这就带来了与实际问题的误差。2.观测误差:测量已知参数时,数据带来的误差。3.截断误差:在设计算法时,近似处理带来的误差。第二节数值计算的误差8函数用泰勒多项式)(xf2()11()(0)(0)(0)(0)2!!nnnPxffxfxfxn近似代替时，有误差(1)11()()()()(1)!nnnnRxfxPxfxn其中在与之间。这种误差就是截断误差。0x例如：94.舍入误差:计算机的字长是有限的,每一步运算均需四舍五入,由此产出的误差。例如：用3.14159近似代替,产生的误差0000026.014159.3R就是舍入误差。10二、误差的基本概念1.误差和误差限设是准确值x的一个近似值,称为近似值的绝对误差,简称误差.又简记.xxxxe)(x)(xee误差是无法计算的(因为准确值x不知道),但可以估计出它的一个上界。即,称是近似值的绝对误差限,简称误差限.)(xxx)(xx误差是有量纲的，可正可负。112.相对误差和相对误差限()()rexxxexxx称为近似值的相对误差。简记为。xre实际计算中,由于准确值x总是未知的,且由于()()exexxx()()exxxxx2(())(())exxxex2(())1()rrexex12()()rexxxexxx相对误差是无量纲的,也可正可负,它的绝对值的上界称为该近似值的相对误差限,记作)(xr简记为r是的平方项级,故当较小时,常取)(xer)(xer13三、有效数字如果近似值x*的误差限是其某一位的半个单位,该位到x*的第一位非零数字共有n位,我们称x*有n位有效数字。定义：*nx位误差限不超过该位的半个单位自左向右看,第一位非零数字14*0.0020.005xx所以x*=3.14作为π的近似值,有3位有效数字；而取x*=3.1416时,所以x*=3.1416作为π的近似值,有5位有效数字。例π=3.1415926535,取x*=3.14时，15120.10mnkxaaaa下面给出有效数字的另一等价定义用表示x的近似值，并将表示成xx若其误差限nmxx1021,则称具有n位有效数字,这里m是整数,a1,a2,,ak为0~9中的一个数字,且a10.x定义：自左向右看,第一位非零数字16例=3.1415926535,取=3.14时，x21021005.0002.0xx即m-n=-2,m=1,n=3,所以=3.14作为近似值时,就有3位有效数字。x17四、相对误差限与有效数字的关系证明mnaaax10.021故111110)1(||10mmaxa111021)(nrax定理1有n位有效数字，。则其相对误差限为mnaaax10.02101a设近似值11111021101050nmnmraa.xxx)(x18nm102111111(1)10102(1)mnaa则它至少有n位有效数字。定理2设近似值mnaaax10.021的相对误差限,10)1(2111na不大于故至少有n位有效数字。x已知证明111102(1)na*xr)(***xxxxr19例解由于,5204所以,41a由定理1有,%1.0102111na即,81104n得4n要使的近似值的相对误差限小于0.1%,要取几位有效数字。20故只要对的近似数取4位有效数字,其相对误差20472.420因此,可取就可小于0.1%,20五、数值运算的误差估计（一）、算术运算的误差所以和或差的误差限是误差限之和。以上的结论适用于任意多个近似数的和或差。同理可得：乘、除运算的误差,以两数为例写出112212222||()||(),0()xxxxxxxx*1*2*2*1*2*1xxxxxx1.21它是对数函数的微分。设u=xy,则lnu=lnx+lny,因而dlnu=dlnx+dlny这就是说,乘积的相对误差是各乘数的相对误差之和,相对误差限是各乘数的相对误差限之和。2.的相对误差是xd()dlnrxxxexxxx)y()x()u()y(e)x(e)u(errrrrr22即商的相对误差是被除数与除数的相对误差之差,但相对误差限是各乘数的相对误差限之和.由此可得:任意多次连乘、连除所得结果的相对误差限等于各乘数和除数的相对误差限之和。同样,若u=x/y,则lnu=lnx–lny,因此dlnu=dlnx–dlny即)()()()()()(yxuyexeuerrrrrr－23例1解lnlnlnlnlnuxyz所以dlndlndlndlnlnuxyzd从而得到dlndlndlnlndlnxxydzu的相对误差限等于乘数x、y和除数z、ω的相对误差限之和。xyuz设求u的相对误差限。因24（二）函数运算误差设f(x)在(a,b)内连续可微,x的近似值为,f(x)的近似值为,其误差为,误差限为[()]fxx)(xf)]([xfe[()]d()()d()()efxfxfxxfxex取绝对值得)()()()()()()]([xxfxxfxexfxfe其中为近似数的误差限。()xx25可得出一元函数运算的误差限和相对误差限分别为：)()()()()()()]([xxfxfxxfxfxfr)()()(|)(|)]([xxfxxfxf26对多元函数),,,,(21nxxxfy自变量的近似值为yxxxn,,,,21的近似值为12(,,,),nyfxxx函数值的运算误差为y1212121211()[(,,,)](,,,)(,,,)(,,,)()()nnnnnniiiiiieyefxxxdfxxxfxxxfxxxexexxx27记则上式简记为,),,,(21iinxfxxxxf)()()(11iniiiniixexfxexfye28相对误差限于是误差限)()()(11iniiiniixexfxexfyeniiniixfxfy11)(||)(||)()(11yxxfyxxfyniiniir29病态问题与条件数第三节误差的定性分析与避免误差的危害30设计算法时应注意的原则一、简化计算步骤,减少运算次数计算多项式的值:0()nknkkPxax每项akxk有k次乘法运算,因此计算Pn(x)共需1122nnn次乘法和n次加法运算。如将Pn(x)写成:1210nnnnPxaxaxaxaxa例131用递推算法:01,,1,2,,.nkknkuauuxakn最终Pn(x)=un共需n次乘法和n次加法运算。一般地要注意:能在循环外计算,就不要放在循环内计算。1210nnnnPxaxaxaxaxa32二、注意避免两个相近数的相减如用四位有效数字计算:例21701313.04130.04结果只有一位有效数字；两个相近的数相减,有效数字会大大损失。170130.0384048如改为：11170130.0384013.041317013有四位有效数字,新算法避免了两个相近数的相减。33三、防止大数“吃掉”小数例3解用五位十进制计算机进行计算:0.1被大数“吃掉”了,从而有10001524920.152492i555524920.10.52492100.000001100.524921010001524920.1i计算34如改为0.1就没有被吃掉。这也是构造算法时要注意的问题,避免重要的参数被吃掉。100010.15249210052492i10001524920.1i35四、避免除数的绝对值远小于被除数的绝对值当|x||y|时,舍入误差会扩大。2()()()xyyxxyy因为36例47311214100.510151010xxxx很小的数作除数有时还会造成计算机的溢出而停机。30.510的舍入误差均为,而舍入误差为:,则710xy2()()()xyyxxyyyx,37五、使用数值稳定的算法用分部积分公式得递推公式:例5110,0,1,2,nxnIxedxnIn=1-nIn-1在运算过程中,舍入误差能控制在某个范围内的算法称为数值稳定的算法,否则就称为不稳定的算法.用四位有效数字计算:近似值的递推公式:nI,11nnnII误差的递推公式:)(nIe,)()(1nnIneIe0110106321.01IedxeIx38于是I7*,I8*与精确值已经面目全非。n精确值In近似值In*n精确值In近似值In*012340.632120.367870.264240.207270.170890.63210.36780.26420.20740.1704567890.145530.126800.112380.100930.091610.14080.11200.2180-0.72807.5520算法一In=1-nIn-1,100*10.6321IeI代入得下表110,0,1,2,nxnIxedxn39由于计算I0有误差不计中间再产生的舍入误差|e(In*)|=n!|e(I0*)|到I8时|e(I8*)|=8!