数值分析第一章

1、1 数值分析 主讲数值分析课题组 Chenning 2 数值分析课程简介数值分析课程简介 数值分析主要包括数值分析主要包括计算方法计算方法和和数值方法数值方法两两 部分。它是部分。它是研究科学与工程技术中数学问题的研究科学与工程技术中数学问题的 数值解及其理论数值解及其理论的一个重要的数学分支，它主的一个重要的数学分支，它主 要涉及到要涉及到代数代数、微积分微积分、微分方程的数值解微分方程的数值解等等 问题。问题。 数值分析及计算的主要任务，就是数值分析及计算的主要任务，就是研究适合研究适合 于在计算机上使用的的于在计算机上使用的的数值计算方法数值计算方法及与此及与此相相 关的理论，如方法的收

2、敛性、稳定性及误关的理论，如方法的收敛性、稳定性及误差分差分 析等。析等。此外，还要根据计算机的特点，研究计此外，还要根据计算机的特点，研究计 算时间最短、需要计算机内存最优等计算方法算时间最短、需要计算机内存最优等计算方法 问题。问题。 数值分析数值分析 3 第一章第一章 数值计算中的误差分析数值计算中的误差分析 第二章第二章 线性方程组的直接解法线性方程组的直接解法 第六章第六章 曲线拟合曲线拟合 第七章第七章 数值积分与数值微分数值积分与数值微分 第九章第九章 常微分方程的数值解法常微分方程的数值解法 目目 录录 第八章第八章 非线性方程的数值解法非线性方程的数值解法 第五章第五章 函数

3、插值函数插值 第三章第三章 线性方程组的迭代解法线性方程组的迭代解法 第四章第四章 矩阵特征值特征向量的计算矩阵特征值特征向量的计算 数值分析数值分析 4 第一章第一章 数值计算中的误差分析数值计算中的误差分析 ：本章的主要内容有 （一） 误差的来源；误差的来源； （二）（二） 绝对误差、相对误差和有效数值绝对误差、相对误差和有效数值; ; （三）（三） 数值计算中误差的传播；数值计算中误差的传播； （四）（四） 数值计算中应注意的问题数值计算中应注意的问题。 数值分析数值分析 5 第一节第一节 误差与数值计算误差与数值计算 的误差估计的误差估计 第二节第二节 选用和设计算法选用和设计算法 适

4、应遵循的原则适应遵循的原则 数值分析数值分析 6 误差与数值计算误差估计误差与数值计算误差估计 一一 误差的来源与分类误差的来源与分类 二二 误差与有效数字误差与有效数字 数值分析数值分析 7 一一 误差的来源与分类误差的来源与分类 按照误差的来源按照误差的来源, ,误差可以分为误差可以分为: :模型误差模型误差、观测误差观测误差 、截断误差截断误差、舍入误差舍入误差四种四种. . 1. 模型误差模型误差 用数值计算方法解决问题时用数值计算方法解决问题时, ,首先必须首先必须建立数学模型建立数学模型. .由由 于实际问题的复杂性于实际问题的复杂性, ,在对实际问题进行抽象与简化时在对实际问题进

5、行抽象与简化时, ,往往 往为了抓住主要因素而忽略了一些次要因素往为了抓住主要因素而忽略了一些次要因素, ,这样就会使得这样就会使得 建立起来的数学模型只是复杂客观现象的一种近似描述建立起来的数学模型只是复杂客观现象的一种近似描述, ,它它 与实际问题之间总会有一些误差与实际问题之间总会有一些误差. .我们把这种数学模型与实我们把这种数学模型与实 际问题之间出现的这种误差称为际问题之间出现的这种误差称为模型误差模型误差. . 数值分析数值分析 8 2 2 观测误差观测误差 在数学模型中往往有一些观测或实验得来的物理在数学模型中往往有一些观测或实验得来的物理 量量, ,由于测量工具和测量手段的限

6、制由于测量工具和测量手段的限制, ,它们与实际量大它们与实际量大 小之间必然存在误差小之间必然存在误差, ,这种误差称为这种误差称为观测误差观测误差. . 3 3 截断误差截断误差 由实际问题建立起来的数学模型由实际问题建立起来的数学模型, ,在很多情在很多情 况下要得到况下要得到 准确解是困难内的准确解是困难内的, ,通常要用数值方法求出它的近似解通常要用数值方法求出它的近似解. .这这 种数学模型的精确解与由数值方法求出的近似解之间的种数学模型的精确解与由数值方法求出的近似解之间的 误差称为误差称为截断误差截断误差,由于截断误差是数值计算方法固有的由于截断误差是数值计算方法固有的, , 故

7、又称为故又称为方法误差方法误差. . 9 4 4 舍入误差舍入误差 用计算机进行数值计算时用计算机进行数值计算时, ,由于计算机的数位有由于计算机的数位有 限限, ,计算时只能对超过位数的数字进行四舍五入计算时只能对超过位数的数字进行四舍五入, ,由此由此 产生的误差称为产生的误差称为舍入误差舍入误差. . 二二 . .误差与有效数字误差与有效数字 1 1 绝对误差与绝对误差限绝对误差与绝对误差限 e=x-x*. 称为近似值称为近似值x x* *的的绝对误差限绝对误差限。 * xxe 简称简称误差限误差限或或精度精度. 设设x x* *为准确值为准确值x x的一个近似值，称的一个近似值，称 为

8、近似值为近似值x x* *的的绝对误差绝对误差 10 有了误差限和近似值，可得到准确值范围有了误差限和近似值，可得到准确值范围 * .xxx 易知，由四舍五入所得到的数，其易知，由四舍五入所得到的数，其误差限误差限 一定一定不超过被保留数不超过被保留数的的最后数位最后数位上的上的半个单位半个单位 2 1 3.143.140.001610 . 2 ( 3.14163.140.0016) 3 1 3.1423.1420.0004110 2 (3.142413.1420.00041) 11 123 1 43 1 3.14159265.3.142,3.141,22 7. 3.141593.1423.1

9、423.14159 11 0.00040,1010 , 22 xxx x x 例：问例：问3.142,3.141,22/7分别作为分别作为 的近似值各具有几位有效数字？的近似值各具有几位有效数字？ 3.142具有具有4位有效数字；位有效数字； 1 32 2 3.141593.1410.00059, 11 1010, 22 x x 3.141具有具有3位有效数字；位有效数字； 3 32 22 73.141593.142850.00126, 11 1022 710 , 22 x 22/7具有具有3位有效数字。位有效数字。 12 2 2 绝对误差、相对误差和其绝对误差、相对误差和其误差误差限限 设设

10、x x* *为准确值为准确值x x的一个近似值，称的一个近似值，称绝对绝对 误差限误差限与与准确值准确值之比为近似值之比为近似值x x* *的的相对误差相对误差。 记记: : * , rr e e x * r exx e xx 称为称为x x* *的的相对误差限相对误差限。 若存在正数若存在正数 , ,使得使得 13 3 3 有效数字有效数字 有效数字有效数字。 x ,xn xn 如果近似值 的误差限是其某一位上的半个单 位且该位直到 的第一位非零数字一共有 位，则 称近似值 有 位 1 * , n x 自左向右看，第一个非零数自左向右看，第一个非零数 误差不超过该数的半个单位。误差不超过该数

11、的半个单位。 14 * x x 一般地，任何一个实数 经过四舍五入后得 到的近似值式都可以写成如下标准形 *12 12 1211 (101010 ) 10 0.10. nm n m nmmn x 为所以，当其绝对误差限 nm xx 10 2 1 * 数。 中的到是，中的数，到是整数 为位有效数字，其中具有时，则称近似值 9091, 321 * n mnx 15 有三位有效数字。 表示近似数0.003400准确到小数点后第五位, 例例1-1： 5 1 0.00340010 2 x 是具有7位有效数字的近似数， 其误差限是 *3 1 104 73 2 xxm n * 1452.046x 例例1-2

12、： 16 绝对误差（限）绝对误差（限） 相对误差（限）相对误差（限） 有效数字有效数字 nm xx 10 2 1 * * r exx e xx 1 1 1 10 2 n a * 12 1 0.10 (0) m n xa aa an 有 位 1 1 1 10 2(1) n r a * 12 1 0.10 (0) m n xa aa an 有 位 有效数字与绝对误差、相对误差的关系有效数字与绝对误差、相对误差的关系 , rr ee 17 4 4 有效数字与绝对误差、相对误差的关系有效数字与绝对误差、相对误差的关系： 的绝此近似值 位有效数字，则有的近似值若某数 * * ) 1 ( x nxx 对误

13、差限为 nm xx 10 2 1 * * 121 1* 1 1 1 * (2)0.10 (0) 1 10, 2 1 10 2(1) m n n r n r xxa aaan x a a xn 若 的近似值有 位有效数字， 则为其相对误差限。反之 若 的相对误差限 满足 则 至少具有 位有效数字。 18 解解 于是有 字是的近似值的首位非零数, 420 1 %110 42 1 )( ) 1(* n rx 即可满足要求。故取解之得3,2nn EX:P13.5 19 小结小结 模型误差模型误差 观测误差观测误差 截断误差截断误差 舍入误差舍入误差 绝对误差绝对误差 绝对误差限绝对误差限 相对误差相对

14、误差 相对误差限相对误差限 有效数字有效数字 有效数字与绝对误差、相对误差的关系有效数字与绝对误差、相对误差的关系 20 第二节第二节 选用和设计算法适应选用和设计算法适应 遵循的原则遵循的原则 一、选用数值稳定的计算公式，控制舍入误差的一、选用数值稳定的计算公式，控制舍入误差的 传播传播 二、尽量简化计算步骤以减少计算次数二、尽量简化计算步骤以减少计算次数 三、尽量避免两个相邻的数相减三、尽量避免两个相邻的数相减 四、小结四、小结 21 * 1212 ()(,)(,) nn e yyyf xxxf xxx n i i i n xe x xxxf 1 * * 2 * 1 * )( ),( 基本

15、运算：基本运算：指四则运算和常用函数的计算。设数值指四则运算和常用函数的计算。设数值 n xxx, 21 ),( 21n xxxf n xxx, 21 nxxx * 2 * 1 * , ),( * 2 * 1 * nxxxfy 近似值分别是近似值分别是 相应的解为相应的解为 计算中求解与参量计算中求解与参量有关有关, ,记：记： 1、基本运算的误差估计、基本运算的误差估计 设设 在点在点 可微可微, ,当数据误差较小当数据误差较小 时，解的时，解的绝对误差绝对误差为为 ),( * 2 * 1 * nxxxf 22 解的解的相对误差相对误差为为 )( ),( ),( )(ln )( )( * *

16、 1 * 1 * 1 * * * ir n i n i i n r xe xxf x x xxf fd y ye ye 注注:函数的和、差、函数的和、差、积、积、商的部分误差商的部分误差公式为：公式为： ),()()( 2121 xexexxe )()()( 2 21 2 1 21 1 21 xe xx x xe xx x xxe rrr )()/()()/( 2 2 211 2 1 21 xexxxxxxe )()()/( 2121 xexexxe rrr 1 22112 ()( )( )e xxx e xxe x 1 212 ()( )( ) rrr e xxe xe x 23 )()()

17、()()/( )()()()()( )()()()()( 212121 212121 212121 xexexexexxe xexexexexxe xexexexexxe rrrrr rrrrr 可得： 即：和、差的误差限不超过各数的误差限的和，积、即：和、差的误差限不超过各数的误差限的和，积、 商的相对误差限不超过各数的相对误差限的和。商的相对误差限不超过各数的相对误差限的和。 则则 的相对误差为的相对误差为x x相对误差的相对误差的n n倍倍。特别有。特别有 相对误差为相对误差为x x相对误差的相对误差的0.50.5倍。倍。 n xx n xy 例例1 1、设、设 , ,求求y y的相对误

18、差与的相对误差与x x的相对误差之的相对误差之 间的关系。间的关系。 )()(ln)(ln)(xnexndxdye r n r 解解：由公式知，：由公式知， 24 1 0 )5/(dxxxI n n (1) )( 1 , 1, 1 5 1 )(, 2 , 1,5 1 1 1 BnnkI k I AnI n I kk nn (2) 算法算法1：x=0.182322 for n=1:20 n x=-5*x+1/n end 算法算法2：x=0.00873016 for n=20:-1:1 n-1 x=-(1/5)*x+1/(5*n) end x =0.1823 n =1 x = 0.0884 n =

19、2 x =0.0581 n = 3 x = 0.0431 n = 4 x = 0.0346 n = 5 x = 0.0271 n =6 x = 0.0313 n =7 x =-0.0134 n = 8 x =0.1920 n = 9 x = -0.8487 n =1 x = 4.3436 n =11 x =-21.6268 n =12 x =108.2176 n =13 x =-541.0110 n =14 x =2.7051e+003 n =15 x = -1.3526e+004 n =16 x =6.7628e+004 n =17 x = -3.3814e+005 n =18 x =1.6

20、907e+006 n =19 x =-8.4535e+006 n =20 x =4.2267e+007 x = 0.0087 ans = 19 x = 0.0083 ans = 18 x = 0.0089 ans =17 x = 0.0093 ans = 16 x = 0.0099 ans = 15 x = 0.0105 EX 25 一个算法是否稳定是非常重要的，如果算法不一个算法是否稳定是非常重要的，如果算法不 稳定，则数值的结果就会严重背离数学模型的稳定，则数值的结果就会严重背离数学模型的真实真实 结果结果。在选择数值计算公式来进行计算时，应用在。在选择数值计算公式来进行计算时，应用在 数

21、值计算过程中不会导致误差迅速增长的计算公式。数值计算过程中不会导致误差迅速增长的计算公式。 一、选用数值稳定的计算公式，控制舍一、选用数值稳定的计算公式，控制舍 入误差的传播入误差的传播 例例 1 计算定积分计算定积分 1 0 1 dxexeI xn n (1.2.1) 26 解解 算法一算法一 利用分部积分法不难求得递推关系式利用分部积分法不难求得递推关系式: : (1.2.2) 6321. 01 1 1 0 1 eI nII nn 由上式可计算得 7280. 0,7200. 0,0400. 0 1600. 0,1680. 0,2080. 0 2640. 0,3680. 0,6321. 0

22、876 543 210 III III III 27 由于 (1.2.3) 1 1 )(max0 1 010 1 n dxxeeI nx x n 125. 0 8 1 7 I :. ,)2 . 2 . 1 ( 87 原因在于果是错误的 的结算出的可见按递推关系式II 则由以上的则由以上的 的不等式可以看出的不等式可以看出 n I 28 . ,87, , ,10 2 1 878 7 4 0 的结果错误 从而使得倍与该误差放大了时 与传播到很快此误差在运算中传播得 的舍入误差本身有不超过 III I I 算法二算法二改写为将递推关系式)2 . 2 . 1 ( )1 ( 1 1nn I n I 29

23、 因为 1 0 1 10 1 1 )(min n e dxxeeI nx x n 可得结合)3 . 2 . 1 ( 1 1 1 1 n I n e n 有 由作初始值取时当)4 . 2 . 1 (,1124. 0,7 7 In 30 6320. 0,3680. 0 2643. 0,2073. 0,1708. 0 1455. 0,1269. 0,1124. 0 01 234 567 II III III .6321. 0 , , 0 7 相差无几的精确结果与 最后便得到小的的计算过程中是逐渐减 引起的初始误差在以后由于此时 I I 31 s0=1-exp(-1); s1=1-s0; for n=

24、2:20 s(n)=1-n*s(n-1); end s(1:20) n 1 1 nn II n 1 1 nn II n 1 1 nn II 0123456 0.63210.36790.2642 0.207 3 0.17090.14550.1268 78910111213 0.11240.10090.0916 0.083 9 0.07740.07180.0669 14151617181920 0.06270.05900.0555 0.057 2 - 0.0295 1.5596-30.1924 s(30)=1/31; for n=30:-1:2 s(n-1)=(1-s(n)/n; end s(1:

25、20) n nII nn / )1 ( 1 n nII nn / )1 ( 1 n nII nn / )1 ( 1 20191817161514 0.63210.36790.26420.20730.17090.14550.12680.11240.10090.09160.08390.07740.07180.0669 6543210 0.06270.05900.05570.05280.05010.04770.0455 32 二、尽量简化计算步骤以减少计算次数二、尽量简化计算步骤以减少计算次数 同样一个问题同样一个问题, ,如果能减少运算次数如果能减少运算次数, ,不但不但 可以节省计算机的计算时间可以节省计算机的计算时间, ,而且还能减少舍而且还能减少舍 入误差入误差, ,这是数值计算必须遵守的原则这是数值计算必须遵守的原则. . 例例2 256 .x计算的值 解解,255 , x若将 的值逐个相乘 那么需要作次 乘法 但若写成 256248163264128 xxxxxxxxxx .只 要 作 8次 乘 法 就 可 以 了 33 三、尽量避免两个相邻的数相减三、尽量避免两个相邻