何曙光 2005年 9月 数值计算方法数值计算方法 主要内容主要内容 第一章 绪论 1） 有关数值方法的基本概念 2） 误差 3） 有效数字 第二章 方程的求解 1） 二分法 2） 迭代法 3） 牛顿法 4） 弦截法 第三章 插值计算 1） 拉格朗日插值 2） 埃特肯插值 3） 牛顿插值 4） 分段插值 5） 样条插值 第四章 数值积分与数值微分 1） 牛顿 — 柯特斯公式 2） 龙贝格算法 3） 数值微分 第五章 线性方程组的直接解法 1） 高斯消去法 2） 三角分解法 第六章 线性方程组的迭代法 1） 雅可比迭代法 2） 塞德尔迭代法 3） 迭代法的收敛性及误差分析 第七章 矩阵特征值与特征向量的计算 1） 幂法 2） 反幂法 主要参考书 施吉林 ， 刘淑珍 ， 陈桂芝 . 计算方法 . 高等教育出版社 . 1999 王能超 . 数值分析简明教程 （ 修订 版 ） . 华中科技大学出版社 . 2002 总学时 （ 40学时 ） 其中 授课 ： 32学时 上机 ： 8学时 先修课程 高等数学 线性代数 C语言等 授课方式 理论讲解 算法分析 上机实践 第一章 引论 第一章 引论 1.3 误差§ 1.1 数值计算的研究对象与特点§ 1.2 数值问题与数值方法§ 本章要点 : 绝对误差 (限 )和相对误差 (限 ) 有效数字位数及其与误差的关系 数值问题的性态与误差的关系 数值算法设计原则 1.1 计算机数值方法的研究对象与特点§ 以计算机为工具 ,求解各种数学模型 ,都要经历三个过程 : 总体设计 ——模型的细化 详细设计 ——主要为算法设计 程序设计 计算机数值方法研究的是将数学模型化为数值问题 ， 并研究求解数值问题的数值方法进而设计数值算法 数值问题 ： 输入数据与输出数据之间函数关系的一个确定而无歧义的描述 即 ： 输入与输出的都是数值的数学问题 如求解线性方程组 bAx = 求解二次方程 02 =++ cbxax cbabA ,,, 与系数常数项向量输入的数据是系数矩阵 是数值问题 一 、 数值问题 1.2 数值问题与数值算法§ 求解微分方程 ?? ? = +=′ 0)0( 32 y xy 不是数值问题 xxy 3, 2 +=函数但输出的不是数据而是输入的虽是数据 将其变成数值问题 ， 即将其 “ 离散化 ” xxy 32 +=即将求函数 nn xxxxyxyxy <<< LL 2121 ),(,),(),(改变成求函数值 “ 离散化 ” 是将非数值问题的数学模型化为数值问题 的主要方法 ， 这也是计算方法的任务之一 21 ,, xxx 和方程的解输出的数据是解向量 二 、 数值方法 数值方法 : 是指解数值问题的在计算机上可执行的系列计算公式 在计算机上可执行的公式 是指只含有加减乘除的公式 现在的计算机中几乎都含有关于开方的标准函数 sqrt() 常见的在计算机上不能直接运行的计算有 : 开方 、 极限 、 超越函数 、 微分 、 积分等等 要在计算机上实行上述运算需将其化为可执行的等价 或近似等价运算 xe超越函数 应化为 !!21 2 n xxxe nx ++++≈ L 的计算应化为的导数函数 )()( xyxy ′ h xyhxyxy )()()( ?+≈′ 如求根公式 a acbbx 2 4 2 2,1 ?±?= 应化为公式 a acbsqrtbx 2 )4( 2 2,1 ?±?= 研究数值方法的主要任务 : 1.将计算机上不能执行的运算化为在计算机上可 执行的运算 2.针对所求解的数值问题研究在计算机上可执行 的且有效的计算公式 3.因为可能采用了近似等价运算 ,故要进行误差分析 , 即数值问题的性态及数值方法的稳定性 本课程的重点就是对线性方程组 、 微积分 、 微分方程 、 矩阵特征值及回归拟合等问题寻找行之有效的数值方法 三 、 数值算法 数值算法是指有步骤地完成解数值问题的过程 . 数值算法有四个特点 : 1.目的明确 算法必须有明确的目的 ,其条件和结论均应有清楚的规定 2.定义精确 对算法的每一步都必须有精确的定义 3.可执行 算法中的每一步操作都是可执行的 4.步骤有限 算法必须在有限步内能够完成解题过程 例 1. 给出等差数列 1,2,3,… ,10000的求和算法 解 : 0,0.1 == SN取 记数器置零 SNSNN ?+?+ ,1.2 ， 否则转若 2,10000.3 <N SN ,.4 输出 1.3 误差§ 一 、 误差的种类及来源 模型误差 在建立数学模型过程中 ,要将复杂的现 象抽象归结为数学模型 ,往往要忽略一 些次要因素的影响 ,而对问题作一些简 化 ,因此和实际问题有一定的区别 . 观测误差 在建模和具体运算过程中所用的数据往 往是通过观察和测量得到的 ,由于精度的 限制 ,这些数据一般是近似的 ,即有误差 截断误差 由于计算机只能完成有限次算术运算和逻辑运算 ,因此要将有些需用极限或无穷 过程进行的运算有限化 ,对无穷过程进行 截断 ,这就带来误差 . L++++= !3!21 32 xx xex L+?+?= !7!5!3sin 753 xxx xx L+?+?=+ !4!3!2)1ln( 432 xxx xx 如 : 若将前若干项的部分和作为函数值的近似公式 , 由于以后各项都舍弃了 ,自然产生了误差 Taylor展开 舍入误差 在数值计算过程中还会遇到无穷小数 ,因 计算机受到机器字长的限制 ,它所能表示 的数据只能有一定的有限位数 ,如按四舍 五入规则取有限位数 ,由此引起的误差 L14159265.3=p L414213562.12 = L166666666.061!31 == 1415927.3≈p 4142136.12 ≈ 16666667.0!31 ≈ 过失误差 由于模型错误或方法错误引起的误差 . 这类误差一般可以避免 数值计算中除了过失误差可以避免外 ,其余误差都是 难以避免的 .数学模型一旦建立 ,进入具体计算时所考 虑和分析的就是截断误差和舍入误差 经过大量的运算之后 ,积累的总误差有时会大得惊人 , 因此如何控制误差的传播也是数值方法的研究对象 . 二 、 误差和误差限 定义 1. 称的一个近似值为为准确值设 ,, * xxx xxxE ?= ** )( .,,* Ex 可简记为简称误差的绝对误差为近似值 知道的往往是未知甚至是无法因为准确值 x 往往也无法求出因此 xxxE ?= ** )( 即绝对值的某个上界而只能知道 ,)( ** xxxE ?= )(|||)(| *** xxxxE e≤?= 的称为数值 ** )( xxe 绝对误差限或误差限 , e简记为 显然 ee +≤≤? ** xxx 的范围准确值 x 或 e±= *xx 0>e 且 215 ±=x若对于 51000 ±=y 15* =x 1000* =y 2)( * =xe 5)( * =ye 哪个更精确呢 ? 吗 ？15* =x 定义 2. 称的一个近似值为为准确值设 ,, * xxx x xx x xExE r ?== *** )()( .,* rEx 可简记为的相对误差为近似值 rrr xx xxxE ee =≤?= )()( *** 的相对误差限为近似值 *x relative error || xr ee = 绝对误差限相对误差限 往往未知 * * * * ** )()( x xx x xExE r ?== || * * xr ee = 代替相对误差 代替相对误差限 15* =x 1000* =y 2)( * =xe 5)( * =ye 因此 %33.1315 2)( ** ==x re %5.010005)( ** ==yre 例 1. . ,28718.2,82281718.2 ** * re ee ee和相对误差限的绝对误差限求 其近似值为已知 == L 解 : eeE ?= *绝对误差 L82001000.0?= L82001000.0|| =E 002000.0≤ 6102 ?×= 6102 ?×=e || * * er ee = 28718.2 102 6?×= 28718.2 102 6?×= 61071.0 ?×≈ 是唯一的 并不和 *ree 例 2. . ,7,5,3 e p 求绝对误差限 位数的近似值经四舍五入取小数点后若 解 : L65592141.3=p 59141.3* =p 142.3* =p 7592141.3* =p epp ≤? || * L407000.0 L65002000.0 L04000000.0 3105.0 ?×≤ 5105.0 ?×≤ 7105.0 ?×≤ 可见 ,经四舍五入取近似值 ,其绝对误差限将 不超过其末位数字的半个单位 有 4位有效数字 有 6位有效数字 三 、 有效数字 定义 3. ., , , , * * * * 位有效数字有简称有效数字 位时具有近似则称用位一位非零数字共有 的第而该位数字到单位超过某一位数字的半个 其绝对误差的绝对值不的近似值作为若 nx nxxn x xx L65592141.3=p 59141.3* =p142.3* =p 7592141.3* =p 有 8位有效数字 1415.3* =p 只有 4位有效数字 形式 ：的下列形式称为规格化的近似值 *xx k naaax 10.0 21 * ×±= L k naaax 10. 21 * ×±= L 则四舍五入得到的近似值 位数的第是对如果 , 110.0 21* +×±= nxaaax knL 位有效数字具有 naaax kn 10.0 21* ×±= L 且 |||| * xxE ?= nk ?×≤ 105.0 因此 ,可根据上述分析对有效数字有如下结果 : 01 ≠a 或 定理 1. 的近似值满足作为若 xx* |||| * xxE ?= nk ?×≤ 105.0 k maaax 10.0 21 * ×±= L 位有效数字至少有 nx* 例 3. 求下列四舍五入近似值的有效数字个数 . 218.0*1 =x 18002.0*2 =x 180.2*3 =x 0.218*4 ?=x 2* 5 1018.2 ×=x 6* 5 1000218.0 ?×=x 3个 3个 4个 4个 3个 5个 位有效数字恰好有时而 mxnm *,≤ ,时则 nm ≥ 例 4. 个近似值有设 395.3=x 0.4*1 =x 9.3*2 =x 4*3 =x || *1 xx ? |95.30.4| ?= 05.0= 21105.0 ?×≤ || *2 xx ? |95.39.3| ?= 05.0= 21105.0 ?×≤ || *3 xx ? |95.34| ?= 05.0= 21105.0 ?×≤ 都至少有两个有效数字知根据定理 *2*1 ,,1 xx 都具有两个有效数字即 *2*1 , xx ?*3 字吗也至少具有两个有效数x 实际上只 1有个 例 5. :1000 效数字位数的下面两个近似值的有判断 =x 9.999*1 =x 1.1000*2 =x 3109999.0 ×= 41010001.0 ×= |||| *11 xxE ?= 1.0= 33105.0 ?×≤ |||| *22 xxE ?= 1.0= 44105.0 ?×≤ 位有效数字有所以 3*1x 位有效数字却有而 4*2x 从以上分析可见 ,四舍五入的近似值的数字都是有效数字 而不是四舍五入得到的近似值的数字不一定是有效数字 定理 2. 的近似值的表达式为作为若 xx * k maaax 10.0 21 * ×±= L 满足则其相对误差位有效数字有若 ** ,)1( rEnx 位有效数字至少有则 nx* 1* 105.0|| +?×≤ n rE 满足的相对误差若反之 **,)2( rEx nrE ?×≤ 105.0|| * 证明 : kmaaax 10.0 21* ×±= L 有位有效数字时有当 ,)1( * nx |||| * xxE ?= nk ?×≤ 105.0 kk x 10||101.0 * ≤≤× ≤? xx* ≤? xx * * * *|| x xxE r ?= ≤ nk ?× 105.0 k101.0 × 1105.0 +?×= n 1* 105.0|| +?×≤ n rE即 满足的相对误差若 **)2( rEx nrE ?×≤ 105.0|| * * * *|| x xxE r ?= k10 n?× 105.0 k10× n?×≤ 105.0 nk ?×= 105.0 则有 则由定理 1.可知 位有效数字至少有则 nx* |||| *11 xxE ?= 例 6: 986.11 =x设 014.12 =x 98.1*1 =x 01.1*2 =x .*2*1 误差限的有效数字位数与相对与分别求 xx 31105.0 ?×≥ 解 : * 1 1 * 1* 1 ||)1( x xxE r ?= = 006.0 98.1 2105.0 ?×≤ 位有效数字至少有根据定理 2,2 *1x 006.0= 位有效数字不会有位有效数字有因此 3,2*1x |||| 2*22 xxE ?= 31105.0 ?×≤ * 2 2 * 2* 2 ||)2( x xxE r ?= = 004.0 01.1 2105.0 ?×≤ 位有效数字至少有根据定理 2,2 *2x 004.0= 位有效数字有因此 3*2x 位有效数字必然有经四舍五入得到事实上 3,*2x 定理 3． 的近似值的表达式为作为若 xx * k maaax 10.0 21 * ×±= L 满足则其相对误差位有效数字有若 ** ,)1( rEnx 位有效数字至少有则 nx* n r aE ?×≤ 1 1 * 10 2 1|| 满足的相对误差若反之 **,)2( rEx n r aE ?× +≤ 1 1 * 10 )1(2 1|| 该 结论可以参照定理 2的证明 ， 请同学们自证 补充 例 7. 少取几位有效数字 ？ ， 应至的相对误差不超过要使 %1.020 解 : .420 1 =a的首位数是 .*20 位有效数字有的近似值设 nx n r ax xxE ?× ×≤ ?= 1 1 * 10 2 1 |*| |*||| 则有 定理 3,相对误差满足 001.01042 1 1 ≤×× ?n %1.0≤ 097.3≥n 即应取 4位 有效数字 ,近似值的误差不超过 0.1%. 五 、 浮点数和浮点运算 (略 ) 六 、 数值方法的稳定性与算法设计原则 例 8. ∫= 101 dxexeI xnn 计算定积分 7,,2,1,0 L=n 解 : nI ∫= 1 0 1 xndex e 1 0 1 xnex e= ∫ ?? 1 0 1 dxex e n xn 11 ??= nnI ,0I如果先计算 721 ,,, III L然后再计算 ,*00 II 的近似值为假设计算出 d=)( *0IE误差为 d=)( *1*11 IEII 的误差为的近似值则 d2)( *2*22 =IEII 的误差为的近似值 d!3)( *3*33 =IEII 的误差为的近似值 LLLLLL d!7)( *7*77 =IEII 的误差为的近似值 d5040= 误差放大 5千倍 ! n II n n ?= ? 1 1但如果利用递推公式 ,7I先计算 !570 千分之一误差的的误差只有 II 因此在计算公式选用及算法设计时 ,应注意以下原则 1. 四则运算中的稳定性问题 (1) 防止大数吃小数 这一类问题主要由计算机的位数引起 假如作一个有效数字为 4位的连加运算 11 ??= nn nII公式 n II n n ?= ? 1 1公式 误差会放大 误差不会放大 4012.04697.04896.04987.01234.010 4 ++++× 1234.010 4 ×= ""4697.0,4896.0,4987.01234.010 4 吃了将小数大数 × 而如果将小数放在前面计算 1234.0104012.04697.04896.04987.0 4 ×++++ 1236.010 4 ×= 在作连加时 ,为防止大数吃小数 ,应从小到大进行相加 , 如此 ,精度将得到适当改善 .当然也可采取别的方法 . (2) 作减法时应避免相近数相减 两个相近的数相减 ,会使有效数字的位数严重损失 01.0cos1 ? 510999958.4 ?×= xcos1 ? 2sin2 2 x= 2 01.0sin2 2 510999958333.4 ?×= 由于 在算法设计中 ,若可能出现两个相近数相减 ,则改变 计算公式 ,如使用三角变换 、 有理化等等 例 9. 解方程 010)110( 992 =++? xx 解 : 由中学知识韦达定理可知 ,方程的精确解为 9 1 10=x 12 =x a acbsqrtbx 2 )4( 2 2,1 ?±?= 而如果在字长为 8,基底为 10的计算机上利用求根公式 1109 +=? b 10101.0 ×= 10100100000000.0 ×+ 机器吃了 因此在计算机上 10101.0? ×=? b 101000000000.0 ×+ 10101.0 ×= 910= a acbsqrtbx 2 )4( 2 1 ?+?= )4( 2 acbsqrt ? 9210 1014)101.0(? ××?×?= 910?= a acbsqrtbx 2 )4( 2 2 ???= 可得利用根的关系 acxx =? 21 9 99 102 1010? =+= 02 1010? 99 =?= 1x若已算出 1 2 1 xa cx ?= 1 10 1 1 10 9 9 =?= 上式是解二次方程的数值公式 (3) 避免小数作除数和大数作乘数 由误差传播的 估 计式 )( yE 2112 ee ?+?≤ xx 21 xxy ?=对于 2 1 x xy =对于 )( yE 22 2 1 1 2 1 ee ?+?≤ x x x ↑|||| 21 xx 或 ↑)( yE ↓|| 2x ↑)( yE 在算法设计时 ,要避免这类算法在计算公式中出现 2. 提高算法效率问题 (1) 尽量减少运算次数 2562 128643216842 222222222 ????????= 15次乘法运算而不是 255次 使用秦九韶算法 01 1 1)( axaxaxaxp n n n n +++= ? ? L 0121 )))((()( axaxaxaxaxp nnn ++++= ?? LL 对多项式 可大大减少计算量 (2) 尽量使用耗时少的运算 都要节省运算时间比比比如 425.0,,2 2 xxxxxxxx ??+ (3) 充分利用存储空间