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 回答