数值计算方法

吕同富康兆敏方秀男清华大学出版社在数学发展中，理论和计算是紧密联系的。现代计算机的出现为大规模的数值计算创造了条件，集中而系统的研究适用于计算机的数值方法变得十分迫切和必要。数值计算方法正是在大量的数值计算实践和理论分析工作的基础上发展起来的，它不仅仅是一些数值方法的简单积累，而且揭示了包含在多种多样的数值方法之间的相同的结构和统一的原理。数值算法是进行科学计算必不可缺少的起码常识；更为重要的是通过对它们的讨论，能够使人们掌握设计数值算法的基本方法和一般原理，为在计算机上解决科学计算问题打下基础。科学素质：拓宽对21世纪科学的了解；加深对数学思想的理解；培养用数学思考世界的习惯数学能力：数学知识的运用能力；对专业中问题建立数学求解方法与实际计算能力应用问题中数学创造性能力计算知识：常用算法的数学理论；在“误差、存贮、速度”之下的实际计算方法；对结果的数值分析方法数学分析(或微积分)高等代数数学软件学习数值计算方法的准备知识我们先来看看学过的一些知识和问题：350x5/3x2^2380xx1,233*34*2*(8)2*2x如果：三次方程呢？n次方程呢？多项式次数一般超过5次，它的根一般已经不能用公式表示65323970xxxxxX=????2320xexxX=???非线性方程呢？问题二：66821222321321321xxxxxxxxx②③①3342212321321321xxxxxxxxx②③①2203312332321xxxxxx23033123232321xxxxxxx②③①方程的个数是3个那如果是20个呢？用什么方法解？一般的呢？11112211211222221122..................nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb我们在数学分析中学过：用克莱姆法则能解决,1,2,,.iiAxinA121930.78(10/)19(20+1)!(20-1)5.110年次秒理论上很“漂亮”的Cramer法则在计算机上并不适用！n=20问题三110201221A求A的特征值和特征向量1111...A............nnnnaaaa求A的特征值和特征向量?美国的人口普查每10年举行一次，下表列出了从1940年到1990年的人口（按千人计）年194019501960197019801990人口（千人）132165151326179323203302226542249633能否利用这些数据合理地估计人口的数量，比如1965年的人口，甚至2015年的人口。两个例子问题四问题5数值积分2101201211010sin?,sin?cos?,1?,ln?xxdxxxdxxdxdxxedx10120111010?,?cos?,?,?xxxdxxdxxdxedxedx第一章绪论1.1科学计算的一般过程1.2数值计算方法的研究内容和特点1.3计算过程的误差及其控制研究求数学问题近似解的方法和过程实际问题数学模型数值计算方法的理论程序设计上机计算求出结果1.1科学计算的一般过程应用数学计算数学•一个科学计算过程主要包括如下几个环节：1.1.1数学建模：将工程问题数学化1.1.2对数学问题给出数值计算方法例1求解线性方程组bAx求解二次方程02cbxax是数值问题cbabA,,,与系数常数项向量输入的数据是系数矩阵21,,xxx和方程的解输出的数据是解向量应用有关学科的知识和数学理论，将实际工程问题，用精炼准确的数学语言对其核心部分进行描述并给出数学模型，这一过程常称为数学建模。一个好的数学模型符合下列两个方面的要求：1.数学模型能真实准确的反映实际工程问题的本质；2.数学模型所用的数学算法能再计算机上实现我们能给出怎样的算法？什么样的算法才能是好算法呢？1.算法的速度（算法的收敛速度）；2.算法所得到结果的精确度；3.算法所占用的计算机资源；1.1.3对数值计算方法进行程序设计1.熟练掌握一门语言，比如c语言，c++，matlab,fortran我们在以后用到的是matlab将数值问题机器化1.1.4上机计算并分析结果理论来源于实践，要应用的实践中去数值模拟物理过程，分析计算结果的可靠性，必要时重复上述过程。其中算法设计是数值计算的核心内容。数值计算方法针对来源于科学与工程中的数学模型问题，介绍计算机上常用的数值方法的算法设计思想并进行算法分析。•数值计算：常称为数值分析或计算数学或计算方法。主要是研究如何运用计算工具（如计算器、计算机等）去获得数学问题的数值解的理论和方法。实践表明：计算方法正在日趋明显地成为数学与计算机科学的交叉科学。对那些在经典数学中，用解析方法在理论上已作出解的存在，但要求出他的解析解又十分困难，甚至是不可能的这类数学问题，数值解法就显得不可缺少，同时又十分有效。§1.2数值计算方法的研究内容与特点•数值计算研究内容：对如下五类问题探索数值求解方法及其与算法有关的理论分析(2)数值逼近（各种函数逼近问题的数值解、数值积分和微分）(5)最优化理论和方法(4)偏微分方程数值解(3)常微分方程数值解法(1)数值代数（线性方程组、非线性方程及方程组的数值解法）算法：从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。运算量(计算量)：一个算法所需的乘除运算总次数计算量是衡量一个算法好坏的重要指标!数值计算的根本任务就是研究算法•研究数值算法的任务主要有：(1)构造计算机上可执行的算法(2)构造计算复杂性好的算法(3)构造可靠性好的数值方法计算机上可执行的运算：四则运算逻辑运算尽可能提高数值方法的计算速度和少占存贮空间。选择或研制能达到“数值问题”要求的计算精度的数值方法，为此须研究数值问题的性态及数值方法的稳定性。计算方法：把求解数学问题转化为按一定次序只进行加、减、乘、除等基本运算——数值方法。例1.1.1例如：计算3次多项式的函数值0122333)(axaxaxaxp直接计算需要6次乘法，3次加法。如果作如下改变：0122333)(axaxaxaxp0123))((axaxaxa只有3次乘法，3次加法。这个算法称作：秦九绍算法。例1.1.2解线性方程组,Axb其中，1212(),(,,...,),(,,...,).TTijnnnnAaxxxxbbbb►克兰姆(Cramer)法则：,1,2,,.iiAxinA运算量(乘除)：(1)!(1)(1)!(1)nnnnn►高斯消元法(Gauss)：运算量(乘除)3211.33nnn20n取Gauss:3060次Cramer:121930.78(10/)19(20+1)!(20-1)5.110年次秒理论上很“漂亮”的Cramer法则在计算机上并不适用！解：ndxxdxxxxIInnnnn15551011011可得算法：01ln6ln50.182315(1,2,......,20)nnIIInn计算积分20,,1,0510ndxxxInn的递推关系式，并研究它的误差传递。例1.1.3具有以下的性质：0nI1.2.nI单调递减3.lim0nnI4.556]1,0[nnnxxxxx时，)1(51)1(61nInn•将问题可算化的手段：将问题可算化是设计一个算法的第一步(1)用有限维空间代替无限维空间(2)用有限过程代替无限过程(3)用简单问题代替复杂问题(4)扰动分析：估计误差或精度§1.3计算过程中的误差及其控制计算公式中的运算必须是在计算机上可执行的运算参与运算的数必须是有限小数或整数因此，数值方法中的取数和运算往往会出现误差，算得的结果（称为计算值）一般也为近似值。在任何科学计算中，其解的精确性总是相对的，而误差则是绝对的。数值方法中的计算公式及参与运算的数，都和数学中的一般情况有所不同，即1.3.1、误差的种类及来源一个物理量的真实值和我们算出的值（即计算值）往往存在差异，它们之差称为误差。模型误差在建立数学模型过程中，要将复杂的现象抽象归结为数学模型，往往要忽略一些次要因素的影响，而对问题作一些简化，因此数学模型和实际问题之间有一定的误差。观测误差在建模和具体运算过程中所用的数据往往是通过观察和测量得到的，受观测方式、仪器精度以及外部观测条件等多种因素限制，不可能获得精确值，由此而来产生的误差。截断误差由于计算机只能完成有限次算术运算和逻辑运算，因此要将有些需用极限或无穷过程进行的运算有限化，对无穷过程进行截断，这就带来误差。231......2!3!xxxex357sin......3!5!7!xxxxx234ln(1)......2!3!4!xxxxx例:若将前若干项的部分和作为函数值的近似公式，由于以后各项都舍弃了，自然产生了误差Taylor展开舍入误差在数值计算过程中还会遇到无穷小数，因计算机受到机器字长的限制，它所能表示的数据其位数只能是有限的，如按四舍五入规则取有限位数，由此引起的误差3.14159265......21.414213562......110.166666666......3!61415927.34142136.1216666667.0!31另外还有过失误差，这类误差是由于模型错误或方法错误所引起的，一般可以避免。结论：误差是不可避免的经过大量的运算之后，积累的总误差有时会大得惊人，因此如何控制误差的传播也是数值方法的研究对象。在４种误差中，前２种是客观存在的，后２种是计算方法引起的。数学模型一旦建立，进入具体计算时所考虑和分析的就是截断误差和舍入误差。因此本课程只涉及这２种误差。在实际问题中求精确解是没有意义的，求近似解是正常的。问题是如何尽量减少误差，提高精度。1.3.2、误差与有效数字定义1.2**xxx设为准确值，为的一个近似值。称*exx.x为近似值的绝对误差，简称误差*x因为准确值往往是未知甚至是无法知道的，*exx因此往往也无法求出。*exx而只能知道绝对值的某个上界，即*||||.exxx数值称为近似值的一个绝对误差限或误差限,简记为显然*xxx有时也表示为*xx0且152x例：对于51000y用绝对误差来刻画近似值的精确程度是有限的，因为它没有反映出它相对于精确值的大小或它占精确值的比例。例如两个量与它们的近似值分别为**yx和yx和31000,1000110,10**yyxx则有误差限3,1**yyxxyx虽然的3倍，但在1000内差3显然比10内差1更精确些。这说明一个近似值的精确程度除了与绝对误差有关外，还与精确值的大小有关，所以这是可以用相对误差来比较这两个近似数的准确度。xy是定义1.3*0*xxx设为准确值，为的一个近似值。称***rexxexxx为近似值的相对误差。***rrxxeexxxr则称为近似值的一个相对误差限。绝对误差和绝对误差限仅考虑了误差值本身的大小，没有考虑准确值的大小。为了能较好地反映近似值的精确程度，还应考虑准确值的大小。r若存在正数满足|*|rx绝对误差限相对误差限*rexxexx*||rx代替相对误差代替相对误差限往往未知3.1415926...10.001...14159.3,142.3,14.3321一个数的近似数往往是通过四舍五入的原则求得的，例如：取以下近似数可以发现每一个近似数的绝对误差限都不超过近似数末尾数的半个单位。如果一个近似