《第1章 - 数值计算的基本概念》由会员分享，可在线阅读，更多相关《第1章 - 数值计算的基本概念（37页珍藏版）》请在金锄头文库上搜索。
1、第一章第一章 数值计算的基本概念数值计算的基本概念n n引言引言n n误差与误差与有效数字有效数字n n算法的稳定性与病态问题算法的稳定性与病态问题n n计算机计算的几个问题计算机计算的几个问题n n算法设计的原则算法设计的原则11 引言引言一、数值学科的研究内容和特点一、数值学科的研究内容和特点n n解决现代工程技术问题的解决现代工程技术问题的解决现代工程技术问题的解决现代工程技术问题的基本过基本过基本过基本过程程程程（如左图）（如左图）（如左图）（如左图）n n数值分析是研究适合于在计算机数值分析是研究适合于在计算机数值分析是研究适合于在计算机数值分析是研究适合于在计算机上使用的实际可行、
2、理论可靠、上使用的实际可行、理论可靠、上使用的实际可行、理论可靠、上使用的实际可行、理论可靠、计算复杂性好的数值计算方法的计算复杂性好的数值计算方法的计算复杂性好的数值计算方法的计算复杂性好的数值计算方法的学科。学科。学科。学科。分析实际问题分析实际问题数值计算方法数值计算方法数学模型数学模型机器求解机器求解 数值分析研究的数值分析研究的核心：算法。核心：算法。构造算法的基本手段：构造算法的基本手段：近似近似研究算法的核心问题：近似对计算研究算法的核心问题：近似对计算的影响的影响误差分析误差分析2 特点特点u 构造性：构造性：u 递推性：递推性：u 离散化：离散化：u 近似替代：近似替代：计算
3、离散点上的近似值；有可靠的理论分析；计算离散点上的近似值；有可靠的理论分析；算法理论主要是连续系统的离散化数值求解。算法理论主要是连续系统的离散化数值求解。方法的构造，解的存在唯一性的证明方法的构造，解的存在唯一性的证明复杂计算过程转化成简单的计算过程的多复杂计算过程转化成简单的计算过程的多次重复（适合计算机计算）次重复（适合计算机计算）在误差允许的范围内，无限次的计算能用在误差允许的范围内，无限次的计算能用有限次计算替代。有限次计算替代。u 模拟仿真：模拟仿真： 可通过计算机的仿真实验验证实际的工程计算可通过计算机的仿真实验验证实际的工程计算32 误差与有效数字误差与有效数字一个物理量的真实
4、值和我们算出的值往往不相等，一个物理量的真实值和我们算出的值往往不相等，其差称为其差称为误差误差。一、误差定义一、误差定义定义定义4分析实际问题分析实际问题数值计算方法数值计算方法数学模型数学模型机器求解机器求解二、误差种类与来源二、误差种类与来源观测误差观测误差模型误差模型误差截断误差截断误差舍入误差舍入误差数据观测所引入的误差，如电数据观测所引入的误差，如电压、天体运行轨道。压、天体运行轨道。数学模型是实际问题的抽象和简数学模型是实际问题的抽象和简化，只是对客观现象的一种近似。化，只是对客观现象的一种近似。其间出现的误差。其间出现的误差。近似计算代替精确求解，如此误差近似计算代替精确求解，
5、如此误差称为称为截断误差截断误差，本身固有，也称，本身固有，也称方方法误差法误差。例如圆周率，自然对数。例如圆周率，自然对数。计算机数系的有限字长，必须进行计算机数系的有限字长，必须进行四舍五入，称为四舍五入，称为舍入误差舍入误差。5 计计算算机机在在处处理理数数据据过过程程中中存存在在计计算算误误差差。原原因因是是机机器器数数系系所所致致。这这一一数数系系的的特特点点是是有有限限、离离散散、支支离离破破碎碎；这这和和数数学学上上常常用用的的实实数数系系无无限限、稠稠密密、连连续续的的特特点点完完全全不不同同。机机器器数的表示方法通常采用浮点数形式，即：数的表示方法通常采用浮点数形式，即：其中
6、其中 a10，且，且 a1, a2, , an 都是整数都是整数09中的任一个数。中的任一个数。 10m称为称为尾数尾数，尾数的位数，尾数的位数n是有限正整数；是有限正整数；m称为称为阶数阶数，阶数也是有界的数。所以，机器数中有最大的数，也有最小阶数也是有界的数。所以，机器数中有最大的数，也有最小的数。用机器数表示实数时，很多情况下都带有误差的数。用机器数表示实数时，很多情况下都带有误差 。附附：计算机数系的特点：计算机数系的特点6二、误差基本概念二、误差基本概念1. 绝对误差绝对误差1.绝对误差不是误差的绝对值，即绝对误差不是误差的绝对值，即 e(x) 可正可负。可正可负。2.通常通常 x
7、是未知的，故是未知的，故 e(x) 未知未知 ，但一般地，但一般地 已知。已知。 设设设设 x x* *为准确值为准确值为准确值为准确值 x x 的近似值，记的近似值，记的近似值，记的近似值，记 称称称称 为为为为x x * *的的的的绝对误差限绝对误差限绝对误差限绝对误差限或或或或误差限误差限误差限误差限。称称 e 为近似值为近似值x*的的绝对值绝对值或或误差误差。定义定义若若例例说明说明72. 相对误差相对误差设某量的准确值为设某量的准确值为 x，x*是是 x 的近似值，称绝对误差的近似值，称绝对误差与准确值之比与准确值之比称称为为x*的的相对误差限相对误差限。为为x*的的相对误差。相对误
8、差。定义定义若若8例例：设：设估计近似数估计近似数x1,x2的绝对误差与相对误差。的绝对误差与相对误差。解：解：是是x1好的近似，好的近似，不是不是x2好的近似。好的近似。近似数的相对误差是近似数精确度的基本度量，一近似数的相对误差是近似数精确度的基本度量，一个近似数个近似数x*的相对误差越小，则近似数越精确。的相对误差越小，则近似数越精确。结论结论:91. er(x)是一个无量纲的数，且是一个无量纲的数，且 x一般是未知的，所以一般是未知的，所以er(x)难求。难求。2. 考察量考察量 较小时较小时3. 通常将通常将 作为作为x*的相对误差。的相对误差。4.相对误差限相对误差限是未知的，但可
9、以确定。是未知的，但可以确定。说明说明103. 有效数字有效数字若近似值若近似值x*的误差限是某一位的半个单位，该位到的误差限是某一位的半个单位，该位到第一位非零数字第一位非零数字 共共n位，称近似值有位，称近似值有n位有效数字。位有效数字。设设 x 为准确值，为准确值，x*为为 x 的近似值且的近似值且x*表示为表示为 换言之，如果换言之，如果称称x*具有具有n位位有效数字。有效数字。定义定义11 一个十进制数近似值的有效数字，不受单位制的影响。一个十进制数近似值的有效数字，不受单位制的影响。 如如g* = 9.81m/s2作为作为g 的近似值，与的近似值，与g* = 0.00981km/s
10、2，均均 为为3位有效数字。位有效数字。 在有效数意义下，不同的有效数位数的近似值的近似精在有效数意义下，不同的有效数位数的近似值的近似精度是不同的。如度是不同的。如10.4200的精度高于的精度高于10.42：前者的绝对误前者的绝对误差不超过：差不超过：后者的绝对误后者的绝对误差不超过：差不超过：有效数字与绝对误差有一定的关系。对于某量的近似有效数字与绝对误差有一定的关系。对于某量的近似值，如果有值，如果有n位有效数字，当位有效数字，当m一定时，一定时，n越大则相对越大则相对误差越小。误差越小。结论结论12定理定理定理定理 ( (有效数字与相对误差的关系有效数字与相对误差的关系有效数字与相对
11、误差的关系有效数字与相对误差的关系) )：设近似值设近似值x*表示为表示为若若x*具有具有n位有效数字，则其相对误差限为位有效数字，则其相对误差限为反之，若反之，若x*的相对误差限的相对误差限则则x*至少具有至少具有n位有效数字。位有效数字。13证明证明：由由x*的表达式可得：的表达式可得：又由定义可知又由定义可知有效数位越多，有效数位越多，相对误差越小相对误差越小所以所以反之，则有：反之，则有：因此，因此， x*具有具有n位有效数字。位有效数字。14为使为使 近似值的相对误差小于近似值的相对误差小于1%，问需要取多少位有，问需要取多少位有效数字？效数字？解：解：的近似值的首位数字的近似值的首
12、位数字a1 = 2, 于是由于是由可解得可解得因此，可取因此，可取 n = 3 即即例：例：153 算法的稳定性和病态问题算法的稳定性和病态问题定义定义一个算法如果输入数据有误差，而在计算过程中一个算法如果输入数据有误差，而在计算过程中舍入误差舍入误差不增长，则称此算法是不增长，则称此算法是数值稳定的数值稳定的，否，否则称此算法为则称此算法为不稳定的不稳定的。一、算法稳定性定义一、算法稳定性定义16计算下式并估计误差。计算下式并估计误差。由分步积分公式，可得由分步积分公式，可得例例解：解：可以计算出下表：可以计算出下表：按递推关系按递推关系17n nn n0 00.63210.63215 50
13、.14800.14801 10.36790.36796 60.11200.11202 20.26420.26427 70.21600.21603 30.20740.20748 8-0.7280-0.72804 40.17040.17049 97.5527.552于是，取于是，取n=9，则有，则有于是，取于是，取n=8，则有，则有而而18现将递推公式改写为：现将递推公式改写为： ，并且取，并且取因此，可得新的递推公式：因此，可得新的递推公式：由上面的递推公式，可得到下面的计算结果：由上面的递推公式，可得到下面的计算结果：193.对于第二种方法，设对于第二种方法，设 ，有，有n nn n0 00.
14、63210.63215 50.14550.14551 10.36790.36796 60.12680.12682 20.26430.26437 70.11210.11213 30.20730.20738 80.10350.10354 40.17080.17089 90.06840.06841.第二种方法比第一种方法计算稳定。第二种方法比第一种方法计算稳定。2.对于第一种方法，设对于第一种方法，设 ，则有，则有分析：分析：因此，误差是逐次放大的。因此，误差是逐次放大的。因此，误差是逐次缩小的。因此，误差是逐次缩小的。20二、病态问题与条件数（针对问题本身）二、病态问题与条件数（针对问题本身）输入
15、数据的微小变动导致输出数据的较大误差，就输入数据的微小变动导致输出数据的较大误差，就被称为被称为病态问题病态问题。衡量是否病态的标准：衡量是否病态的标准：条件数条件数 不同的问题，条件数具体定义不同。不同的问题，条件数具体定义不同。对于函数值计算问题，条件数定义为：对于函数值计算问题，条件数定义为：一般情况下，条件数大于一般情况下，条件数大于10，就认为问题病态。，就认为问题病态。设设 f (x) = xn，则，则Cp = n，即对于该函数，误差会被放大，即对于该函数，误差会被放大n倍倍通过构造特殊算法来解决通过构造特殊算法来解决定义定义21条件数和函数的误差估计条件数和函数的误差估计 设原始
16、数据设原始数据设原始数据设原始数据x x1 1，x x2 2，x xn n，y y 与与与与x xi i有关，是由有关，是由有关，是由有关，是由x xi i计算所得计算所得计算所得计算所得的解。若的解。若的解。若的解。若x x1 1，x x2 2，x xn n, ,的近似值为的近似值为的近似值为的近似值为x x1 1* *，x x2 2* *， x xn n, ,* *，那么那么那么那么相应的解也有一定的误差，记为相应的解也有一定的误差，记为相应的解也有一定的误差，记为相应的解也有一定的误差，记为y y* *，此时此时此时此时解的绝对误差为解的绝对误差为解的绝对误差为解的绝对误差为: :e*(
17、y) = f (x*) f (x) e*(x) = x* x = f ( )(x* x) (中值定中值定理理)一元的情形：一元的情形：绝对误差条件数绝对误差条件数22x* 与与 x 非常接近时，可认为非常接近时，可认为 f ( ) f (x*) ，则有：则有：|e*(y)| | f (x*)|e*(x)|即：即：x*产生的误差经过产生的误差经过 f 作用后被放大作用后被放大/缩小了缩小了| f (x*)|倍。倍。故称故称| f (x*)|为为放大因子放大因子 或或 绝对条件数绝对条件数 .相对误差条件数相对误差条件数23一元的情形一元的情形 f 的条件数在某一点是的条件数在某一点是小小大大，则
18、称，则称 f 在该点是在该点是好条件的好条件的坏条件的坏条件的.24例例(病态问题病态问题) 设有方程组设有方程组A已知系数已知系数b测量数据测量数据x待求数据待求数据其中其中如果测量数据不够精确，即测量数据仅保留了如果测量数据不够精确，即测量数据仅保留了2位有效数字，位有效数字，即即 ，计算结果为，计算结果为以上问题称为病态的问题，病态是问题本身固有的。以上问题称为病态的问题，病态是问题本身固有的。那么很容易计算那么很容易计算若测量数据为准确数据，若测量数据为准确数据，即即254 机器计算的几个问题与算法设计原则机器计算的几个问题与算法设计原则数值计算的一般标准：数值计算的一般标准：数值计算
19、的一般标准：数值计算的一般标准：1. 1.运算次数的多少运算次数的多少运算次数的多少运算次数的多少( (计算效率计算效率计算效率计算效率); );2. 2.运算过程是否规律运算过程是否规律运算过程是否规律运算过程是否规律( (易编程易编程易编程易编程); );3. 3.需要记录的中间结果的多少需要记录的中间结果的多少需要记录的中间结果的多少需要记录的中间结果的多少( (储存量储存量储存量储存量); );4.运算方案能否控制误差的传播和积累以保证计算结运算方案能否控制误差的传播和积累以保证计算结果有足够的果有足够的精度（数值稳定性）精度（数值稳定性）26一、减少运算次数一、减少运算次数 不不仅仅
20、能能提提高高计计算算精精度度，而而且且能能减减少少误误差差的的积积累累1、对同一种计算方法，要选用计算量少的运算次序、对同一种计算方法，要选用计算量少的运算次序例例例例：计算多项式：计算多项式 的值。的值。27(b) 利用秦九韶算法：利用秦九韶算法：解解：(a)直接计算每一项再求和：直接计算每一项再求和：计算计算pn(x)的值只需做的值只需做n次乘法次乘法n次加法。次加法。则则计算计算pn(x)的递推公式：的递推公式：计算计算anxn需做需做n次乘法，次乘法，计算计算pn(x)的值需做乘法次数：的值需做乘法次数：加法次数：加法次数：n28(a) 利用级数利用级数2、对于不同的算法，要注意收敛速
21、度，讲效率、对于不同的算法，要注意收敛速度，讲效率例例 计算计算 ln2 的近似值，要求误差小于的近似值，要求误差小于10.解：解：取取x = 1，有，有误差误差计算量太大计算量太大29(b) 使用级数使用级数则，取则，取用前用前 9 项（即取项（即取 m = 8）计算就能达到精度要求计算就能达到精度要求:得：得：30若若 用四位有效数字进行计算时：用四位有效数字进行计算时：有理数的有限数集，即浮点有理数的有限数集，即浮点数集（参读教材数集（参读教材p22-29）一一个个好好的的算算法法必必须须是是数数值值稳稳定定的的，否否则则结结果果不不可可靠，计算失败（数值不稳定）。靠，计算失败（数值不稳
22、定）。1. 注意计算机数系的运算特点注意计算机数系的运算特点例例 讨论在计算机数系中分别用公式讨论在计算机数系中分别用公式 和和 a a b b mm1 1 m m2 2 准确值准确值准确值准确值 5.2435.243 5.243 5.243 8.3558.3558.3558.355 6.8006.8001.5561.556 6.7996.7991.5571.557 6.7996.7991.5561.556无误差时，必相等；有舍入误差时，可能不相等。无误差时，必相等；有舍入误差时，可能不相等。二、二、 数值计算中要构造和使用数值稳定的方法数值计算中要构造和使用数值稳定的方法求求a,b中点时所得
23、结果是否相同。中点时所得结果是否相同。31例例 4位有效数字舍入运算：位有效数字舍入运算：1234+0.4+0.3+0.2+0.1=12340.4+0.3+0.2+0.1+1234=1235若若 出出 现现 “溢溢 出出 ”应应立立即即中中断断应应避避免免出出现现 “大大数数吃吃小小数数”事先预防、事先预防、 事后解事后解决决 例例 求求解解:设设 则则 可防溢出可防溢出针对计算机的计算特点，必须注意：针对计算机的计算特点，必须注意：解解:计算机算法设计时，必须作到：计算机算法设计时，必须作到：322. 防止两接近的数相减防止两接近的数相减例例 求下列方程的根求下列方程的根解解: :(a) 用
24、用8位浮点数位浮点数 (有效数字有效数字)计算计算 是因为求是因为求 的误差的误差( (并不大并不大),),进行减法后导致不应忽视的进行减法后导致不应忽视的后果后果 准确准确不稳定不稳定33两接近数相减两接近数相减损失了有效数字损失了有效数字(b)用用4位浮点数位浮点数 (有效数字有效数字)计算计算(c)数值稳定的方法数值稳定的方法改用公式改用公式仍用仍用4 位浮位浮点数计算点数计算当当 | x | 1 时：时：几种经验技巧几种经验技巧34前面有例题，计算前面有例题，计算3. 设法控制误差的传播设法控制误差的传播 第二种方法比第一种方法计算稳定。第二种方法比第一种方法计算稳定。 对于第一种方法
25、，设对于第一种方法，设，则有，则有因此，误差是逐次放大的。因此，误差是逐次放大的。 对于第二种方法，设对于第二种方法，设，则有，则有因此，误差是逐次缩小的。因此，误差是逐次缩小的。(当时给出了两种方法当时给出了两种方法)必须小心控制误差的传播必须小心控制误差的传播并估计误差。并估计误差。35三三 计算过程中应十分小心处理病态的数学问题计算过程中应十分小心处理病态的数学问题引起引起函数的很大误差函数的很大误差病态问题病态问题病态问题一般要用高精度病态问题一般要用高精度( (双精度双精度) )计算或解病态问题计算或解病态问题的方法解决。的方法解决。 输入的很小输入的很小 的误差的误差361. 求求 的近似值的相对误差不超过的近似值的相对误差不超过0.1%，要取几位有效，要取几位有效数字？数字？作作 业业一、教材上的作业一、教材上的作业二、补充作业二、补充作业三、编程作业三、编程作业教材教材P. 43 1. P. 44 5. P. 44 8.2. 设设，假定，假定g是准确的，而对是准确的，而对t的测量有的测量有秒的误差，秒的误差，证明：当证明：当t增大时，增大时，S的绝对误差增大而相对误差却减小。的绝对误差增大而相对误差却减小。1. 用用MATLAB编程实现编程实现P44. 第第7题题(x = 3 时时)，写出相应代码。，写出相应代码。37
