矩陣指數解決例項問題

Created: November-22, 2018

*求 f(n)：第 n 個 Fibonacci 數。*當 n 相對較小時，問題很容易。我們可以使用簡單的遞迴，f(n) = f(n-1) + f(n-2)，或者我們可以使用動態程式設計方法來避免一遍又一遍地計算相同的函式。但如果問題出現，你會怎麼做？**給定 0 <n <10⁹，找到 f(n)mod 999983？**動態程式設計將失敗，那麼我們如何解決這個問題呢？

首先讓我們看看矩陣求冪如何有助於表示遞迴關係。

先決條件：

鑑於兩個矩陣，知道如何找到他們的產品。此外，給定兩個矩陣的乘積矩陣，以及其中之一，知道如何找到另一個矩陣。
給定大小為 d X d 的矩陣，知道如何在 O（d 3 log(n)）中找到其 n 次冪。

模式：

首先，我們需要一個遞迴關係，我們希望找到一個矩陣 M ，它可以將我們引導到一組已知狀態的所需狀態。讓我們假設，我們知道給定遞迴關係的 k 個狀態，並且我們想要找到第 （k + 1）個 狀態。設 M 是 k X k 矩陣，我們從遞迴關係的已知狀態構建矩陣 A：[k X 1] ，現在我們想要得到一個矩陣 B：[k X 1] ，它代表一組下一個狀態，即 MXA = B ，如下所示：

       |  f(n)  |     | f(n+1) |
       | f(n-1) |     |  f(n)  |
   M X | f(n-2) |  =  | f(n-1) |
       | ...... |     | ...... |
       | f(n-k) |     |f(n-k+1)|

所以，如果我們可以相應地設計 M ，我們的工作就會完成！然後矩陣將用於表示遞迴關係。

型別 1：
讓我們從最簡單的一個開始，f(n) = f(n-1) + f(n-2)
我們得到，f(n+1) = f(n) + f(n-1)。
我們假設，我們知道 f(n) 和 f(n-1); 我們想找出 f(n+1)。
根據上述情況，矩陣 A 和矩陣 B 可以形成如下：

 Matrix A          Matrix B

|  f(n)  |        | f(n+1) |
| f(n-1) |        |  f(n)  |

[注意：矩陣 A 將始終以這樣的方式設計，即 f(n+1) 所依賴的每個狀態都將存在]

現在，我們需要設計一個 2X2 矩陣 M ，使其滿足如上所述的 MXA = B. B,第一個元素是 f(n+1)，實際上是 f(n) + f(n-1)。為了得到這個，我們需要從矩陣 A 得到 1 X f(n) 和 1 X f（n-1） 。所以 M 的第一行將是 [1 1] 。 **** **** **** **** **** ****

| 1   1 |  X  |  f(n)  |  =  | f(n+1) |
| ----- |     | f(n-1) |     | ------ |

[注意：—–意味著我們不關心這個值。]
同樣， B 的第 2 項是 f(n)，只需從 A 中取 1 X f(n) 即可得到，所以 M 的第 2 行是[ 1 0]。 **** ****

| ----- |  X  |  f(n)  |  =  | ------ |
| 1   0 |     | f(n-1) |     |  f(n)  |

然後，我們得到我們所期望的 2×2 矩陣M。

| 1   1 |  X  |  f(n)  |  =  | f(n+1) |
| 1   0 |     | f(n-1) |     |  f(n)  |

這些矩陣簡單地使用矩陣乘法匯出。

型別 2：

讓它變得有點複雜：找到 f(n) = a X f(n-1) + b X f(n-2)，其中 a 和 b 是常數。
這告訴我們，f(n+1) = a X f(n) + b X f(n-1)。
到目前為止，應該清楚矩陣的維數將等於依賴的數量，即在這個特定的例子中，再次為 2.因此，對於 A 和 B ，我們可以構建兩個大小為 2 X 1 的矩陣：

Matrix A             Matrix B
|  f(n)  |          | f(n+1) |
| f(n-1) |          |  f(n)  |

現在對於 f(n+1) = a X f(n) + b X f(n-1)，我們需要在物鏡矩陣 M 的第一行中使用[a，b] 。而對於 B 中的第二項，即 f(n)，我們已經在矩陣 A 中得到了它，所以我們只需要將矩陣 M 的第二行引導到[1 0]。這次我們得到：

| a   b |  X  |  f(n)  |  =  | f(n+1) |
| 1   0 |     | f(n-1) |     |  f(n)  |

很簡單，嗯？

型別 3：

如果你已經活到了這個階段，你已經長大了，現在讓我們面對一個複雜的關係：找到 f(n) = a X f(n-1) + c X f(n-3)？
哎呀！幾分鐘前，我們所看到的只是連續的狀態，但在這裡，狀態 f（n-2） 缺失。現在？

實際上這不再是問題，我們可以將關係轉換如下：f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3)，推理 f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2)。現在，我們看到，這實際上是型別 2 中描述的形式。所以這裡目標矩陣 M 將是 3 X 3 ，並且元素是：

| a 0 c |     |  f(n)  |     | f(n+1) |
| 1 0 0 |  X  | f(n-1) |  =  |  f(n)  |
| 0 1 0 |     | f(n-2) |     | f(n-1) |

這些計算方法與型別 2 相同，如果你覺得困難，請在筆和紙上進行嘗試。

型別 4：

生活變得越來越複雜，而 Mr 先生，問題現在要求你找到 f(n) = f(n-1) + f(n-2) + c，其中 c 是任何常數。
現在這是一個新的，我們在過去看到的所有，在乘法之後， A 中的每個狀態都轉換為 B 中的下一個狀態。

f(n) = f(n-1) + f(n-2) + c
f(n+1) = f(n) + f(n-1) + c
f(n+2) = f(n+1) + f(n) + c
.................... so on

所以，通常我們無法通過以前的方式獲得它，但我們如何將 c 新增為狀態：

      |  f(n)  |   | f(n+1) |
  M X | f(n-1) | = |  f(n)  |
      |    c   |   |    c   |

現在，設計 M 並不困難。這是它的完成方式，但不要忘記驗證：

  | 1 1 1 |     |  f(n)  |     | f(n+1) |
  | 1 0 0 |  X  | f(n-1) |  =  |  f(n)  |
  | 0 0 1 |     |    c   |     |    c   |

第 5 類：

讓我們完全放下：找到 f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e。讓我們把它作為鍛鍊給你。先試著找出狀態和矩陣M。並檢查它是否與你的解決方案匹配。還發現矩陣一個和B。

| a 0 c d 1 |
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 0 1 |

型別 6：

有時復發是這樣的：

f(n) = f(n-1)   -> if n is odd
f(n) = f(n-2)   -> if n is even

簡而言之：

f(n) = (n&1) X f(n-1) + (!(n&1)) X f(n-2)

在這裡，我們可以在奇數偶數的基礎上分割函式，併為它們保留 2 個不同的矩陣並分別計算它們。

7 型：

感覺有點太自信了？對你有益。有時我們可能需要在他們感興趣的地方保持多次重複。例如，讓重現; atopm 是：

g(n) = 2g(n-1) + 2g(n-2) + f(n)

這裡，遞迴 g(n) 取決於 f(n)，並且這可以在相同的矩陣中計算，但是尺寸增加。從這些我們在第一個設計矩陣的一個和B。

 Matrix A            Matrix B
|  g(n)  |          | g(n+1) |
| g(n-1) |          |  g(n)  |
| f(n+1) |          | f(n+2) |
|  f(n)  |          | f(n+1) |

在這裡，g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n)。現在，使用上述過程，我們可以找到目標矩陣 M ：

| 2 2 1 0 |
| 1 0 0 0 |
| 0 0 2 2 |
| 0 0 1 0 |

因此，這些是遞迴關係的基本類別，用於通過這種簡單的技術解決。