3

嗨我一直在做一些关于矩阵求逆(线性代数)的研究,我想对算法使用 C++ 模板编程,我发现有很多方法,比如:Gauss-Jordan Elimination or LU Decomposition 我发现函数 LU_factorize (c++ boost library)

  1. 从程序员或数学家的角度,我想知道是否还有其他方法,哪种方法更好(优点/缺点)?

  2. 如果没有其他更快的方法,boost 库中是否已经有(矩阵)反转函数?,因为我搜索了很多,但没有找到。

4

5 回答 5

5

正如您所提到的,标准方法是执行 LU 分解,然后求解恒等式。这可以使用 LAPACK 库来实现,例如,使用dgetrf(factor) 和dgetri(compute inverse)。大多数其他线性代数库具有大致等效的功能。

当矩阵是奇异的或接近奇异的时,有一些较慢的方法可以更优雅地降级,并且出于这个原因使用。例如,如果矩阵可逆, Moore-Penrose 伪逆等于逆,并且即使矩阵不可逆也经常有用;它可以使用奇异值分解来计算。

于 2010-07-28T20:32:46.257 回答
3

我建议你看看Eigen源代码。

于 2010-07-28T20:27:40.760 回答
2

请谷歌或维基百科了解以下流行语。

首先,确保你真的想要逆。求解系统不需要反转矩阵。矩阵求逆可以通过求解 n 个系统来执行,右手边是单位基向量。所以我将专注于解决系统问题,因为它通常是你想要的。

这取决于“大”是什么意思。基于分解的方法通常必须存储整个矩阵。分解矩阵后,您可以一次求解多个右手边(从而轻松反转矩阵)。我不会在这里讨论分解方法,因为您可能已经知道它们。

请注意,当一个矩阵很大时,它的条件数很可能接近于零,这意味着该矩阵是“数值不可逆的”。补救措施:预处理。检查维基百科。文章写得很好。

如果矩阵很大,您不想存储它。如果它有很多零,它是一个稀疏矩阵。要么它具有结构(例如带对角线块矩阵……),并且你有专门的方法来解决涉及此类矩阵的系统,要么它没有。

当你面对一个没有明显结构的稀疏矩阵,或者你不想存储的矩阵时,你必须使用迭代方法。它们只涉及矩阵向量乘法,不需要特定形式的存储:您可以在需要时计算系数,或者以您想要的方式存储非零系数等。

方法是:

  • 对于对称定正矩阵:共轭梯度法。简而言之,求解 Ax = b 等于最小化 1/2 x^TA x - x^T b。
  • 一般矩阵的双共轭梯度法。虽然不稳定。
  • 最小残差方法或最佳 GMRES。有关详细信息,请查看维基百科文章。您可能想在重新启动算法之前试验迭代次数。

最后,您可以使用稀疏矩阵执行某种分解,并使用专门设计的算法来最小化要存储的非零元素的数量。

于 2010-08-02T12:17:35.413 回答
1

根据矩阵的实际大小,您可能只需要在任何给定时间将一小部分列保留在内存中。这可能需要覆盖对矩阵元素的低级写入和读取操作,我不确定 Eigen 是否会允许您这样做,否则它是一个相当不错的库。

对于这些矩阵非常大的非常狭窄的情况,有StlXXL库设计用于对主要存储在磁盘中的数组进行内存访问

编辑更准确地说,如果您有一个未在可用 RAM 中修复的矩阵,则首选方法是进行blockwise inversion。矩阵被递归分割,直到每个矩阵都适合 RAM(这当然是算法的调整参数)。这里棘手的部分是避免在将矩阵拉入和拉出磁盘时使矩阵的 CPU 饿死以进行反转。这可能需要在适当的并行文件系统中进行调查,因为即使使用 StlXXL,这也可能是主要瓶颈。虽然,让我重复一遍咒语;过早的优化是所有编程罪恶的根源。这种邪恶只能通过编码、执行和配置文件的净化仪式来消除

于 2011-02-14T19:25:55.977 回答
0

您可能想在 LAPACK 周围使用 C++ 包装器。LAPACK 是非常成熟的代码:经过充分测试、优化等。

Intel Math Kernel Library就是一个这样的包装器。

于 2010-07-28T20:59:20.507 回答