计算科学 - 如何有效地求解线性矩阵方程：AX-XA=B？ - 吾爱随笔录

如何有效地求解线性矩阵方程：AX-XA=B？

计算科学线性代数算法正则

2021-12-26 15:02:18

最近我一直在使用 Fortran 解决一些数学问题。我想到一个线性矩阵方程：

A X - X A = B

$AX-XA=B$

其中和是已知的矩阵，而是需要求解的矩阵。我知道这看起来像一个典型的李雅普诺夫方程。然而，为了对空间友好地求解这个方程，可以使用一种迭代的方式来获得当 Kronecker 乘积时 $A$ $B$ $n\times n$ $X$ $X$

A I - I A^{T}

$AI-IA^T$

是非奇异的。

不幸的是，这不是我的情况。我的问题中的克罗内克产品是单一的。因此，我不能使用空间友好的迭代方式来解决问题，而是使用非常占用空间的方法来显式生成和存储 Kronecker 产品！！！然后我使用矩阵算法的 Moore-Penrose 伪逆来生成这个巨大矩阵的伪逆，并使用库矩阵向量乘法程序来求解方程。

对于小矩阵，这没问题。但是当矩阵的大小增加时（例如当 n 上升到几百）我的计算机的内存已经完全用完了。任何人都可以帮助解决这个问题，以便我可以使用空间友好的算法来解决这样的问题？非常感谢。

3个回答

另一个可能有帮助的想法是模仿 Bartels-Stewart 算法来求解一般的 Sylvester 方程。

我假设和是完整的矩阵，所以没有稀疏性可以利用。生成的算法将花费。 $A$ $B$ $n\times n$ $O(n^3)$

您需要计算 Schur 形式和，其中上三角、下三角、和正交。的 Schur 形式得到后者。）然后你可以将你的问题转化为方程，其中，。和是三角形的事实，您可以通过一种反向替换例如，比较你得到的 LHS 和 RHS $A=QUQ^T$ $A=RLR^T$ $U$ $L$ $diag(U)=diag(L)$ $Q,R$ $A^T$ $UY-YL=F$ $Y=Q^TXR$ $F=Q^TBR$ $U$ $L$ $Y$ $(n,n)$ $U_{nn}Y_{nn}-Y_{nn}L_{nn}=F_{nn}$ ，只有一个未知数，可以显式求解。然后你求解等等。 $Y_{n-1,n}$

与“传统” Bartels-Stewart 算法的区别在于，在您的情况下，与对角线上的项对应的方程将退化，因为。所以需要来保证可解性，并且可以任意设置的对应元素。 $U_{nn}=L_{nn}$ $F_{ii}=0$ $Y$

我希望我自己解释了——如果你想了解更多关于 Bartels-Stewart 算法的信息，我认为他们 70 年代的原始文章很短且可读。

solve_sylvesterscipy 中的函数将解决这个问题。我不知道你提到的奇点是否会影响它。

如果您的奇异问题的最小二乘解就足够了，您可以尝试使用耦合西尔维斯特方程的迭代最小二乘解中的迭代方法。这些方法应该比您当前的方法需要更少的内存。

其它你可能感兴趣的问题

上一篇从蒙特卡洛数据中提取相关矩阵下一篇为什么不使用这种更简单的逐步回归变体？