计算科学 - 解决几乎对称/伴随系统的算法？ - 吾爱随笔录

解决几乎对称/伴随系统的算法？

计算科学线性代数矩阵稀疏矩阵矩阵分解

2021-11-29 20:04:10

我熟悉用于求解线性方程组的 Cholesky 分解和 LU 分解。

我有一个问题，我有大型稀疏矩阵（例如，1000x1000 或更大），其中只有一两行/列（最后几行/列）破坏对称性。我知道 Cholesky 的效率几乎是 LU 的两倍，但由于这些异常行/列，我不能使用 Cholesky。

是否有另一种方法或算法可以处理这种特殊情况 - 即，利用几乎整个矩阵是自伴/对称的事实（仅此处为实数值）？

1个回答

让我们表达矩阵 $A \in \mathbb{R}^{n \times n}$ 我们想用它来解决线性系统

A = S + U V

$A = S + U V$ 在哪里

S

$S$ 是一个对称矩阵，

U \in R^{n \times r}

$U \in \mathbb{R}^{n \times r}$ ，和

V \in R^{r \times n}

$V \in \mathbb{R}^{r \times n}$ . 那是，

U V

$U V$ 是一个低秩更新，以解决缺乏对称性。从你的问题看来

r

$r$ 只是 1 或 2。

伍德伯里矩阵恒等式告诉我们

A^{- 1} x = (I_{n \times n} - \underset{W}{\underset{⏟}{S^{- 1} U (I_{r \times r} + V S^{- 1} U)^{- 1}}} V) S^{- 1} x = (I_{n \times n} - W V) S^{- 1} x .

$A^{-1} x = (I_{n \times n} - \underbrace{S^{-1} U (I_{r \times r} + V S^{-1} U)^{-1}}_{W} V) S^{-1} x = (I_{n \times n} - W V) S^{-1} x.$ 现在，对称矩阵出现逆

S

$S$ . 在预处理步骤中，您可以计算 Cholesky 分解

S

$S$ 和预计算

W = S^{- 1} U (I_{r \times r} + V S^{- 1} U)^{- 1}

$W = S^{-1} U (I_{r \times r} + V S^{-1} U)^{-1}$ . 注意

W

$W$ 只需要

O (r n^{2})

$\mathcal{O}(r n^2)$ 计算失败，这应该可以忽略不计。

预处理后，可以求解线性系统 $(I_{n \times n} - W V) S^{-1} x$ . 从右到左工作，我们可以使用前/后替换来计算 $S^{-1} x$ . 然后，我们需要执行矩阵向量乘法 $\left( I_{n \times n} - W V \right)$ . 以 $\mathcal{O}(r n)$ , 可以忽略不计。

其它你可能感兴趣的问题

上一篇非线性偏微分方程多重网格法中的平滑算子问题下一篇“丑陋”鞍点系统的迭代线性求解器