数值分析讲稿课件.ppt

1、数值分析（Numerical Analysis）开课单位：计算机与控制学院 张敏洪（数学科学学院）mh_ 考试方式：闭卷。作业占2030，卷面7080。有课外上机时间，讲义、作业及答案可下载。课件、参考书、作业、参考答案：校园网站 主要参考书：主要参考书：1.李庆扬等，数值分析，华中理工大学出版社，武汉，1994。2.丁丽娟等，数值计算方法，北京理工大学，1998。3.David Kincaid,Ward Cheney.王国荣等译.数值分析（Numerical Analysis)第三版2005。4.（美）H.Mathews,D.Fink，数值方法matlab版，电子工业社出版，北京，2002。

2、5.（美）F.施依德，数值分析第二版，科学出版社，北京，2002。Chap.1 绪论绪论 1 数值分析的对象与特点数值分析的对象与特点数值分析：数值分析：研究适合计算机进行科学计算的方法。研究适合计算机进行科学计算的方法。使用计算机、离散。使用计算机、离散。解决科学技术和工程问题的步骤解决科学技术和工程问题的步骤:实际问题实际问题建立数学模型建立数学模型研究计算研究计算方法方法 编程上机计算编程上机计算求的结果求的结果。例如例如:某一地区的地形图某一地区的地形图,用空中航测方用空中航测方法法,空中连续拍照。空中连续拍照。为形成三维地形图为形成三维地形图,建立了一个大建立了一个大型超定线性方程组

3、。型超定线性方程组。采用最小二乘方法求解该方程组采用最小二乘方法求解该方程组的最小二乘解的最小二乘解,然后再整体平滑。然后再整体平滑。编程序编程序,形成一个大型程序形成一个大型程序,上机上机进行计算。进行计算。数值分析课的主要基础与内容数值分析课的主要基础与内容:计算机只能进行加减乘除四则运算和一计算机只能进行加减乘除四则运算和一些简单的函数计算些简单的函数计算(即使是函数也是通过数值即使是函数也是通过数值分析处理分析处理,转化为四则运算而形成了的一个小转化为四则运算而形成了的一个小型软件包型软件包)。1.数值代数数值代数:求解线性方程组的解法求解线性方程组的解法（分直接方法和间接方法），求矩

4、阵的特征（分直接方法和间接方法），求矩阵的特征值与特征向量。值与特征向量。2.数值逼近：插值和数值逼近，数值微数值逼近：插值和数值逼近，数值微分和数值积分。分和数值积分。3.3.方程求解：非线性方程、常微分方方程求解：非线性方程、常微分方程、偏微分方程数值解法。程、偏微分方程数值解法。特点：特点：1.面向计算机。面向计算机。2.有可靠的理论分析（收敛性、稳定性、有可靠的理论分析（收敛性、稳定性、误差分析）。误差分析）。3.要有好的计算复杂性（时间、空间）要有好的计算复杂性（时间、空间）4.要有数值试验。要有数值试验。对算法所要考虑的问题对算法所要考虑的问题:1.计算速度。计算速度。例如例如,求

5、解一个求解一个20阶线性方程组阶线性方程组,用消用消 元法需元法需3000次乘法运算次乘法运算;而用克莱姆法则而用克莱姆法则要进行要进行 次运算次运算,如用每秒如用每秒1亿次乘亿次乘法运算的计算机要法运算的计算机要30万年。万年。2.存储量。存储量。大型问题有必要考虑。大型问题有必要考虑。3.数值稳定性。数值稳定性。在大量计算中在大量计算中,舍入误差是积累还是舍入误差是积累还是能控制能控制,这与算法有关。这与算法有关。209.7 102 2误差的来源与误差分析的重要性误差的来源与误差分析的重要性 误差的来源与种类误差的来源与种类 实际问题实际问题建立数学模型建立数学模型研究计算方研究计算方法法

6、编程上机计算编程上机计算求的结果求的结果。1.模型误差模型误差:在建立数学模型过程中在建立数学模型过程中,不不可能将所有因素均考虑可能将所有因素均考虑,必然要进行必要的简必然要进行必要的简化化,这就带来了与实际问题的误差。这就带来了与实际问题的误差。2.测量误差测量误差:测量已知参数时测量已知参数时,数据带来的数据带来的误差。误差。3.截断误差截断误差:在设计算法时在设计算法时,必然要近似处必然要近似处理理,寻求一些简化。寻求一些简化。例：例：当当 很小时，可用很小时，可用 作为作为 的近似值，其截断误差小于的近似值，其截断误差小于 。例：例：对函数对函数 用用TaylorTaylor展开，用

7、多项式展开，用多项式 近似代替，则数值方法的截断误差为近似代替，则数值方法的截断误差为 2462(1)cos124!6!(2)!nnxxxxxnx212xcos x42 4x()2(0)(0)(0)()(0)1!2!nnnfffP xfxxxn(1)1()()()()(1)!nnnnfRxfxPxxn()f x4.4.舍入误差舍入误差:计算机的字长是有限的计算机的字长是有限的,每一步运算均需每一步运算均需四舍五入四舍五入,由此产出的误差称舍入误差。由此产出的误差称舍入误差。例：例：、1 13 3，取小数点取小数点8 8位、位、1616位。位。数值分析主要讨论截断误差。测量误差数值分析主要讨论截

8、断误差。测量误差看作初始的舍入误差看作初始的舍入误差,数值分析也要从整体数值分析也要从整体来讨论舍入误差的影响来讨论舍入误差的影响,但这儿不讨论模型误但这儿不讨论模型误差。差。误差分析的重要性：误差分析的重要性：可可举例说明举例说明 例：计算并分析误差例：计算并分析误差 (n=0，1，2）。由积分估值）。由积分估值 且由积分性质知且由积分性质知 可设计如下两种算法：可设计如下两种算法：105nnxIdxx11111111000(5)515555nnnnnnnxxxxIdxxdxdxIxxn110001011111min()max()6(1)555(1)nnnxxx dxIx dxnxxn 算法

9、算法1 1：取：取 按公式按公式 (n=0(n=0，1 1，2 2)依次计算依次计算 的近似值。的近似值。设设 。假设计算过程中不产生新。假设计算过程中不产生新的舍入误差，则有的舍入误差，则有 (n=0(n=0，1 1，2 2)误差扩散。误差扩散。1001ln1.25Idxx115nnIIn12,II*000eII*111555nnnnnneIIIIe0(5)nnee 算法算法 2 2：从从 计算计算 ，由由应有应有 。数值稳定，在运算过程中，舍入误差不增大。数值稳定，在运算过程中，舍入误差不增大。nI1nI111()5nnIIn115nnee 01()5nnee 115nnIIn3 3误差的

10、基本概念误差的基本概念 3.1（绝对）误差与（绝对）误差限（绝对）误差与（绝对）误差限 是精确值是精确值,是它的一个近似值是它的一个近似值,称称 是近似值的绝对误差。简称误差。是近似值的绝对误差。简称误差。误差是有量纲的误差是有量纲的,可正可负。可正可负。误差是无法计算的误差是无法计算的,但可以估计出它的一个上但可以估计出它的一个上界。即界。即 ,称称 是近似值是近似值 的误差限的误差限,即即 。x*x*exx*xx*x*xxx 3.2相对误差与相对误差限相对误差与相对误差限 称称 为近似值为近似值 的相对误差的相对误差,记作记作 。相对误差是个相对数相对误差是个相对数,是无量纲的是无量纲的,

11、也可正可负。也可正可负。相对误差的估计相对误差的估计,称为相对误差限称为相对误差限,即即 。实际中实际中,是未知的是未知的,可用可用 来代替来代替 。当当 较小时较小时,因两者的差为因两者的差为:是是 的高阶无穷小，可忽略不计。的高阶无穷小，可忽略不计。*exxxx*xre*rxxxxx*x*rexxexxr2*22*()()rxxxOxxxxxxxxr 3.33.3有效数字有效数字 定义定义:如果近似值如果近似值 的误差限是的误差限是 (某一位某一位数的半个单位数的半个单位),则称则称 准确到小数点后准确到小数点后n位位,并从第一个并从第一个非零的数字到这一位的所有数字均为有效数字。非零的数

12、字到这一位的所有数字均为有效数字。例：例：3.1415926535,3.1416有五位有效数字有五位有效数字,误差限为误差限为0.00005。例：例：近似值准确到小数点后近似值准确到小数点后五位，有三位有效数字。五位，有三位有效数字。510.003400102x*x1102n*x有效数字与误差限的关系：有效数字与误差限的关系：有有n位有效数字位有效数字,标准形式为标准形式为 ，则有则有 。有效位数越多，（绝对）误差限越小。有效位数越多，（绝对）误差限越小。准确到小数点后准确到小数点后3位。位。*x*1210mnxa aa*11102m nxx*5123456.789,9;1.23456789

13、10 5.xnxm例：，*1311101022m nxx 有效数字与相对误差限的关系：有效数字与相对误差限的关系：定理定理1：，若，若 有有n位有效位有效数字，则其相对误差限为数字，则其相对误差限为 反之，若反之，若 的相对误差限的相对误差限 则则 至少具有至少具有n位有效数字。位有效数字。*1210mnxa aa*x(1)1110;2nra*x(1)1110;2(1)nra*x证：证：因因 ，故当，故当 有有n位有效位有效数字时，数字时，。反之，由反之，由 因此，因此，至少具有至少具有n位有效数字。位有效数字。证毕。证毕。定理说明，有效位数越多相对误差限越小。定理说明，有效位数越多相对误差限

14、越小。*1110(1)10mmaxa*x11*110.5 10110102m nnrmaax *11111(1)10100.5 102(1)mnm nrxaa *x*1210mnxa aaL3.4数值计算中误差估计数值计算中误差估计 数值计算中误差的传播：数值计算中误差的传播：对一元函数的计算对一元函数的计算:设设 是是 的近似值。如果的近似值。如果 可微，有可微，有 介于介于 与与 之间，取绝对值得之间，取绝对值得*xx()f x*2()()()()()()2ff xf xfxxxxxx*x*2*()()()()()()2ff xf xfxxx 对多元函数对多元函数 :若若 分别是分别是 的

15、近似值的近似值,则则12(,)nf x xx*12,nxxx12,nxxx*121212(,)(,)(,)nnne f x xxf x xxf x xx*121(,)()()nnkkkkfxxxxxx 四则运算中误差的传播四则运算中误差的传播 四则运算误差限的公式四则运算误差限的公式:这是因为这是因为,故故*1212()()()xxxx*121221()()()x xxxxx*1221*122*22()()(0)xxxxxxxx*12121212121212()e x xx xx xx xx xx xx x*122211()()xxxxxx*1 21222111221()()()e x xx

16、xxx xxxxxx 4 4数值计算中应注意的几个原则数值计算中应注意的几个原则1、关于数值稳定性的算法。关于数值稳定性的算法。一个程序往往要进行大量的四则运算才能一个程序往往要进行大量的四则运算才能得出结果得出结果,每一步的运算均可能会产生舍入误差。每一步的运算均可能会产生舍入误差。在运算过程中在运算过程中,舍入误差能控制在某个范围内的算舍入误差能控制在某个范围内的算法称之为数值稳定的算法法称之为数值稳定的算法,否则就称之为不稳定的否则就称之为不稳定的算法。算法。例例:用分部积分公式得递推式用分部积分公式得递推式:用四位有效数字计算用四位有效数字计算:,nxnIex e dxn1100 1

17、2,nnInIIe11011.I00 6321.II1010 3679.II21120 2642.II 32130 2074.II43140 1704.II 541 50 1480.II65160 1120.II 76170 2160.II 87180 7280nxnxnIex e dxex de111100可以估计出可以估计出 故故 与精确值一位有效数字也没有。这与精确值一位有效数字也没有。这是由于如果是由于如果 有误差有误差 ,不计中间不计中间再产生的舍入误差再产生的舍入误差,该误差随着计算：该误差随着计算：到到 时时 误差扩大了误差扩大了4 4万倍。因而该算法不是稳定的。万倍。因而该算法

18、不是稳定的。neInn11011.I70 04600 1250.I80 04090 1111,II78I0.e400 5 10*()()()nnnnnnnneIInInIn IIne1111111!nen e0I8!eee800840320如果递推式如果递推式 改为由改为由 ,逐步计算逐步计算 直到直到 。计算结果有四位有效数字计算结果有四位有效数字,如果如果 有误差有误差 ,其传播其传播 到所引起的误差仅为到所引起的误差仅为 故该算法是稳定的。故该算法是稳定的。nnInI11nnIIn111.I 70 1124,II65.I 006321I7e7I0!eee07711750402 2、注意避

19、免两个相近数的相减。、注意避免两个相近数的相减。两个相近的数相减两个相近的数相减,有效数字会大大损失。有效数字会大大损失。因两数之差因两数之差x-y的相对误差为的相对误差为 当当x与与y很接近时，两数之差很接近时，两数之差x-y的相对误差的相对误差会很大，有效数字位将严重丢失。会很大，有效数字位将严重丢失。避免办法：进行变换。避免办法：进行变换。*()()()()()rxyxye xe yexyxyxy 例：例：如用四位有效数字计算如用四位有效数字计算:结果只有一位有效数字结果只有一位有效数字;如改为如改为:有四位有效数字。有四位有效数字。避免了两个相近数的相减。避免了两个相近数的相减。.17

20、0130 0384048.1701313 04130 04.11170130 0384013 041317013 例：用四位浮点数计算例：用四位浮点数计算解解:只有一位有效数字只有一位有效数字,有效数字大量损失有效数字大量损失,造成相造成相对误差扩大。对误差扩大。结果仍然有四位有效数字。这说明了算法设计的结果仍然有四位有效数字。这说明了算法设计的重要性。重要性。117 5 97 6 0225110.1318 100.1316 100.2 107597605611110.1734 10759760759 7600.5768 103.3.避免除数的绝对值远小于被除数的绝对值。避免除数的绝对值远小于

21、被除数的绝对值。,当当 时时,舍入误舍入误差会扩大。差会扩大。例例:的舍入误差均为的舍入误差均为 ,而而 ,则则的舍入误差为的舍入误差为:很小的数作除数有时还会造成计算机的溢出而停机。很小的数作除数有时还会造成计算机的溢出而停机。2xyyxxyy xy ,x y30.510 *710yx xy 7311214100.51010.51010 xxxx *1221*122*22()()(0)xxxxxxxx4.4.防止大数吃掉小数。防止大数吃掉小数。计算机在进行运算时，首先要把参加运算的数对计算机在进行运算时，首先要把参加运算的数对阶，即把两数都写成绝对值小于阶，即把两数都写成绝对值小于1而阶码相

22、同的数。而阶码相同的数。如如 ，必须改写成，必须改写成 如果计算机只能表示如果计算机只能表示8 8位小数，则算位小数，则算 出出 ，大数，大数“吃吃”了小数。了小数。这种情况有时允许，有时不允许。这种情况有时允许，有时不允许。9101a10100.1 100.0000000001 10a 100.1 10a 例如例如:被大数吃掉了。被大数吃掉了。如按如按 ,就没有被吃掉。就没有被吃掉。这也是构造算法时要注意的问题。这也是构造算法时要注意的问题。1010,10,abca 1010101010101010100abc b 0acbbb b 例例:一元二次方程一元二次方程x2(109+1)x+109

23、=0其精确解为其精确解为 X1=109,X2=1。如用求根公式如用求根公式:用用8 8位的计算机求解位的计算机求解,有有 及及 ;则则 的值与精确解差别很大。若用的值与精确解差别很大。若用 因此因此,算法的选用很重要。算法的选用很重要。21,242bbacxa21891894104 101010bac 99101109999912(10)10(10)1010,022xx 2x292992422 1012(10)104bbaccxabbac 5 5简化计算步骤简化计算步骤,减少运算次数。减少运算次数。例例:计算计算 的值的值 如果逐个相乘要用如果逐个相乘要用254次乘法。次乘法。若若 只需只需1

24、414次乘法。次乘法。例例:计算多项式的值计算多项式的值:如若按如若按 有有 次乘法运算次乘法运算,计算计算 共需共需 次乘法和次乘法和n n次加法运算。次加法运算。如写成如写成,用递推算法用递推算法:,:,最终最终 ,共需共需n n次乘法和次乘法和n n次加法运算。次加法运算。255248163264128xx xxxxxxx1110()nnnnnP xa xa xax akka xk nPx 1122n nn 1210nnnnPxa xaxaxaxa 01,1,2,.nkkn kuauuxakn nnP xu 255x例：计算例：计算 的近似值，要求误差小于的近似值，要求误差小于 。方法方

25、法1 1：用级数用级数 的前的前n n项部分和来计算。项部分和来计算。，若，若 ，则需，则需 。即要取前十万项求和，计算量大，舍入误差即要取前十万项求和，计算量大，舍入误差积累，将使有效数字丢失。积累，将使有效数字丢失。ln25101111(1)ln21234nn 111Rn51101n510n 方法方法2 2：用级数：用级数 计算。计算。当时当时 ，有，有取前取前5 5项之和作近似值，产生的截断误差为项之和作近似值，产生的截断误差为 此算法有效。此算法有效。224111ln2(1)13521nxxxxxxn13x22111ln2133 95 9(21)9nn25672111()3 11 913 915 9R 522111(1)31 1999545211113119121191019