什么是有限精度算术,它在计算机计算时如何影响 SVD?

机器算法验证 回归 机器学习 多重共线性 svd 矩阵分解
2022-04-02 08:45:47

正在阅读David Belsley 和 Virginia Klema的论文“检测和评估多重共线性引起的问题:奇异值分解的使用”。

执行 SVD 后,在统计非零奇异值的个数时,论文中指出

问题出现是因为计算机使用有限算术......

更具体地说,由于计算机使用的算术精度和舍入误差,将假定为零的特征值存储为非零特征值。

有人可以详细说明这个算术精度和舍入误差吗?

2个回答

TLDR;在计算机中,数字存储在有限的内存槽中。例如,数学中的整数是整数,例如 ...,-2,-1,0,1,2,3,... 可以从负无穷大到正无穷大的两个方向。在计算机中,这个数字可以用诸如int8_t,情况更糟这就是作者的意思。π2

只要你有时间,长答案就可以。例如,“每个计算机科学家都应该知道的关于浮点运算的知识”是任何在计算机上计算数字的人的必读书籍。我将谈到三个主题。

计算机整数缺乏数学整数的某些性质

不仅整数类型是有界的,而且它们还缺少一些您期望从整数中获得的属性。例如,在数学中,如果给定,那么也是如此。然而,在计算机数学中可能并非如此。例如,以下代码输出您期望的不同:a>0b>0a+b>0110111

#include <iostream>

int main() {
  short int a = 17000, b = 17000, r;
  std::cout << (a > 0);
  std::cout << (b > 0);
  r = a + b;
  std::cout << (r > 0);

}

计算机“真实”数字是可数的

数学中的实数是不可数的。这就是实数与整数和有理数的巨大差异。Stevin引入实数的概念,例如时,这对欧洲数学来说是一个巨大的突破。它们填补了有理数之间的空白,例如 1/3。 2

尽管实数和整数的数量都是无限的,但实数比整数多。更奇怪的是,数学中正整数和负整数的数量是相同的:)

这些属性不会保留在计算机数学中。double例如,在 C++ 中,精度实数和long整数的数量完全相同,而且是有限的!准确地说因此,应该是连续体的基数(幂集)等于整数(整数)的基数!264

任意精度数学

由于这些限制,一些深奥的数学问题不可能使用标准的机器算术来解决。因此,数学家为所谓的任意精度算术库创建了库,这些库可以极大地扩展存储在计算机中的数字范围。然而,“任意”仍然是一个有限的概念。当涉及到实数时,他们比标准机器算术更接近数学概念,但他们没有完全实现它。

浮点算术是对实数算术的一种近似。从某种意义上说,它是一个近似值,一个数字的所有数字都没有被存储,而是被截断到一定的精度水平。这会产生错误,因为无法存储诸如之类的具有无休止数字序列的值(因为您没有足够的内存来存储无休止的数字序列)。这就是“有限精度”的含义:只存储最大的数字。2

浮点值表示在某个公差范围内,称为机器 epsilon 或 ,这是由于舍入导致的相对误差的上限。ϵ

当您组合具有有限精度的多个操作时,这些舍入误差会累积,从而导致更大的差异。

在奇异值为零的情况下,这意味着由于舍入误差,一些真正为零的奇异值将被存储为非零值。

一个例子:一些矩阵有奇异值但是您的 SVD 算法可能会返回奇异值或类似的小数字。最终值在数字上为零;在算法的数值容差范围内为零。A[2,1,0.5,0]2.0, 1.0, 0.5, 2.2e-16

浮点标准由 IEEE 754 管理。