计算方法第一讲

1、数值分析数值分析赵丽娜赵丽娜v邓建中，刘之行，西安交通大学出版社，计算方法，邓建中，刘之行，西安交通大学出版社，计算方法，2001年年v李庆扬，关冶李庆扬，关冶 数值分析原理，清华大学出版社，数值分析原理，清华大学出版社，2000年年v李庆扬，易大义，王能超李庆扬，易大义，王能超 现代数值分析，高教出版现代数值分析，高教出版社，社，1995年年vMichael T. H. Scientific Computing: An introductory Survey, 清华大学出版社，清华大学出版社，2001vMatlews J. H. Numerical Methods Using Matlab,

2、 电子工业电子工业出版社，出版社，2002教材与参考书 数值分析或计算方法的历史早于计算机的产生，数值分析或计算方法的历史早于计算机的产生，许多（如今仍在使用的）概念与方法由二十许多（如今仍在使用的）概念与方法由二十世纪前的伟人给出世纪前的伟人给出 Newton (1642-1727) Euler(1707-1783) Lagrange(1736-1813) Laplace(1749-1817) Legendre(1752-1833) Hermite(1822-1901) Gauss(1777-1855) Cauchy(1789-1857) Jacobi(1804-1851) Adams(18

3、19-1892) Chebyshev(1821-1894) Laguerre(1834-1886)第一讲数值分析的意义内容与方法n 起源：寻找有效的方法获得数学问题的近似解。n 数学问题源于物理，天文，勘测等n 在仅使用纸，笔，大脑，而不是计算机进行计算时，算法效率尤为重要。n 如今，大规模计算成为可能，更要仔细分析控制截断误差1.1 数值分析的起源与意义v随着计算机的普及与发展，计算机性能的大幅提高，海量数据的出现，科学计算更为重要v科学计算已成为现代科学技术的研究方法的第三大方法 理论推导，科学试验，科学计算v其他应用：符号计算、计算几何、定理的机器证明科学计算的定义v将科学技术问题科学技

4、术问题通过建立数学模型转换为数数学问题学问题；v将数学问题离散化得到数值问题数值问题；v使用数值计算方法数值计算方法求出数值问题的解数值问题的解；v并把所得的解作为原科技问题的解原科技问题的解。实际问题数学问题可计算问题数学建模构造算法计算求解计算结果反馈、修正、应用解决实际问题计算数学是科学计算的核心v计算数学-对数学模型问题研究数值求解方法，分析方法的性质 数学问题通过数值计算方法化为可计算问题，然后进行计算求得结果v按研究内容可分为：数值代数、数值逼近、数值微积分、微分方程数值解、最优化计算、概率统计计算、计算几何、计算力学等。是否有了计算机，找到数学公式就可以得到正确的结果？例例1：1

5、23123123111123611113234121114734560 xxxxxxxxx解为：解为：x1 = x2 = x3 =1如近似为：如近似为：则解为：则解为：1231231230.500.331.80.500.330.251.10.330.250.200.78xxxxxxxxx1236.222,38.25,33.65xxx 1.2 数值问题与算法v数值问题是指输入数据（原始数据，问题中的已知量）与输出数据（结果）之间的函数关系的明确的无歧异的问题v数学问题未必是数值问题，但它往往可以用数值问题来逼近例例2：求常微分方程：求常微分方程22(0)0dyxydxy由题目要求，需给出y=y(

6、x)解析式，该问题不是数值问题；若输出y=y(x)在（给定步长h）x=h, x=2h, x=nh处的近似值，则该问题转化为数值问题。算法及其好坏v计算机的基本运算：四则运算、简单逻辑运算v计算机的算法可分为串行算法和并行算法v好的算法： 1、面向计算机，易于编程和计算实现； 2、计算复杂性好：计算时间少、占用内存少； 3、计算稳定性好：能有效控制由于方法近似和舍入 误差引起的误差增长，结果能达到所要求的精度； 4、适用性好。例例3：计算多项式：计算多项式x = a时时p(a)的值。的值。1011( )nnnnp xa xa xaxa 普通方法 时间：n(n+1)/2次乘法；n次加法 秦九韶算法

7、001,1,2,( )kkknbabaabknp ab时间：n次乘法；n次加法例：计算多项式：例：计算多项式：需需10次乘法次乘法4次加法。次加法。4次乘法次乘法4次加法。这是多项式计算的次加法。这是多项式计算的秦九韶秦九韶算算法法。3次乘法次乘法5次加法。次加法。4320.06250.4251.2151.9122.1296xxxx(0.06250.425)1.215)1.912)2.1296xxxx22(0.50.6)0.50.7 (0.50.6)0.80.9xxx例例4 解代数方程解代数方程 ：11 11221121 1222221 122nnnnnnnnnna xa xa xba xa

8、xa xba xa xa xb/,1,2,kkxDDkn直接法：用直接法：用Cramer法则解，法则解， 若若det(A)不为0，1.3 数值计算的基本方法论v有限近似无限：有限维空间代替无限维空间；有限和代替积分或无限级数；差商近似导数；v代数方程组近似微分方程组；v高阶方程低阶化v非线性问题线性化v复杂函数用简单函数来代替（多项式泰勒展开）v一般矩阵简单化原则：复杂问题Q1 简单问题Q2Q2与Q1的解在一定意义下相同。直接方法（适用于可有限步内直接计算得到解的问题）截断近似：利用一些展开式截取其若干项来近似迭代法线性化：非线性问题局部线性化化整为零：将整体问题分割为若干小部分处理外推法：利

9、用已算出的结果适当组合得到更精确 的结果35721sin3!5!7!(21)!nnxxxxxxRn例例5：计算：计算sinx，x 0， /423 0 x 例例6：求解函数方程：求解函数方程f (x)=0.例例7：求解函数方程：求解函数方程例例9：求解常微分方程：求解常微分方程0( , ) , , ( )yf x yxa by ay 1(,)nnnnyyhf xy例例8：计算定积分：计算定积分( )bafx dx一个具体的例子：一个具体的例子：迭代格式为：迭代格式为：2,0,1(0)1xyyxyy 1(2/)nnnnnyyh yxy精确解：精确解：( )12y xxxn0.10.20.30.40

10、.51yn1.11.19181.27741.35811.43511.7848yn1.09591.18111.26621.34341.41641.7379Y(xn)1.09541.18321.26491.34161.41421.7320例：求方程例：求方程 根，如根，如z10系数系数 210略有误差，为略有误差，为 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 解为：，则解为：v某

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

12、算，结果为：如果先进行有理化在计算，结果为：0.05574，显然，显然，后一种计算精度高。后一种计算精度高。例：如在尾数为例：如在尾数为4位的计算机上计算位的计算机上计算精确值为精确值为34.5612，计算时如先加前两项，再加后一，计算时如先加前两项，再加后一项，结果为项，结果为34.57，如先加后两项，再加前一项，结，如先加后两项，再加前一项，结果为果为34.56，显然，后一种算法更好。，显然，后一种算法更好。98021010 (0.3197) 10 (0.2456) 10 (0.1352)例：如在尾数为例：如在尾数为4位的计算机上计算位的计算机上计算按两种不同递推计算，结果为：按两种不同递

13、推计算，结果为：11011,0,1,2,71(1)/nxnnnnnIex e dx nInIIIn 第一种算法第一种算法第二种算法第二种算法真正值真正值I00.63210.63200.6321I10.36800.36790.3679I60.04000.12690.1268I70.72000.11240.1124由此可见，舍入误差对计算有影响，影响小的算法称由此可见，舍入误差对计算有影响，影响小的算法称为为数值稳定数值稳定的算法。的算法。有些算法具有递推性，称之为有些算法具有递推性，称之为迭代法或逐次逼近法迭代法或逐次逼近法。再计算一些复杂的函数的值，有时我们用一些简单的再计算一些复杂的函数的值

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

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

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

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

18、3.1415926535，1416. 3x则x准确到小数后4位，具有5位有效数字。 显然，近似值的绝对误差越小，其准确到小数后的位数越多。 注意，若 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，简单计算可得：简单计算可得：1

19、2121212121212()()()()()()xxxxxxxxxxxxxx 1221121212()()()()()()x xxxxxx xxx112122221212(/)()/()(/)()()xxxxxxxxxxx 11()( ),()( )22xxxxx可见，当可见，当x1和和x2同号时，同号时，反之，当反之，当x1和和x2异号时，尤其异号时，尤其12211212()()()()()()xxxxxxxx 1212210,()()( )xxxxxx这表明，大小接近的异号数相加或大小这表明，大小接近的异号数相加或大小接近的同号数相减，会严重损失有效接近的同号数相减，会严重损失有效数字！

20、数字！乘数绝对值很大，或除数接近零时，可乘数绝对值很大，或除数接近零时，可能会严重扩大绝对误差，减少精度！能会严重扩大绝对误差，减少精度！开方会减少相对误差，提高精度。开方会减少相对误差，提高精度。一般地，设数学问题的解为一般地，设数学问题的解为 ,近似解为：近似解为：则绝对误差为：则绝对误差为：相对误差为：相对误差为：12( ,)nyx xx12( ,)nyx xx 1212121( )( ,)( ,)( ,)( )nnnniiiyyyx xxx xxx xxxx niiinnixxxxxxxxxyyy12121)(),(),()()( 和和 起对误差的放大和缩小作用，其绝对值分别称起对误差

21、的放大和缩小作用，其绝对值分别称为所求解的数学问题的绝对误差下的条件数为所求解的数学问题的绝对误差下的条件数和相对误差下的条件数。条件数很大时称该和相对误差下的条件数。条件数很大时称该问题为问题为病态问题病态问题或或坏条件问题坏条件问题，它是问题固，它是问题固有的属性，与算法无关。但由于这类问题数有的属性，与算法无关。但由于这类问题数据的微小变化会引起解的剧烈变化，对于这据的微小变化会引起解的剧烈变化，对于这类问题的计算，一般要采用类问题的计算，一般要采用高精度计算高精度计算，或，或改变问题的提法，降低条件数。改变问题的提法，降低条件数。12(,)nix xxxinnixxxxxxxx),()

22、,(21212.5舍入误差的影响舍入误差的影响在计算机中，用浮点法表示的数（称为浮点数）在计算机中，用浮点法表示的数（称为浮点数）的尾数，位数是固定的，称为字长。设计算机的尾数，位数是固定的，称为字长。设计算机字长为字长为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则对于多数相加则对于多数相加相对误差相对误差 123121312