第1章_计算方法概论

1、第1章 计算方法概论 运用数学方法解决科学研究或工程技术问题，一般按运用数学方法解决科学研究或工程技术问题，一般按如下途径进行：如下途径进行：实际问题实际问题模型设计模型设计算法设计算法设计程序设计程序设计上机计算上机计算问题的解问题的解 其中其中算法设计算法设计是计算方法课程的主要内容是计算方法课程的主要内容. . 1 计算方法又称数值分析，是计算数学的重要组成部分。计算方法又称数值分析，是计算数学的重要组成部分。 1 1. .1 1 引言引言21 1. .1 1.1.1 计算方法的意义计算方法的意义 计算方法对于计算速度与增强计算结果的准确性来说，计算方法对于计算速度与增强计算结果的准确性

2、来说，与计算机硬件同等重要。这就导致了计算方法研究领域的与计算机硬件同等重要。这就导致了计算方法研究领域的空前活跃。空前活跃。1 1. .1 1.2.2 计算方法的任务计算方法的任务 计算方法课程研究常见的基本数学问题的数值解法计算方法课程研究常见的基本数学问题的数值解法.包包含了含了数值代数数值代数(线性方程组的解法、非线性方程的解法、线性方程组的解法、非线性方程的解法、矩阵求逆、矩阵特征值计算等矩阵求逆、矩阵特征值计算等)、数值逼近数值逼近、数值微分与数值微分与数值积分、常微分方程及偏微分方程数值积分、常微分方程及偏微分方程的数值解法等的数值解法等.它的基它的基本理论和研究方法建立在数学理

3、论基础之上，研究对象是本理论和研究方法建立在数学理论基础之上，研究对象是数学问题，因此它是数学的分支之一数学问题，因此它是数学的分支之一. 1 1.2.2 算法与效率算法与效率31 1.2.1.2.1 算法算法 进行科学计算，需要构造确定型数值算法，确定型算法进行科学计算，需要构造确定型数值算法，确定型算法可定义为：从给定的已知量出发，按指定的运算顺序，经可定义为：从给定的已知量出发，按指定的运算顺序，经过有限次的四则运算及逻辑运算，可求出给定问题的数值过有限次的四则运算及逻辑运算，可求出给定问题的数值解的完整的计算步骤。解的完整的计算步骤。1 1.2.2.2.2 算法的效率算法的效率 一个算

4、法所需要四则浮点运算的总次数定义为它的计算一个算法所需要四则浮点运算的总次数定义为它的计算量，单位是量，单位是flopflop。由于。由于+ +，- -运算速度很快，可忽略，因此运算速度很快，可忽略，因此，算法的计算量简化为该算法所需要的乘法和除法运算的，算法的计算量简化为该算法所需要的乘法和除法运算的总次数。计算量越小，计算效率就越高。总次数。计算量越小，计算效率就越高。1 1.2.3.2.3 算法的表述形式算法的表述形式 算法的表述形式是多种多样的算法的表述形式是多种多样的. . 1 1 用数学公式和文字说明描述用数学公式和文字说明描述，这种方式符合人们的，这种方式符合人们的理解习惯，和算

5、法的推证相衔接，易于学习接受，但离上理解习惯，和算法的推证相衔接，易于学习接受，但离上机应用距离较大机应用距离较大. . 2 2用框图描述用框图描述，这种方式描述计算过程流向清楚，易于，这种方式描述计算过程流向清楚，易于编制程序编制程序 ，详略难以掌握，详略难以掌握. . 4 4 算法程序算法程序，即，即用计算机语言描述用计算机语言描述的算法，它是面对的算法，它是面对计算机的算法。我们以后讨论的算法，都有现成的程序文计算机的算法。我们以后讨论的算法，都有现成的程序文本和软件可资利用本和软件可资利用. . 但从学习算法的角度看，这种描述方但从学习算法的角度看，这种描述方式并不有利式并不有利. .

6、 3 3 算法描述语言算法描述语言，它是表述算法的一种通用语言。有，它是表述算法的一种通用语言。有特定的表述程序和语句。可以很容易地转化为某种计算机特定的表述程序和语句。可以很容易地转化为某种计算机语言，同时也具有一定的可读性。语言，同时也具有一定的可读性。4 本教材将采用前三种方式表述各种算法本教材将采用前三种方式表述各种算法. .1 1.2.4 .2.4 算法的基本特点算法的基本特点 1 算法常表现为一个无穷过程的算法常表现为一个无穷过程的截断截断： 例例1 1 计算计算 sin sin x的值，的值，40,x 根据根据sinsin x 的无穷级数的无穷级数)!12() 1(! 7! 5!

7、 3sin12753nxxxxxxnn( 1.1) 这是一个无穷级数，我们只能在适当的地方这是一个无穷级数，我们只能在适当的地方“截断截断”，使计算量不太大，而精度又能满足要求，使计算量不太大，而精度又能满足要求. . 如计算如计算 sin 0.5sin 0.5，取，取n=3n=3479625.0!75.0!55.0!35.05.05.0sin7535 据泰勒余项公式，它的误差应为据泰勒余项公式，它的误差应为! 9) 1(94R4, 0( 1.2)791013.3362880)4/(R可见结果是相当精确的可见结果是相当精确的. .实际上结果的六位数字都是正确的实际上结果的六位数字都是正确的.

8、2 算法常表现为一个连续过程的算法常表现为一个连续过程的离散化离散化 例例2 2 计算积分值计算积分值. .1011dxxI将将0 0，1 1分为分为4 4等分，分别计算等分，分别计算4 4个小曲边梯形的面积的个小曲边梯形的面积的近似值，然后加起来作为积分的近似值近似值，然后加起来作为积分的近似值( (如图如图1-1).1-1).记被积记被积函数为函数为 f(x) ，即，即6xxf11)(011yxxy11图1-1计算有：计算有：I0.697 024，与精，与精确值确值0.693 147比较，可知结比较，可知结果不够精确，如进一步细分果不够精确，如进一步细分区区间，精度可以提高间，精度可以提高

9、.3 , 2 , 1 , 0,41iihxhihxfxfTiii2)()(1 3 3 算法常表现为算法常表现为“迭代迭代”形式形式. .迭代是指某一简单算法迭代是指某一简单算法的多次重复，后一次使用前一次的结果的多次重复，后一次使用前一次的结果. .这种形式易于在计这种形式易于在计算程序中实现，在程序中表现为算程序中实现，在程序中表现为“循环循环”过程过程. . 例例3 3 多项式求值多项式求值. . 7nnnxaxaxaaxP2210)(30iiTI 用用tk表示表示xk，uk表示表示(1.4)(1.4)式前式前k+1项之和项之和. .作为初值令作为初值令： (1.5)0001aut 对对k

10、=1,2,n，反复执行：，反复执行： (1.6)kkkkkktauuxtt11 显然显然Pn(x)=un，而，而(1.6)(1.6)式是一种简单算法的多次循环式是一种简单算法的多次循环. . 令令 k=1,2, ,n (1.7)knkknaxvvav10 对此问题还有一种更好的迭代算法对此问题还有一种更好的迭代算法.8011012312012110111)()()()(axaxaxaaxaxaxaxaaxaxaxaaxaxaxaxPnnnnnnnnnnnnnnn 显然显然Pn(x)=vn . 这两种算法都是将这两种算法都是将n次多项式化为次多项式化为n个一次多项式来计算个一次多项式来计算，这种

11、化繁为简的方法在数值分析中，这种化繁为简的方法在数值分析中经常使用经常使用. 下面估计一下以上两种算法的计算量：下面估计一下以上两种算法的计算量： 第一法：执行第一法：执行n次次(1.6)(1.6)式，每次式，每次2 2次乘法，一次加法，次乘法，一次加法，共计共计2 2n次乘法，次乘法，n次加法次加法； 第二法：执行第二法：执行n次次(1.7)(1.7)式，每次式，每次1 1次乘法，一次加法，次乘法，一次加法，共计共计n次乘法，次乘法， n次加法次加法. . 显然第二种方法运算量小，它是我国宋代数学家秦九韶显然第二种方法运算量小，它是我国宋代数学家秦九韶最先提出的，被称为最先提出的，被称为“秦

12、九韶算法秦九韶算法”. . 例例4 4 不用开平方计算不用开平方计算 ( (a0)0)的值的值. .a 假定假定x0是是 的一个近似值，的一个近似值，x0 0 0，则，则 也是也是 的的一个近似值，且一个近似值，且x0和和 两个近似值必有一个大于两个近似值必有一个大于 ，另，另aaaa0 xa0 xa9a一个小于一个小于 ，可以设想它们的平均值应为，可以设想它们的平均值应为 的更好的平均的更好的平均值，于是设计一种算法：值，于是设计一种算法：a10 (k=0,1,2,) (1.8) 如计算如计算 ，取，取x0 =2=2，有，有 (k=0,1,2,)3kkkxaxx211kkkxxx3211计算

13、有：计算有：x0 0=2=2 x1 1=1.75=1.75 x2 2=1.732 142 9=1.732 142 9 x3 3=1.732 050 8=1.732 050 8 可见此法收敛速度很快，只算三次得到可见此法收敛速度很快，只算三次得到8 8位精确数字位精确数字. . 迭代法应用时要考虑是否收敛、收敛条件及收敛速度等迭代法应用时要考虑是否收敛、收敛条件及收敛速度等问题，今后课程将进一步讨论问题，今后课程将进一步讨论. . 1.4 误 差 1.4.1 误差的来源误差的来源 在运用数学方法解决实际问题的过程中，每一步都可能在运用数学方法解决实际问题的过程中，每一步都可能带来误差带来误差.

14、1 模型误差模型误差 在建立数学模型时，往往要忽视很多次要在建立数学模型时，往往要忽视很多次要因素，把模型因素，把模型“简单化简单化”，“理想化理想化”，这时模型就与真实，这时模型就与真实背景有了差距，即带入了误差背景有了差距，即带入了误差. . 2 测量误差测量误差 数学模型中的已知参数，多数是通过测量数学模型中的已知参数，多数是通过测量得到得到. .而测量过程受工具、方法、观察者的主观因素、不可而测量过程受工具、方法、观察者的主观因素、不可预料的随机干扰等影响必然带入误差预料的随机干扰等影响必然带入误差. . 3 截断误差截断误差 数学模型常难于直接求解，往往要近似替数学模型常难于直接求解

15、，往往要近似替代，简化为易于求解的问题，这种简化带入误差称为方法误代，简化为易于求解的问题，这种简化带入误差称为方法误差或截断误差差或截断误差. . 4 舍入误差舍入误差 计算机只能处理有限数位的小数运算，初计算机只能处理有限数位的小数运算，初始参数或中间结果都必须进行四舍五入运算，这必然产生舍始参数或中间结果都必须进行四舍五入运算，这必然产生舍入误差入误差. .11 在数值分析课程中不分析讨论模型误差；在数值分析课程中不分析讨论模型误差；截断误差截断误差是数是数值分析课程的主要讨论对象，它往往是计算中误差的主要部值分析课程的主要讨论对象，它往往是计算中误差的主要部分，在讲到各种算法时，通过数

16、学方法可推导出截断误差限分，在讲到各种算法时，通过数学方法可推导出截断误差限的公式的公式( (如如(1.2)(1.2)式式) )；舍入误差舍入误差的产生往往带有很大的随机的产生往往带有很大的随机性，讨论比较困难，在问题本身呈病态或算法稳定性不好时性，讨论比较困难，在问题本身呈病态或算法稳定性不好时，它可能成为计算中误差的主要部分；至于测量误差，我们，它可能成为计算中误差的主要部分；至于测量误差，我们把它作为初始的舍入误差看待把它作为初始的舍入误差看待. . 误差分析是一门比较艰深的专门学科误差分析是一门比较艰深的专门学科. .在数值分析中主要在数值分析中主要讨论讨论截断误差及舍入误差截断误差及

17、舍入误差. .但一个训练有素的计算工作者，但一个训练有素的计算工作者，当发现计算结果与实际不符时，应当能诊断出误差的来源，当发现计算结果与实际不符时，应当能诊断出误差的来源，并采取相应的措施加以改进，直至建议对模型进行修改并采取相应的措施加以改进，直至建议对模型进行修改.12 1.4.2 误差的基本概念误差的基本概念 1 误差与误差限误差与误差限 定义定义1.11.1 设设x*是准确值，是准确值，x是它的一个近似值，称是它的一个近似值，称e e= =x- -x* *为近似值为近似值x的的绝对误差绝对误差，简称，简称误差误差. 误差是有量纲的量，量纲同误差是有量纲的量，量纲同x，它可正可负，它可

18、正可负. . 误差一般无法准确计算，只能根据测量或计算情况估计误差一般无法准确计算，只能根据测量或计算情况估计出它的绝对值的一个上限，这个上界称为近似值出它的绝对值的一个上限，这个上界称为近似值x的的误差限误差限，记为，记为 x- -x* *，其意义是：，其意义是：x-x* *x+在工程中常记为：在工程中常记为： x* *= = x.如如 l=10.2=10.2. .mmmm，R=1500=1500100100 2 相对误差与相对误差限相对误差与相对误差限 误差不能完全刻画近似值的误差不能完全刻画近似值的精度精度. .如测量百米跑道产生如测量百米跑道产生10cm10cm的误差与测量一个课桌长度

19、的误差与测量一个课桌长度产生产生1cm1cm的误差，我们不能简单地认为后者更精确，还应的误差，我们不能简单地认为后者更精确，还应考考虑被测值的大小虑被测值的大小.下面给出定义下面给出定义：13 定义定义1.21.2 误差与精确值的比值误差与精确值的比值 称为称为x的的相对误差相对误差，记作，记作er.*xxxxe 相对误差是无量纲的量，常用百分比表示，它也可正可相对误差是无量纲的量，常用百分比表示，它也可正可负负. .相对误差也常不能准确计算，而是用相对误差限来估计相对误差也常不能准确计算，而是用相对误差限来估计. 相对误差限相对误差限：|*rrexxxx 实际上由于实际上由于x*不知道，用上

20、式无法确定不知道，用上式无法确定r ，常用，常用x代代x*作分作分母，此时：母，此时：14| xr 以后我们就用以后我们就用 表示相对误差限表示相对误差限.| x 例例5 5 在刚才测量的例子中，若测得跑道长为在刚才测量的例子中，若测得跑道长为1001000.1m0.1m，课桌长为，课桌长为1201201cm 1cm ，则，则显然后者比前者相对误差大显然后者比前者相对误差大.%1 . 01001 . 0) 1 (r%83. 01201)2(r 1.4.3 有效数字有效数字 定义定义1.31.315 定义定义1.41.416 如：如：=3.14159265=3.14159265 则则3.143.

21、14和和3.14163.1416分别有分别有3 3位和位和5 5位有效数字位有效数字. .而而3.1433.143相对于相对于也只能有也只能有3 3位有效数字位有效数字 如如a=0.034537a=0.034537，则近似数，则近似数0.03450.0345有有3 3位有效数字位有效数字又如近似数又如近似数c=30.4c=30.4和和d=30.40d=30.40分别有分别有3 3位和位和4 4位有效数字位有效数字 如计算机上得到方程如计算机上得到方程x3 3- -x-1=0-1=0的一个正根为的一个正根为1.324721.32472，保，保留留4 4位有效数字的结果为位有效数字的结果为1.32

22、51.325，保留，保留5 5位有效数字的结果为位有效数字的结果为1.3247.1.3247.相对误差与有效数位的关系十分密切相对误差与有效数位的关系十分密切. .定性地讲，定性地讲，相相对误差越小，有效数位越多，反之亦正确对误差越小，有效数位越多，反之亦正确. .定量地讲，有如定量地讲，有如下两个定理下两个定理. . 定理定理1.1 设近似值设近似值x=0.=0.a1a2an1010m有有n位有效数字，位有效数字，则其相对误差限则其相对误差限 此定理的证明不难，可作为习题完成此定理的证明不难，可作为习题完成. .111021nra17 定理定理1.21.2 设近似值设近似值x= =0.0.a

23、1a2an1010m m的相对误差限的相对误差限不大于不大于 ，则它至少有，则它至少有n位有效数字位有效数字. .1110) 1(21na 证证 x |( |(a1+1+1）1010m-1m-1由定义由定义1. .3知知x有有n位有效数字位有效数字.nmmnaaxxxxxx105 . 010) 1(10) 1( 21|1111* 例例6 6 计算计算sin 1.2sin 1.2，问要取几位有效数字才能保证相对，问要取几位有效数字才能保证相对误差限不大于误差限不大于0.0.01%. 解解 sin1.2=0.93sin1.2=0.93，故，故a1 1=9,=9,m=0=0 解关于解关于n的不等式的

24、不等式 10-n1810-5=1.810-4.41110%01. 01021nra18 所以取所以取n=4，即可满足要求，即可满足要求. 对有效数字的观察比估计相对误差容易得多，故监视有效对有效数字的观察比估计相对误差容易得多，故监视有效数字是否损失，常可发现相对误差的突然扩大数字是否损失，常可发现相对误差的突然扩大. . 例例6 6 计算计算 ，视已知数为，视已知数为精确值，用精确值，用4位浮点位浮点数计算数计算. .76017591 解解 原式原式=0.1318=0.13181010-2-2-0.1316-0.13161010-2-2=0.2=0.21010-5 -5 . . 结果只剩一位

25、有效数字，有效数字大量损失，造成相对结果只剩一位有效数字，有效数字大量损失，造成相对误差的扩大误差的扩大. .若通分后再计算：若通分后再计算： 原式原式= =就得到就得到4 4位有效数字的结果位有效数字的结果. .下文将会提到相近数字相减会扩下文将会提到相近数字相减会扩大相对误差大相对误差.56101734. 0105768. 01760759119 1.5 设计算法时应注意的原则设计算法时应注意的原则 1.5.1数值运算时误差的传播数值运算时误差的传播当参与运算的数值带有误差时，结果也必然带有误差，问题当参与运算的数值带有误差时，结果也必然带有误差，问题是结果的误差与原始误差相比是否扩大是结

26、果的误差与原始误差相比是否扩大. 1)对函数对函数f(x)的计算的计算:设设x是是x*的近似值，则结果误差的近似值，则结果误差用用泰勒展式泰勒展式分析分析2)*()()*)()(*)(2xxfxxxfxfxf *)()()(xfxfxfe2*)()(*)()(2xxfxxxfxfe )(2)()(| )(|)(|2xfxxfxfe )(| )(|)(|xxfxf忽略第二项高阶无穷小之后，可得函数忽略第二项高阶无穷小之后，可得函数f(x)的误差限估计式的误差限估计式20 2)对多元函数对多元函数f(x1*,x2*,xn*)=A*,设设x1,x2,xn是是x1*,x2*,xn*的近似值，则的近似值

27、，则A=f(x1,x2,xn)是结果的近似值。是结果的近似值。其中其中),(),()(*2*121nnxxxfxxxfAe| ),(),(|*nnxxxfxxxfAA2121)(|),(2*211xOxxxxxxfkkknnk|max*kkkxxx略去高阶项后略去高阶项后)(),()(211kknnkxxxxxfA)10. 1 (21 3）四则运算中误差的传播）四则运算中误差的传播 按（按（1.10）易得）易得:其中其中(1.11)取等号取等号,是因为作为多元函数是因为作为多元函数,加减法的一次函数，泰加减法的一次函数，泰勒展开没有二次余项。勒展开没有二次余项。)()()(2121xxxx)(

28、|)(|)(122121xxxxxx例例7：若电压若电压V=220 5V，电阻，电阻R=300 10 ，求电流，求电流I并计并计算其误差限及相对误差限。算其误差限及相对误差限。解：解：22122121)(|)(|xxxxxxx)11. 1 ()12. 1 ()13. 1 ()(7333. 0300220AI22所以所以)(0411. 090000530010220)(|)(|)(2ARVRRVI)(0411. 07333. 0AI1.5.2 算法中应避免的问题算法中应避免的问题1）避免相近数相减）避免相近数相减 由公式由公式(1.11)(|)(|)(|)(|)()(221212112221211211212121xxxxxxxxxxxxxxxxxxxxxxxxrrr%67333.00411.0)(Ir)()()(2121xxxx23当当x1和和x2十分相近时，十分相近时， x1-x2接近零，接近零，将很大，所以将很大，所以|211xxx)(21xxr和和|212xxx)(),(21xxrr从直观上看，相近数相减会造成有效数位的减少，本章例从直观上看，相近数相减会造成有效数位的减少，本章例6就就是一个例子是一个例子.有时，通过改变算法可以避免相近数相减有时，通过改变算法可以避免相近数相减.大很多，即相对误差将显著扩大大很多，即相对误差将显著扩大.将比将比例例8: 解方程解方程x