第一章 基本知识 1.1 计算机中的数 1.2 误差分析 1.3 数值计算中出现的问题 1.4 求解题目本身的特性 1.5 典型示例分析

Presentation on theme: "第一章 基本知识 1.1 计算机中的数 1.2 误差分析 1.3 数值计算中出现的问题 1.4 求解题目本身的特性 1.5 典型示例分析"— Presentation transcript:

1 第一章 基本知识 1.1 计算机中的数 1.2 误差分析 1.3 数值计算中出现的问题 1.4 求解题目本身的特性 1.5 典型示例分析
第一章 基本知识 1.1 计算机中的数 1.2 误差分析 1.3 数值计算中出现的问题 1.4 求解题目本身的特性 1.5 典型示例分析 浙江大学研究生学位课程 《实用数值计算方法》

2 1. 计算机中数的表示的近似性 2. 误差的来源和传播 3. 数值方法的稳定性,计算步骤的合理性 4. 题目本身数学模型的特性 5
1. 计算机中数的表示的近似性 2. 误差的来源和传播 3. 数值方法的稳定性,计算步骤的合理性 4. 题目本身数学模型的特性 5. 应注意的要点 浙江大学研究生学位课程 《实用数值计算方法》

3 1.1 计算机中的数 整数 Integer 离散 无限 精度 Precision t 实数 Real Number 连续 无限
第一章 1.1 计算机中的数 整数 Integer 离散 无限 实数 Real Number 连续 无限 有理数 Rational Number 稠密 无限 复数 Complex Number 连续 无限 浮点数 Floating Point Number 浮点数集 F 离散 无限 数基 Number Base 精度 Precision t 阶域 Exponential Range 上界 U 下界 L 浙江大学研究生学位课程 《实用数值计算方法》

4 di 尾数数字 digit figure (整数) e x的阶数 exponent, 或characteristic 往往
第一章 1.1.1 x的尾数 mantisa 分式 fraction di 尾数数字 digit figure (整数) e x的阶数 exponent, 或characteristic 往往 规格化浮点数系 Fn Normalized Floating Point Number System d10 t位有效数的 相对精度 Minimum Relative Accuracy 浙江大学研究生学位课程 《实用数值计算方法》

5 从L到U的阶次个数 从2到t,共t-1位的di有种选择 第1位的d1可以有(-1)种选择 正数和负数有相同个数 Fn 中的浮点数的总数
第一章 1.1.1 Fn 中的浮点数的总数 从L到U的阶次个数 从2到t,共t-1位的di有种选择 第1位的d1可以有(-1)种选择 正数和负数有相同个数 示例: 即相对误差界 Relative Error Bound 浙江大学研究生学位课程 《实用数值计算方法》

6 第一章 示例浮点数集 序数 数值 位置 (1/2+0/4+0/8)2-1=4/16 (1/2+0/4+0/8)20=8/16 (1/2+0/4+0/8)21=16/16 (1/2+0/4+0/8)22=32/16 (1/2+0/4+1/8)2-1=5/16 (1/2+0/4+1/8)20=10/16 (1/2+0/4+1/8)21=20/16 (1/2+0/4+1/8)22=40/16 (1/2+1/4+0/8)22=48/16 (1/2+1/4+0/8)20=12/16 (1/2+1/4+0/8)20=12/16 (1/2+1/4+0/8)21=24/16 (1/2+1/4+1/8)2-1=7/16 (1/2+1/4+1/8)20=14/16 (1/2+1/4+1/8)21=28/16 (1/2+1/4+1/8)22=56/16 浙江大学研究生学位课程 《实用数值计算方法》

7 1.1.2 浮点数表示实数的问题 (2) F 中绝对值最大的数 (1) 最接近实数Z的浮点数 两浮点数间的绝对值差 相对差
第一章 浮点数表示实数的问题 (1) 最接近实数Z的浮点数 两浮点数间的绝对值差 相对差 浮点数 x=fl(Z) 和 实数 Z 的最大相对误差 即相对误差界 Relative Error Bound 用任何=2k作数基表示(0.1)10均需无穷位 (0.1)10=( …...)2 =( …...)4 =( ……)6 =( …...)16 因此 10fl(0.1)1.0 (2) F 中绝对值最大的数 浙江大学研究生学位课程 《实用数值计算方法》

8 (3) F 中绝对值最小的非零Z 它近似表示的Z的最大绝对值 对前例 对于 则产生上溢错误 Overflow 它近似表示的非零最小绝对值
第一章 1.1.2 它近似表示的Z的最大绝对值 对前例 对于 则产生上溢错误 Overflow (3) F 中绝对值最小的非零Z 它近似表示的非零最小绝对值 浙江大学研究生学位课程 《实用数值计算方法》

9 对于 则机器将给出结果为0 或产生下溢错误 Underflow (4) 对Z成立的运算律，对F不一定成立 设 则 然而 所以
第一章 1.1.2 对于 则机器将给出结果为0 或产生下溢错误 Underflow (4) 对Z成立的运算律，对F不一定成立 设 则 然而 所以 浙江大学研究生学位课程 《实用数值计算方法》

10 1.1.3 机器最小数 Machine Epsilon 能使 1.0  eps > 1.0 的最小浮点数 eps
可以用来表示该机器浮点运算的准确程度 自动找出该计算机 eps 值的程序 EPS = 1.0 10 EPS = 0.5  EPS EPSI = EPS + 1.0 IF(EPSI.GT.1.) GOTO 10 EPS = 1.4  EPS 浙江大学研究生学位课程 《实用数值计算方法》

11 1.2 误差分析 结果 1.2.1 误差的来源 现 实 世 界 研究 对象 数学模型的建立 模型 误差 计算方法 的构成 方法 误差 测量
现 实 世 界 研究 对象 数学模型的建立 模型 误差 计算方法 的构成 方法 误差 测量 数据 数值运算 的执行 舍入 误差 测量 误差 结果 浙江大学研究生学位课程 《实用数值计算方法》

12 1.2.2 术语和定义 (1) 绝对误差 Absolute Error, 或误差 Error E(X) = X  XA
术语和定义 (1) 绝对误差 Absolute Error, 或误差 Error E(X) = X  XA 误差 近似值 准确值 (2) 绝对误差界 Absolute Error Bound, 或 误差界 Error Bound 或 近似地习惯表示为 (3) 相对误差 Relative Error 浙江大学研究生学位课程 《实用数值计算方法》

13 (4) 相对误差界 Relative Error Bound
1.2.2 (4) 相对误差界 Relative Error Bound (5) 有效位数 Significant Digit n位有效数字 Xn 计算机中得到数字的两类方法 舍入 rounding 截断 chopping 由准确值经舍入得到的xn的误差界为第n位的半个单位 例如对10进制数: 误差界为: 浙江大学研究生学位课程 《实用数值计算方法》

14 1.2.2 取3位有效数, n=3, m=1 取5位有效数, n=5, m=1 浙江大学研究生学位课程 《实用数值计算方法》

15 浙江大学研究生学位课程 《实用数值计算方法》

16 1.2.3 数据误差在差分运算中的传播 浙江大学研究生学位课程 《实用数值计算方法》

17 1.2.4 条件数 Condition Number 为了定量分析误差的传播，要弄清 对于
在x=a附近作Taylor展开 （x=a为准确值） 又 故 任何三种情况，都能使条件数很大。 （1）a 很大 （相对于f(a)和f '(a)） （2）f '(a)很大 （相对于a和f(a)） （3）f(a)很小 （相对于f '(a)和a） 浙江大学研究生学位课程 《实用数值计算方法》

18 在 附近作Taylor展开 （xi=ai为准确值）
1.2.4 推广到多元的情况，对 在 附近作Taylor展开 （xi=ai为准确值） 其中 其中 偏条件数： 浙江大学研究生学位课程 《实用数值计算方法》

19 1.2.4 对于误差界 浙江大学研究生学位课程 《实用数值计算方法》

20 1.2.5 代数运算的条件数 将以上方法用于考察基本代数运算 （1）加减法 对于 （2）乘除法 对于加法 对于减法 当 时； ，坏条件
代数运算的条件数 将以上方法用于考察基本代数运算 （1）加减法 对于 对于加法 对于减法 当 时； ，坏条件 （2）乘除法 好条件 浙江大学研究生学位课程 《实用数值计算方法》

21 （3）乘冥 不是坏条件 对于 不是坏条件 对于 n < 1 时好条件 n >> 1 时坏条件 1.2.5
浙江大学研究生学位课程 《实用数值计算方法》

22 1.3 数值计算中的问题 1.3.1 数值相近两数相减的结果 内接多边形边数不断增加将趋近于圆周 用此方法计算圆周率:
对于 的圆,内接正六边形每边长为1.0 不断将边数加倍, 周边总长的一半将逐渐趋近于 值 浙江大学研究生学位课程 《实用数值计算方法》

23 圆内接多边形的边数增加一倍后，新边长Sn+1与原边长 Sn间的关系，见前图，有：
1.3.1 圆内接多边形的边数增加一倍后，新边长Sn+1与原边长 Sn间的关系，见前图，有： 因为 所以： 但用此公式无论以单精度或倍精度，都得不到正确结果，见 表1-6 递推运算 Recursive Operation 所得的结果 原因（1） 的条件数很大 舍入误差造成的影响很大 （2）计算出来的 还要乘 倍 误差又进一步放大 浙江大学研究生学位课程 《实用数值计算方法》

24 1.3.1 表1-6 由内接多边形递推计算圆周率  = …... 浙江大学研究生学位课程 《实用数值计算方法》

25 现若将递推算式作以下改进 避免了相近两数的相减， 经11次递推运算，收敛于7位有效数近似值。 从以上示例可以看出：
1.3.1 现若将递推算式作以下改进 避免了相近两数的相减， 经11次递推运算，收敛于7位有效数近似值。 从以上示例可以看出： （1）解析法理论上准确的算式，不一定适用于数值计算。 尤其对递推运算; （2）递推计算开始阶段显示出正确趋势，并不意味继续 执行能收敛到正确结果; （3）对算式作合适的改变能大大改变递推运算的结果。 因为运算的条件数有根本性的变化; 浙江大学研究生学位课程 《实用数值计算方法》

26 1.3.2 正负交替级数累和计算中的问题 指数函数可展开为无穷项收敛级数 Convergent Infinite Series
正负交替级数累和计算中的问题 指数函数可展开为无穷项收敛级数 Convergent Infinite Series 试用 的浮点数系 由以上级数计算 之值。见表1.7 可见运算到第27项时对累和的第5位有效数字不再有影响 停止继续计算，得到： 然而实际上准确值是： 连第一位数都是错的！！ 原因是：第3 ~10项，数量级101，误差界为0.510-3。 故这些项加减运算结果10-3位上不准，现26项加和为10-3 数量级，故第一位也不准 误差界： 浙江大学研究生学位课程 《实用数值计算方法》

27 1.3.2 表 级数各项数值及累加和 浙江大学研究生学位课程 《实用数值计算方法》

28 （1）对正负项交替级数的累和问题需要特别注意。 若某些项的数量级远大于结果数量级，则可 能隐含着数值相近两数求差运算；
1.3.2 若更换一种算法，仍用 浮点数系 按照 结果准确到第四位有效数字。 从以上示例可以看出： （1）对正负项交替级数的累和问题需要特别注意。 若某些项的数量级远大于结果数量级，则可 能隐含着数值相近两数求差运算； （2）由递推步骤得到收敛的计算结果还不能认为 该结果是准确可靠的。 浙江大学研究生学位课程 《实用数值计算方法》

29 1.3.3 运算次序对结果的影响 用 的浮点数集， 以不同顺序作以下计算： 得到的结果相差很大，原因是：
运算次序对结果的影响 用 的浮点数集， 以不同顺序作以下计算： 得到的结果相差很大，原因是： （1）在很大的数上，加以很小的数，由于有效位数 的限制，可能等于没有加上这个数。 故SB的值很小。 （2）将很多较小的数加和而成较大的数后， 再加之较大的数，仍有作用。 故SA的值比较准确。 浙江大学研究生学位课程 《实用数值计算方法》

30 1.3.4 减少运算次数 求解一个给定问题，减少运算次数 节省机器时间 减少舍入误差传播放大 示例 求多项式的值 则有 乘法次数为 n
减少运算次数 求解一个给定问题，减少运算次数 节省机器时间 减少舍入误差传播放大 示例 求多项式的值 上式顺序计算时 乘法次数为 加法次数为 改为下列计算顺序 则有 乘法次数为 n 加法次数为 n 浙江大学研究生学位课程 《实用数值计算方法》

31 1.3.5 算法的稳定性问题 Stability 如果初始数据的误差，以及计算过程中的舍入误差 在该算法所包含的一系列相继运算中会不断放大，
这是数值不稳定的算法 Unstable Algorithm 例如，计算积分值 用分部积分法 既然 时 时 所以 而且 浙江大学研究生学位课程 《实用数值计算方法》

32 用 的浮点数系，经A1出发 递推计算得到： 分析：算式系解析方程导出 计算过程中未见有相近大数相减 剩下的可能性是从初始值起的舍入误差
1.3.5 用 的浮点数系，经A1出发 递推计算得到： 分析：算式系解析方程导出 计算过程中未见有相近大数相减 剩下的可能性是从初始值起的舍入误差 A1的舍入误差是 进一步估计 浙江大学研究生学位课程 《实用数值计算方法》

33 这样误差的传播情况成为： 所以 依次类推 得到： 由此可以估计得： 对前面计算结果作校正 由于误差在计算过程中放大很严重，所以这是一种
1.3.5 所以 依次类推 得到： 由此可以估计得： 对前面计算结果作校正 由于误差在计算过程中放大很严重，所以这是一种 数值不稳定的算法。 下面寻找一种数值稳定的相反的算法，把乘法改为除法。 用相反的递推关系 这样误差的传播情况成为： 即 浙江大学研究生学位课程 《实用数值计算方法》

34 依次类推 可见从 n 很大的 An 值开始，反过来算，误差将不断减小。 但首先要设法估计 An 的一个值。 根据 可见 取 递推计算
1.3.5 依次类推 可见从 n 很大的 An 值开始，反过来算，误差将不断减小。 但首先要设法估计 An 的一个值。 根据 可见 取 递推计算 浙江大学研究生学位课程 《实用数值计算方法》

35 1.4 题目本身的特性 数值计算特性 稳定性 Stability 在运算过程中舍入误差的影响是否
题目本身的特性 数值计算特性 稳定性 Stability 在运算过程中舍入误差的影响是否 会被很大地扩大 条件 Condition ，条件数 Condition Number 自变量的变差引起应变量很大变化的运算 是坏条件的，条件数很大，因而也是不稳定的 敏感度 Sensitivity 输入数据的变化造成输出结果的变化程度 敏感度高的问题条件数大 收敛阶 Order of Convergence 迭代计算中每步运算误差减少速率与 运算参数（步长、项数、点数）的关系 浙江大学研究生学位课程 《实用数值计算方法》

36 1.4.1 多项式系数对根的灵敏度 对二次方程 在重根附近， ，对x的计算是坏条件的 其中 所以 又由 得到 浙江大学研究生学位课程
多项式系数对根的灵敏度 对二次方程 其中 所以 又由 得到 在重根附近， ，对x的计算是坏条件的 浙江大学研究生学位课程 《实用数值计算方法》

37 Wilkinson 示例 若将 的系数改为 ，得 用 的浮点数系求解，得到的根为 使20个根中的10个成了复数，最大移开实轴达2.81。
1.4.1 Wilkinson 示例 若将 的系数改为 ，得 用 的浮点数系求解，得到的根为 其根为 使20个根中的10个成了复数，最大移开实轴达2.81。 这是由于题目本身的特性，系数对根的敏感度造成。 将方程写成 弄清 的变化将引起x的变化多大？ 浙江大学研究生学位课程 《实用数值计算方法》

38 1.4.1 在每一个根值位置上， 应有 由此可求出 对每个根 的影响如下： 浙江大学研究生学位课程 《实用数值计算方法》

39 1.4.2 线性代数方程组系数对根的敏感度 设二元线性代数方程组： 得到的解 将系数作微小更动为： 得到的解 若将系数改为： 则得不到解
线性代数方程组系数对根的敏感度 设二元线性代数方程组： 得到的解 将系数作微小更动为： 得到的解 若将系数改为： 则得不到解 3.001x+y1 2.999x+y1 3x+y7 3x+y1 o 浙江大学研究生学位课程 《实用数值计算方法》

40 1.5 典型示例分析 1.5.1 差分算法的收敛阶 对函数 ，在 处 用差分算法计算 Absolute Error Slope= -1
典型示例分析 差分算法的收敛阶 对函数 ，在 处 用差分算法计算 Slope= -1 Slope= +1 Absolute Error Slope= -2 15 decimal digits accuracy is used in the computation 浙江大学研究生学位课程 《实用数值计算方法》

41 用两种不同的差分格式近似求导 （A） （B） 由前图可见 对格式A，误差随着步长减小而按比例减小 这种格式收敛阶为1，或线性收敛
1.5.1 用两种不同的差分格式近似求导 （A） （B） 由前图可见 对格式A，误差随着步长减小而按比例减小 这种格式收敛阶为1，或线性收敛 =O（1/h） 对格式B，收敛阶为2 =O（1/h2） 两种格式，当h小到一定程度后，受舍入误差影响， 开始发散，阶数为-1 =O（h） 格式B不需要用太小的步长，即可达到较高的精度， 但受舍入误差影响的程度则差不多。 浙江大学研究生学位课程 《实用数值计算方法》

42 1.5.2 圆周率算法的收敛阶 考察几种不同的圆周率算法 ，所以 （a）无穷级数法 Infinite Series
圆周率算法的收敛阶 考察几种不同的圆周率算法 （a）无穷级数法 Infinite Series （b）梯形面积法 Trapezoidal Rule 在 r=1.0 的 1/4 圆内不断增加梯形分割数， 总面积趋于 （c）三角形面积法 Archimedes’ Method 不断增加圆内接三角形数 4，8，16，，2p， 每一个三角形面积为 ，根据 以及 由 开始 （d）Taylor 级数 ，所以 浙江大学研究生学位课程 《实用数值计算方法》

43 四种不同算法运行得到收敛阶见下图。 Error （A）（B）的收敛速度太慢 （C）的收敛速度快，但受到舍入误差影响大
1.5.2 四种不同算法运行得到收敛阶见下图。 （A）（B）的收敛速度太慢 （C）的收敛速度快，但受到舍入误差影响大 （D）收敛速度快，受舍入误差影响小，是好的算法。 Error Computations made with 14.5 decimal digit arithmetic by CDC 6500 Number of Terms, 浙江大学研究生学位课程 《实用数值计算方法》

44 1.5.3 一元二次方程的根 对于 坏条件 根为： 可以将以上四式统一表示为以下二式 其中 p>0 时 SIGN(P)=+1
一元二次方程的根 对于 坏条件 根为： 可以将以上四式统一表示为以下二式 其中 p>0 时 SIGN(P)=+1 p<0 时 SIGN(P)=― 以上方法适用于p2>4q 浙江大学研究生学位课程 《实用数值计算方法》

45 示例误差计算，对 的根 x1 不合适的算式计算结果 合适的算式计算结果 以上计算用 的浮点数系得到 1.5.3 浙江大学研究生学位课程
以上计算用 的浮点数系得到 浙江大学研究生学位课程 《实用数值计算方法》

46 习 题 1. The following expression is numerically Unstable for
习 题 1. The following expression is numerically Unstable for x near zero. Evaluate this expression for x=10-3, 10-5, 10-7, and Manipulate the expression into a numerically stable form and estimate the accuracy obtained in evaluating them. 2. Consider the following two FORTRAN Programs: EPS=1. 10 EPS=EPS/ 2. WRITE(6, 20) EPS 20 FORMAT(1H, G20.10) EPS1=EPS+1. IF (EPS1. GT. 1.) GOTO 10 STOP END 浙江大学研究生学位课程 《实用数值计算方法》

47 Run the programs and explain the results.
EPS=1. 10 EPS=EPS/2. WRITE(6, 20) EPS 20 FORMAT(1H, G20, 10) IF(EPS. GT. 0.) GOTO 10 STOP END Run the programs and explain the results. 浙江大学研究生学位课程 《实用数值计算方法》