哈尔滨工程大学工程算法课件1绪论.ppt

1、1工程常用算法21 绪论 第第1 1节节 数值算法概论数值算法概论 第第2 2节节 预备知识与误差预备知识与误差3第第1 1节数值算法概论节数值算法概论 数值计算已经是计算机处理实际问题数值计算已经是计算机处理实际问题的一种关键手段。的一种关键手段。它使各科学领域从定性分析阶段走向它使各科学领域从定性分析阶段走向定量分析阶段，从粗糙走向精密。定量分析阶段，从粗糙走向精密。42.2.计算机数值方法的研究对象与特点计算机数值方法的研究对象与特点5计算问题计算问题 2*123121122120038300,1A,A3,;(),P,P;14.1;Tbaxxxxbxx x xyP xx xxy P xy

2、xx xxdxabxyxyy xy 1.求方程在上的根；2.求解线性方程组其中 为 阶可逆方阵，3.已知为上的直线，满足求计算定积分I=5.解常微分方程初值问题6例例:10I5nnxdxx计算 7例如例如105nnxIdxx1018161.5,ln1 12.,0 015.95nnnnIIInIIInnInI11111005155nnnnnxxIIdxxdxxn构造算法如下：018110161.5,ln51 12.,0.01955nnnnnnnnxIIIdIIIInxxIIn91018161.5,ln112.,0 015.95nnnnIIInIIInnInI对格式对格式1，如果前一步有误差则被放

3、大，如果前一步有误差则被放大5倍倍加到第一步。加到第一步。对格式对格式2，为稳定格式对舍入误差有抑制，为稳定格式对舍入误差有抑制作用。作用。原因：原因：称为不稳定称为不稳定格式格式10误差的传播与积累误差的传播与积累例：例：蝴蝶效应蝴蝶效应纽约的一只蝴蝶翅膀一纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起了台风来了拍，风和日丽的北京就刮起了台风来了以上是一个以上是一个病态问题病态问题113.3.数值算法数值算法 针对输入与输出都是数值的数学问题针对输入与输出都是数值的数学问题 2121122300,3niinyxyxxx xxhy xhy xy xy xy xy xhyxx求解微分方程将其变成数

4、值问题，即将其“离散化”,离散化是将非数值问题的数学模型化为数值问题的主要方法，这也是计算方法的其解：任务之一。12计算方法的主要任务计算方法的主要任务:1.1.将计算机上不能执行的运算将计算机上不能执行的运算化为化为在计算机上可执在计算机上可执行的运算行的运算.2.2.针对所求解的数值问题研究在计算机上可执行的针对所求解的数值问题研究在计算机上可执行的且有效的计算公式且有效的计算公式.3.3.因为可能采用了近似等价运算因为可能采用了近似等价运算,故要进行误差分析故要进行误差分析,即数值问题的性态及数值方法的即数值问题的性态及数值方法的稳定性稳定性.13数值算法是指有步骤地完成解数值问题的过程

5、数值算法是指有步骤地完成解数值问题的过程.数值算法有四个特点数值算法有四个特点:1.1.目的明确：目的明确：2.2.定义精确：定义精确：3.3.算法可执行：算法可执行：4.4.步骤有限步骤有限：算法必须有明确的目的算法必须有明确的目的,其条件和其条件和结论均应有清楚的规定结论均应有清楚的规定对算法的每一步都必须有精确的对算法的每一步都必须有精确的定义定义算法中的每一步操作都是可执行算法中的每一步操作都是可执行的的算法必须在有限步内能够完成解算法必须在有限步内能够完成解题过程题过程14例如例如 给出等差数列给出等差数列1,2,3,10000的求和的求和 算法算法算法构造如下算法构造如下:1.取取

6、N=0,S=0 记数器置零记数器置零2.N+1 N,S+N S3.若若N 10000,转转2，否则，否则4.输出输出N,S15255X计算例如：例如：255254X=XXXX 个乘法.计算 工作量：N=254flop2.255248163264128X=X XXXXXXX=14flop 8N计算工作量：，个储存空间16第第2 2节预备知识与误差节预备知识与误差1.1.模型误差模型误差 在建立数学模型过程中在建立数学模型过程中,要将复杂的现象抽象归结为数学模要将复杂的现象抽象归结为数学模型型,往往要忽略一些次要因素的影响，而对问题作一些简化往往要忽略一些次要因素的影响，而对问题作一些简化,因因此

7、和实际问题有一定的区别此和实际问题有一定的区别.2.2.观测误差观测误差 在建模和具体运算过程中所用的数据往往是通过观察和测在建模和具体运算过程中所用的数据往往是通过观察和测量得到的量得到的,由于精度的限制由于精度的限制,这些数据一般是近似的这些数据一般是近似的,即有误差即有误差.3.3.截断误差截断误差 由于计算机只能完成有限次算术运算和逻辑运算由于计算机只能完成有限次算术运算和逻辑运算,因此要将因此要将有些需用极限或无穷过程进行的运算有限化有些需用极限或无穷过程进行的运算有限化,对无穷过程进行对无穷过程进行截断截断,这就带来误差这就带来误差.一、误差的种类及来源一、误差的种类及来源17如：

8、如：2335723412!3!sin3!5!7!ln 1+2!3!4!xxxexxxxxxTaylorxxxxx 展开若将前若干项的部分和作为函数值的近似公式，由于以后各项都舍弃了，自然产生了误差。184.4.舍入误差舍入误差 在数值计算过程中还会遇到无穷小数在数值计算过程中还会遇到无穷小数,因计算机受到机器字长的限制因计算机受到机器字长的限制,它它所能表示的数据只能有一定的有限位数所能表示的数据只能有一定的有限位数,如按四舍五入规则取有限位数如按四舍五入规则取有限位数,由此由此引起的误差引起的误差=3.141592652=1.41421356211=0.16666666636！=3.1415

9、92672=1.414213611=0.1666736！数学模型一旦建立，进入具体计算时所考虑数学模型一旦建立，进入具体计算时所考虑和分析的就是和分析的就是截断误差和舍入误差截断误差和舍入误差。19二、误差与有效数字二、误差与有效数字o绝对误差绝对误差o相对误差相对误差2*10*=0.7430.006xexxxxxexxedx绝对误差其中 为精确值，为 的近似值。的上限记为，称为，工程上常记为例限如：*reex*rxx的定义为相对误差上限20o有效数字有效数字121*m-n0.1000.5 1010mnm nnxa aaaxxaxn 用科学计数法，记其中若即 的截取按四舍五入规则，则称 为有

10、位有效数字，精确到。*1*31 4*=3.1415926535897932=3.1415=0.31415 100.5 100.5 104例：；问：有几位有效数字？请证明你的结论。证明：，and有 位有效数字，精确到小数点第3位21例如例如*-6-66*662.718281822.71828,.0.000 001820.000 00182=2 102 102.718 282 100.71 102.718 28rreeEeeEe 已知，其近似值为e求 的绝对误差限 和相对误差限解：绝对误差0.000002 2 10*r和并不是唯一的22*3*5*7.=3.141592653.1420.000 40

11、73.141590.000 002 653.141592 70.000 000 04若 经四舍五入取小数点后3、5、7位数的近似值，求绝对误差限解：0.5 100.5 100.5 10例如可见可见,经四舍五入取近似值经四舍五入取近似值,其绝对误差限将不其绝对误差限将不超过其末位数字的半个单位超过其末位数字的半个单位23*12m*0.100.5 10.1.kk nxxxa aaExxmnxnmnxm 若 作为 的近似值满足：则时，定理至少有 位有效数字则时，恰好有 位有效数字*14*225*6360.2183218.040.0021832.18 1032.18040.21800 105xxxxx

12、x 求下列四舍五入近似值的有效数字个数例.个个个个如个个24*123*1 21*1 22*1 23*12*12*33.9534.03.944.03.950.050.5 103.93.950.050.5 1043.950.050.5 101.xxxxxxxxxxxxxxx设有 个近似值根据定理 知、都至少有两个有效数字即、都具有两个有效数字也至少具有两个有例如效数字吗？实际上只有1位25*11*111*0.001%1102%1100.001%23,6log6,6=3.14159.nrnrnaaann 为使的相对误差小于，至少应取几位有效数字？解:假设取到 位有效数字，则其相对误差上限为要保证其相

13、对误差小于0.001，只要保证其上限满足已知则从以上不等式可解得即，应取例:26三、数值运算的误差估计三、数值运算的误差估计1.1.函数值的误差函数值的误差*12*11n1212n,=,nnAf x xxx xxx xxAA f x xxA假设 要计算多元函数值，已知，为的近似值，于是可求 的近似值，下面估计 的绝对误差及相对误差。1212,nnx xxf x xx这一问题也可以说成：由于初始数据有误差，引起计算 运算 得到的结果有误差，如何估计初始数据的误差对计算结果的影响。27函数值函数值A的绝对误差的绝对误差 *1212*1212*111,1,2,Tnninnnjjjjnnjjjx xx

14、 xx xjjjf x xxxx xxTaylore xinAAf x xxf x xxf xxxxf xf xe Ae xe Ae xxx于是有或利用在点,的展开，且设,都很小 即初始数据误差很小，因而可略去高阶项，,者28函数值函数值A A的相对误差的相对误差 *110,0,1,jnjrrjjjnjxxjxxjAxjnAxe Af xeAexAf xxxf xf xxL设则 的相对误差为因子 jrjrrxexeAeA反映了 的相对误差对相对误差的影响程度，称这些因子为计算问题的条件数。若这些因子的绝对值很大 条件数很大。则可能很大，即与绝对值很大的因子相对应的初始数据有微小的误差都可能引起

15、A有很大的误差。29加、减、乘、除运算的误差估计加、减、乘、除运算的误差估计1,ix inA L病态问题或破坏条件问题如果问题的数据有微小误差，都会引起计算结果 有很大误差，称这种问题为。多个数据进行加、减、乘、除等运算所得结果的误差估计是上述函数值误差说明：的特例。2*1312312311231231.21,3.65,9.811;,njjx xjxxxx xxf xfx xxe Ae xxfffe fxxxxxx设都精确到小数点后两位。试估计由这些数据计算的相对误差解：令则由知例：30 21232112322221230.5 10,3.65,1.21,1.3.65 1.21 10.5 102

16、.93 10.2.93 100.206 10.1.21 3.659.81rxxxfffxxxxxfffx xx其中636321,21.4,1132 2,9970 2213222f 计算利用下列等式计算，哪一个得得到的结果最好？，例：31 L6666663363363*612解：210.00505063,若取 21.4，则111121=0.00523282.41.4+12+122132 232.80.008113210.005125332.832 24219970 299701.411经比较得知以计算的结果最好，下面进行理论分析32 2令2近似值为1.4,并令1,xxfxxfx 3334*323

17、2,997021.40.02xfxxfxxxx32*7*112*224*33*4431,2,3,4,610.0146 320.246 320.005317013+2 2iifxfxie fxfxxxxe fxfxxxxe fxfxxxxe fxfxxx上面是用作为的近似，由函数的误差估计式可知由此可见计算时误差最小。这些例题再次表明一些表达式在理论上是等价的，但在数值计算的过程中并说明：不等价。33四、误差危害的防止四、误差危害的防止10001100051512345,0.10.4.0.12345 10.0.4,0.000004 10,01.iiiiiiiAA下面举例来解释大数“吃”小数的过程

18、，假设在五位十进制计算机上计算其中先把运算的数字写成规格化防止大数“吃”小数形式由于在计算机内进行加减时要对阶。若取对阶时在五位的计算机中表示为机器。3455550.12345 100.000004 100.000004 100.12345 10A因此ii1000331555550.1 100.4 100.001 100.12345 100.004 100.12345 101244512745iiAA符号表示机器中相等。这个结果显然不是我们希望的，产生这个结果的原因是由于运算中出现大数1234“吃掉”小数 造成的，如果计算时先把数量级相同的1000个 相加，最后再加上12345就不会出现大数“

19、吃”小数的现象。这时，有说明：说明：防止大数防止大数“吃吃”小数的方法：小的数尽量先加、减。小数的方法：小的数尽量先加、减。352.2.要避免除数绝对值远小于被除数的绝对值的除法要避免除数绝对值远小于被除数的绝对值的除法 ,0,rrxxxeexeyyx eyyy用绝对值小的数作为除数的误差会增大，事实上，由于若可能很大因此应尽量避免。1212120.0000111222000000.50000253999981999980.999995199999xxxxxx例：线性方程组其准确解为364111211112441112100.100010 0.100010 0.100010 0.200010

20、0.100010 0.200021100.1000/2,100.100010 0.100010 0.100010 xxxxxx现在四位浮点数十进制（仿机器实际计算）下用消去法求解,上述方程写成若第 个方程减去第 个方程除以则出现用小的数作分母，并导致大数吃小数得到6621210.2000100.20000,1,xxxx由此解出显然严重失真。若反过来用第2个方程消去第1个方程中含有 的项。则避免了大数被小数除，得到37说明：说明：o 不难分析可得小数作分母会使误差放大，从而可能不难分析可得小数作分母会使误差放大，从而可能会掩盖所求结果的有效数字。会掩盖所求结果的有效数字。o 通过对上例的讲解，体

21、会如何在算法过程中尽量避通过对上例的讲解，体会如何在算法过程中尽量避免小数作分母。免小数作分母。理论上相等，数值结果不一定相同理论上相等，数值结果不一定相同66211112112100.1000100.100010 0.200010 0.100010 0.20000.5000,10 0.10001.000 xxxxx由此求得相当好的近似解383.3.避免相近数相减避免相近数相减说明：说明：相近数相减会损失有效数位，从而增大相对误差。相近数相减会损失有效数位，从而增大相对误差。7773272731101 cos2cos20.9994.101 cos2101 0.99946 101 cos2sin

22、2101 cos22 sin 1106.13 10sin10.0175.AAxxA例：计算用四位数字表示由于直接代入计算可得只有一位有效数字，若利用则具有三位有效数字此例说明可通过改变计算公式避免或减少有效数：字的损失。392sin1 cos1 cosxxx当然我们还可以通过恒等式：达到类似的目的。121122lglglg111xxxxxxxxxxx 如果 和 很接近时，由用右边的算式可避免有效数字的损失。当 很大时，由知，也可用右端的算式代替左端算式，避免相近类似地，数相减。40 *2*,2f xf xxxfxf xf xfxxxxx此外，若但 与 并不接近时，可用泰勒展开取右端的有限项近似

23、左端，避免相近数相减。如果无法改变算式，则采用增加有效位数进行计算；在计算机上则采用双倍字长运算。但这要增加计算机计算时间和多占内存单元412121*1112637.941610863,863863,637.9487.940.06,118630.062715.94863xxxxxxxx 例：已知有3位有效数字。求二次方程的较小正根，要求有3位有效数字。解：容易得到方程的两个根：故此方程的最小正根为若将直接代入。则至多只有一位有效数字。若改用则方程最小正根的近似值具有3位有效数字。424.4.避免使用不稳定的算法避免使用不稳定的算法 稳定性算法：稳定性算法：一个算法如果受初始误差的影响较小，一个

24、算法如果受初始误差的影响较小，便说这个算法具有较好的稳定性，否则便说便说这个算法具有较好的稳定性，否则便说这个算法的稳定性不好。这个算法的稳定性不好。下面我们通过几个例子来说明如何避免使用不下面我们通过几个例子来说明如何避免使用不稳定的算法稳定的算法43 110111100012011211,0,1,10,1,1311112!7,0.nxnnnxnnkIex e dx nIInInIex e dxeIIIIekeekke LLLL例1.计算并估计误差。解：由部分积分可得计算 的递推公式若计算出 代入上式，可逐次求出，的值。要计算 就要先计算，若用泰勒多项式前 项部分和作为的近似。即并取保留四位

25、小数计算，则得147367911R=0.367910.8!4e，截取误差44 000180.632130.632110,1,0nnnnnIIIIAInInIII 计算过程中小数点后五位数字按四舍五入原则舍入，由此产生的舍入误差这里先不讨论，当初值取为时，用计算 的近似递推公式计算结果见下表的 列，从表中看到 出现负值，这与一切相矛盾。45 11100111001090111141=11,2,minmaxnnxnxnnnnnnnnnexex dxInxex dxnIIIIIIInIEnEnee L下面来分析上述算法：实际上，由积分估值得因此，当较大时，用上述计算结果 近似 显然是不正确的。那么什

26、么原因使计算结果错误呢？设E初值误差，下面考虑它对后面那结果的影响令E由得4600001!nnnEn EIEIEn 容易推得这说明 有误差则 的误差就是的倍。4080881918,10,=80249,11010nEEEIIneI例如，若则！这说明 完全我们现在换一种方案不接近 了。由取得47 1*99*98761*9*1*-400*0110.06842 1010=0.068411,9,8,11=!nnniiineIIIIIIIIBIInnIIIEIIEEn我们粗略取然后将公式倒过来计算，即由 算出，公式为计算结果见上表的 列，虽然初始数据不是很精确，但我们发现 与 一样，误差也不超过10，令容

27、易下面来分得到析原因：48 *09*!.ABAnnnnEIEAInIE即因此，尽管较大，但用于在上述算法中误差逐近缩小，故可用 近似反之，当用方案计算时，尽管初值 相当准确，由于计算过程中的误差是逐步扩大的，因而计算结果越来越不可靠，即此例说明。在数值计算中如不注意误差分析，用了类似方案的计算公式。就不会出现“差之毫厘，失之千里”的错误比缩小了倍，算法是不稳定算法结果。尽管数值计算中估计误差，算法是稳定算比较困难法。，我们仍应重视计算过程的误差分析49-1010*00*200*110000*2221111*1010102=101,1,2,.21.413=21.41,1102=10-1 10+1=1010=101 101101010nnnyyynyyyyyyyyyyyyyyyyyyyy 例：序列 满足递推关系若有 位有效数字，计算到时误差有多大？这个计算过程稳定吗？解：因，于是：类推有，可见这个计算过程不稳定。505.5.注意简化计算步骤，减少运算次数注意简化计算步骤，减少运算次数说明：说明：一般来说运算次数减少，则计算过程的积累一般来说运算次数减少，则计算过程的积累误差有可能下降误差有可能下降