Ruby矩阵计算中的浮点错误

Question

我正在编写一些涉及查找给定矩阵的特征向量的代码,并且很惊讶Ruby在简单的情况下会产生一些不合理的结果.

例如,以下矩阵具有与特征值1相关联的特征向量:

> m = Matrix[[0r, 1/2r, 1/2r, 1/3r],
             [0r,  0r,  1/4r, 1/3r],
             [0r, 1/4r,  0r,  1/3r],
             [1r, 1/4r, 1/4r,  0r]]

Ruby发现特征值足够好,但特征向量爆炸:

> m.eigen.eigenvalues[2]
=> 1.0000000000000009

m.eigen.eigenvectors[2]
=> Vector[5.957702309312754e+15, 5.957702309312748e+15, 5.957702309312743e+15, 5.957702309312753e+15]

实际的特征向量应为(7,4,4,9).

这不是麻烦吗？如果Ruby无法处理微小的矩阵,那么我们怎么能相信呢？或者我做错了什么？

Answer 1

不，这并不令人烦恼。该矩阵可能无法与特定的特征向量算法实现很好地配合。毕竟，高效且稳定的通用特征向量计算并不简单。

\n\n

该Matrix库改编自JAMA，一个 Java 矩阵包，它表示它进行数值计算而不是符号计算：

\n\n

\n

不包括。JAMA 绝不是一个完整的线性代数环境……它侧重于进行数值线性代数所需的原理数学功能

\n

\n\n

QR 算法：数值计算

\n\n

查看源代码Matrix::EigenvalueDecomposition，我发现它命名了QR算法的用法。我不完全理解数学的复杂性，但我想我可能理解为什么这个计算失败。计算机制如下：

\n\n

\n

在第 k 步（从 k = 0 开始），我们计算 QR 分解 A _k =Q _k R _k ...在某些条件下，^[4]矩阵 A _k收敛为三角矩阵，即 Schur 形式A、将三角矩阵的特征值列在对角线上，特征值问题就解决了。

\n

\n\n

在“伪”Ruby 中，这在概念上意味着：

\n\n

working_matrix = orig_matrix.dup\nall_q_matrices = []\nloop do\n  q, r = working_matrix.qr_decomposition\n  all_q_matrices << q\n  next_matrix = r * q\n  break if difference_between(working_matrix, next_matrix) < accuracy_threshold\nend\neigenvalues = working_matrix.diagonal_values\n

\n\n

对于特征向量，继续：

\n\n

\n

收敛后，AQ = Q\xce\x9b，其中 \xce\x9b 是 A 收敛到的特征值的对角矩阵，其中 Q 是到达该值所需的所有正交相似变换的组合。因此 Q 的列是特征向量。

\n

\n\n

在“伪”Ruby 中，继续：

\n\n

eigenvectors = all_q_matrices.inject(:*).columns\n

\n\n

数值计算中的浮点错误

\n\n

我们可以看到，进行了数值计算的迭代来计算近似特征值，并且作为副作用，Q收集了一堆近似矩阵。然后，Q将这些近似矩阵组合在一起以形成特征向量。

\n\n

近似值的复合可能是导致结果极其不准确的原因。Math StackExchange 上的灾难性取消示例显示了具有 400% 相对误差的简单二次计算。您可能可以想象具有重复算术运算的迭代矩阵算法会做得更糟。

\n\n

一粒盐

\n\n

再说一遍，我对算法的数学和实现都没有深入的了解，所以我不知道计算的哪些部分导致了您的特定 85110032990182200% 错误，但我希望您现在可以理解它是如何实现的可能已经发生了。

\n