我想计算向量，
s = AB u,
其中 s 和 u 是 N 维复数向量，A 是 N×M 复数矩阵，B 是 M×N 复数矩阵。当 A、B 和 u 的元素表示为浮点数时，以下两种方式中哪一种精度更高（有效位数更高）？
(1) 先计算 B u。
首先做矩阵向量乘法，
y = B u
然后，另一个矩阵向量乘法
s = A y
(2) 先计算AB。
首先做矩阵-矩阵乘法，
C = AB
然后，矩阵向量乘法
s = C u
有没有已知的一般规则？
顺便说一句，我知道方法（1）比方法（2）更有效。
问问题
1775 次
2 回答
7
矩阵向量乘法比矩阵矩阵乘法具有更好的数值稳定性，所以我希望方法（1）更准确。
更详细地说，矩阵向量乘法具有很好的前向和后向误差界限。如果我们以矩阵向量乘法 y = B u 为例，那么 y 的误差为单位舍入的 2n 倍（使用标准双精度数时为 1e-16）乘以矩阵中的最大数 B 倍向量 u 中的最大数。这是前向误差界。
后向误差界是计算出的 y 不是 B 和 u 的乘积，而是一个稍微不同的矩阵 B' 和向量 u 的乘积。B 和 B' 之间的差值以 2n 倍单位舍入乘以矩阵 B 中的最大值为界。
对于矩阵-矩阵乘法，有一个类似于矩阵-向量乘法的前向误差界，但没有很好的后向误差界。
这是一个一般原则：输出较少的计算（例如矩阵-向量乘法）比输出较多的计算（例如矩阵-矩阵计算）更可能是向后稳定的。
但是，这是否有任何区别是另一个矩阵。可能是方法（2）恢复了后向稳定性，因为矩阵-向量乘积跟随矩阵-矩阵乘积。也可能是对于您的特定应用程序，没有太大区别，甚至方法（2）实际上更准确。
但是，鉴于方法（1）肯定是更快的一种，也可能是更准确的一种，我肯定会选择那个选项。
2011 年 9 月 29 日添加：我最喜欢这个主题的来源是 Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, 2002。但是许多数值分析教科书都讨论了前向和后向误差分析，尤其是那些专注于线性代数。
前向误差相当直观。如果您知道 B 和 u 是正确的，那么您感兴趣的是计算得到的乘积 B u 与精确乘积之间的差异；这就是前向错误分析告诉你的。当矩阵 B 不正确时，后向误差就会发挥作用（它可能是早期计算的结果导致了错误，或者它最终来自遭受实验或建模错误的测量）。假设 B 中的误差为 1e-10，并且乘法中的后向误差小于此值，例如 1e-11。这意味着尽管乘法的结果对于您提供给算法的 B 不正确，但对于另一个矩阵 B 是正确的，该矩阵 B 与原始 B 非常接近，以至于它很可能是正确的 B B 你给了算法。
前向和后向误差分析具有不同的优势：有时一种适用，有时另一种适用，有时混合使用。理想情况下，算法应该具有良好的前向和后向误差界限，但这并不经常发生。
于 2011-09-26T09:50:55.933 回答
2
除非算法是专门设计用来做额外的工作来补偿数值不准确的，一个很好的经验法则是给定两种计算相同事物的方法，做更少工作的算法有更好的准确度（毕竟，有发生四舍五入的机会更少）。这不是普遍正确的，因此它并没有消除考虑这些事情的义务，但这是一个很好的起点。
在您的情况下，它恰好是完全正确的。在不知道任何关于矩阵中特定值的先验知识的情况下，应该首选方法 (1)。（可以构建方法（2）更准确的特定情况，但它们通常是高度人为的）。
于 2011-09-26T12:15:31.947 回答