避免矩阵乘法中的算术溢出

计算科学 线性代数 线性求解器 稳定 预处理
2021-12-05 07:20:47

我正在为求解以下矩阵方程:x

(JTJ)x=JTr

  • J矩阵m×n
  • x是大小为n
  • r是大小为m

此外,mn

有时非常大(例如 1000)并且,因此即使使用双精度数字也无法进行标准乘法nJ10128

我发现用非零值缩放对结果有可预测的影响(它与将上述等式的两边乘以标量具有相同的效果),所以我正在考虑计算一个比例因子,以便可以解决上述等式没有溢出。然而,太小的比例因子也会危及矩阵乘法的准确性。J

此外,可以包含非常小和非常大的值。J

所以问题是如何选择一些比例因子,以便我们可以,避免数字太大,同时保持乘法的高精度。sJsJ

我的想法:

  • 使中元素的平均值/中位数等于例如J103
  • 根据其最大列的总和缩放J
  • 找到一些“预处理器”矩阵并用代替 ...预处理解可以使用逆变换获得,但是可以变得非常大,因为它必须是AJAJAm×m

有任何想法吗?

1个回答

这不是您问题的直接答案,而是另一种方法。

看起来您正在使用正规方程解决最小二乘 (LS) 问题。众所周知,正规方程是解决最小二乘问题的糟糕方法,因为JTJ往往是非常病态的。

那么你为什么不直接解决LS问题(Jx=r) 使用例如 QR 分解?LAPACK 例程 DGELS 将为您做到这一点。

http://www.netlib.org/lapack/lug/node27.html

Octave、MATLAB、Python 和其他脚本语言中有此例程的接口,因此如果您不想使用,则不需要使用 Fortran/C/C++。

如果您有兴趣阅读有关使用 QR 分解来解决 LS 问题的更多信息,Cleve Moler 书中的这一章提供了一个非常易读的介绍:

http://www.mathworks.com/moler/leastsquares.pdf