[矩阵]矩阵构造方法练习与总结

快速求递推式第n项

1. Fibonacci递推公式：$$fn=f{n-1}+f_{n-2}​$$

   [解法]：考虑递推公式中含有两项，则考虑$$1 \times 2$$矩阵：

   $$ \left[ \begin{matrix} f{n-2} & f{n-1} \end{matrix} \right] \tag{1}$$

   我们需要得到$$1 \times 2$$的矩阵（未知数）：

   $$ \left[ \begin{matrix} f{n-1} & f{n} \end{matrix} \right] \tag{2}$$

   那么考虑这样的乘法（矩阵乘法）：

   $$ \left[ \begin{matrix} f{n-2} & f{n-1} \end{matrix} \right] \times A = \left[ \begin{matrix} f{n-1} & f{n} \end{matrix} \right] $$,其中$$A$$为转移矩阵，很容易退出$$A$$是$$2 \times 2$$矩阵: $$ \left[ \begin{matrix} 0 & 1\ 1 & 1 \end{matrix} \right] $$ 所以就有： $$ \left[ \begin{matrix} f_1 & f_2 \end{matrix} \right] \times \left[ \begin{matrix} 0 & 1\ 1 & 1 \end{matrix} \right] = \left[ \begin{matrix} f_2 & f_3 \end{matrix} \right] $$ 最后就能得到：

   ​ $$ \left[ \begin{matrix} f1 & f_2 \end{matrix} \right] \times \left[ \begin{matrix} 0 &1 \1 &1 \end{matrix} \right] ^{n-1} = \left[ \begin{matrix} f_n & f{n+1} \end{matrix} \right] $$

2.递推式：$$ fn=f{n-1}+f_{n-2}+1,f_1=f_2=1$$:

[解法]：同样，考虑递推式中含有三项，构造如下矩阵乘法：

$$ \left[ \begin{matrix} f{n-2} & f{n-1} & 1 \end{matrix} \right] \times A = \left[ \begin{matrix} f{n-1} & f{n} & 1 \end{matrix} \right]​

$$

按照上述方法即可构造转移矩阵：

$$ \left[ \begin{matrix} 0 & 1 & 0\1 & 1 & 0 \ 0 & 1 & 1 \end{matrix} \right]

$$ 即：

$$ \left[ \begin{matrix} f1 & f_2 & 1 \end{matrix} \right] \times \left[ \begin{matrix} 0 & 1 & 0 \ 1 & 1&0 \ 0&1&1 \end{matrix} \right] ^{n-1}= \left[ \begin{matrix} f{n}&f_{n+1}&1 \end{matrix} \right]

$$

3.递推式：$$fn=f{n-1}+f_{n-2}+n+1,f_1=f_2=1$$:

[解法]：考虑$$1 \times 4$$矩阵$$ \left[ \begin{matrix} f{n-2} & f{n-1} &n &1 \end{matrix} \right] $$ ,可以列出一下乘法等式：

$$ \left[ \begin{matrix} f{n-2} & f{n-1} & n & 1 \end{matrix} \right] \times A = \left[ \begin{matrix} f_{n-1} & f_n & n+1 &1 \end{matrix} \right]

$$ 同理即可构造转移矩阵：

$$ \left[ \begin{matrix} 0&1&0&0\1&1&0&0 \ 0&1&1&0\0&1&1&1 \end{matrix} \right]

$$ 即：

$$ \left[ \begin{matrix} f1 &f_2 &3 &1 \end{matrix} \right] \times \left[ \begin{matrix} 0&1&0&0\1&1&0&0\0&1&1&0\0&1&1&1 \end{matrix} \right] ^{n-1} = \left[ \begin{matrix} f{n-1}&f_n&n+1&n \end{matrix} \right]

$$ 4.递推式$$fn=f{n-1}+f{n-2},f_1=f_2=1$$的前n项和为$$s_n=\sum {i=1} ^n f_i$$：

[解法]：仿照之前的思路，构造$$1 \times 3$$的矩阵：$$ \left[ \begin{matrix} f{n-2} & f{n-1} &s{n-2} \end{matrix} \right] $$,希望通过乘$$3 \times 3$$的矩阵得到$$ 1\times 3$$的矩阵$$ \left[ \begin{matrix} f{n-1}&fn &s{n-1} \end{matrix} \right] $$，即：

$$ \left[ \begin{matrix} f{n-2} & f{n-1} &s{n-2} \end{matrix} \right] \times A= \left[ \begin{matrix} f{n-1} &fn & s{n-1} \end{matrix} \right]

$$ 按照同样的方法即可构造转移矩阵：

$$ \left[ \begin{matrix} 0&1&0\1&1&1\0&0&1 \end{matrix} \right]

$$ 这样的矩阵规模是$$ (r+1) \times (r+1)$$ ,又$$\because f_1=f_2=s_1=1$$

$$ \therefore \left[ \begin{matrix} f1 &f_2 &s_1 \end{matrix} \right] \times \left[ \begin{matrix} 0&1&0\1&1&1\0&0&1 \end{matrix} \right] ^{n-1} = \left[ \begin{matrix} f_n &f{n+1} &s_n \end{matrix} \right]

$$

1. 递推式$$fn=f{n-1}+f{n-2}+n+1,f_1=f_2=1$$的前n项和为$$s_n=\sum{i=1} ^n f_i$$:

   [解法]：考虑$$1 \times 5$$的矩阵$$ \left[ \begin{matrix} f{n-2} &f{n-1} &s{n-2}&n&1 \end{matrix} \right] $$,构造： $$ \left[ \begin{matrix} f{n-2} & f{n-1} &s{n-2} & n&1 \end{matrix} \right] \times A= \left[ \begin{matrix} f{n-1} &f_n & s{n-1} &n+1 &1 \end{matrix} \right]
   $$ 也可以构造出转移矩阵： $$ \left[ \begin{matrix} 0&1&0&0&0\1&1&1&0&0\0&0&1&0&0\0&1&0&1&0\0&1&0&1&1 \end{matrix} \right] $$ 即： $$ \left[ \begin{matrix} f1 & f_2 &s_1 & 3& 1 \end{matrix} \right] \times \left[ \begin{matrix} 0&1&0&0&0\1&1&1&0&0\0&0&1&0&0\0&1&0&1&0\0&1&0&1&1 \end{matrix} \right] ^{n-1}= \left[ \begin{matrix} f_n &f{n+1}&s_n &n+2 &1 \end{matrix} \right] $$

   总结

   一般的，如果有$$ fn=p \cdot f{n-1} + q \cdot f{n-2} +r \cdot n + s$$,可以构造转移矩阵为： $$ \left[ \begin{matrix}0 &q&0&0&0\1&p&1&0&0\0&0&1&0&0\0&r&0&1&0\0&s&0&1&0 \end{matrix} \right] $$ 更一般的，对于$$f_n=\sum(a{n-i} \cdot f_{n-i})+Poly(n),(Poly(n)表示关于n的多项式)$$，其中$$0<i\leq c (c为常数)$$,依然可以利用构造矩阵解决此类问题。

   设$$Degree(Poly(n))=d$$,规定$$Poly(n)=0$$时，$$d=-1$$，此时对应于常系数线性齐次递推关系。

   例如：$$A0=A_1=1,A_n=x \cdot A{n-1}+y \cdot A{n-2} (n \ge 2)$$ ;给定三个值n,x,y，求：$$S_n=\sum {i=1} ^n A_i ^2$$.

   [解法]：考虑$$1 \times 4$$的矩阵X，使得有如下关系成立： $$ \left[ \begin{matrix} S{n-2} & A{n-1}^2 & A{n-2}^2 &A{n-1} \cdot A{n-2} \end{matrix} \right] \times X = \left[ \begin{matrix} S{n-1} &An^2 &A{n-1}^2 & An \cdot A{n-1} \end{matrix} \right] = \left[ \begin{matrix} S{n-2}+A{n-1}^2 & x^2 \cdot A{n-1}^2 + y^2 \cdot A{n-2}^2 + 2 \cdot x \cdot y \cdot A{n-1} \cdot A{n-2} & A{n-1}^2 & x \cdot A{n-1}^2 + y \cdot A{n-2} A{n-1} \end{matrix} \right] $$ 则构造出的X为： $$ \left[ \begin{matrix} 1&0&0&0\1&x^2&1&x\0&y^2&0&0\0&2xy&0&y \end{matrix} \right] $$ 所以： $$ \left[ \begin{matrix} S_0 &A_1^2 &A_0^2 &A_1A_0 \end{matrix} \right] \times X^n= \left[ \begin{matrix} S_n &A{n+1}^2 &An^2 & A{n+1}A_n \end{matrix} \right] $$ ​