注意:正如 Warren Weckesser 指出的那样,我在最初发布的代码中犯了一个愚蠢的错误。更正后,一些求解器会给出正确答案,但其他求解器会给出 NaN 或错误答案。我还忘记在输出中包含运行时警告;他们现在在那里。我已经相应地修改了问题。我也许可以使用有效的求解器,但如果我了解其他求解器失败的原因,我会更开心。
我正在尝试使用 scipy.sparse.linalg 中的一个或多个求解器来求解稀疏线性方程组。在系统小到可以直接求解的测试用例中,一些稀疏求解器给出了错误的答案,如下例所示:
import numpy as np
import scipy.sparse as ss
A = np.matrix([[ 0., 0., 0., 0., 0., 1., -1., -0., -0., -0., -0.],
[ 0., 0., 0., 0., 0., 2., -0., -1., -0., -0., -0.],
[ 0., 0., 0., 0., 0., 2., -0., -0., -1., -0., -0.],
[ 0., 0., 0., 0., 0., 2., -0., -0., -0., -1., -0.],
[ 0., 0., 0., 0., 0., 1., -0., -0., -0., -0., -1.],
[ 1., 2., 2., 2., 1., 0., -0., -0., -0., -0., -0.],
[-1., 0., 0., 0., 0., 0., -1., -0., -0., -0., -0.],
[ 0., -1., 0., 0., 0., 0., -0., -1., -0., -0., -0.],
[ 0., 0., -1., 0., 0., 0., -0., -0., -1., -0., -0.],
[ 0., 0., 0., -1., 0., 0., -0., -0., -0., -1., -0.],
[ 0., 0., 0., 0., -1., 0., -0., -0., -0., -0., -1.]])
b = np.matrix([0.,0.,0.,0.,0.,1.,0.,0.,0.,0.,0.]).T
As = ss.coo_matrix(A)
# The linear system Ax = b has a solution:
x1 = np.linalg.solve(A,b)
print("Solution to Ax = b:",x1)
print("Ax - b = ",A*x1-b)
print("Info and maximum error in solutions found by various other methods: ")
x2,info = ss.linalg.bicg(As,b)
print("bicg:",info,np.max(np.abs(x2-x1.ravel())))
x2,info = ss.linalg.bicgstab(As,b)
print("bicgstab:",info,np.max(np.abs(x2-x1.ravel())))
x2,info = ss.linalg.cgs(As,b)
print("cgs:",info,np.max(np.abs(x2-x1.ravel())))
x2,info = ss.linalg.gmres(As,b)
print("gmres:",info,np.max(np.abs(x2-x1.ravel())))
x2,info = ss.linalg.lgmres(As,b)
print("lgmres:",info,np.max(np.abs(x2-x1.ravel())))
x2,info = ss.linalg.minres(As,b)
print("minres:",info,np.max(np.abs(x2-x1.ravel())))
x2,info = ss.linalg.qmr(As,b)
print("qmr:",info,np.max(np.abs(x2-x1.ravel())))
当我运行它时,我得到以下输出:
Solution to Ax = b: [[ 0.07142857]
[ 0.14285714]
[ 0.14285714]
[ 0.14285714]
[ 0.07142857]
[-0.07142857]
[-0.07142857]
[-0.14285714]
[-0.14285714]
[-0.14285714]
[-0.07142857]]
Ax - b = [[ 0.00000000e+00]
[ 0.00000000e+00]
[ 2.77555756e-17]
[ 0.00000000e+00]
[ 1.38777878e-17]
[ 0.00000000e+00]
[ 2.77555756e-17]
[ -2.77555756e-17]
[ -5.55111512e-17]
[ 2.77555756e-17]
[ 0.00000000e+00]]
Info and maximum error in solutions found by various other methods:
bicg: 1 nan
bicgstab: 1 nan
cgs: 1 nan
gmres: 0 5.55111512313e-17
lgmres: 0 1.38777878078e-16
minres: 0 0.142857142857
qmr: -11 0.142857142857
/Users/ebunn/anaconda/lib/python3.5/site-packages/scipy/sparse/linalg/isolve/iterative.py:197: RuntimeWarning: invalid value encountered in multiply
work[slice2] *= sclr2
/Users/ebunn/anaconda/lib/python3.5/site-packages/scipy/sparse/linalg/isolve/iterative.py:318: RuntimeWarning: invalid value encountered in multiply
work[slice2] *= sclr2
/Users/ebunn/anaconda/lib/python3.5/site-packages/scipy/sparse/linalg/isolve/minres.py:244: RuntimeWarning: divide by zero encountered in double_scalars
Acond = gmax/gmin
x2 的每次计算都应该是与 x1 相同的线性系统的解,因此最后七行中的所有这些错误都应该为零(或至少很小)。
gmres 和 lgmres 有效,但其他的无效。在大多数情况下,信息正确指示失败,但 minres 指示成功 (info=0),同时返回全为零的解决方案(不正确)。
以下是一些可能相关的附加信息:
- 矩阵A是对称的但不是正定的。
- 矩阵 A 的条件非常好。
- 如果我在所有稀疏求解器中用原始矩阵 A 替换稀疏表示 As,结果不会改变——也就是说,如果我说 ss.linalg.bicg(A,b)而不是 ss.linalg.bicg(As,b) 等
- 包含 bicgstab 实际上是不公平的,因为文档说它仅适用于正定矩阵。我将其包含在内是希望它能起作用,因为这种方法原则上适用于不定矩阵。
- 我正在运行 Python 3.5.1,scipy 版本 0.17.0。
当然,对于这个系统来说,无所谓,因为直接求解是微不足道的。对于需要稀疏性的较大问题,这是一个预热问题。
gmres 和/或 lgmres 可能会满足我的需求,但我仍然想了解其他人出了什么问题,部分是为了我自己的理解,也是为了我可能有一套更广泛的方法来从中选择。特别是,这两种有效的方法都没有利用 A 的对称性,如果有一种方法可以利用它可能会很好。
请您参考如下方法:
当我运行你的代码 (py3) 时,我收到了一堆警告
Maximum error in solutions found by various other methods:
bicg: nan
/usr/lib/python3/dist-packages/scipy/sparse/linalg/isolve/iterative.py:197: RuntimeWarning: invalid value encountered in multiply
work[slice2] *= sclr2
bicgstab: nan
/usr/lib/python3/dist-packages/scipy/sparse/linalg/isolve/iterative.py:318: RuntimeWarning: invalid value encountered in multiply
work[slice2] *= sclr2
cgs: nan
gmres: 0.285714285714
lgmres: 0.285714285714
/usr/lib/python3/dist-packages/scipy/sparse/linalg/isolve/minres.py:244: RuntimeWarning: divide by zero encountered in double_scalars
Acond = gmax/gmin
minres: 0.142857142857
qmr: 0.142857142857
正如 Warren 警告的那样,对于 gmres 情况,数组形状可能会影响您。非 nan 情况下的错误均为 0.1428 或 2 倍。
添加:
print(x2)
print(x2-x1.ravel())
产生:
[ 0.07142857 0.14285714 0.14285714 0.14285714 0.07142857 -0.07142857
-0.07142857 -0.14285714 -0.14285714 -0.14285714 -0.07142857] 0
[[ 4.16333634e-17 0.00000000e+00 -5.55111512e-17 5.55111512e-17
0.00000000e+00 -1.38777878e-17 -1.38777878e-17 -2.77555756e-17
0.00000000e+00 -2.77555756e-17 0.00000000e+00]]
当我正确比较 2 个解决方案时没有错误。
