计算萨姆

Question

我停留在以下问题：

对于给定的指数N，2×2矩阵A和一个极限L，递归地计算矩阵S：

S = I + A + A^2 + A^3 + ... + A^N

其中I是单位矩阵。

如果任何矩阵S的元素的是大于或等于L.递减用L，直到它 比L.下

我的算法如下：

// Pre-condition: 
// Parameters: 
// An integer indicating an exponent 
// A 2d 2x2 integer array must exist as an instance attribute 
// Post-condition: The matrix resulting from the sum of multiplied matrices 
// i.e. A^2 + A^1 + I 
public int[][] computeMatrixSum(int exp) 
{ 
    if(exp == 0) 
    { 
     return new int[][] 
     { 
      new int[]{ 1,0 }, 
      new int[]{ 0,1 } 
     }; 
    } 
    else 
    { 
     int[][] matrixB = new int[matrix.length][matrix[0].length]; 
     int[][] matrixC = new int[matrix.length][matrix[0].length]; 

     matrixB = matrix; 

     for(int expC = exp; expC > 1; expC--) 
     { 
      // Multiply the matrix 
      for(int i = 0; i < matrix.length; i++) 
      { 
       for(int k = 0; k < matrixB[0].length; k++) 
       { 
        for(int j = 0; j < matrix[0].length; j++) 
        { 
         matrixC[i][k] += matrix[i][j] * matrixB[j][k]; 
        } 
       } 
      } 
      matrixB = matrixC; 
      matrixC = new int[matrix.length][matrix[0].length]; 
     } 

     // Recursively calculate the sum of the other matrix products 
     int[][] tmpSum = computeMatrixSum(exp-1); 

     int[][] matrixSum = new int[matrixB.length][matrixB[0].length]; 

     for(int row = 0; row < matrixB.length; row++) 
     { 
      for(int col = 0; col < matrixB[0].length; col++) 
      { 
       matrixSum[row][col] = matrixB[row][col] + tmpSum[row][col]; 
      } 
     } 

     return matrixSum; 
    } 
} 

// Pre-condition: 
// Parameters: 
// An integer indicating the exponent to apply on the matrix 
// An integer indicating the limit of the elements of the 2d matrix sum 
// An 2d 2x2 integer array must exist as an instance attribute 
// Post-condition: The matrix resulting from the sum of multiplied matrices 
// that has elements that are not greater than the given limit 
// i.e. A^2 + A^1 + I 
public int[][] solve(int exp,int limit) 
{ 
     int[][] matrixSum = computeMatrixSum(exp); 

     for(int row = 0; row < matrixSum.length; row++) 
     { 
      for(int col = 0; col < matrixSum.length; col++) 
      { 
       while(matrixSum[row][col] >= limit) 
        matrixSum[row][col] -= limit; 
      } 
     } 

     return matrixSum; 
} 

我的算法作品。但是，对于大数值的N来说，它太慢了。这是因为当我将它们相乘时，我一直在重新计算所有指数的结果。

我不知道任何其他算法更有效地解决这个问题。

有人能请指教吗？

谢谢。

Answer 1

您可以申请Horner's method改造“单项式形式转化为高效计算的形式，”用实例here和here多项式的建议。您可以利用JScience类Matrix来简化编码。

Answer 2

如果A-I是可逆的，那么你可以找到S完全一样具有几何级数，只是记住，你必须通过逆相乘，而不是划分：

S = I + A + A^2 + A^3 + ... + A^N 
AS = A + A^2 + A^3 + ... + A^N + A^{N+1} 
AS-S = A^{N+1}-I 
(A-I)S = A^{N+1}-I 
S = (A-I)^{-1} (A^{N+1}-I) 

如果N确实是巨大的，那么你会想要exponentiate by squaring。递减L很容易，但您可能需要使用模数运算符。

如果A-I是奇异的，这种做法是行不通的，我能想到的最好的办法是使用A的Jordan normal form（这也将在第一种情况下，如果你想工作，）。