数值分析: 基础概念

舍入误差

一般来说, 计算机并不能精确表示一个实数. 例如实数 $$ \sqrt{2} = 1.4142135623730950488 \dots $$ 是一个无限小数, 计算机并不可能完全精确的存储这个实数, 通常计算机中的 \(\sqrt{2}\) 是一个拥有 16 位精度的双精度浮点数 \(1.4142135623730951\). 这样产生的误差称为舍入误差. 在宏观世界里, 这个舍入误差 (\(10^{-16}\)) 可以直接被忽略掉, 因为它实在太小了:

  • 一个原子直径的百万分之一. 原子大小通常在 0.1 到 0.5 纳米之间, 即 \(1\times 10^{-10}\) 到 \(5\times 10^{-10}\) 米.
  • 是人类在实验室内创造的最低温度的百万分之一. 由德国, 美国, 奥地利等国科学家组成的一个国际科研小组在实验室内创造了仅仅比绝对零度高 0.5 纳开尔文 (\(5\times 10^{-10}\)K) 的温度纪录, 这是人类历史上首次达到绝对零度以上 1.0 纳开以内的极端低温.
  • 世界上最快的相机每两张照片间隔时间的百万分之一. 世界上最快的相机每秒可拍10万亿张照片 (截止 2018 年), 即 \(10^{-10}\) 秒.
  • 距离为一米的两个成年人之间的万有引力大小的 \(10^{10}\) 分之一. 普通成年人的质量 \(65\) kg, 由万有引力公式 \(F=G \frac{Mm}{r^2}=6.67\times 10^{-11}\cdot 65^2 = 2.8181\times 10^{-6}\) N.

但是当计算量很大时, 舍入误差一般是不能忽略的, 控制这个误差在理论和应用中都非常重要的.

浮点数

Double Floating
双精度浮点数存储格式 (From Wikipedia)

计算机中的实数采用浮点数的形式存储在内存中, 具有如下标准化表示 $$ (-1)^s\cdot 2^{c-1023}\cdot (1+f).$$ 其中, \(s, c, f\) 分别用来表示实数的符号, 指数小数. 例如一个 64 位双精度浮点数具有如下的二进制形式 $$ \underbrace{0}_{\text{sign indicator}} \underbrace{10000000011}_{11-\text{bit exponent} } \ \underbrace{1011100100010000000000000000000000000000000000000000}_{52-\text{bit binary fraction}}$$

  • 第一个是符号位, 0 表示正, 1 表示负. \(s=0\).
  • 后面 11 位为指数位, \(c=10000000011 = 1\cdot 2^{10} + 1\cdot 2^1 + 1\cdot 2^0 = 1027 \);
  • 再后面 52 位表示小数位, $$ \begin{align*} f&=1011100100010000000000000000000000000000000000000000 \\ &= 1\cdot 2^{-1}+1\cdot 2^{-3}+ 1\cdot 2^{-4} + 1\cdot 2^{-5} +1\cdot 2^{-8} + 1\cdot 2^{-12} \\ &= 0.722900390625 \end{align*} $$

因此上面的二进制数就是 \((-1)^0 \cdot 2^{1027-1023}\cdot (1+0.722900390625)=27.56640625\).

上述浮点数形式可以表示的最大数为 $$ 0\ \ 11111111111\ \ 1111111111111111111111111111111111111111111111111111 $$ 等于 \(2^{1023}\cdot (2-2^{-52})\approx 1.7976931348623157\times 10^{308}. \) 超过这个数称为上溢. 最小的数为 \((-1)^0 \cdot 2^{1-1023}\cdot (1+0)\approx 2.2250738585072014\times 10^{-308}.\) 小于这个数称为下溢.

误差

定义 如果 \(p^*\) 是 \(p\) 的一个近似值, 那么, 绝对误差为 \(|p − p^*|\), 相对误差为 \(\frac{|p − p^∗|}{|p|}\), 其中 \(p \neq 0\).

这里定义的误差是用来衡量数值解与真实解之间的近似程度, 是在实数空间中的. 事实上, 根据问题的不同误差可以定义在任意的赋范空间上, 对应地, 绝对值替换为范数.

近似值 \(p^* \) 相对真实值 \(p\) 有 \(t\) 位有效数字, 如果 \(t\) 是满足下式的最大整数 $$ \frac{|p − p^∗|}{|p|} \leq 5\times 10^{-t}. $$

收敛性

数值分析中存在各种各样的数值算法, 如果一个算法连续地依赖于初始值, 那么它就是稳定的, 否则就是非稳定的. 这里稳定的意义是当初始数据发生一个微小变化时, 对应的数值解也发生一个微小变化.

如果一个算法产生的数值解可以任意趋于真实解, 我们就称这个算法是收敛的. 一个典型的例子是二分法求方程的根, 数值误差满足 \(e_n = e_{n-1}/2 = e_0/2^n , \) 可以看出误差逐渐趋于零. 如何刻画一个算法的收敛速度呢?

假设 \(\left\{ \beta_n \right\}\) 是一个趋于零的正实数数列, 如果存在一个正常数 \(C\) 使得误差 \(\left\{ e_n \right\}\) 满足 $$ |e_n|\leq C \beta_n, $$ 那么我们就称误差具有 \(O(\beta_n) \) 收敛速度.

利用这个定义, 二分法的收敛速度就是 \(O(1/2^n) \). 另外一个关于收敛速度的例子是有限元方法的收敛性

  • h-FEM. 通常求解一个具有光滑解的椭圆方程时, 线性有限元方法的收敛速度为 \(O(h) \), 即当一致加细网格时, 网格大小 \(h\) 变成原来的一半, 误差也变成原来的一半.
  • p-FEM. 当考虑 p 有限元方法时, 通常不改变网格大小而只是通过提高多项式次数来增加数值精度. 这里的收敛速度关于多项式次数通常为指数收敛, 即达到 \(O(e^{-ap})\), 其中 \(a\) 是一个正常数.

总结

数值分析中涉及的基本概念还有很多, 例如截断误差, 误差增长速度, 条件稳定, 以及避免大数小数运算等等. 读者可以在学习中逐渐了解.

参考文献

  1. Burden, R. L., & Faires, J. D. (2010). Numerical Analysis. In Cengage Learning (9th ed.).
  2. Double-precision floating-point format – Wikipedia.
  3. Ciarlet, P. G. (2002). The Finite Element Method for Elliptic Problems. In Classics in Applied Mathematics (Vol. 40).
分享到:

You may also like...

3.5 2 投票数
文章评分
guest
1 评论
最久
最新 最赞
内联反馈
查看所有评论
匿名
游客
匿名
28 天 前

讲的挺清楚的

1
0
希望看到您的想法,请发表评论。x
()
x