[工学]计算方法第一章r课件.ppt

1、计算方法计算方法吴开谡吴开谡教材：西安交通大学出版社教材：西安交通大学出版社 计算方法计算方法作者：邓建中作者：邓建中第一章第一章 计算方法的一般概念计算方法的一般概念1 计算方法的意义、内容与方法计算方法的意义、内容与方法实际问题实际问题数学模型数学模型数值计算方法数值计算方法程序设计程序设计计算机计算出结果计算机计算出结果应用数学应用数学计算数学计算数学计算数学的根本任务是研究怎样通过计算计算数学的根本任务是研究怎样通过计算机所能执行的基本运算（加、减、乘、除机所能执行的基本运算（加、减、乘、除等），求出所研究的问题的数值解或近似等），求出所研究的问题的数值解或近似数值解。数值解。由基本运

2、算和运算顺序的规定所构成的完由基本运算和运算顺序的规定所构成的完整的解题步骤，称为算法。整的解题步骤，称为算法。1、构造计算机能用的算法：、构造计算机能用的算法：例例1：计算：计算sinx，x 0，/4例例2：求解函数方程：求解函数方程f(x)=0.35721sin3!5!7!(21)!nnxxxxxxRn例例3：求解常微分方程：求解常微分方程0(,),(0)yf x yxa byy 1(,)nnnnyyhf xy一个具体的例子：一个具体的例子：迭代格式为：迭代格式为：2,0,1(0)1xyyxyy 1(2/)nnnnnyyh yxy精确解：精确解：()12y xxxn0.10.20.30.4

3、0.51yn1.11.19181.27741.35811.43511.7848yn1.09591.18111.26621.34341.41641.7379Y(xn)1.09541.18321.26491.34161.41421.73202、怎样才能算的又快又省：、怎样才能算的又快又省：算法要既要节省内存又要运算速度快。算法要既要节省内存又要运算速度快。例：计算多项式：例：计算多项式：需需10次乘法次乘法4次加法。次加法。4次乘法次乘法4次加法。这是多项式计算的次加法。这是多项式计算的秦九韶秦九韶算法算法。3次乘法次乘法5次加法。次加法。4320.06250.4251.2151.9122.129

4、6xxxx(0.06250.425)1.215)1.912)2.1296xxxx22(0.50.6)0.50.7(0.50.6)0.80.9xxx下面给出下面给出秦九韶秦九韶算法的一般计算格式。算法的一般计算格式。对于多项式对于多项式计算计算x=a的值的值p(a)，1011()nnnnp xa xa xaxa001,1,2,()kkknbabaabknp ab记第记第k个内括号的值为个内括号的值为bk，记记b0=a0，bn=p(a)，则则秦九韶秦九韶算法算法计算公式为计算公式为对于复杂大型的计算，计算速度与内存节省具对于复杂大型的计算，计算速度与内存节省具有决定意义！有决定意义！例，例，解代数

5、方程解代数方程：用用Cramer法则解，法则解，11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb/,1,2,kkxDDkn3计算结果可靠计算结果可靠计算机在计算过程中对数有要求与限制。计算机在计算过程中对数有要求与限制。不符不符合要求的作近似处理，用近似数计算，有时合要求的作近似处理，用近似数计算，有时会对计算带来较大影响。会对计算带来较大影响。例：例：解为：解为：x1=x2=x3=1123123123111123611113234121114734560 xxxxxxxxx如近似为：如近似为：则解为：则解为：123

6、1231230.500.331.80.500.330.251.10.330.250.200.78xxxxxxxxx1236.222,38.25,33.65xxx 例：求方程例：求方程 根，如根，如 z1 0系 数系 数 2 1 0 略 有 误 差，为略 有 误 差，为 210.000000119，则根，则根20变为变为20.847，19和和18变为变为19.502 1.94i.例：求解微分方程例：求解微分方程(1)(2)(20)0zzz0,(0)(0)1,0(0)1,(0)1,(1),22xxxyyyyyexyyyyeexy 解为：，则解为：某些问题的计算中，由于数据的微小变化引某些问题的计算

7、中，由于数据的微小变化引起解的剧烈变化，称这类问题为起解的剧烈变化，称这类问题为病态问题病态问题和和坏条件问题坏条件问题。对于这类问题的计算，一定要。对于这类问题的计算，一定要采用采用高精度计算高精度计算。但对于非病态的良态问题，如算法不当，由于但对于非病态的良态问题，如算法不当，由于计算机的近似性，有时也可能得到不可靠的计算机的近似性，有时也可能得到不可靠的结果。结果。例：如在尾数为例：如在尾数为4位的计算机上计算位的计算机上计算其真正值为其真正值为0.05572809，但计算结果为：，但计算结果为：0.0560，但如果先进行有理化在计算，结果为：但如果先进行有理化在计算，结果为：0.055

8、74，显然，后一种计算精度高。显然，后一种计算精度高。例：如在尾数为例：如在尾数为4位的计算机上计算位的计算机上计算精确值为精确值为34.5612，计算时如先加前两项，再加后一，计算时如先加前两项，再加后一项，结果为项，结果为34.57，如先加后两项，再加前一项，如先加后两项，再加前一项，结果为结果为34.56，显然，后一种算法更好。，显然，后一种算法更好。98021010(0.3197)10(0.2456)10(0.1352)例：如在尾数为例：如在尾数为4位的计算机上计算位的计算机上计算按两种不同递推计算，结果为：按两种不同递推计算，结果为：11011,0,1,2,71(1)/nxnnnnn

9、Iex e dx nInIIIn 第一种算法第一种算法第二种算法第二种算法真正值真正值I00.63210.63200.6321I10.36800.36790.3679I60.04000.12690.1268I70.72000.11240.1124由此可见，舍入误差对计算有影响，影响小的算法称由此可见，舍入误差对计算有影响，影响小的算法称为为数值稳定数值稳定的算法。的算法。有些算法具有递推性，称之为有些算法具有递推性，称之为迭代法或逐次逼近法迭代法或逐次逼近法。再计算一些复杂的函数的值，有时我们用一些简单的再计算一些复杂的函数的值，有时我们用一些简单的函数（如多项式、有理函数等）来近似之，这称为

10、函数（如多项式、有理函数等）来近似之，这称为函数逼近函数逼近。有时要求逼近函数与被逼近函数之间在。有时要求逼近函数与被逼近函数之间在某些点函数值及若干阶导数值相等，这种逼近称为某些点函数值及若干阶导数值相等，这种逼近称为插值插值；有时要求在逼近区间上的最大误差取极小，；有时要求在逼近区间上的最大误差取极小，这称为这称为最佳一致逼近最佳一致逼近；或在某些点的误差值平方和；或在某些点的误差值平方和取极小，这称为取极小，这称为最佳平方逼近最佳平方逼近。2 误差及有关概念误差及有关概念2.1误差的来源误差的来源真实值与我们所获得的值之间的差异就是真实值与我们所获得的值之间的差异就是误差误差。对实际问题

11、的研究需要建立数学模型，这带来对实际问题的研究需要建立数学模型，这带来模型模型误差误差。求解数学问题时需要若干参量和初始值，这些数据求解数学问题时需要若干参量和初始值，这些数据往往通过对实际问题的观测得到，由于观测引起往往通过对实际问题的观测得到，由于观测引起的误差称为的误差称为观测误差观测误差（数据误差、模型参量误数据误差、模型参量误差差）。求解数学问题时，由于算法而引起的误差）。求解数学问题时，由于算法而引起的误差称为称为方法误差方法误差（截断误差截断误差）。计算机计算时只能）。计算机计算时只能对有限位数进行计算，超过的进行舍入，由此引对有限位数进行计算，超过的进行舍入，由此引起的误差称为

12、起的误差称为舍入误差舍入误差（计算误差计算误差）。）。实际问题数学问题可计算问题数学建模构造算法计算求解计算结果（模型误差）（方法误差）（舍入误差、输入数据误差）2.2 绝对误差与相对误差绝对误差与相对误差设设x为真正值，为真正值，为近似值，称：为近似值，称：为近似值的为近似值的绝对误差绝对误差（简称（简称误差误差）通常我们要求绝对误差不能超过某个值通常我们要求绝对误差不能超过某个值，称称为为绝对误差限绝对误差限或或误差限误差限。x()()xE xxx(),xxxxxx设设x为真正值，为真正值，为近似值，称：为近似值，称：为为 的相对误差。的相对误差。如果存在如果存在 r，使得使得，称之为，称

13、之为 相对误差限。相对误差限。在实际计算中，相对误差限很小时，也取：在实际计算中，相对误差限很小时，也取：x()()/()/xxxxxx x()()/()/rxxxxxx x()()/()/xxxxxx 2.3有效位数与有效数字有效位数与有效数字如果如果 的误差限为的误差限为0.510-n，即即则称其准确到小数后第则称其准确到小数后第n位，并称位，并称 的第一的第一个非零数字到第个非零数字到第n位的全部数字为位的全部数字为 的有的有效数字。效数字。x x x 1102nxx例如，若 x=3.1415926535，1416.3x则x准确到小数后4位，具有5位有效数字。显然，近似值的绝对误差越小，

14、其准确到小数后的位数越多。注意，若 x=0.200001，,2000.0,2.021xx则1x作为 x 的近似只有1位有效数字，而2x作为 x 的近似具有4位有效数字。具有 k 位有效数字，则易知)0(10.0121aaaaxmk)1(121102110.01021|)(|kmknaaaax若这说明近似值的相对误差越小，其有效数字越多。2.4 数据误差的影响数据误差的影响2.4 数据误差的影响数据误差的影响对两个数对两个数x1和和x2，简单计算可得：简单计算可得：12121212121212()()()()()()xxxxxxxxxxxxxx 1221121212()()()()()()x x

15、xxxxx xxx112122221212(/)()/()(/)()()xxxxxxxxxxx 11()(),()()22xxxxx可见，当可见，当x1和和x2同号时，同号时，反之，当反之，当x1和和x2异号时，尤其异号时，尤其12211212()()()()()()xxxxxxxx 1212210,()()()xxxxxx这表明，大小接近的异号数相加或大小这表明，大小接近的异号数相加或大小接近的同号数相减，会严重损失有效接近的同号数相减，会严重损失有效数字！数字！乘数绝对值很大，或除数接近零时，可乘数绝对值很大，或除数接近零时，可能会严重扩大绝对误差，减少精度！能会严重扩大绝对误差，减少精度

16、！开方会减少相对误差，提高精度。开方会减少相对误差，提高精度。一般地，设数学问题的解为一般地，设数学问题的解为 ,近似解为：近似解为：则绝对误差为：则绝对误差为：相对误差为：相对误差为：12(,)nyx xx12(,)nyx xx1212121()(,)(,)(,)()nnnniiiyyyx xxx xxx xxxxniiinnixxxxxxxxxyyy12121)(),(),()()(和和 起对误差的放大和缩小作用，其绝对值分别称起对误差的放大和缩小作用，其绝对值分别称为所求解的数学问题的绝对误差下的条件数为所求解的数学问题的绝对误差下的条件数和相对误差下的条件数。条件数很大时称该和相对误差

17、下的条件数。条件数很大时称该问题为问题为病态问题病态问题或或坏条件问题坏条件问题，它是问题固，它是问题固有的属性，与算法无关。但由于这类问题数有的属性，与算法无关。但由于这类问题数据的微小变化会引起解的剧烈变化，对于这据的微小变化会引起解的剧烈变化，对于这类问题的计算，一般要采用类问题的计算，一般要采用高精度计算高精度计算，或，或改变问题的提法，降低条件数。改变问题的提法，降低条件数。12(,)nix xxxinnixxxxxxxx),(),(21212.5舍入误差的影响舍入误差的影响在计算机中，用浮点法表示的数（称为浮点数）在计算机中，用浮点法表示的数（称为浮点数）的尾数，位数是固定的，称为

18、字长。设计算机的尾数，位数是固定的，称为字长。设计算机字长为字长为t，任意数任意数x十进制是按舍入原则表为浮十进制是按舍入原则表为浮点数点数则相对误差的绝对值则相对误差的绝对值)1()1(110211021|)(|ttax)0(10.0)(121aaaaxflmt记记称称 为计算机的相对精度。我们有：为计算机的相对精度。我们有：()()()(1)fl xxxfl xxx 12121121221212312124()()(1)()()(1)()()(1)(/)(/)(1)fl xxxxfl xxxxfl x xx xfl xxxx则对于多数相加则对于多数相加相对误差相对误差 1231213121

19、3212123212123123()()(1)()(1)(1)()(1(1)()(1)fl fl xxxflxxxxxxxxxxxxxxxxx12212123(1)xxxxx类似地有类似地有 在在 大体相同情况下，如大体相同情况下，如则则 于是可得，多数相加时，一般先加绝于是可得，多数相加时，一般先加绝对值较小的数，相对误差较小！对值较小的数，相对误差较小！1212,1223xxxx)1()1)()(21321322321321xxxxxxxxxxflxfl通常称舍入误差对计算结果影响不大通常称舍入误差对计算结果影响不大的算法为的算法为稳定的算法稳定的算法，反之为，反之为不稳不稳定的算法定的算

20、法。计算数学的特点：计算数学的特点：1、面向计算机（构造计算机能用的算法）；面向计算机（构造计算机能用的算法）；2、要有可靠的理论分析（指误差、算法的收要有可靠的理论分析（指误差、算法的收敛性、稳定性等）；敛性、稳定性等）；3、要有好的计算复杂性（指算法省时、节省要有好的计算复杂性（指算法省时、节省内存）；内存）；4、要有数值试验要有数值试验 (检验算法及程序的正确性检验算法及程序的正确性)避免误差危害的若干原则：避免误差危害的若干原则：1、避免除数绝对值远远小于被除数绝对值的避免除数绝对值远远小于被除数绝对值的除法。（危害：导致舍入误差增大）除法。（危害：导致舍入误差增大）2、避免相近两数相减。（危害：引起有效数避免相近两数相减。（危害：引起有效数字的严重损失）字的严重损失）3、防止大数吃掉小数。防止大数吃掉小数。4、简化计算步骤，减少运算次数。（可以节简化计算步骤，减少运算次数。（可以节省计算机计算时间，更可以减少舍入误差）省计算机计算时间，更可以减少舍入误差）