在Python中求解看似(但实际上不是！)超定的稀疏线性系统

Question

我有一个稀疏矩阵a（使用scipy.s稀疏）和一个向量b，并且想求解x的Ax=b。a的行多于列，所以它看起来是超定的；然而，A的行是线性相关的，因此实际上A的行秩等于列的数量。例如，A可以是

A = np.array([[1., 1.], [-1., -1.], [1., 0.]])

而b是

b = np.array([0., 0., 1.])

解决方案是x=[1.，-1.]。我想知道如何使用scipy.sparse.linarg中的函数在Python中解决这个系统。谢谢！

Answer 1

您的系统是否可能不确定？如果不是，并且实际上有一个解决方案，那么最小二乘法解决方案就是这个解决方案，所以你可以尝试

from scipy.sparse.linalg import lsqr
return_values = lsqr(A, b)
x = return_values[0]

如果你的系统实际上是欠定的，这应该会给你找到最小的L2范数解。如果不起作用，请将参数damp设置为非常小的值（例如1e-5）。

如果您的系统是精确地确定的（即A是全秩的），并且有一个解，并且您的矩阵A很高，正如您所描述的，那么您可以在正规方程中找到一个等效系统：

A.T.dot(A).dot(x) == A.T.dot(b)

在CCD_ 5中具有独特的解决方案。这是一个平方线性系统，因此可以使用线性系统求解器（如scipy.sparse.linalg.spsolve ）来求解

解决问题的正式正确方法是使用SVD。你有一个形式的系统

A [MxN] * x [Nx1] = b [Mx1]

SVD将矩阵A分解为另外三个矩阵，因此得到：

U [MxM] * S[MxN] * V[N*N] * x[Nx1] = b[Mx1]

矩阵U和V都是正交的（它们的逆是它们的转置），并且S是对角矩阵。如果我们重写上面的内容，我们得到：

S[MxN] * V [N * N] * x[Nx1] = U.T [MxM] * b [Mx1]

如果是M > N，则矩阵S的最后一行M - N将为零，如果您的系统确实已确定，则U.T b的最后一列M - N也应为零。这意味着您可以将您的系统解决为：

>>> a = np.array([[1., 1.], [-1., -1.], [1., 0.]])
>>> b = np.array([0., 0., 1.])
>>> u, s, v = np.linalg.svd(a)
>>> np.allclose(u.T.dot(b)[-m+n:], 0) #check system is not overdetermined
True
>>> np.linalg.solve(s[:, None] * v, u.T.dot(b)[:n])
array([ 1., -1.])