矩阵与递推

课件: 矩阵与递推

矩阵在第二个月就学过,递推就更早。 当时教练说矩阵可以加速递推,但是我弱,当时并不知道怎么加速。

直到上个月我才在厕所里脑补出来矩阵如何加速递推……


由于概念在课件中讲得很详细,我们来探讨一下如何推出对应的矩阵吧。

我们需要构造:$[F_n , F_{n+1}]$乘上某个东西,得到之后的斐波那契数。

我们应该如何构造矩阵乘法的结果呢?显然这个东西必须循环,也就是变成$[F_k , F_{k+1}]$的格式,来方便我们快速幂。

那么大体的思路就是:$[F_n , F_{n+1}] \times sth. = [F_{n+1} , F_{n+2}]$

首先我们发现,$F_{n+1}$必须保留下来。那么矩阵一定要留出一列来把$F_{n+1}$照抄。所以矩阵就是:$\begin{bmatrix} 0 & x \\ 1 & y \end{bmatrix}$

由于斐波那契数列的性质,构造$F_{n+2}$需要$F_n+F_{n+1}$,所以$x=1,y=1$。这样补上之后,我们得到一个矩阵乘法:

$\begin{bmatrix} F_n & F_{n+1} \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}= \begin{bmatrix} F_{n+1} & F_{n+2} \end{bmatrix} $

然后就可以快速幂了。


总结一下思路:

1.先构造起始矩阵和目标矩阵。
2.确定乘数矩阵。
3.快速幂。

然后问题就解决了。

一个递推如果要用矩阵来加速,应该满足后项可以由前项唯一确定。同时构造的矩阵要尽量小,以免在矩阵乘法上浪费过多的时间。


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close