数值分析-数值计算方法

1、数值计算方法数值计算方法The Method of Numerical ComputationNumerical Analysis教教 材材林成森 编著数值计算方法 上下册科学出版社 1998先行课程先行课程 数学分析 ( Mathematical Analysis ) 线性代数 ( Linear Algebra ) 常微分方程 ( Original Differential Equation 简写为 ODE ) 计算机基础及计算机语言第一章第一章 算术运算中的误差分析初步算术运算中的误差分析初步 数值方法、算法 误差来源 误差大小的衡量方法 舍入误差与有效数字 数据误差在算术运算中的传播 机

2、器误差数值方法数值方法( (Numerical Method)Numerical Method)： 数值方法是对给定问题的输入数据和所需计算结果之间的关系的一种明确的描述。例： 用 Newton 法 ( 将在 Ch2 4 中讨论) 计算 3 。给定3的一个初始近似值 )0(,00 xx由迭代公式： ,2, 1,)3(2111nxxxnnn产生一个序列 ,10nxxx算法：算法：( (Algorithm)Algorithm) 它是算术和逻辑运算的完整描述，按一定顺序执行这些运算，经有限步把输入数据的每一个容许集转换成输出数据。建立数值方法的基本原则：建立数值方法的基本原则： 便于在计算机上实现

3、计算工作量尽量小 存储量尽量小 问题的解与近似解的误差小误差的来源误差的来源( (Error Resource)Error Resource)：模型误差 ( Model Error )数据误差 ( Data Error )截断误差 (Truncation Error )离散误差 ( Discrete Error )数据计算过程中的误差误差大小的衡量：误差大小的衡量：绝对误差 （ absolute error ) 相对误差 （ relative error )误差界 （ bound of error ) 舍入误差与有效数字舍入误差与有效数字 舍入误差 （rounding error )（四舍五入

4、表示近似数产生的误差 ） 有效数字 第一位非零数字到最右边的数字为止的所有的数字被称为有效数字有效数字。数据误差在算术运算中的传播数据误差在算术运算中的传播 初始数据误差和计算结果中产生的误差之间的关系 避免相减相消避免相减相消。设yx,分别是初始数据yx,的近似值，即yxeyyexx,yxee ,分别是yx,的绝对误差。考察用yx,分别代替yx,计算函数值 ),(yxfz 产生的误差。即),(yxfz 的误差。 假设绝对误差yxee ,的绝对值都很小，且),(yxf可微，则z的误差 ),(),(yxfyxfzzez可以近似地表示成 yxzeyxyfeyxxfe),)(),)( （5. 1）而

5、且， yeyxyfzyxeyxxfzxzeryxzz),)(),)( yxryxyfzyryxxfzx),)(),)( (5. 2)初始数据误差和计算结果中产生的误差之间有下列关系（1）:),(yxyxf绝对误差： yxyxeee；相对误差： yxyxryxyryxxr从上式可见，接近相等的同号数相减时，会使计算结果的误差变得很大。 故应避免相减相消故应避免相减相消。（2）:),(xyyxf 绝对误差： yxyxexeye； 相对误差： yxyxrrr （3）:/),(yxyxf 绝对误差： 2/yexeyeyxyx； 从上式可见， 应避免绝对值很小的数作分母。 相对误差： yxyxrrr/例

6、 1 求方程 0,02acbxax 的两个根分别为 aacbbx2421和 aacbbx2422若,0b且042 acb，则1x需改为 acbbcx4221例例 2 计算表达式 xcos1。 当 0 x时 为避免相减相消，应利用 恒等式 2sin2cos12xx 机器误差机器误差 计算机中数的表示 浮点运算和舍入误差设计算机中的数x为有限位小数，表示为 tkkkJdx11010 (6.1)其中UJL（L 和 U 是正整数或零）t 为计算机的字长字长，tidi, 1,都是9 , 2 , 1 , 0中的一个数字若记 ttkkkdddda211. 010 (6.2)则 Jax10 (6.3) 如果

7、J 不变，则(6.4)或(6.5)为定点定点表示，此时通常取 tJJ 0 或 如果阶 J 可变，则(6.4)或(6.5)为浮点浮点表示， 若尾数的第一位数字1d非零，则该数称为规格化浮点数规格化浮点数。尾数对十进制满足 11 . 0 a 对二进制满足 121 a 例：例： 若2, 1, 3, 2ULtp 则相应的规格化浮点数共有 33 个浮点数。 J=-1 J=0 J=1 J=2 41 21 1 2 165 85 45 25 83 43 23 3 167 87 47 27 以及数 0. 令 xxxR 则对十进制系统有tRxx105),1 ( (6.11)对二进制系统有 t2 (6.16)若用只

8、“舍”不“入”的断位法，则界为 t 110 或 t 12 浮点数计算时，对加减法，首先要对阶， 即将两数的小数点对齐，使其阶相等。 对阶方法是：阶小的向大的对。然后尾数相加。 浮点数加减法分别记为 例 1： 10, 5pt，用断位法。计算 0.3124910 0.82718撞=0.11396壮 例 2： 10, 5pt，用舍入法。计算 0.2106210-5 0.12345 10-3=0.1255610-3 例 3 在5, 3,10ULtp的断位机上 对数 0.0438 , 0.0693 , 13.2 进行加法运算那么 先加前两个数后再加第三个数为 0.13310 若先加后两个数再加第一个数为

9、 0.13210 由此可见，对于浮点运算，通常的运算规律通常的运算规律 不再成立。不再成立。 例 4 在5, 3,10ULtp的断位机上求 x=0.12378, y=0.12362 的差。则 3101000. 0RRyxRx的相对误差为 410467. 6RRxxxRy的相对误差为 410618. 1RRyyy但00016. 0 yx， RRyx 的相对误差为 6 . 00001. 000006. 0 出现相减相消。 作乘法运算时，不必对阶。下面考察计算机中浮点数的算术运算的舍入误差：下面考察计算机中浮点数的算术运算的舍入误差： 设 Fyx,，均为规格化的浮点数。 用)/(),(),(yxfl

10、yxflyxfl分别表示得到准确的yxyxyx/,后按相关舍入规则进行舍入的结果，即 Ryxyxfl)()( RRyxyxflyxyxfl)/()/(,)()(就上述例 2， 3101255562. 0 yx因此31012556. 0)(,yxflFyx而据(6.11)和(6.16)式，立得下述定理：定理定理 1 )1)()(1yxyxfl (6.17) )1)()(2yxyxfl (6.18) )1)()(3yxyxfl (6.19) )1)(/()/(4yxyxfl (6.20)其中 , 4 , 3 , 2 , 1, iepsi （二进制系统）（十进制系统）tteps2105下面讨论更复杂

11、的浮点运算的误差界：下面讨论更复杂的浮点运算的误差界： 通过例子可见，在做三个以上的数的加法运算时，做三个以上的数的加法运算时，需要考虑相加的两个同号数的阶数应尽量接近。需要考虑相加的两个同号数的阶数应尽量接近。 定义 )()(zyxflflzyxfl据(6.17)式，)1 ()1)(1)()1)()1)()1)()(221211zyxzyxzyxflzyxfl (6.21)其中 . 2 , 1, iepsi为估计)1 (i，先证明下面的引理引理引理（Lemma） 若), 2 , 1(niepsi， 且01. 0epsn，则 niiepsnepsn101. 11)1 (1， (6.23)其中

12、二进制系统）十进制系统）；(2(105tteps(6.23)式还可改写成 1,01. 11)1 (1niiepsn (6.24)证明证明 ( Proof ) 由假设epsi，有 nininepseps1)1 ()1 ()1 ( (6.25)对函数nx)1 ( 作 Taylor 展开 nxxxnnnxxnn1)1 (2) 1(1)1 (22(6.26)由(6.25)的左边不等式及(6.26)式，便证得(6.23)的左边不等式。又由于 ! 3! 2132xxxex )! 4231 (212xxxxx当01. 00 x，有 xxexexx01. 11201. 01101. 0于是有 epsneepsepsnn01. 11)1 ( （6.27）由(6.25)右边不等式及(6.27)式，便证得(6.23)的右边不等式 用归纳法可以证明下面的定理：定理（Theorem）若01. 0epsn，则 )2(01. 11 )01. 11 ()(21111epsinyxepsnyxyxfliiniiinii (6.28)其中 ., 2 , 1, 1nii以上误差分析的一个特点是，将初始数据的实际浮点运算归结为初始近似数据的精确数学运算。误差分析的方法误差分析的方法 向后误差分析-将计算过程的误差归结为初始误差的误差，这种误差分析方法称为向后误差分析； 向前误差分