对于很大的n，计算诸如A ^ i + A ^（i + 1）+ A ^ i + 2 ........ A ^ n之类的矩阵总和的最佳方法是什么？
我想到了两种可能的方法：
1）对A ^ i使用对数矩阵乘幂（LME），然后乘以A来计算后续矩阵。
问题：因为我仅将LME算法用于最低功耗，所以并没有真正利用它！
2）使用LME查找A ^ n并记住中间计算。
问题：大n需要太多空间。
有第三种方法吗？
注意：
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
因此，您将执行对数步数，并且无需计算逆数。
虽然直接实施将导致一个(log n)^2因素，你可以把它log n通过计算的力量A为你计算B。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句