计算科学 - 稀疏的、欠定的线性方程组 - 吾爱随笔录

稀疏的、欠定的线性方程组

计算科学线性代数算法线性求解器稀疏矩阵

2021-12-20 22:10:02

我正在寻找一种算法来解决线性方程组的欠定系统与，和。显然，存在无限数量的解向量（或根本没有解）。但是，如果是稀疏的，则的某些分量可能是唯一确定的。示例：

A x = b

$\mathbf{A}\,\mathbf{x} = \mathbf{b}$

A \in R^{n \times n}

$\mathbf{A} \in \mathbb{R}^{n\times n}$

b \in R^{n \times 1}

$\mathbf{b} \in \mathbb{R}^{n\times 1}$

r a n k (A) < n

$rank(\mathbf{A}) < n$

x

$\mathbf{x}$

A

$\mathbf{A}$

x = [x_{1}, \dots, x_{n}]

$\mathbf{x} = [x_1,\ldots,x_n]$

[\begin{matrix} 2 & - 1 & 0 & 0 \\ 1 & 0 & 2 & 4 \\ 1 & 0 & 2 & 4 \\ 1 & 2 & 0 & 0 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix}] = [\begin{matrix} 0 \\ 1 \\ 1 \\ 5 \end{matrix}]

$\begin{bmatrix}2 & -1 & 0 & 0\\1&0&2&4\\1&0&2&4\\1 & 2 & 0 & 0\end{bmatrix} \,\begin{bmatrix}x_1 \\x_2 \\ x_3 \\ x_4\end{bmatrix} = \begin{bmatrix}0 \\ 1 \\ 1 \\ 5\end{bmatrix}$ 如何找到具有此属性的和）？我将不胜感激相关文献的指点。

x_{i}

$x_i$

x

$\mathbf{x}$

x_{1}

$x_1$

x_{2}

$x_2$

3个回答

这里的问题是确定在哪里有的任何分量是由线性方程组唯一确定的。 $x$

这是一种方法：通过使用显示 QR 分解的秩或通过 SVD 或通过许多其他方法中的任何一种来的零空间的基础。令为大小为 x的矩阵，其列包含的基础。如果行是，则由方程唯一确定。 $A$ $U$ $n$ $p$ $N(A)$ $i$ $U$ $0$ $x_{i}$

不幸的是，这在实践中不会很好地工作，因为在确定的基础时会有小的舍入误差。例如，使用 MATLAB，我为您的示例矩阵计算了零空间： $N(A)$

A=[2 -1 0 0; 1 0 2 4；1 0 2 4；1 2 0 0]

一个=

 2    -1     0     0
 1     0     2     4
 1     0     2     4
 1     2     0     0

空（一）

答案=

-5.5511e-17

8.9443e-01

-4.4721e-01

在这种情况下，零空间是一维的。查看这个零空间的基向量，很明显是由方程唯一确定的。然而，对应于的零空间基向量的分量很小但不完全为 0。因此不清楚是否由方程唯一确定。 $x_{1}$ $x_{2}$ $x_{2}$

解决此问题的另一种方法是用精确的有理算术计算矩阵的 RREF，然后获得的零空间的基础。在这种情况下，我们得到： $A$ $A$

参考(A)

答案=

 1     0     0     0
 0     1     0     0
 0     0     1     2
 0     0     0     0

因此 x=[0; 0; -2; 1] 是一维的基向量。由此可以清楚地看出和是由方程唯一确定的。在这种情况下，我们很幸运，MATLAB 计算的 RREF 产生了一个精确的答案——对于一个更大的矩阵，我们可能会看到一些舍入误差，然后就需要使用更高（或无限）精度的算术。 $N(A)$ $x_{1}$ $x_{2}$

使用方程和变量的标准稀疏重新排序。如果一切顺利，则矩阵将分解为对角块（可能还有一些剩余部分），可以更轻松地检查解决方案的部分唯一性。

Scotch 项目提供“顺序和并行稀疏矩阵块排序”

SuiteSparse 的 btf 工具使用“最大化对角线上的非零点数量的最大匹配”和“一种查找图的强连通分量的方法”来“给出排列以阻止上三角形式”。

谷歌提供了更多讨论该理论和其他 stackexchange 和溢出问题的论文链接，例如 ( https://mathoverflow.net/questions/68041/showing-block-diagonal-structure-of-matrix-by-reordering )。

这些算法将矩阵的稀疏结构解释为二分图，并从条目中构造边权重。例如日志量级（整数的位长度）加上其他行条目的数量乘以其他列条目的数量。对于这个矩阵，它将给出权重矩阵

[\begin{matrix} 4 & 1 & - & - \\ 6 & - & 3 & 4 \\ 6 & - & 3 & 4 \\ 3 & 1 & - & - \end{matrix}]

$\begin{bmatrix} 4&1&-&-\\ 6&-&3&4\\ 6&-&3&4\\ 3&1&-&- \end{bmatrix}$ 然后应用匈牙利算法或变体来找到定义重新排序的对角线的最大权重匹配。可以在这里看到

(1, 1), (2, 3), (3, 4), (4, 2)

$(1,1),(2,3),(3,4),(4,2)$ . 然后应用聚类和部分图排序的半启发式算法以在对角线上获得尽可能多的条目。这将导致这里移动

(2 : 3, 3 : 4)

$(2:3, 3:4)$ 块到左上角对角线位置。

您可能希望最小化 $L_0$ 规范 $||x||_0$ 英石 $Ax=b$ ，以找到最稀疏的解决方案。其他 $p$ - 规范也适用于具体情况。一些需要跟进的资源是：

http://www.math.vanderbilt.edu/~foucart/FL08.pdf http://ftp.math.uga.edu/~mjlai/papers/surveySS.pdf

这些方法应该已经涵盖了您想要解决的情况。

其它你可能感兴趣的问题

上一篇如何在 Eigen C++ 中有效地定位大向量的不同段？下一篇在集合概率中散列？