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

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


『引入』

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

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

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

这就是递推式。


『构造』

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

先找到 $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{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$:(也就是最开始说的中间那个矩阵)

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

⑥ 结束:

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


The End

Thanks for reading!

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

0%