线性方程的快速近似解？
我需要求解 N 个线性方程组作为数值优化器的中间步骤。 AFAIK 相当简单的算法精确地做到这一点是 O(N^3) （尽管我在一些数学论文中看到了一个非常复杂的算法，可以用 O(N^2.8) 和一个巨大的常数来完成）。在某些情况下，N 很大，即几千。
有没有什么好方法可以在小于 O(N^3) 的时间内获得线性方程组的近似解？
编辑：
如果有帮助的话，这里有一些更多的细节。
我的矩阵是对称的，而不是稀疏的。
这是 Newton-Raphson 的二阶导数矩阵。我正在尝试在 2000 维空间中优化某些内容。
I need to solve a system of N linear equations as an intermediate step in a numerical optimizer. AFAIK reasonably simple algorithms for doing so exactly are O(N^3) (though I saw a horibly complicated one in some math paper that could do it in something like O(N^2.8) with a huge constant). In some cases N is huge, i.e. several thousand.
Is there any good way to get a decent approximate solution to a system of linear equations in less than O(N^3)?
Edit:
Here are some more details if it helps at all.
My matrix is symmetric, and not sparse.
It's the second derivative matrix from Newton-Raphson. I'm trying to optimize something in a 2000-dimensional space.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
迭代方法有 Jacobi、Gauss-Seidel、cg、GMRES 等。
There are iterative methods like Jacobi, Gauss-Seidel, cg, GMRES etc.
对于对称矩阵，共轭梯度法实现起来很简单，并且会击败大多数其他迭代方法（例如高斯-赛德尔，SOR）。主循环由矩阵向量乘法和一些其他向量运算组成。
一旦你开始工作，你可以使用预处理来进一步提高收敛性。
For a symmetric matrix, the conjugate gradient method is simple to implement, and will beat most other iterative methods (e.g. Gauss-Seidel, SOR). The main loop consists of a matrix-vector multiply and a few other vector operations.
Once you've got it working, you can use preconditioning to improve the convergence even more.
是的，如果你从它们的系数得到的矩阵是稀疏的。例如，如果您有一个三对角矩阵，则可以使用“Rightlay”方法（保加利亚语，不确定确切的翻译），该矩阵的运算时间为 O(N)。还有其他算法仍然是 O(N^3)，但如果矩阵符合它们所需的某些不变量（稀疏、对角占优、三角形等），则可以获得令人难以置信的结果。
如果您坚持使用基于不变量的特定方法，那么进一步加快速度的唯一方法就是使用多线程。
尝试 此搜索。
Yes, if the matrix you get from their coefficients is sparse. There's the method of the "Right lay" (in Bulgarian, not sure about the exact translation) if you have a tri-diagonal matrix, for instance, which operates in O(N). There are other algorithms that are still O(N^3) but achieve incredible results if the matrix conforms to some invariant that they require (sparse, diagonal-prevailing, triangular, etc.).
If you're stuck to a specific method based on your invariant, the only way to further speed things up is to go multi-threaded.
Try this search.