数值分析第1章数值分析与科学计算引论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数值分析与科学计算引论,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数值分析与科学计算引论,*,2024/11/28,数值分析与科学计算引论,1,第,1,章 数值分析与科学计算引论,数值分析的对象、作用与特点,数值计算的误差,数值计算的,误差定性分析与避免误差危害,数值计算中算法设计的技术,2024/11/28,数值分析与科学计算引论,2,1.1,数值分析的对象、作用与特点,1.1.1,研究对象与作用,计算数学,根据实际问题的数学模型提出问题求解的数值计算方法，并对方法进行理论分析和软件实现,.,1.1.2,特点,算法能在计算机上实现，并有好的计算复杂性；,面向计算机，提供切实可行的有效算法；,有可靠的理论分析，能达到精度要求，算法的收敛性与数,值稳定性，,算法的,误差分析；,通过数值实验 证明算法行之有效。,计算机上实现数值计算，解决实际问题,.,1.1.3,实际应用,2024/11/28,数值分析与科学计算引论,3,1.2,数值计算的误差,误差的来源与分类,模型误差,在将实际问题归结为数学模型时，需要对问题作一定的简化和假设。,观测误差,数学模型中需要用到的一些系数、初值等常数来自于测量仪器或统计资料，由于客观条件和仪器精度的限制不可避免有误差。,方法误差,(,截断误差,),模型的准确解,与用,数值方法求得的近似解,之间的误差称为“,截断误差,”。,舍入误差,在上机实际计算时，由于计算机对所运算的对象按机器字长四舍五入而产生的最终计算解与模型的准确解之间的误差。,实际算法,:,有限、四则运算化,（理论计算误差）,2024/11/28,数值分析与科学计算引论,4,误差的产生,实际问题,数学模型,建 模,模型,误差,观测,误差,数值方法,数值解,离散,截断,误差,计算,舍入,误差,实例,2024/11/28,数值分析与科学计算引论,5,大家一起猜？,1,1/,e,将 作,Taylor,展开后再积分,S,4,R,4,取,则,称为,截断误差,|,舍入误差,|,=0.743,由截去部分,引起,由留下部分,引起,例,1,近似计算,解,：,2024/11/28,数值分析与科学计算引论,6,1.2.2,误差与有效数字,绝对误差,/*absolute error*/,其中，,x,准确值，,x,*,x,的近似值,，例如：,上常记为,，称为,绝对误差限,，,一般地，的上限记为,误差绝对值不能超过某个正数,工程,注,：,e*,理论上讲是唯一确定的，可能取正,，,也可能取负。,e*,0 时，,x*,称为强近似值，,e*0 不唯一，当然,越小越具有参考价值。,通常是不知道的,根据具体情况,，可,事先,估计,出误差的范围,误差绝对值的“,上界,”，或称“,误差限,”，即有,2024/11/28,数值分析与科学计算引论,7,例,2,设,=3.1415926,近似值,A,=3.14,它的绝对误差是,0.0015926,，有,-,A,=0.0015926,0.002=0.210,-2,可见，,绝对误差限,*不是唯一的，但,*,越小越好,例,3,又近似值,A,=3.1416,，它的绝对误差是,0.0000074,，有,|-,A,|=0.0000074,0.000008=0.810,-5,例,4,又近似值,A,=3.1415,，它的绝对误差是,0.0000926,，有,|-,A,|=0.0000926,0.0001=0.110,-3,绝对误差限并不能很好地反映近似值的好坏，,x,*,=10,，,x,*,=1,，,y,*,=10000,，,y,*,=5,虽然,y,*,是,x,*,的,5,倍，但在,10000,内差,5,显然比,10,内差,1,好。,2024/11/28,数值分析与科学计算引论,8,相对误差,/*relative error*/,x,*,的,相对误差限,注：,从 的定义可见，实际上被,偷换,成了 ，而后才考察其上限。那么这样的偷换是否,合法,？,严格的说法是，与 是否反映了,同一数量级,的误差？,关于此问题的详细讨论可见教材,p5,。,实际计算中，相对误差通常取为：,2024/11/28,数值分析与科学计算引论,9,例,5,解,结论,?,俗称,“,好坏,”,、,“,多少,”,是相对的,近似数的相对误差是近似数精确度的基本度量,一个近似数 的相对误差越小，则近似数越精确。,结论,设 ，,估计近似数 的绝对误差与相对误差。,但 是 的一个,好的近似,，不是 的,好的近似,。,2024/11/28,数值分析与科学计算引论,10,有效数字,例,6,问：有几位有效数字？请证明你的结论。,4,3,若近似值,x*,的误差限是,某一位的半个单位,该位到,x*,的第一位,非零数字共有,n,位,就说,x*,有,n,位有效数字,.,证明,注,：,如果,x*,是由,x,四舍五入得到的近似值，则,x*,的每一位,都是有效数字。当,x,已知 时，可根据需要产生每位皆有效,的近似值。,有,n,位有效数字,的,x*,可表示为,2024/11/28,数值分析与科学计算引论,11,有效数字与相对误差的关系,有效数字,相对误差限,已知,x,*,有,n,位,有效数字,，则其,相对误差,为,相对误差限,有效数字,已知,x,*,的,相对误差,满足,可见,x,*,至少,有,n,位,有效数字,。,2024/11/28,数值分析与科学计算引论,12,假设,*取到,n,位有效数字，则其相对误差上限满足,要保证其相对误差限小于,0.001%,，只要保证其上限满足,已知,a,1,=3,，则从以上不等式可解得,n,6,log6,，即,n,6,，应取,*,=3.14159,。,例,7,为使,的相对误差小于,0.001%,至少应取几位有效数字？,解,2024/11/28,数值分析与科学计算引论,13,问题,：,这些,公式的形式,有什么,特点,？使你想到什么？,代数运算的误差估计,1.2.3,数值运算的误差估计,2024/11/28,数值分析与科学计算引论,14,函数值的误差估计,问题：,对于,y =f,(,x,),，若用,x,*,取代,x,，将对,y,产生什么影响？,由函数的,泰勒展开式,函数值的,相对误差,（,限,），有：,2024/11/28,数值分析与科学计算引论,15,相对误差条件数,f,的条件数在某一点是,小,大,，则称,f,在该点是,好条件的,坏条件的,。,问题：,若,的近似值为,则 的近似值,于是函数值 的误差,2024/11/28,数值分析与科学计算引论,16,1.3,误差定性分析与避免误差危害,一个工程或科学计算问题往往要运算千万次，由于每步运算都有误差，如果每步都做误差分析是不可能的，也不科学,.,误差积累有正有负，绝对值有大有小，都按最坏情况估计误差限得到的结果比实际误差大得多，这种保守的误差估计不反映实际误差积累,.,概率分析法,威尔金森,(Wilkinson),的,向后误差分析法,穆尔,(Moore),的,区间分析法,.,1.3.1,舍入误差的定量分析方法,2024/11/28,数值分析与科学计算引论,17,例,8,计算,公式一,:,注意此公式,精确,成立,记为,则初始误差,?,?,?!,!,发生了,什麽,?!,1.3.2,数值稳定性与误差的传播,2024/11/28,数值分析与科学计算引论,18,考察第,n,步的误差,我们有责任改变。,造成这种情况的是,不稳定的算法,迅速积累,误差呈递增走势,.,可见初始的小扰动,公式二,:,注意此公式与,公式,一,在理论上,等价,。,方法：,先估计一个,I,N,再反推要求的,I,n,(,n,N,),。,可取,2024/11/28,数值分析与科学计算引论,19,取,我们很幸运！,2024/11/28,数值分析与科学计算引论,20,考察反推一步的误差：,以此类推，对,n,N,有：,误差逐步递减,这样的算法称为,稳定的算法,。,舍入误差的定性分析,一个算法如果输入数据有扰动（即误差），而计算过程中舍入误差不增长,则称此算法是,数值稳定,的，否则此算法就称为,不稳定,的。,数值稳定性,/,*Numerical,Stability,*/,2024/11/28,数值分析与科学计算引论,21,病态问题,输入数据的微小扰动（即误差），引起输出数据（即问题解）的相对误差很大的数学问题。,（,3.3,）,称为,计算函数值问题,的,条件数,.,计算函数值 时，,若 有扰动 ，,相对误差为 ，,函数值 的相对误差为,相对误差比值,1.3.2,病态问题与条件数,病态问题举例,计算函数值问题的条件数,很大的问题,病态问题,2024/11/28,数值分析与科学计算引论,22,函数,它表示相对误差可能放大 倍,.,如 ，,有 ，,自变量相对误差为 ，,函数值相对误差为 ，,一般情况下,条件数 就认为是病态，越大，病态越严重,.,的条件数,若取,这时问题可以认为是病态的,.,计算函数值问题举例,2024/11/28,数值分析与科学计算引论,23,避免相近二数相减。,举例：,a,1,=0.12345,，,a,2,=0.12346,，各有,5,位有效数字。,而,a,2,a,1,=0.00001,，只剩下,1,位有效数字。,几种经验性避免方法：,当,|,x,|1,时：,避免小分母,:,分母小会造成舍入误差增大。,选用稳定的算法。,1.3.3,避免误差危害的若干原则,2024/11/28,数值分析与科学计算引论,24,避免大数,吃,小数,举例：,用单精度计算 的根。,精确解为,算法,1,：,利用求根公式,在计算机内，,10,9,存为,0.1,10,10,，,1,存为,0.1,10,1,。,做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即,1,的指数部分须变为,10,10,，则：,1=0.,00000000,01,10,10,，取单精度时就成为：,10,9,+1=0.10000000,10,10,+0.00000000 10,10,=0.10000000 10,10,大数,吃,小数,x,3.81574,y,0.0001,=,=,38157.4,x,3.81574,y+,y,0.0001+0.00001,=,=,34688.5,2024/11/28,数值分析与科学计算引论,25,算法,2,：,先取,再利用,求和时,从小到大,相加，可使和的误差减小。,举例：,按从小到大、以及从大到小的顺序分别计算,1+2+3+40+10,9,先化简再计算，减少步骤，避免误差积累。,一般来说，计算机处理下列运算的速度为,如计算多项式的值用秦九韶法,(P11).,2024/11/28,数值分析与科学计算引论,26,算法设计的好坏,影响计算结果的精度，好算法大量节省计算时间,.,1.4,数值计算中算法设计的技术,算法设计的一个重要原则,减少运算次数,1.4.1,多项式求值的秦九韶算法,设给定 次多项式,求 处的值,.,直接计算 再相加,加法次数,减少计算量，减少误差,多项式求值,乘法次数,计,算,量,2024/11/28,数值分析与科学计算引论,27,记,（,4.1,）,则,.,求 在 点的值,.,其中,秦九韶算法,计算量,加法次数,乘法次数,优点,由,（,4.1,）,式,2024/11/28,数值分析与科学计算引论,28,对 求导得,故,.,则,（,4.1,）,其中,计算 的秦九韶算法,2024/11/28,数值分析与科学计算引论,29,此处,例,8,设 ，用秦九韶算法求,和 的值,.,用（,4.1,）和（,4.2,）式构造出计算表格（,1-2,）,解,2024/11/28,数值分析与科学计算引论,30,迭代法举例,开方运算,迭代法,数值计算普遍使用的重要方法,迭代法与开方求值,迭代法的构造,假定 ，求 等价于解方程,（,4.3,）,先给定一个初始近似 ，令 ，是一个,校正量，称为增量，,按同一公式重复计算逐次逼近真值的方法,即,舍去高阶项 ，则得,即,