Cholesky 分解和正向替换不如反演准确?

机器算法验证 matlab 计算统计 距离 逆矩阵 胆汁分解
2022-04-16 06:57:11

我最近问了这个问题,要求一种有效的方法来计算马氏距离(不计算倒数)。公认的解决方案是使用 Cholesky 分解和前向选择。

但是,在重要的情况下,这似乎不太准确。假设并且具有以下迭代算法(阿布拉莫维奇估计器p>n

V(n+1)=i=1nxixiTxTV(n)1x+ϵI

请注意,允许每个迭代在下一步中是可逆的。ϵ

然而,当我在 MATLAB 中进行实验时,我发现虽然 Cholesky 分解确实比计算逆运算更快,但涉及逆运算的解决方案更准确。这是异常现象还是众所周知的现象?我知道 Cholesky 分解除了比逆分解更有效外,还应该更准确。

1个回答

对于大多数情况,Cholesky 分解应该是求解线性方程组(例如 )的更快且数值更稳定的方法,因为描述的是正定矩阵。线性系统解决方案背后的标准主力是 QR 分解;它确实需要系统是正定的,甚至是平方的。Ax=bAA

在相对较小的矩阵中可能会发现一些性能差异,因为可能会使用直接分析解决方案,但对于大于的系统,通常情况并非如此。一般来说,就性能而言,Cholesky 分解的速度大约是LU分解的两倍,LU 分解的速度大约是QR 分解的两倍,而 QR 分解的速度大约是SVD 分解的两倍它们都有不同的条件,因此它们是适用的,但它们都可以用来求解线性系统。3×34×4

鉴于您使用的是 MATLAB,MATLAB 的mldivide运算符将自动进行某些检查并根据上述最佳分解计算解决方案(以及一些额外的,例如检查您是否有Hessenberg 矩阵并使用带状求解器)。为矩阵 ( ) 供电^-1是求解线性方程组的一种相当低效的方法。它很可能会诉诸矩阵的奇异值分解。这在数值上是稳定的,但非常慢。