计算方法第一章ppt

,Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,计算方法讲义,主 讲：佘红伟,Email,：,第一章 绪 论,内容提要,1.1,引 言,1.2,误差的度量与传播,1.3,选用算法时应遵循的原则,1.1,引 言,课程特点,数值分析或数值计算方法主要是研究,如何运用计算机去获得数学问题的,数值解,的理论和方法。,对那些在经典数学中，用解析方法在理论上已作出解的存在，但要求出他的解析解又十分困难，甚至是不可能的这类数学问题，数值解法就显得不可缺少，同时有十分有效。,鉴于实际问题的复杂性，通常将其具体地分解为一系列子问题进行研究，本课程主要涉及如下几个方面问题的求解算法：,非线性方程的近似求解方法；,线性代数方程组的求解方法；,函数的插值近似和数据的拟合近似；,积分和微分的近似计算方法；,常微分方程初值问题的数值解法；,矩阵特征值与特征向量的近似计算方法；等等,本课程主要内容,计算机解决科学计算问题的主要过程,实际问题,数学模型,数值计算方法,程序设计,上机运行求出解。,其中：,实际问题,数学模型,：由实际问题应用科学知识和数学理论建立数学模型的过程，是应用数学的任务,.,数值计算方法,程序设计,计算结果,：根据数学模型提出求解的数值计算方法，直到编出程序上机算出解，是计算数学的任务。,算法分类,分类方法,1,：若算法包含有一个进程则称其为,串行算法,，否则为,并行算法,。,分类方法,2,：从算法执行所花费的时间角度来讲，若算术运算占绝大多数时间则称其为,数值型算法,，否则为,非数值型算法,。,本课程介绍数值型串行算法。（其它类型算法参阅数据结构、并行算法等课程。）,算法的可靠性,可靠性,：可靠性包括原问题的适定性算法的收敛性、稳定性等。,适定性：,是指解存在、惟一，且解对原始数据具有连续依赖,收敛性：,是研究当允许计算步越来越多时，是否能够得到越来越可靠的结果，也就是研究截断误差是否能够趋于零,对于给定的算法，稳定性分析是指随着计算过程的逐步向前推进，研究观测误差、舍入误差对计算结果的影响是否很大。,本课程的学习方法,尽管我们所学算法有限，但许多仍有学多学生会觉得公式多，理论分析复杂。我们提出如下的几点学习方法，仅供初学者参考。,1,、以算法的理论分析为基础，理解记忆公式；,2,、理解每章算法建立的数学背景、数学原理和基本线索；,3,、熟练掌握所学基本算法；,4,、从算法的理论分析中学习推理证明方法，提高推理证明能力；,5,、认真进行数值计算的训练。,1.2,误差知识,内容提要：,一、误差的来源及其分类,二、误差的度量,三、误差的传播,一、误差来源及其分类,1),模型误差（描述误差）,反映实际问题有关量之间的计算公式（数学模型）通常是近似的。,2,）观测误差,数学模型中包含的某些参数是通过观测得到的。,在计算方法中不研究这两类误差，总是假定数学模型是正确合理的反映了客观实际问题,。,3,）截断误差（方法误差）,数值方法精确解与待求解模型的理论分析解之间的差异。,这是由于我们需要将无穷过程截断为有限过程，而使得算法必须在有限步内执行结束而导致的。,例如：,4,）舍入误差,在实现数值方法的过程中，由于计算机表示浮点数采用的是有限字长，因而仅能够区分有限个信息，准确表示某些数，不能准确表示所有实数，这样在计算机中表示的原始输入数据、中间计算数据、以及最终输出结果必然产生误差，称此类误差为舍入误差。,例如：利用计算机计算,e,的近似值,e,n,时，实际上得不到,e,n,的精确值，只能得到,e,n,的近似,e,*,；,这样,e,*,作为,e,的近似包含有,舍入误差,和,截断误差,两部分：,二、误差的度量,绝对误差,相对误差,有效数字,各种度量之间的关系,1.,绝对误差,绝对误差定义：近似值减准确值,绝对误差限：,2.,相对误差,Remark,:,绝对误差限虽然能够刻划对同一真值不同近似的好坏，但它不能刻划对不同真值近似程度的好坏。,3.,有效数字,为了规定一种近似数的表示法，使得用它表示的近似数自身就直接指示出其误差的大小。为此需要引出有效数字和有效数的概念。,有效数,：当,x,*,准确到末位，即,n=p,，,则称,x,*,为,有效数,。,举例：,x=,x,1,*,=3.141,x,2,*,=3.142,3,位有效数字，非有效数,4,位有效数字，有效数,Remark1,:,有效数的误差限是末位数单位的一半，可见有效数本身就体现了误差界。,Remark2,:,对真值进行四舍五入得到有效数。,Remark3,:,准确数字有无穷多位有效数字。,Remark4,:,从实验仪器所读的近似数（最后一为是估计位）不是有效数，估计最后一位是为了确保对最后一位进行四舍五入得到有效数。,例,从最小刻度为厘米的标尺读得的数据,123.4cm,是为了得到有效数,123.cm,读得数据,156.7cm,是为了得到有效数,157.cm,。,4.,误差度量间的联系,绝对误差与相对误差,绝对误差与有效数字,相对误差与有效数字,定理证明,证毕,Remark,1,、,该定理实质上给出了一种求相对误差限的方法。,2,、仅从 并不能保证,x,*,一定具有,n,位有效数字。如,设其近似值,a=0.484,，,其相对误差为：,我们并不能由此断定,a,有两位有效数字，因为,例题,解：,三、误差的传播,概念,：近似数参加运算后所得之值一般也是近似值，含有误差，将这一现象称为,误差传播,。,误差传播的表现：,算法本身可能有截断误差；,初始数据在计算机内的浮点表示一般有舍入误差；,每次运算一般又会产生新的舍入误差，并传播以前各步已经引入的误差；,误差有正有负，误差积累的过程一般包含有误差增长和误差相消的过程，并非简单的单调增长；,运算次数非常之多，不可能人为地跟踪每一步运算,。,初值误差传播：假设每一步都是准确计算，即不考虑截断误差和由运算进一步引入的舍入误差，,仅介绍初始数据的误差传播规律。,研究方法：,泰勒,（,Taylor,）,方法,n,元函数,复习泰勒公式,泰勒公式分析初值误差传播,相对误差：,进而得到如下绝对误差限和相对误差限传播关系：,对于一元函数，有如下初值误差传播近似计算公式：,二元函数算术运算误差传播规律,绝对误差限,相对误差限,尽量避免相近的数相减,例,x=52.127 x,*,=52.129,四位有效数字,y=52.123 y,*,=52.121,四位有效数字,A=,x-y,=0.004 A,*,=x,*,-y,*,=0.008,零位有效数字,结论：避免相近数相减,1.3,数值试验与算法性能比较,一些避免相近数相减示例,当,|x|1,时,当,|x|1,时,两种算法的相对误差图比较,尽可能避免绝对值很小的数做分母，防止出现溢出。,当,a,b,中有近似值时，由,若 ，则 可能很大。当,a,b,都是准确,值时，由于 很大，会使其它较小的数加不到,中而引起严重误差，或者会发生计算机“溢出”，导致计算无法进行下去。,算例,用不同位数的浮点数系统求解如下线性方程组,算法,1,：顺序消去法，分别保留,4,位和,7,位小数进行计算；,算法,2,：将第,1,个和第,2,个方程交换次序后，使用消去法分别保留,4,位和,7,位小数进行计算；,准确解：,算例,算法,1a,0.0000,0.10,10,1,0.5000,0.25,10,7,算法,2a,0.2500,0.75,10,7,0.5000,0.25,10,7,算法,1b,0.2600000,0.40,10,1,0.4999987,0.10,10,6,算法,2b,0.2500020,0.50,10,8,0.5000000,0.25,10,7,计算结果,选用数值稳定性好的算法,。,定义,：一个算法,如果在运算过程中舍入误差在一定条件下能够得到控制,或者舍入误差的增长不影响产生可靠的结果,则称该算法是数值稳定的,否则称其为数值不稳定,.,例：计算如下积分近似值的两种方案比较,方法,1,：,方法,1,计算结果,方法一结果分析,方法一分析：计算结果表明,舍入误差的传播近似依,5,的幂次进行增长,因而是一种不稳定的方法。,方法二：,由此分析知，该方法是稳定的。关于初值的近似可由下面式子得到：,方法,2,计算结果,总之,除了算法的正确性之外,在算法设计中至少还,应,:,1,尽量避免两个相近的近似数相减,;,2,合理安排量级相差很大的数之间的运算次序,防止大数,吃掉,小数,;,3,尽可能避免绝对值很小的数做分母,;,4,防止出现溢出,;,5,简化计算步骤以减少运算次数,;,6,选用数值稳定性好的算法,.,本章知识结构图,本章典型例题,例,1:,指出如下有效数的有效数字位数并计算绝对误差限和相对误差限。,解,:1,）,x,*,有,2,位有效数字，,绝对误差限为：,相对误差限为：,2,）,y,*,有,3,位有效数字，,绝对误差限为：,相对误差限为：,3,）,z,*,有,5,位有效数字，,绝对误差限为：,相对误差限为：,解,:,由题意知，近似数,x,*,的绝对误差限 ，相对误差限 。,例,2:,已知 试求 的相对误差限。,注意：此处正好有：,解,:,例,3:,已知桌子长宽近似值 ，并且已知 ，求近似面积 的绝对误差限和相对误差限。,例,4:,下列公式如何变形才能使数值计算得到比较精确的结果。,