第1章数值计算引论课件.ppt

1、第第1 1章章 数值计算引论数值计算引论第第2 2章章 非线性方程的数值解法非线性方程的数值解法第第3 3章章 线性代数方程组的数值解法线性代数方程组的数值解法第第4 4章章 插值法插值法第第5 5章章 曲线拟合的最小二乘法曲线拟合的最小二乘法第第6 6章章 数值积分和数值微分数值积分和数值微分第第7 7章章 常微分方程初值问题的数值解法常微分方程初值问题的数值解法数值计算方法数值计算方法 第第1 1章章数值计算引论1.1 数值计算方法 1.2 误差的来源1.3 近似数的误差表示法1.4 数值运算误差分析1.5 数值稳定性和减小运算误差 第第1 1章章 数值计算引论 数值计算方法与误差分析数值

2、计算方法与误差分析 理工科大学本科生理工科大学本科生 科学研究。科学研究。 现代科学研究的三大手段现代科学研究的三大手段 理论分析、科学实验、科学计算。理论分析、科学实验、科学计算。1.11.1数值计算方法数值计算方法1.1.1 1.1.1 数值计算方法及其主要内容数值计算方法及其主要内容 1. 1.课程名称：科学与工程数值计算方法课程名称：科学与工程数值计算方法 简称：科学计算、科学与工程计算、数值分析、简称：科学计算、科学与工程计算、数值分析、计算方法、数值计算方法。计算方法、数值计算方法。 科学与工程：从实用的角度，将科学研究与工科学与工程：从实用的角度，将科学研究与工程技术上遇到的实际

3、问题用数学模型来描述，以程技术上遇到的实际问题用数学模型来描述，以便进行定量的分析、研究。便进行定量的分析、研究。 数值：数、数字，由数值：数、数字，由0-90-9十个数字、小数点和正十个数字、小数点和正负号等组成的数。负号等组成的数。 计算方法：解题的方法。可以用自然语言、计算方法：解题的方法。可以用自然语言、数学语言或约定的符号语言来描述。数学语言或约定的符号语言来描述。 计算：只能包括计算机能够直接处理的运算计算：只能包括计算机能够直接处理的运算, ,即加减乘除等基本运算。即加减乘除等基本运算。 数值计算：相对于非数值计算，如查表、排数值计算：相对于非数值计算，如查表、排序等。用（序等。

4、用（0-90-9十个数字、小数点、正负号等组成十个数字、小数点、正负号等组成的）数，通过计算机进行加减乘除等基本运算。的）数，通过计算机进行加减乘除等基本运算。 2 2。数值算法：对科学研究与工程技术上遇到的。数值算法：对科学研究与工程技术上遇到的实际数学问题的解法归结为用数值进行加减乘除等实际数学问题的解法归结为用数值进行加减乘除等基本运算，并有确定运算顺序，完整而准确的描述基本运算，并有确定运算顺序，完整而准确的描述称为数值算法。称为数值算法。 数值计算方法是研究用数字计算机解决数学问数值计算方法是研究用数字计算机解决数学问题的数值算法及其理论的一门课程。题的数值算法及其理论的一门课程。

5、3.主要内容：工程上遇到的数学问题 数值计算的误差分析 非线性方程 线性方程组 插值法 最小二乘法 数值积分和数值微分 常微分方程1.1.2 用计算机解题的步骤 当给定一个科学研究与工程技术上遇到的实际问题时，首先根据专业知识建立实际问题的数学模型，即模型化（modeling)或建模。然后对数学模型进行求解。 数学模型（包括公式、表格、图形等）求解有两条途径：求解析解和数值解。 求解析解，解以表达式表示，这是准确解。 求数值解，解是以一些离散点上取值的形式表示，多数情况下，数值解是近似的，求数值解要用计算机。求数学模型数值解的方法称为数值计算方法。 选择计算方法以后进行程序设计，即用程序语言把

6、算法编成程序，然后上机得出数值解。 实际问题-数学问题(建模)-构造数值计算方法- 程序设计-上机计算-数值解-结果分析离散化插值法迭代法逼近法设f(x)是定义在a,b上的连续函数，当它们的表达式很复杂，甚至写不出来时，我们可以选择若干个离散点 x0, x1, xna,b 求出f(x)在这些点处的函数值或函数值的近似值 fi= f(xi) i=0,1,n, 从而得到一个如下的函数值列表：xx0 x1xnyf(x0)f(x1)f(xn)对于任意给出的某个函数y=f(x)的函数值列表: 我们可以构造一个简单函数，比如n次多项式pn(x)，满足条件 pn(xi)=yi, i=0,1,n 并利用pn(

7、x)近似表示f(x)。提示：由于pn(x)是一个多项式函数，用它在某一点处的函数值、导数值、区间上的定积分等来近似未知函数y=f(x)的值、微分、定积分xx0 x1xnyy0y1yn设f(x)是满足某种特定条件的函数，表达式比较复杂甚至写不出来，但是我们可以把它表示为一个简单函数系列 fn(x),n=1,2,的极限,即 lim fn(x)=f(x) (n) 这样我们就可以根据不同的精度要求选取适当大的正数N,利用fN(x)近似替代f(x)。提示：如果f(x)可以展为泰勒级数，那么我们可以取fn(x)为f(x)的泰勒展式前n+1项。如要计算某个真值 x*，可构造一个序列xn,n=0,1,2,，该

8、序列满足： x0 已知； 有一个简单函数(t)， 且xn+1=(xn)，n=0,1,2, lim xn=x* (n) 则，可反复利用xn+1=(xn)， 经过N 次后，用xn+1 作为x* 的近似值。 实例：求5的平方根的迭代格式1.初值x0=2，xn+1=2+1/(xn+2) 简单迭代法2.初值x0=2，xn+1=（xn+1/xn)/2 牛顿迭代法请大家练习用两种迭代法求解的结果算法：为解决某一特定问题或完成某个特定任务而设计或规定的一个有限步的操作指令序列称为算法。提示：算法具有如下一些特征：输入：有0个或多个输入输出：有一个或多个输出(处理结果)确定性：每步定义都是确切、无歧义的有穷性：

9、算法应在执行有穷步后结束有效性：每一步操作均可由有限次最基本的运算来完成。算法的描述：自然语言：流程图：伪代码：算法的评价：程序的可读性好；节省计算时间节省存储空间数值稳定性与收敛性 既然研究典型的数学问题的计算方法、或者说数值解方法最后都要用“算法”来描述，所以对具体的计算方法的评价也就转化为对算法的评价。一个算法的好坏可用下面几个指标来刻划程序的可读性好；节省计算时间节省存储空间数字稳定性好在一个迭代过程中，如果我们有 其中c为非零常数，则称xn p阶收敛于x*。术语：当p=1时，称算法具有线性速率收敛；当1p2时，称算法具有超线性收敛速率；当p=2时，称算法具有二次终结性质或二次收敛速率

10、。cp|nx*x|1nx*x|limn*xnxnlim0,1,n)n(x1nx本书程序的基本结构采用模块化程序设计思想主要分四大模块FormProblem( )：主要完成程序的参数（常量）设置Operation( )：完成算法的基本操作ShowTable( )：完成计算结果（含中间结果）的屏幕输出SaveTable( )：计算结果的保存（写文件）误差的来源即产生误差的原因。主要有四种：误差的来源即产生误差的原因。主要有四种：1. 1.模型误差模型误差-建立的数学模型和实际的距离，建立的数学模型和实际的距离，客观量的准确值与数学模型的准确解的差。客观量的准确值与数学模型的准确解的差。例如自由落体

11、运动方程例如自由落体运动方程误差的来源误差的来源2.观测误差：数学模型当中的参数或常数常常是是观测或实验来的，这样必然有误差，称为观测误差或测量误差，由观测数据而产生的误差。例如自由落体运动方程3.截断误差(方法误差)-数学模型的准确解与利用数值计算方法得到的准确解之差。无穷过程用有穷项代替例如:无穷级数取前n项代替()0k= 01()!kfxk1()0k= 01()!nkfxk1()()()000k= 0k= 0k=n111()()()!nkkkfxfxfxkkk截断误差用有限的过程代替无限的过程，和用简单的计算问题代替复杂的计算问题所产生 的误差。230.66666666667(230.6

12、6666666666）4.舍入误差 ：计算工具字长是有限位，在计算时只能对有限位数字进行运算，超过这个位数时，要舍入，于是产生舍入误差。原始数据、中间步骤和最终结果都可能产生舍入误差。 如圆周率3.14159265 一般实数不能精确存储，例如：在10位十进制数限制下：1.3.1 绝对误差 1 1 定义定义 设*x是精确值x的一个近似值， 则 *)(xxxe 为近似值*x的绝对误差，简称误差。其特点： *exx *e可正可负 *e越小越好 有量纲 2 绝对误差限：估计*e的上界* 定义定义 设*x是真值x的近似值，若 *e=*xx 则称*是*x的绝对误差限，简称误差限（界） 。 *为正 *e在*

13、的范围内 有量纲 *尽可能的小，取末位的半个单位。 例如： 有毫米刻度的尺子， 读出的近似值的误差，不会超过毫米的一半（半个毫米） 。 读出 35 毫米代表 34.5 到 35.5 之间。 误差是半个毫米，误差限是末位的半个单位。 3 四舍五入的误差限：设 mnxxxx10. 021 其中), 2 , 1(ixi是0,1,9中的数字，且01x，m为整数，n为正整数。 四舍时 mnxxxx10. 0*21 其中14nx， 五入时 1 21*0.(1) 10mnnxx xxx 其中15nx， 则四舍五入的误差限nmxx1021*。即用四舍五入得到的近似数的误差限是末位的半个单位。 四舍时的误差限：

14、 *110.000100.0049910102mmm nnxxx 五入时的误差限： *1(0.0001 0.00) 10mnxxx 11(1 0.) 10102m nm nnx 则四舍五入的误差限nmxx1021*。即用四舍五入得到的近似数的误差限是末位的半个单位。 例 圆周率取四舍五入的近似数 3.1416，求其误差限。 解法 1： 误差限是末位的半个单位，41021* 解法 2：1*10,1,52m nmn1 54mn ， 41*10 .2 1. 引入：引入： 10mm 误差误差 1mm 1m 误差误差 2mm 2 定定义义 设*x是精确值x的一个近似值， 则 xxx 为近似值*x的相对误

15、差。 相对误差无量纲，用百分数表示。 实际上精确值x往往是未知的， 所以常常把*()rxxexx 作为*x的相对误差。 3 相对误差（限） ：估计re的上界 定义定义 设*x是真值x的近似值，若 rrxxxxxee 则称r是近似数*x的相对误差（限） 。 例：用 3.14 作为的近似值，求其相对误差。 解：四舍五入的近似值 3.14 的绝对误差2*1021， 相 对 误 差%159. 014. 310212*xr 1.3.2 有效数字：由绝对误差决定。 定义定义 设x的近似值mnxxxx*10. 021，若*x的绝对误差nm*x-x1021 则称近似值*x为x的有n位有效数字的近似值。 其中1

16、2,nx xx是*x的有效数字。近似值*x具有n位有效数字，它准确到第n位。 定定义义 设x的近似值mnxxxx*10. 021，若*x的绝对误差nm*x-x1021 则称近似值*x为x的有n位有效数字的近似值。 其中12,nx xx是*x的有效数字。近似值*x具有n位有效数字，它准确到第n位。 1.3.3 有效数字：由绝对误差决定。有效数字：由绝对误差决定。 若近似值x*的绝对误差(限)是某位的半个单位，则说 x* 精确到该位，若从该位到 x* 的左面第一位非零数字一共有n位，则称近似值x*有n位有效数字。例：求 3.142 和 3.141 作为圆周率的近似值有几位有效数字。 解：313.1

17、420.0004070.0005102，1m， 3,4m nn。有 4 位有效数字。 213.1410.000590.005102，1m， 2,3mnn。有 3 位有效数字。 例： 以722作为圆周率的近似值有几位有效数字。 解解:7223.142857， 3.141592。 2102100126. 0722。因为 m=1，m-n=-2 ，所以 n=3，有 3 位有效数字。 1.用四舍五入得到的近似数的误差限是末位的半个单位。近似数的误差限是末位的半个单位，则有n位有效数字。因此用四舍五入得到的近似数是有效数字。 2.在公式运算中，要先区分准确量和近似数。准确数有无穷多位有效数字. 3.有效数

18、字位与小数点后有多少位数无直接关系。绝对误差、相对误差、有效数字三者关系。 *和 n 的关系 1*102m n *和r的关系 *rx n 和r的关系 两个定理。 定理 若近似数mnxxxx10. 021具有 n 位有效数字，则其相对误差 )1(1*1021nrx 证 因mnxxxx10. 021，有1110.mxx， 又，x有 n 位有效数字，即1102m nxx，因此 )1(111*1021101021nmnmrxxxxxe，即)1(1*1021nrx 例：用 3.14 作为的近似值，求其相对误差。 解：四舍五入的近似值各位都是有效数字，即 n=3,由定理 %17. 010321)13(*r

19、 和前例比较，说明结果不同的原因。 已知近似数x有两位有效数字， 求其相对误差。 解解 因 n=2, )1(1*1021nrx第 1 位1x未给出， 11x %5101211021)1()1(1*nnrx 91x %56. 0109211021)1()1(1*nnrx， 取 %5*r。 1.定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。 2.在实际应用时，为了要使所取近似数的相对误差满足一定要求，可以用定理，确定所取近似数应具有有效数字的位数。 定理 若近似数mnxxxx*10. 021，的相对误差限 (1)11102(1)nrx 则它至少具有n位有效数字。 证 mnxxxx*

20、10. 021有11(1) 10mxx 则 xxxxxx(1)1111110(1)10102(1)2nmm nxx， 即它至少具有n位有效数字。 例 已知近似数x*的相对误差限为 0.25%，问x*至少有几位有效数字？ 解解 由*0.25%r，根据定理，有 (1)110.25%102(1)nx x1的取值范围是 1 到 9，由于x1未给出，取 x1=1，n= 3 x1=9，n=2.3 按最不利情况，x*至少有 2 位有效数字。 1.1.定理给出的是一个充分条件，而不是必要条件。定理的定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。即若近似数有逆命题不成立。即若近似数有n n位有效

21、数字，相对误差不一定满位有效数字，相对误差不一定满足定理。足定理。 2.2.在实际应用时，为了要使所取近似数具有在实际应用时，为了要使所取近似数具有n n位有效数字，位有效数字， 要要求所取近似数的相对误差满足定理的要求。求所取近似数的相对误差满足定理的要求。 1.4 1.4 数值运算误差分析数值运算误差分析 函数运算误差函数运算误差 算术运算误差算术运算误差函数y=f(x1,x2)的全微分为： 若x1,x2的准确值为x1*,x2*,则y的准确值为y*=f(x1*,x2*) 又 的dx1x1*-x1= dx2 x2*-x2= dy y*-y= 故： 相对误差： )(1x22112211xxfx

22、xfdxxfdxxfdy)(2x)(y)()()(222111xyxxfxyxxfy2211dxxfdxxfdy和差积商的误差估计：(x1x2)= (x1) (x2)(x1x2)= x2(x1)+x1 (x2)(x1/x2)= (x1)/x2- (x2)x1/x22 (x1x2)=(x1/(x1x2）)(x1) (x2/(x1x2）)(x2)(x1x2)= (x1)+ (x2)(x1/x2)= (x1)- (x2)定义：设y=f(t)是在某个x附近连续可微的实函数， 也称为是一个数学问题，记 称cond(f,x)为数学问题y=f(t)在t=x处的条件数， 也可简称为数学问题 y=f(x)的条件

23、数。注释 在表示一个数学问题的条件数时，有时候需要明确指出f的自变量x，以及f(x)在x=x0处的条件数，这时，也可以把条件数更具体地表示为)()( ),cond(xfxfxxf )()( ),(cond0000 xfxfxxxf 计算数学问题的条件数举例 例： 试求tan(x)在x=/6处的条件数。21.10.57741.3330.5236),condtan(333.1)cos(1)tan(5774.031)tan(5236.06/020000 xxxxxx解：分析：记(x0)、(x0)和f(x0)、f(x0)分别为x0和f(x0)的绝对误差和相对误差，则有 (x0)=(x0)/x0 f(x

24、0)=f(x0)/f(x0) 利用f(x0)=f(x0)(x0), 即得结论1：f(x0)=condf(x),x0(x0)000000000 x)x()x(f)x( fx)x(f)x()x( f)x(f 结论2：如果一个数学问题y=f(x)的条件数的绝对值|condf(x),x0|1，那么有|f(x)|1，则数学问题是不稳定的，或者说是病态的，输入值的微小误差可以导致输出值的较大的误差复合函数的条件数：假设函数关系y=f(x)是通过一个中间变量u复合而成的，即y=y(u)，u=u(x)。利用复合函数的求导规则 我们有亦即：condy(u(x),x0=condy(u),u0 condu(x),x

25、0 udxduxydudyuxfdxdududyxxfdxxdfxxf)()()(),cond(dxdududydxxdf)( 1.5 1.5 数值稳定性和减小运算误差数值稳定性和减小运算误差 在计算过程中误差不会扩大或对计算结果的精度要求影在计算过程中误差不会扩大或对计算结果的精度要求影响不大。响不大。 减小运算误差减小运算误差: :1 1 要避免两相近数相减。要避免两相近数相减。2 2 要防止大数吃掉小数要防止大数吃掉小数 。3 3 要避免除数绝对值远小于被除数绝对值要避免除数绝对值远小于被除数绝对值 。4 4 注意简化计算步骤，减少运算次数注意简化计算步骤，减少运算次数 。例：计算积分例

26、：计算积分110ed ,1,2,8nxnExxn写成递推公式写成递推公式 1112,3,81/ ennEnEnE)(!)1()()(111EnEnEnnn 误差传递规律误差传递规律公式改为公式改为 nEEnn 11则误差按规律则误差按规律 |1| )(|1nnEnE 逐渐缩小逐渐缩小 1.5.1 1.5.1 数值稳定性数值稳定性: : 一个算法，如果计算结果受误差的影响一个算法，如果计算结果受误差的影响小，就称这个算法具有较好的数值稳定性。否则，就称数值小，就称这个算法具有较好的数值稳定性。否则，就称数值稳定性不好。因此要设法控制误差的传播稳定性不好。因此要设法控制误差的传播 。1.5.2 1

27、.5.2 减小运算误差减小运算误差1.1.要避免相近两数相减要避免相近两数相减 13.5846-13.5839=0.000713.5846-13.5839=0.00076 6位有效数字变成了位有效数字变成了1 1位有效数字。损失了有效数字的位数。位有效数字。损失了有效数字的位数。111 xxxx)1(1111 xxxx当当x x接近于接近于0 0时，应时，应2cos1sinsincos1xtgxxxx或或 8 9 7 68 9 7 59 4 .7 4 29 4 .7 3 60 .0 0 6例例 解一元二次方程解一元二次方程a x2+ bx+c=0 ，其中其中-b , c21,242bbacxa

28、 100.1 10b 910101010.1 100.0000000001 10b 91210 ,0 xx224bacb2 2 要防止大数要防止大数“吃掉吃掉”小数，注意保护重要物理参数。小数，注意保护重要物理参数。 9101910在在8位十进制计算机上计算。要规格化和对阶。位十进制计算机上计算。要规格化和对阶。结果，结果，大数大数“吃掉吃掉”小数。小数。类似地类似地21,242bbacxa 92911011 10cxax改变计算方法改变计算方法假如一元二次方程有绝对值不同的两个实根，记sign(b)表示取b符号，记x1为绝对值较小的那一个实根，也就是分子是同号两数相减的那一个；x2为绝对值较

29、大的那一个实根，从而有对于求x1来说，可以把分子有理化，从而得到aacbbbx24)sign(21aacbbbx24)sign(22acbbbcx4)sign(221如果记 那么x1，x2还可进一步简单地表示为x1=c/Quad(a,b,c)，x2=Quad(a,b,c)/a其中x1，x2分别为一元二次方程的绝对值较小，较大的根。求解Quad(a,b,c)的c语言函数可以说明为double Quad(double a,double b, double c)24)sign(),Quad(2acbbbcba例例 在在5位十进制计算机上计算位十进制计算机上计算在在5位十进制计算机上计算。要规格化和对

30、阶。位十进制计算机上计算。要规格化和对阶。结果，结果，大数大数“吃掉吃掉”小数。小数。改变计算方法，按绝对值由小到大相加。改变计算方法，按绝对值由小到大相加。1000152492iiA1000551524920.52492 100.000004 10iiA50.52492 103 3 注意简化计算步骤，减少运算次数，避免误差积累注意简化计算步骤，减少运算次数，避免误差积累 255x255248163264128xxx x x x xxx例：计算例：计算 的值。的值。 又如又如100111)111() 1(11000110001 nnnnnn2552()/xxx只需只需14次乘法。次乘法。对于一

31、般形式的多项式 A(x)=a0+a1x+anxn把它表示为：PolyValue(x,A,n)= a0+a1x+anxn其中A是(2.1)式给出的多项式A(x)的系数构成的(行)向量，亦即： A=(a0,a1,an) 程序设计时，可以把A说明为一个n+1维数组，此时约定A0存放a0，A1存放a1，An存放an。函数声明：double PolyValue(double x,double*A,int n)思想：按次数由低到高的顺序逐项求和。用变量power存放x的各次幂，并利用xk=xxk-1来简化计算。源程序：（见下页）double PolyValue ( double x, double*A, int n) double power=1.0, y; int k; y=A0; for(k=1;k=0;k-)y=y*x+Ak; return y;算法的计算量：乘法：n次，加法：n次。秦九韶算法的补充说明秦九韶算法现在已经越来越受到重视，还有更重要的原因。假设计算一个基于泰勒展式的多项式的值，不失一般性可以假设它的各项都是正的，注意到级数收敛的必要条件是它的通项将趋近于零。当计算的项数比较大时采用秦九韶算法可明显地提高精度（实际计算表明可以保证精度）。