计算方法第一章课件

1、数值计算方法12引 言第一章31.数值计算方法及其主要研究内容 随着科学技术的飞速发展，科学计算愈来愈显示出其重要性。科学计算的应用之广已遍及各行各业，例如：气象资料的分析图像，飞机、汽车及轮船的外形设计，高科技研究等都离不开科学计算。因此，作为科学计算的数学工具数值计算方法，已成为各高等院校数学、物理和计算机应用专业等理工科本科生的专业基础课，也是工科硕士研究生的学位必修课。4计算数学：常称为数值分析或（数值）计算方法。 主要是研究如何运用计算工具（如计算 器、计算机等）去获得数学问题的数值 解的理论和方法。当代实践表明：计算方法正在日趋明显地成为数学 与计算机科学的交叉性科学。 对那些在经

2、典数学中，用解析方法在理论上已作出解的存在，但要求出他的解析解又十分困难，甚至是不可能的这类数学问题，数值解法就显得不可缺少，同时又十分有效。5边缘科学：计算物理，计算力学，计算化学， 计算生物学，计算经济学等。算法：从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。运算量(计算量)： 一个算法所需的乘除运算总次数计算量是衡量一个算法好坏的重要指标!计算数学的根本任务就是研究算法6 研究数值算法的任务主要有：(1) 构造计算机上可执行的算法(2) 构造计算复杂性好的算法(3) 构造可靠性好的数值方法计算机上可执行的运算：四则运算逻辑

3、运算尽可能提高数值方法的计算速度和少占存贮空间。选择或研制能达到“数值问题”要求的计算精度的数值方法，为此须研究数值问题的性态及数值方法的稳定性。计算方法：把求解数学问题转化为按一定次序只 进行加、减、乘、除等基本运算 数值方法。7例1.1.1求二次方程求根公式为：的根。开方运算不能在计算机上直接进行运算，必须化为可在计算机上执行的等价运算。即应化为公式：8例1.1.2 已知 a0, a1, a2 , an, x, 计算多项式：直接计算：运算量（乘法）秦九韶算法（1247年）：运算量：9例1.1.3 解线性方程组其中， 克兰姆(Cramer)法则： 运算量(乘除)：高斯消元法(Gauss)：运

4、算量(乘除)Gauss: 3060次Cramer:理论上很“漂亮”的Cramer法则 在计算机上并不适用！10一个计算过程主要包括如下几个环节：(1) 数学建模：将工程问题数学化工程中的数学模型一般可分为三类：(2) 算法设计：将数学问题数值化连续型（确定型）离散型（统计型）不确定型（随机型）本书重点讨论例1.1.4 求解线性方程组求解二次方程是数值问题11求解微分方程不是数值问题将其变成数值问题，即将其“离散化”“离散化”是将非数值问题的数学模型化为数值问题的主要方法，这也是计算方法的任务之一?12(3) 程序设计：将数值问题机器化软件开发方法：结构化方法：面向过程，“自顶而下，逐步细化”其

5、关键方面：划分模块设计或选择模块的算法充实细节组装式开发方法：面向对象，“自下向上”13例1.1.5求二次方程的根。此问题本身可看成功能单一的模块数值方法：直接方法，即用求根公式迭代方法（后面将介绍）须考虑的细节：14(4) 上机运行：数值模拟物理过程(5) 计算结果再表示：如图像的可视化等(6) 可靠性分析：分析计算结果的可靠性，必要时 重复上述过程。其中算法设计是本书的核心内容。本书针对来源于科学与工程中的数学模型问题，介绍计算机上常用的数值方法的算法设计思想并进行算法分析。15 本书研究内容：对如下五类问题探索数值求解方法 及其与算法有关的理论分析(1) 非线性方程求根(2) 求解线性代

6、数方程组的数值方法(3) 数值逼近：插值逼近和最佳逼近(4) 数值微分和数值积分(5) 常微分方程数值解法16 将问题可算化的手段：将问题可算化是设计一个算 法的第一步(1) 用有限维空间代替无限维空间(2) 用有限过程代替无限过程(3) 用简单问题代替复杂问题(4) 扰动分析：估计误差或精度17余项(即截断误差)为例1.1.6解根据微分学的Taylor公式，有将问题可算化，即用有限过程代替无限过程仅包含有限次的四则运算18 构造算法的途径：(多用于确定型连续的数学模型)(1) 迭代技术（迭代法）(2) 离散化技术(3) 离散问题解析化技术(4) 优化技术19例1.1.7解若已知根的粗略近似值

7、，根据Taylor公式，有取等式右边前二项近似替代f(x)，就会得到容易求解的线性方程称为迭代序列Newton迭代法对于迭代法，通常需考虑迭代序列的收敛性与收敛效率！202.误差及误差分析计算公式中的运算必须是在计算机上可执行的运算参与运算的数必须是有限小数或整数因此，数值方法中的取数和运算往往会出现误差，算得的结果（称为计算值）一般也为近似值。在任何科学计算中，其解的精确性总是相对的，而误差则是绝对的。数值方法中的计算公式及参与运算的数，都和数学中的一般情况有所不同，即21一、误差的种类及来源一个物理量的真实值和我们算出的值（即计算值）往往存在差异，它们之差称为误差。模型误差在建立数学模型过

8、程中，要将复杂的现象抽象归结为数学模型，往往要忽略一些次要因素的影响，而对问题作一些简化，因此数学模型和实际问题之间有一定的误差。观测误差在建模和具体运算过程中所用的数据往往是通过观察和测量得到的，受观测方式、仪器精度以及外部观测条件等多种因素限制，不可能获得精确值，由此而来产生的误差。22截断误差由于计算机只能完成有限次算术运算和逻辑运算，因此要将有些需用极限或无穷过程进行的运算有限化，对无穷过程进行截断，这就带来误差。例:若将前若干项的部分和作为函数值的近似公式，由于以后各项都舍弃了，自然产生了误差Taylor展开23舍入误差在数值计算过程中还会遇到无穷小数，因计算机受到机器字长的限制，它

9、所能表示的数据其位数只能是有限的，如按四舍五入规则取有限位数，由此引起的误差另外还有过失误差，这类误差是由于模型错误或方法错误所引起的，一般可以避免。24结论：误差是不可避免的经过大量的运算之后，积累的总误差有时会大得惊人，因此如何控制误差的传播也是数值方法的研究对象。在种误差中，前种是客观存在的，后种是计算方法引起的。数学模型一旦建立，进入具体计算时所考虑和分析的就是截断误差和舍入误差。因此本课程只涉及这种误差。在实际问题中求精确解是没有意义的，求近似解是正常的。问题是如何尽量减少误差，提高精度。25二、误差和误差限定义1.2.1 绝对误差限或误差限,26显然有时也表示为且哪个更精确呢?27

10、定义1.2.2 绝对误差和绝对误差限仅考虑了误差值本身的大小，没有考虑准确值的大小。为了能较好地反映近似值的精确程度，还应考虑准确值的大小。28绝对误差限相对误差限代替相对误差代替相对误差限因此往往未知29例1.2.1解30例1.2.2解可见，经四舍五入取近似值，其绝对误差限将不超过其末位数字的半个单位。31三、浮点数与有效数字定点数：小数点的位置固定在个位数后。机器数：计算机中可表示的数。为了提高精度，机器数通常是用浮点数表示的。称为基数称为尾数或数码称为阶码32其中基数是正整数，一般取为，但为照顾习惯和书写方便，通常化为十进制数输入或输出。阶码是整数。一定型号的计算机，尾数的位数t是固定的

11、，称为计算机的位数；阶码m也有一定的取值范围：33有4位有效数字有6位有效数字定义1.2.3 有8位有效数字只有4位有效数字！由于计算机只能表示有限个数，故通常利用某种舍入规则(如四舍五入，截断误差等)，将数进行浮点化。因而势必产生舍入误差。34n+m位有效数字n-m位有效数字n位有效数字如何确定有效数字、绝对误差限、相对误差限？说明有效数字位数与小数点的位置无关。只有写成规格化形式后，小数点后的位数才能反映出其有效位数的多少。35因此，根据上述分析，对有效数字有如下结果：定理1.2.1 例1.2.3求下列四舍五入近似值的有效数字位数.3位3位4位4位3位5位补充36例1.2.4实际上只有1位

12、！试求它们的有效数字位数。解k=1, n=2, m=237例1.2.5从以上分析可见，四舍五入的近似值的数字都是有效数字而不是四舍五入得到的近似值的数字不一定是有效数字。k=3, m=4n=3k=4, m=5n=438定理1.2.2 证明下面的结果论述了相对误差与有效数字的关系补充39即则有由定理1.2.1可知，40例1.2.6解4142定理1.2.3 该结论可以参照定理1.2.2的证明，请同学们自证补充定理说明:有效数字位数越多相对 误差限就越小，反之亦然。 43例1.2.7解则根据定理1.2.3，相对误差满足即应取4位有效数字，近似值的误差不超过0.1%.44四、误差的传播1、数据误差的传

13、播由多元函数的Taylor展开公式可得，的绝对误差为：相对误差为：称为 f 的条件数，其绝对值的大小可反映函数值对数据的敏感程度45利用上面的误差估计公式，可以得到两个数的和、差、积、商的误差估计462、舍入误差的传播因舍入导致的相对误差限仅与计算机的字长有关，通常称相对误差限 为计算机的相对精度。即47在计算机中，数需首先转化为机器数，比如浮点数，在运算器中参与运算后仍需将运算结果转化成浮点数的形式进行存储。48由上面的讨论可以看出，为了求得满意的计算解，在选用计算公式和设计算法时，都应注意如下普遍原则：(1) 防止大数吃小数主要由计算机的位数引起选用算法应遵循的原则计算机中数的计算特点：加

14、法先对阶，后运算，再舍入。乘法先运算，再舍入。不在计算机数系中的数做四舍五入处理。49计算机在进行运算时，首先要把参加运算的数对阶，即把两数都写成绝对值小于1而阶码相同的数。例1.2.8在四位浮点十进制数的计算机上计算1+ 104 解1+ 104 =0.1000 101+ 0.1000 105 = 0.00001 105 + 0.1000 105(对阶计算) = 0.10001 105 = 0.1000 105 = 10450作一个有效数字为4位的连加运算而如果将小数放在前面计算在作连加时，为防止大数吃小数，应从小到大进行相加，如此，精度将得到适当改善。当然也可采取别的方法。例1.2.951(

15、2) 作减法时应避免两个相近数相减两个相近的数相减，会使有效数字的位数严重损失！例1.2.10用四位浮点数计算 解只有一位有效数字,有效数字大量损失，造成相对误差扩大。结果仍然有四位有效数字。这说明了算法设计的重要性。在算法设计中，若可能出现两个相近数相减，则改变计算公式，如使用三角变换、有理化等等。52例1.2.11解方程解方程的精确解为而如果在字长为8，基底为10的计算机上利用求根公式机器吃了因此在计算机上53上式是解二次方程的数值公式的值与精确解差别很大！54(3) 避免小数作除数和大数作乘数小数作除数或大数作乘数会产生溢出错误，因而产生大的误差。在算法设计时，要避免这类情况在计算公式中

16、出现。此时可以根据一些具体情况, 把某些算式改写成另一种等价的形式，如分母有理化等。根据误差传播的估计式553.算法的稳定性如前所述，由于各种误差的存在，计算机往往只能近似地求解实际问题，因而计算时会冒风险。例1.3.1分析Wilkinson多项式的根对系数的敏感程度。见书P15例1.3.2可以看出： Wilkinson（威尔金森）多项式系数的微小变化，引起多项式根的剧烈波动。因此， Wilkinson多项式的根对系数相当敏感。一、问题的性态56如把方程组的系数舍入成两位有效数字它的精确解为x1 = -6.222. x2= 38.25 x3= -33.65.例1.3.2求解线性方程组其精确解为

17、 x1=x2=x3=1.57若对方程组的系数和中间结果均取3位10进制有效数字，然后用Gauss消元法求解，得到计算解为：显然，该计算解的精度较差。同样用Gauss消元法求解方程组：也取3位10进制有效数字，得到计算解为：容易验证，它是方程组的精确解。58上述例子表明，数值问题计算解的精度，与数值问题本身的性态有关。定义1.3.1 在数值问题中，如果输出数据对输入数据的扰动（如误差）很敏感，即若输入数据（如原始数据）有较小的变化，会引起输出数据（如计算解）的较大变化，称这类数值问题为病态问题或坏条件问题。非病态问题又称为良态问题。当计算机用近似计算求解病态问题时，是相当冒险的，得到的结果可能根

18、本不可靠。因此，处理病态问题必须非常小心，一般应采用高精度算法。对于良态问题，由于舍入误差的影响，不恰当的算法同样可引起计算结果的不可信。59二、算法的稳定性与设计原则例1.3.3计算定积分解一个程序往往要进行大量的四则运算才能得出结果，每一步的运算均可能会产生舍入误差。在大量计算中,舍入误差是积累还是能控制,这与算法有关。60误差放大 5千倍!并假设计算过程中不产生新的舍入误差 。误差会放大由公式可推出：61显然算法不稳定。理论上成立的算法，在计算机上计算时，由于初值的误差在计算过程中的传播，而导致结果的失真，这是我们数值计算方法所要研究的。(2) 利用递推公式误差不会放大数值稳定，在运算过程中，舍入误差不增大。 62定义1.3.2 如果对于良态问题，在运算过程中,舍入误差能控制在某个范围内的算法称之为数值稳定的算法,否则就称之为不