矩阵指数解决实例问题

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 |

因此，这些是递归关系的基本类别，用于通过这种简单的技术解决。