对于非常大的 n，计算诸如 A^i + A^(i+1) + A^i+2....A^n 之类的矩阵之和的最佳方法是什么？
我想到了两种可能的方法：
1) 对 A^i 使用对数矩阵求幂(LME)，然后通过乘以 A 来计算后续矩阵。
问题：并没有真正利用 LME 算法，因为我只将它用于最低功率！
2) 使用 LME 求 A^n 并记住中间计算。
问题：大 n 需要太多空间。
有第三种方法吗？
问问题
8346 次
3 回答
12
请注意：
A + A^2 = A(I + A)
A + A^2 + A^3 = A(I + A) + A^3
A + A^2 + A^3 + A^4 = (A + A^2)(I + A^2)
= A(I + A)(I + A^2)
让
B(n) = A + ... + A^n
我们有：
B(1) = A
B(n) = B(n / 2) * (I + A^(n / 2)) if n is even
B(n) = B(n / 2) * (I + A^(n / 2)) + A^n if n is odd
因此，您将执行对数步数，无需计算逆数。
虽然直接实现会导致一个因素，但您可以通过计算as you compute的能力(log n)^2来保持它。log nAB
于 2013-09-19T09:38:25.507 回答
4
您可以使用以下事实：n矩阵的几何级数之和等于：
S_n = (I-A)^(-1) (I-A^n)
而且，由于您不是从 0 开始，您可以简单地计算：
result = S_n - S_i
i你的起始索引在哪里。
于 2013-09-19T09:27:04.453 回答
1
为什么不将矩阵对角化以使乘法便宜。
编辑：
只要矩阵是非奇异的，您就应该能够找到矩阵 A 的对角线表示 D 使得 A = PDP^-1 其中 P 由 A 的特征向量组成，并且 D 具有沿对角线的 A 的特征值。获得 D^m = D*D^(m-1) 很便宜，因为它只是沿对角线相乘（即与矩阵维数相同的乘法数）
获得 S(m)=S(m-1)+D^m 也很便宜，因为您只添加对角线元素。
然后你有
A^i + A^(i+1) + A^i+2........A^n = P(D^i + D^(i+1) + D^i+2.. ......D^n)P^-1 = P( S(n) - S(i) )P^-1
唯一困难的是找到P和P^-1
于 2013-09-19T09:17:28.950 回答