我需要一些帮助来解决这个问题。
我想解决Ax = b，
在哪里A is n x n (square matrix), b is n x 1 matrix。
但是 A 矩阵有这个属性： + 病态 (K >> 1) (可能大于 10 ^ 8) + 对称正定矩阵（因为它是协方差矩阵）
我已经尝试过 Jacobi 方法，但不幸的是收敛速度很慢。我避免使用 Cholesky 分解。
而且我已经尝试过共轭梯度，但不幸的是，如果矩阵 A 的条件数太大，它就无法收敛。
更新：我需要一种可以在并行框架（如 MPI）中运行的方法。所以我不能在当前迭代中使用需要 x[i] 的 Gauss-seidal 。
我可以用什么样的方法来解决这种问题？谢谢 ：）
我猜测您的麻烦是由于矩阵向量乘积的计算不准确引起的。（我从来没有见过共轭梯度完全不能减少残差，除非矩阵向量乘积很差。重启后的第一次迭代只是做了最陡的下降。）
您可以尝试再次运行共轭梯度，但在计算矩阵向量乘积时使用扩展精度或Kahan 求和或其他东西。
或者，如果您的矩阵具有某些已知结构，您可能会尝试找到一种不同的方式来编写矩阵向量积，以减少计算结果中的舍入。如果我能看到你的矩阵，我也许可以在这里给出更具体的建议。
查看您上传的矩阵，有一些事情似乎有点奇怪：
K是一个相对较小 ( 400 x 400) 的密集矩阵。K包含大量接近零的条目，带有 ( abs(K(i,j)) < 1.E-16*max(abs(K)))。对于这种大小的矩阵，直接计算 Cholesky 分解应该是最有效的方法。我不知道你为什么说你不能这样做？
迭代技术，例如预处理共轭梯度方法，通常仅用于非常大且稀疏的方程组，因此在这里似乎不适用。
在求解诸如此类的稀疏线性方程组时，重要的不是矩阵中的行数/列数，而是矩阵本身的稀疏模式。
例如，如果您的矩阵A非常稀疏，则可以直接计算稀疏Cholesky 分解A = L*L'。但请注意，方程的排序决定了结果因子的稀疏模式，选择一个糟糕的排序策略A可能会导致灾难性的填充L*L'和糟糕的性能。
有许多策略，例如Approximate Minimum Degree和Multi-level Nested Dissection，应该用于重新排序A以获得伪最优稀疏性L*L'。
存在许多实现高性能稀疏分解的好包，包括上述重新排序方案的实现。我建议查看 Davis 的CHOLMOD 包。
如果您仍然发现您的方程组太大而无法使用直接因式分解进行有效处理，您应该研究预处理您的迭代PCG求解器。良好的预处理可以减少线性系统的有效条件数——在大多数情况下大大提高收敛性。
您应该始终至少使用简单的对角Jacobi 预处理器，尽管通常可以使用更复杂的方法来实现更好的性能，例如不完全 Cholesky 分解或可能的代数多网格或多级方法。您可能会发现PETSc 库在这方面很有帮助，因为它包含许多迭代求解器和预处理方案的高性能实现。
希望这可以帮助。
我已经看到（但没有真正接受）最近的工作，例如http://www.cs.yale.edu/homes/spielman/precon/precon.html。把你所说的和维基百科联系起来，你可能想看看http://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method ，这是http://en.wikipedia.org/的一个特例wiki/Successive_Over-relaxation。
如果事与愿违，您总是可以降低一个级别（找到更快的实现或在问题上投入更多硬件）或提高一个级别（尝试找到另一种方法来实现您的目标，而不涉及解决大型线性系统，或经常解决它们）。