哪种方式具有更好的精度来计算矩阵矩阵向量积,AB u？

Question

我想计算矢量,

s = AB u,

其中s和u是N维复矢量,A是N×M复合矩阵,B是M-by-N复矩阵.当A,B和u的元素表示为浮点数时,以下哪两种方法具有更好的准确度(更高有效位数)？

(1)首先计算B u.

首先进行矩阵向量乘法,

y = B u

然后,另一个矩阵 - 向量乘法

s = A y

(2)首先计算AB.

首先进行矩阵 - 矩阵乘法,

C = AB

然后,矩阵向量乘法

s = C u

有没有已知的一般规则？

顺便说一句,我知道方法(1)比方法(2)更有效.

Answer 1

矩阵向量乘法具有比矩阵 - 矩阵乘法更好的数值稳定性,因此我认为方法(1)更准确.

更详细地说,矩阵向量乘法具有良好的前向和后向误差界限.例如,如果我们采用矩阵向量乘法y = B u,那么y中的误差由单位四舍五入(当使用标准双精度数时为1e-16)乘以矩阵B次中的最大数乘以2n倍.向量中最大的数字u.这是前向错误界限.

向后误差界限是计算出的y不精确地是B和u的乘积,但它恰好是稍微不同的矩阵B'和向量u的乘积.B和B'之间的差异由单位舍入次数的2n倍乘以矩阵B中的最大数量.

对于矩阵 - 矩阵乘法,存在类似于矩阵向量乘法的前向误差界限,但没有良好的向后误差界限.

这是一般原则:具有较少输出的计算(例如矩阵向量乘法)比具有更多输出的计算(例如矩阵 - 矩阵计算)更可能是向后稳定的.

但是,这是否有所不同是另一个矩阵.由于矩阵 - 矢量乘积遵循矩阵 - 矩阵乘积,方法(2)可能恢复向后稳定性.对于您的特定应用,也可能没有太大差异,甚至方法(2)实际上更准确.

但是,鉴于方法(1)肯定是更快的方法,也可能是更准确的方法,我肯定会选择这个方案.

2011年9月29日补充:我最喜欢的主题是Nicholas J. Higham,数值算法的准确性和稳定性,SIAM,2002.但许多关于数值分析的教科书都讨论了前向和后向误差分析,特别是那些专注于线性代数.

前向错误非常直观.如果您知道B和u是正确的,那么您感兴趣的是计算的产品B u和确切的产品之间的差异; 这是前向错误分析告诉您的内容.当矩阵B不正确时,后向误差开始起作用(它可能是早期计算提交错误的结果,或者最终来自遭受实验或建模错误的测量).假设B中的误差是1e-10,并且乘法中的后向误差小于此,比如1e-11.这意味着虽然乘法的结果对于你给算法的B是不正确的,但是对于另一个与原始B非常接近的矩阵B来说它是正确的,它与正确的B一样可能是正确的B. B你给了算法.所以在某种意义上说,这是你所希望的那样好.

前向和后向误差分析具有不同的优势:有时适用,有时适用,有时适用.理想情况下,算法应具有良好的前向和后向错误界限,但这种情况不会经常发生.