学习笔记 - 矩阵加速构造矩阵

感觉前一篇博客的构造矩阵部分写得很迷，估计大多数reader们会懵……
精益求精，再写一篇；
把矩阵加速的普遍式子总结一下~

『引入』

如果看过上一篇博客的两个例题，我们应该能够理解矩阵加速的递推式的基本形式（这里就以3个元素的矩阵举例）。

我们令 $A(i),B(i),C(i)$ 分别表示与 $i$ 相关的项，那么矩阵加速的一般形式就是：

$\begin{bmatrix}A(i)\\B(i)\\C(i)\end{bmatrix}=\begin{bmatrix}M_{1,1}\ M_{1,2}\ M_{1,3}\\M_{2,1}\ M_{2,2}\ M_{2,3}\\M_{3,1}\ M_{3,2}\ M_{3,3}\end{bmatrix}\times \begin{bmatrix}A(i-1)\\B(i-1)\\C(i-1)\end{bmatrix}$

假设我们已经构造出了这么一个矩阵，那么这意味着什么呢（也就是它所对应的转移方程式是什么）?

$A(i)=M_{1,1}A(i-1)+M_{1,2}B(i-1)+M_{1,3}C(i-1)\\ B(i)=M_{2,1}A(i-1)+M_{2,2}B(i-1)+M_{2,3}C(i-1)\\ C(i)=M_{3,1}A(i-1)+M_{3,2}B(i-1)+M_{3,3}C(i-1)\\$

这就是递推式。

『构造』

那么我们做题的时候当然是先找到了递推式，再来构造矩阵啊。所以我们可以倒过来想。

先找到 $A(i-1),B(i-1),C(i-1)$ （当然不一定是3个），也就是递推式右边所有与 $i$ 有关的数值以及常数项（比如 $i$,$f[i]$,$\frac{2}{i}$,$1$ 之类的），就得到了最右边的矩阵；知道了 $A(i-1),B(i-1),C(i-1)$ 当然也就知道 $A(i),B(i),C(i)$ 了，那么我们就可以得到最左边的矩阵了。

我们把 $A(i),B(i),C(i)$ 各用 $[M_1A(i-1)+M_2B(i-1)+M_3C(i-1)]$ 的形式表示出来，那么 $M_1,M_2,M_3$ 不就是矩阵的值了吗？

『例子』

看一个例子，reader们可以自己先推一下，看看自己到底会没有~

我们现在已经找到了递推式：
$f[0][i]=3f[1][i-1]+f[0][i-2]+2i$
$f[1][i]=f[0][i-1]+f[2][i-2]+3i$
$f[2][i]=f[2][i-1]+2f[1][i-2]+i$

来构造一个矩阵加速的模型！

过程如下：

① 找到 $A(i-1),B(i-1),C(i-1)…$ ：$f[0][i-1]$,$f[1][i-1]$,$f[2][i-1]$,$f[0][i-2]$,$f[1][i-2]$,$f[2][i-2]$,$i$,$1$；

② 得到 $A(i),B(i),C(i)…$ ：$f[0][i]$,$f[1][i]$,$f[2][i]$,$f[0][i-1]$,$f[1][i-1]$,$f[2][i-1]$,$i$,$1$；

③ 列出矩阵：

$\begin{bmatrix}f[0][i]\\f[1][i]\\f[2][i]\\f[0][i-1]\\f[1][i-1]\\f[2][i-1]\\i\\1\end{bmatrix} = M\times \begin{bmatrix}f[0][i-1]\\f[1][i-1]\\f[2][i-1]\\f[0][i-2]\\f[1][i-2]\\f[2][i-2]\\i\\1\end{bmatrix}$

④ 列出递推式：
$\begin{smallmatrix}f[0][i]=0·f[0][i-1]+3·f[1][i-1]+0·f[2][i-1]+1·f[0][i-2]+0·f[1][i-2]+0·f[2][i-2]+2·i+0\times 1\end{smallmatrix}$
$\begin{smallmatrix}f[1][i]=1·f[0][i-1]+0·f[1][i-1]+0·f[2][i-1]+0·f[0][i-2]+0·f[1][i-2]+1·f[2][i-2]+3·i+0\times 1\end{smallmatrix}$
$\begin{smallmatrix}f[2][i]=0·f[0][i-1]+0·f[1][i-1]+1·f[2][i-1]+0·f[0][i-2]+2·f[1][i-2]+0·f[2][i-2]+1·i+0\times 1\end{smallmatrix}$
$\begin{smallmatrix}f[0][i-1]=1·f[0][i-1]+0·f[1][i-1]+0·f[2][i-1]+0·f[0][i-2]+0·f[1][i-2]+0·f[2][i-2]+0·i+0\times 1\end{smallmatrix}$
$\begin{smallmatrix}f[1][i-1]=0·f[0][i-1]+1·f[1][i-1]+0·f[2][i-1]+0·f[0][i-2]+0·f[1][i-2]+0·f[2][i-2]+0·i+0\times 1\end{smallmatrix}$
$\begin{smallmatrix}f[2][i-1]=0·f[0][i-1]+0·f[1][i-1]+1·f[2][i-1]+0·f[0][i-2]+0·f[1][i-2]+0·f[2][i-2]+0·i+0\times 1\end{smallmatrix}$
$\begin{smallmatrix}i=0·f[0][i-1]+0·f[1][i-1]+0·f[2][i-1]+0·f[0][i-2]+0·f[1][i-2]+0·f[2][i-2]+1·i+0\times 1\end{smallmatrix}$
$\begin{smallmatrix}1=0·f[0][i-1]+0·f[1][i-1]+0·f[2][i-1]+0·f[0][i-2]+0·f[1][i-2]+0·f[2][i-2]+0·i+1\times 1\end{smallmatrix}$

⑤ 列出矩阵 $M$：（也就是最开始说的中间那个矩阵）

$\begin{bmatrix} 0\ 3\ 0\ 1\ 0\ 0\ 2\ 0\\ 1\ 0\ 0\ 0\ 0\ 1\ 3\ 0\\ 0\ 0\ 1\ 0\ 2\ 0\ 1\ 0\\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\\ 0\ 1\ 0\ 0\ 0\ 0\ 0\ 0\\ 0\ 0\ 1\ 0\ 0\ 0\ 0\ 0\\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 0\\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 1 \end{bmatrix}$

（早知道举一个简单一点的例子了……推这个矩阵的时候我整个人是崩溃的……）

⑥ 结束：

$\begin{bmatrix}f[0][i]\\f[1][i]\\f[2][i]\\f[0][i-1]\\f[1][i-1]\\f[2][i-1]\\i\\1\end{bmatrix} = \begin{bmatrix} 0\ 3\ 0\ 1\ 0\ 0\ 2\ 0\\ 1\ 0\ 0\ 0\ 0\ 1\ 3\ 0\\ 0\ 0\ 1\ 0\ 2\ 0\ 1\ 0\\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\\ 0\ 1\ 0\ 0\ 0\ 0\ 0\ 0\\ 0\ 0\ 1\ 0\ 0\ 0\ 0\ 0\\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 0\\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 1 \end{bmatrix}\times \begin{bmatrix}f[0][i-1]\\f[1][i-1]\\f[2][i-1]\\f[0][i-2]\\f[1][i-2]\\f[2][i-2]\\i\\1\end{bmatrix}$

各位看懂了吗？还有疑问就请发邮箱了~

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ，欢迎提问~