計算薩姆

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（這也將在第一種情況下，如果你想工作，）。