矩阵功率和 [英] Matrix power sum
问题描述
什么是计算矩阵比如A ^ I + A的总和的最好办法^(I + 1)+ A ^ I + 2 ........ A ^ n表示非常大的n?
What is the best way to calculate sum of matrices such as A^i + A^(i+1) + A^i+2........A^n for very large n?
我没有想到的两种可能的方式:
1)使用对数矩阵幂(LME)的A ^我,然后通过乘法计算以后的矩阵。
1) Use logarithmic matrix exponentiation(LME) for A^i, then calculate the subsequent matrices by multiplying by A.
问题:并没有真正利用LME算法,因为我用它只能实现低功耗!
Problem: Doesn't really take advantage of the LME algorithm as i am using it only for the lowest power!!
2)使用LME查找^ n和memoize的中间计算。
2)Use LME for finding A^n and memoize the intermediate calculations.
问题:需要太多的空间大的n
Problem: Too much space required for large 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
所以,你会做的步骤的对数数和没有必要计算逆。
So you will be doing a logarithmic number of steps and there is no need to compute inverses.
虽然直接实施将导致(log n)的^ 2
的因素,你可以在保持日志N
通过计算 A的权力
为你计算 B
。
While a direct implementation will lead to a (log n)^2
factor, you can keep it at log n
by computing the powers of A
as you compute B
.
这篇关于矩阵功率和的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!