Question

浮点数算术

为了理解准确性，我们首先需要了解计算机（有限和离散）如何存储数字（无限且连续）

练习

花点时间看看下面的函数 f 。 在尝试运行它之前，在纸上写下 x1 = f(110) 的输出。 现在，（仍在纸上）将其代入 f 并计算 x2 = f(x1) 。 继续进行 10 次迭代。

这个例子来自 Greenbaum 和 Chartier 的 Numerical Methods 的第 107 页。

def f(x):
    if x <= 1/2:
        return 2 * x
    if x > 1/2:
        return 2*x - 1

仅仅在你写下你认为答案应该是什么之后，运行下面的代码：

x = 1/10
for i in range(80):
    print(x)
    x = f(x)

'''
0.1
0.2
0.4
0.8
0.6000000000000001
0.20000000000000018
0.40000000000000036
0.8000000000000007
0.6000000000000014
0.20000000000000284
0.4000000000000057
0.8000000000000114
0.6000000000000227
0.20000000000004547
0.40000000000009095
0.8000000000001819
0.6000000000003638
0.2000000000007276
0.4000000000014552
0.8000000000029104
0.6000000000058208
0.20000000001164153
0.40000000002328306
0.8000000000465661
0.6000000000931323
0.20000000018626451
0.40000000037252903
0.8000000007450581
0.6000000014901161
0.20000000298023224
0.4000000059604645
0.800000011920929
0.6000000238418579
0.20000004768371582
0.40000009536743164
0.8000001907348633
0.6000003814697266
0.20000076293945312
0.40000152587890625
0.8000030517578125
0.600006103515625
0.20001220703125
0.4000244140625
0.800048828125
0.60009765625
0.2001953125
0.400390625
0.80078125
0.6015625
0.203125
0.40625
0.8125
0.625
0.25
0.5
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
'''

哪里不对？

问题：数学是连续的或无限的，但计算机是离散的和有限的

计算机的数字表示的两个局限：

• 它们不能是随意大小
• 它们之间肯定存在差距

我们需要关心准确性的原因是，计算机无法存储无限准确的数字。 可以创建给出非常错误答案的计算（特别是在多次重复操作时，因为每个操作可能会使错误成倍增加）。

计算机如何存储数字：

尾数也可以称为有效数。

IEEE 双精度算术：

数字可以大到 1.79×10308 ，小到 2.23×10-308 。

区间 [1,2] 由离散子集表示：

区间 [2,4] 表示为：

浮点并不是等间距的。

来源： 你从未想过要了解浮点数，但将被迫了解

机器 ε

1 和下一个较大数字之间的距离的一半。 这可能因计算机而异。IEEE 双精度标准规定：

浮点运算的两个重要属性

实数 x 与其最接近的浮点近似值 fl(x) 之间的差值，总是小于机器 ε ，相对而言。对于某些 ε ，其中 ：

* 为任何操作（ + ， - ， × ， ÷ ）， ⊛ 是它的浮点模拟，对于一些 ε ，其中 ：

也就是说，浮点运算的每个操作都精确到最大为机器 ε 的相对误差。

历史

事后看来，浮点运算似乎是一个明确的选择，但存在许多存储数字的方法：

• 定点算术
• 对数和半对数数系统
• 连续分数
• 有理数
• 有理数的可能无限字符串
• 级别索引数字系统
• 固定斜杠和浮动斜杠数字系统
• 2-adic 数字

对于参考，请参阅“ 浮点运算手册 ”的 第 1 章 （免费）。 是的，有一本关于浮点的完整的 16 章书！

浮点运算的时间线历史

• 公元前 1600：巴比伦基数 60 的系统是最早的浮点系统（Donald Knuth）。 使用基数 60 的浮点表示来表示尾数（如果两个数字的比率是 60 的幂，则表示相同）
• 1630：滑动规则。仅操纵有效数字（基数 10）
• 1914：Leonardo Torres 和 Quevedo 使用浮点运算描述了 Babbage 的分析引擎的的机电实现。
• 1941：第一个真正的现代实现。 Konrad Zuse 的 Z3 电脑。 使用基数 2，具有 14 位有效数字，7 位指数和 1 个符号位。
• 1985：IEEE 754-1985 二进制浮点运算标准发布。 提高了准确性，可靠性和便携性。 William Kahan 主导。

“已经引入了许多不同的方法来在计算机上近似实数。然而，浮点运算是迄今为止在现代计算机中最常用的表示实数的方法。使用有限集合（“机器数字”）模拟无限连续集（实数） 并不是一项简单的任务：必须在速度，准确性，动态范围，易用性和实现以及内存之间找到明智的妥协。如果选择得当的参数（基数，精度，极值指数等），浮点运算似乎对于大多数数值应用来说是一个非常好的折衷方案。”

尽管基数 2（二进制）似乎是计算机中非常明显的赢家，但在各个方面使用了各种其他基数值：

• 早期机器 PDP-10，Burroughs 570 和 6700 使用 基数 8
• 基数 16 的 IBM 360
• 基数 10 的财务计算，袖珍计算器，Maple
• 基数 3 的俄罗斯 SETUN 计算机（1958 年）。 优点：最小化 beta x p （符号乘位数），对于固定的最大可表示数字 beta^p - 1 。舍入等于截断
• 基数 2 最常见。 理由：易于实现。 研究表明（带有隐式前导位），这比其他所有基数都具有更好的最坏情况或平均精度。

条件作用和稳定性

由于我们无法在计算机上准确表示数字（由于存储的有限性以及浮点结构中数字之间的间隔），因此了解输入中的小扰动如何影响输出变得非常重要。

“稳定的算法几乎可以为几乎正确的问题提供正确的答案。”--Trefethen

条件作用：数学问题的扰动行为（例如最小二乘）

稳定性：用于在计算机上解决该问题的算法的扰动行为（例如，最小二乘算法，householder，回代，高斯消除）

示例：矩阵的特征值：

import scipy.linalg as la 

A = np.array([[1., 1000], [0, 1]])
B = np.array([[1, 1000], [0.001, 1]])

print(A)

print(B)

'''
[[    1.  1000.]
 [    0.     1.]]
[[  1.00000000e+00   1.00000000e+03]
 [  1.00000000e-03   1.00000000e+00]]
'''

np.set_printoptions(suppress=True, precision=4)

wA, vrA = la.eig(A)
wB, vrB = la.eig(B)

wA, wB
'''
(array([ 1.+0.j,  1.+0.j]), array([ 2.+0.j,  0.+0.j]))
'''

提醒：浮点运算的两个属性

实数 x 与其最接近的浮点近似值 fl(x) 之间的差值总是小于机器 ε ，相对而言。

浮点运算的每个运算 + ， - ， × ， ÷ 都精确到最大为机器 ε 的相对误差。

我们将看到的例子：

• 经典与修正的 Gram-Schmidt 精度
• Gram-Schmidt 与 Householder（计算 QR 分解的两种不同方式），答案的正交性如何
• 方程组的条件

近似的准确度

我们很少需要大规模地进行高精度的矩阵计算。 事实上，我们经常进行某种机器学习，而不太准确的方法可以防止过度拟合。

在许多情况下，输入数据可能不那么精确，因此使用输入数据和计算来寻求更高的准确度是没有意义的。

• 随机数据结构
• 布隆过滤器
• HyperLogLog
• 局部敏感哈希
• 跳过列表
• Count-min 草图
• 最小哈希

示例：布隆过滤器能够使用每个元素的 <10 位，搜索集合的成员性，具有 1% 的假阳性。 这通常表示数千次的内存使用减少。

通过对所有退回的项目进行第二阶段（确切）检查，可以轻松处理假阳性 - 对于稀有项目，这可能非常有效。 例如，许多网络浏览器使用布隆过滤器来创建一组被阻止的页面（例如，带有病毒的页面），因为被阻止的网页只是整个网络的一小部分。 可以通过获取布隆过滤器返回的任何内容并使用完整的精确列表检查 Web 服务来处理假阳性。 （详细信息请参阅 布隆过滤器教程 ）。

随机算法

• Karger 算法（图的最小切割）
• 随机回归
• 蒙特卡罗模拟
• 随机 LU 分解（高斯消元）
• 随机 SVD

如果我们接受一些精度降低，那么我们通常可以通过使用近似算法将速度提高几个数量级（和/或减少内存使用）。 这些算法通常以一定的概率给出正确的答案。 通过多次重新运行算法，你通常可以加倍增加该概率！

昂贵的错误

以下示例来自 Greenbaum 和 Chartier。

欧洲航天局在阿丽亚娜 5 火箭上 10 年花费了 70 亿美元。

当你尝试将 64 位数放入 16 位空间（整数溢出）时会发生什么：

from IPython.display import YouTubeVideo
YouTubeVideo("PK_yguLapgA")

https://www.youtube.com/embed/PK_yguLapgA

这是一个浮点错误，耗资 4.75 亿英镑：

1994 纽约时报关于英特尔奔腾错误的文章

资源：浮点运算的更多信息，请参阅 Trefethen & Bau 的第 13 讲和 Greenbaum & Chartier 的第 5 章。