计算科学 - 矩阵求逆的 Cholesky 分解扰动 - 吾爱随笔录 - 问答

矩阵求逆的 Cholesky 分解扰动

计算科学线性代数矩阵逆

2021-12-25 01:33:43

我正在寻找一种计算成本低廉的计算方式 $x$ 这样

(L L^{T} + μ^{2} I) x = y

$(L L^T + \mu^2 I)x = y$ 在哪里

L \in R^{n \times n}

$L \in \mathbb{R}^{n \times n}$ 是一个下三角定正矩阵（具有一些非常小的特征值），

y \in R^{n}

$y \in \mathbb{R}^n$ 和

μ \in R

$\mu \in \mathbb{R}$ 是已知的。如果有必要，我可以假设

μ ≪ 1

$\mu \ll 1$ 但

μ^{2}

$\mu^2$ 大于的最小特征值

L L^{T}

$LL^T$ .

基本上，我想充分利用我对 Cholesky 分解的了解 $L L^T$ . 最终，我希望能够计算 $x$ 在 $\mathcal{O}(n^2)$ . 也欢迎采用近似方法。

我在这里看到，这在更一般的情况下似乎不可行，但我希望 $\mu$ 可以帮助...

任何想法，参考或警告？谢谢你的帮助。

2个回答

不幸的是，虽然在低秩更新后更新 Cholesky 分解很容易，但像这样在全秩更新后更新 Cholesky 分解并不比重新计算 Cholesky 分解容易。

要考虑的替代方法是计算矩阵的特征值分解，

$A=LL^{T}=UDU^{T}$ .

添加 $\mu^{2}I$ 到 $A$ 简单地添加 $\mu^{2}$ 的特征值 $A$ ，所以

$A+\mu^{2}I=UVU^{T}$

在哪里 $V=D+\mu^{2}I$ . 然后，解决 $(A+\mu^{2}I)x=y$ ，我们让

$UVU^{T}x=y$

或者

$x=UV^{-1}U^{T}y$ .

对于每个值 $\mu$ 你有兴趣，这只需要 $O(n^{2})$ 额外的工作（三个矩阵向量乘法，其中一个只是对角缩放矩阵。注意不要将矩阵相乘！）与计算 Cholesky 分解相比 $A$ ，计算特征值分解也是 $O(n^{3})$ ，但它通常比 Cholesky 分解慢一个数量级。在摊销的基础上，如果你有足够的（比如几十到几百）价值，这将收回成本 $\mu$ 考虑。

您可以将您的问题重新表述为优化问题，并使用梯度下降进行数值求解。您可能会很快收敛，因为您最初的猜测将是您已经拥有的解决方案 $\mu^2=0$ .

更正式地说，我们喜欢找到 $x$ 最小化：

$f(x) = ||(LL^T+μ^2I)x -y||^2$ ，其中已给出。 $L, μ^2, y$

为了解决这个问题，从开始并使用梯度下降步骤更新梯度的每次评估都应该花费你。 $f(x_0) = f(A^{-1}y)$ $f(x)$ $O(d^2)$

由于您最初的猜测很好，因此其他迭代方法可能会很好用。参见例如第 2 章，这里

其它你可能感兴趣的问题

上一篇预处理对称舒尔补下一篇具有非齐次狄利克雷 BC 的 FEM 中的 Lax-Milgram 引理