2

我知道这更像是一个复杂性理论问题，而不是一个编程问题，希望我在这里没有做错事情，如果是错误的地方，我很抱歉，但我希望你们中的某个人有答案。它甚至在某种程度上与编程相关，因为它是一个复杂性理论问题。

我正在研究线性循环序列，我读到为了获得它弹出的序列的第 n 个值，你需要获得一些伴随矩阵的幂，我想知道是否有已知的算法来获得幂这种矩阵的快速方式..

我无法给出编码示例，但我会尝试为您提供更多解释：

k阶齐次线性循环序列：
s(n+k)=a(k-1)s(n+k-1)+a(k-2)s(n+k-2)+... +a(0)
for n=0,1,.. 其中 s(i) 是序列的第 i 个值，a(i) 是代数域中的系数。

A 是上述序列的伴随矩阵，如果它是：
( 0 0 0 0 ... 0 a(0) )
( 1 0 0 0 ... 0 a(1) )
( 0 1 0 0 ... 0 a (2) )
( .. .. .. .. .. .. .. .. ..)
( 0 0 0 0 ... 1 a(k-1) )
此外，理论指出，对于我们有序列：
s(n) = s(0)A^n for n=0,1,..
就是这样，感谢您的帮助。

4

2 回答 2

2

快速找到矩阵幂的常用策略是将其对角化（执行特征向量分解）：

A = P -1 DP

其中 D 是对角矩阵。然后，您可以通过计算将 A 提高到 n 次方

A n = P -1 D n P

其中 D n计算速度很快，因为它是一个对角矩阵，因此您只需分别计算每个元素的幂即可。

但是，并非所有矩阵都是可对角化的——我不知道您的伴侣矩阵是否可以。在任何情况下，您都可能会发现这篇 Wikipedia 文章很有帮助。

于 2009-04-07T14:48:38.830 回答
1

您可以使用矩阵乘积计算n矩阵的 th 次方：MO(log n)

  • 如果n=0，返回I
  • 如果n是偶数，计算N=Mn/2并返回N*N
  • 如果n是奇数，计算N=Mn-1并返回M*N
于 2009-04-26T12:27:02.747 回答