哪一个是更快/更稳定：反转矩阵或具有多个右手边解线性方程组的三个系统？

Question

我有两个方程我求解每个递归圆：

X = A - INV（B）* Y * INV（B）， X = X + A” * INV（B）* A，

我解决问题是这样的：

C = INV（B）的Ŷ<=> BC = Y，解决C. d = C INV（B）<=> DB = C <=> B'D '= C'，解决d'

E = INV（B）* A <=> BE = A，解决例如

所有矩阵随时间变化，所以我必须再次做到这一点（或反相）每递归。 N通常以约1-10，甚至更多，但通常这样的事情。 B是正定所以可以在因数分解使用的Cholesky，然后解决多个右手边的方程。

这是慢得多或不仅仅是反相乙快，然后做矩阵乘法与？一个反演VS求解线性方程组的三个系统（有另一个公式太）加上一些变调。我认为它至少数值上更稳定比反转？

感谢。

Answer 1

首先，让我们假设你所有的矩阵都是为了N×N的的。 Cholesky分解然后可以在O完成（N ^ 3/6）的操作（对于n的大值）。

求解B * C（1）= Y（i）或L * L'* C（1）= Y（I）（乔列斯基）是2 *为O（n ^ 2/2）或为O（n ^ 2 ），但解决BC这些方程= Y是解决N（因为Y是n×n个），所以在总我们为O（n ^ 3）。

解决d”显然是类似于这一点，所以另一个为O（n ^ 3）。

移调d”至d是rougly为O（n ^ 2），没有计算虽然，刚刚（从对角元素，这当然是相同的间隔）交换数据。

在BE求解E中的第二公式中= A是向后Cholesky分解一次取代，所以为O（n ^ 3）

A” * E为n ^ 2 *（N MULT和n-1加载），其是O（2 * N ^ 3 - N ^ 2）

这总计为：O（N ^ 3/6）+ 3 *为O（n ^ 3）+ O（N ^ 2）+ O（2 * N ^ 3 - N ^ 2）〜O（31 * N R个3/6）〜O（5 * N ^ 3）（对于n的大数值）

请注意，我还没有计算矩阵加法/减法，但是这是不相关的，因为它们将是相同的，如果我们决定要反转B.我也跳过A到A”出于同样的原因。

好了，所以如何昂贵是反相的矩阵？以及我们湾解决矩阵方程：

B * INV（B）= I，这是相同的解决B * X（I）= E（ⅰ），其中i = 1..N，其中e（i）是在一基座单元矢量这通常是通过使用高斯消除到系统变换到一个三角形的形式，其需要大约为O（n ^ 3/3）的操作完成。当三角测量由它需要为O（n ^ 2/2）的操作来解决它（向后取代）。但是，这必须做N次，这给了我们一个总的O（N ^ 4/3）+ O（N ^ 3/2）操作，所以你可以看到，我们已经在边缘。

然而，知道B的Cholesky因式分解当计算INV（B）为O（n ^ 3）（因为求解L * L'* INV（B）= I是相同的解决BE = A）

因此，我们然后有：为O（n ^ 3/6）（B的乔列斯基）+ O（N ^ 3）（计算与乔列斯基INV（B））+ 4 * O（2N ^ 3-N ^ 2） （4个矩阵乘法）〜O（9 * N ^ 3），这是更好一点，但仍然差。

所以我建议你留在你目前的做法。但你要记住，这是对于n值很大。除非n是100+，我不认为它很重要，许多无论如何。