计算方法课件第一章ppt.ppt

计计 算算 方方 法法何凯何凯教材教材n计算方法计算方法,易大义等易大义等,浙江大学出版社浙江大学出版社,2002 2002年第年第2 2版版2计算方法计算方法课程体系课程体系n第一章第一章 数值计算中的误差数值计算中的误差n第二章第二章 插值法插值法n第三章第三章 曲线拟合的最小二乘法曲线拟合的最小二乘法n第四章第四章 数值积分数值积分n第五章第五章 非线性方程的数值解法非线性方程的数值解法n第六章第六章 方程组的数值解法方程组的数值解法n第七章第七章 常微分方程数值解法常微分方程数值解法3计算方法计算方法课程体系课程体系本本课课程程的的内内容容数值逼近数值逼近数值代数数值代数常微分方程的数值方法常微分方程的数值方法插值法插值法数据拟合的最小二乘法数据拟合的最小二乘法数值积分和数值微分数值积分和数值微分*线性方程组的求解线性方程组的求解非线性方程组的求解非线性方程组的求解矩阵特征值矩阵特征值*4第一章第一章数值计算中的误差数值计算中的误差3 学时学时本章内容本章内容n1.1 1.1 引言引言n1.2 1.2 误差的种类及其来源误差的种类及其来源n1.3 1.3 绝对误差和相对误差绝对误差和相对误差n1.4 1.4 有效数字及其与误差的关系有效数字及其与误差的关系n1.5 1.5 误差的传播与估计误差的传播与估计n1.6 1.6 选用算法应遵循的原则选用算法应遵循的原则n小结小结n作业与实验作业与实验6本章要求本章要求n1.熟悉计算方法在解决实际问题中所处的地位熟悉计算方法在解决实际问题中所处的地位,熟悉计算方法是以计算机为工具求近似解的数熟悉计算方法是以计算机为工具求近似解的数值方法；值方法；n2.熟悉绝对误差（限），相对误差（限）及有熟悉绝对误差（限），相对误差（限）及有效数字概念；效数字概念；n3.熟悉公式；熟悉公式；n4.熟悉选用算法应遵循的原则。熟悉选用算法应遵循的原则。71.1 引言引言n解决科学技术和工程问题的步骤解决科学技术和工程问题的步骤:n什么是什么是数值计算方法数值计算方法:将所预求解的数学模将所预求解的数学模型简化成一系列算术运算和逻辑运算型简化成一系列算术运算和逻辑运算,以便以便在计算机上求解在计算机上求解,并对算法的稳定性、收敛并对算法的稳定性、收敛性和误差进行分析。性和误差进行分析。实际问题数学问题提供计算方法实际问题数学问题提供计算方法程序设计上机计算结果分析程序设计上机计算结果分析81.1 引言引言n简单地说，就是研究如何用计算机有效地简单地说，就是研究如何用计算机有效地解决一个数学问题。解决一个数学问题。n如何理解这两个含义？如何理解这两个含义？这句这句话有话有两个两个含义含义（1）有一个有效的数学方法）有一个有效的数学方法（2）一个能实现方法的有效程序）一个能实现方法的有效程序 （算法）（算法）先看两个例子先看两个例子91.1 引言引言n算法影响计算的速度和效率算法影响计算的速度和效率 （见课本（见课本 P2 秦九韶算法）秦九韶算法）例例1 古代中国人的贡献古代中国人的贡献多项式的计值：多项式的计值：设设 f(x)=a0 xn+a1 xn-1+an-1 x+an原始的算法需：原始的算法需：n+n-1+1=n(n+1)/2 次乘法。次乘法。秦九韶算法：秦九韶算法：f(x)=(.(a0 x+a1)x+an-1)x+an 仅需仅需 n 次乘法。次乘法。计算代价快速下降计算代价快速下降。101.1 引言引言n算法影响计算的精度算法影响计算的精度例例2 设多项式为设多项式为(x-2)9,我们来计算其在区间我们来计算其在区间1.92,2.08上的值。上的值。令令 p(x)=(x-2)9 q(x)=x9 18 x8+144 x7 672 x6+2016 x5-4032 x4+5376 x3 4608 x2+2304 x-512 则则 p(x)=q(x)，以下我们分别作画以下我们分别作画 p(x)与与 q(x)的图。的图。11n上例说明，即使数学上的恒等公式，用计上例说明，即使数学上的恒等公式，用计算机来算，结果也是不一样的。算机来算，结果也是不一样的。p(x)q(x)121.2 误差的种类及其来源误差的种类及其来源n一一.误差来源误差来源例1，例2 的结果的根源实实际际问问题题数数学学模模型型建建立立算算法法上上机机计计算算结结果果(初初值值误误差差)观观测测误误差差模模型型误误差差(方方法法误误差差)截截断断误误差差舍舍入入误误差差131.2 误差的种类及其来源误差的种类及其来源n二二.误差分类误差分类1.模型误差（描述误差）模型误差（描述误差）/*Modeling Error*/n简化，抽象问题后建立的数学模型与实际问简化，抽象问题后建立的数学模型与实际问题之差。题之差。2.观测误差观测误差 /*Measurement Error*/n观测和实验得到的参量（物理量为电压、电观测和实验得到的参量（物理量为电压、电流、温度等）流、温度等）141.2 误差的种类及其来源误差的种类及其来源3.截断误差（方法误差）截断误差（方法误差）/*Truncation Error*/n有限过程代替无限过程的误差（无穷级数有限过程代替无限过程的误差（无穷级数求和，只能取前面有限项求和来近似代替）求和，只能取前面有限项求和来近似代替）。这种计算方法本身出现的误差，所以也。这种计算方法本身出现的误差，所以也称为方法误差。如称为方法误差。如n右端是截断误差。右端是截断误差。151.2 误差的种类及其来源误差的种类及其来源4.舍入误差舍入误差 /*Roundoff Error*/n计算机字长有限，一般实数不能精确存储，于计算机字长有限，一般实数不能精确存储，于是产生舍入误差。是产生舍入误差。n例如：在例如：在 10 位十进制数限制下：位十进制数限制下：n舍入误差很小，本课程将研究它在运算过程中舍入误差很小，本课程将研究它在运算过程中是否能有效控制。是否能有效控制。161.2 误差的种类及其来源误差的种类及其来源n据说据说,美军美军1910年的一次部队的命令传递是这样的年的一次部队的命令传递是这样的:营长营长对对值班军官值班军官:明晚大约明晚大约 8点钟左右点钟左右,哈雷彗星将哈雷彗星将可能在这个地区看到可能在这个地区看到,这种彗星每隔这种彗星每隔 76年才能看见年才能看见一次。命令所有士兵着野战服在操场上集合一次。命令所有士兵着野战服在操场上集合,我将我将向他们解释这一罕见的现象。如果下雨的话向他们解释这一罕见的现象。如果下雨的话,就在就在礼堂集合礼堂集合,我为他们放一部有关彗星的影片。我为他们放一部有关彗星的影片。值班军官值班军官对对连长连长:根据营长的命令根据营长的命令,明晚明晚8点哈雷彗点哈雷彗星将在操场上空出现。如果下雨的话星将在操场上空出现。如果下雨的话,就让士兵穿就让士兵穿着野战服列队前往礼堂着野战服列队前往礼堂,这一罕见的现象将在那里这一罕见的现象将在那里出现。出现。171.2 误差的种类及其来源误差的种类及其来源连长连长对对排长排长:根据营长的命令根据营长的命令,明晚明晚 8 点点,非凡的哈非凡的哈雷彗星将身穿野战服在礼堂中出现。如果操场上雷彗星将身穿野战服在礼堂中出现。如果操场上下雨下雨,营长将下达另一个命令营长将下达另一个命令,这种命令每隔这种命令每隔 76 年年才会出现一次。才会出现一次。排长排长对对班长班长:明晚明晚 8 点点,营长将带着哈雷彗星在礼营长将带着哈雷彗星在礼堂中出现堂中出现,这是每隔这是每隔 76 年才有的事。如果下雨的年才有的事。如果下雨的话话,营长将命令彗星穿上野战服到操场上去。营长将命令彗星穿上野战服到操场上去。班长班长对对士兵士兵:在明晚在明晚 8 点下雨的时候点下雨的时候,著名的著名的 76 岁岁哈雷将军将在营长的陪同下身着野战服哈雷将军将在营长的陪同下身着野战服,开着他那开着他那“彗星彗星”牌汽车牌汽车,经过操场前往礼堂。经过操场前往礼堂。181.3 绝对误差和相对误差绝对误差和相对误差n一绝对误差一绝对误差/*absolute error*/设设 准确值，准确值，近似值。近似值。称称 为为 的绝对误差的绝对误差(简称误差简称误差)为为 的绝对误差限。的绝对误差限。n二相对误差二相对误差/*relative error*/称称 为为 的相对误差。的相对误差。实用中，常用实用中，常用 表示表示 的相对误差。的相对误差。称称 为为 的相对误差限。的相对误差限。191.4 有效数字及其与误差的关系有效数字及其与误差的关系n一有效数字一有效数字/*significant digits*/一定要从规格化后的数来判断其位数一定要从规格化后的数来判断其位数有效位数与第一个非有效位数与第一个非 0 项后的数字个数是不项后的数字个数是不一致的。一致的。四舍五入所得到的数是一致的。四舍五入所得到的数是一致的。201.4 有效数字及其与误差的关系有效数字及其与误差的关系n 注注:四舍五入规则修正为四舍五以上入四舍五入规则修正为四舍五以上入,五时若前一五时若前一位是偶数则位是偶数则5舍去舍去,奇数则进一奇数则进一,以减少积累误差。以减少积累误差。211.4 有效数字及其与误差的关系有效数字及其与误差的关系n 221.4 有效数字及其与误差的关系有效数字及其与误差的关系n二有效数位与误差的关系二有效数位与误差的关系231.4 有效数字及其与误差的关系有效数字及其与误差的关系n证：证：241.4 有效数字及其与误差的关系有效数字及其与误差的关系n例例5：为使为使*的相对误差小于的相对误差小于0.001%,至少应取几位有效数字？至少应取几位有效数字？解：解：假设假设 *取到取到 n 位有效数字，则其相对误差上限为位有效数字，则其相对误差上限为 要保证其相对误差小于要保证其相对误差小于0.001%，只要保证其上限满足，只要保证其上限满足 已知已知 a1=3，则从以上不等式可解得，则从以上不等式可解得 n 6 log6，即即 n 6，应取，应取 *=3.14159。251.5 误差的传播与估计误差的传播与估计n例：例：蝴蝶效应蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！和日丽的北京就刮起台风来了？！以上是一个以上是一个病态问题病态问题 /*ill-posed problem*/关于本身是病态的问题，还是留给数学家去头痛吧！关于本身是病态的问题，还是留给数学家去头痛吧！NYBJ261.5 误差的传播与估计误差的传播与估计n一一.一元函数情形一元函数情形271.5 误差的传播与估计误差的传播与估计n二二.多元函数情形多元函数情形281.5 误差的传播与估计误差的传播与估计n二二.多元函数情形（续）多元函数情形（续）291.5 误差的传播与估计误差的传播与估计n例例6：测得某桌面的长测得某桌面的长a的近似值的近似值a*=120cm,宽宽b的近似的近似值值b*=60cm。若已知。若已知|e(a*)|0.2cm,|e(b*)|0.1cm。试。试求近似面积求近似面积s*=a*b*的绝对误差限与相对误差限。的绝对误差限与相对误差限。301.6 选用算法应遵循的原则选用算法应遵循的原则n一一.尽量简化计算步骤，减少乘除运算的次数。尽量简化计算步骤，减少乘除运算的次数。311.6 选用算法应遵循的原则选用算法应遵循的原则n二二.防止大数防止大数“吃掉吃掉”小数小数当当|a|b|时，尽量避免时，尽量避免a+b。例如，假设计算。例如，假设计算机只能存放机只能存放10位尾数的十进制数，则位尾数的十进制数，则例：例：321.6 选用算法应遵循的原则选用算法应遵循的原则 算法算法1：利用求根公式利用求根公式 在计算机内，在计算机内，109 存为存为 0.1 1010，1存为存为 0.1 101。做做加法时，两加数的指数先向大指数对齐，再将浮点部加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即分相加。即 1 的指数部分须变为的指数部分须变为 1010，则：则：1=0.0000000001 1010，取单精度时就成为：取单精度时就成为：109+1=0.10000000 1010+0.00000000 1010 =0.10000000 1010大数大数吃吃小数小数331.6 选用算法应遵循的原则选用算法应遵循的原则?算法算法2：例：例：按从小到大、以及从大到小的顺序分别计算按从小到大、以及从大到小的顺序分别计算 1+2+3+40+109注：注：注：注：求和时求和时从小到大从小到大相加相加,可使和的误差减小。可使和的误差减小。341.6 选用算法应遵循的原则选用算法应遵循的原则n三三.尽量避免相近数相减尽量避免相近数相减 例：例：a1=0.12345，a2=0.12346，各有各有 5 位有效数字。位有效数字。而而a2-a1=0.00001,只剩下只剩下 1 位有效数字。位有效数字。351.6 选用算法应遵循的原则选用算法应遵循的原则n四四.避免绝对值很小的数做分母，会造成浮点溢避免绝对值很小的数做分母，会造成浮点溢出出/*over flow*/当当|b|a|时，应尽量避免时，应尽量避免 。361.6 选用算法应遵循的原则选用算法应遵循的原则n五五.选用数值稳定性好的算法，以控制舍入误差选用数值稳定性好的算法，以控制舍入误差高速增长高速增长37小结小结n1.1 引言引言一一.算法影响计算的速度和效率算法影响计算的速度和效率二二.算法影响计算的精度算法影响计算的精度n1.2 误差的种类及其来源误差的种类及其来源一一.误差来源误差来源二二.误差分类误差分类n1.模型误差（描述误差）模型误差（描述误差）n2.观测误差观测误差n3.截断误差（方法误差）截断误差（方法误差）n4.舍入误差舍入误差n1.3 绝对误差和相对误差绝对误差和相对误差一一.绝对误差绝对误差二二.相对误差相对误差38小结小结n1.4 有效数字及其与误差的关系有效数字及其与误差的关系一一.有效数字有效数字二二.有效数位与误差的关系有效数位与误差的关系n1.5 误差的传播与估计误差的传播与估计一一.一元函数情形一元函数情形二二.多元函数情形多元函数情形n1.6 选用算法应遵循的原则选用算法应遵循的原则一一.尽量简化计算步骤，减少乘除运算的次数。尽量简化计算步骤，减少乘除运算的次数。二二.防止大数防止大数“吃掉吃掉”小数小数三三.尽量避免相近数相减尽量避免相近数相减四四.避免绝对值很小的数做分母，会造成浮点溢出避免绝对值很小的数做分母，会造成浮点溢出五五.选用数值稳定性好的算法，以控制舍入误差高速增长选用数值稳定性好的算法，以控制舍入误差高速增长39作业与实验作业与实验n作业（上作业本）：作业（上作业本）：习题一（习题一（P26P26）：）：3 3、6 6、101040