矩阵加速 fibo

$$ F(x) = \begin{equation} \begin{cases} 1 \qquad \qquad \qquad \qquad \qquad x \leq 2\\ F(x - 1) + F(x - 2) \quad \; \, \, x > 2 \end{cases} \end{equation} $$

$$ { \begin{bmatrix} F(x - 1)\\ F(x - 2) \end{bmatrix} } \rightarrow { \begin{bmatrix} F(x)\\ F(x - 1) \end{bmatrix} } $$

$$ \begin{bmatrix} F(x)\\ F(x - 1) \end{bmatrix} = { \begin{bmatrix} F(x - 1) + F(x - 2)\\ F(x - 1) \end{bmatrix} } \leftarrow { \begin{bmatrix} F(x - 1)\\ F(x - 2) \end{bmatrix} } $$

$$ \begin{bmatrix} F(x - 1) + F(x - 2)\\ F(x - 1) \end{bmatrix} = \begin{bmatrix} F(x - 1) \times 1 + F(x - 2) \times 1 \\ F(x - 1) \times 1 + F(x - 2) \times 0 \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} F(x - 1)\\ F(x - 2) \end{bmatrix} $$

$$ \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} F(x - 1)\\ F(x - 2) \end{bmatrix} = \begin{bmatrix} F(x)\\ F(x - 1) \end{bmatrix} $$

$$ ( \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} ) \times \begin{bmatrix} F(x - 1)\\ F(x - 2) \end{bmatrix} = \begin{bmatrix} F(x + 1)\\ F(x) \end{bmatrix} $$

$$ \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} ^ 2 \times \begin{bmatrix} F(x - 1)\\ F(x - 2) \end{bmatrix} = \begin{bmatrix} F(x + 1)\\ F(x) \end{bmatrix} $$

$$ \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} 1 = F(2)\\ 1 = F(1) \end{bmatrix} = \begin{bmatrix} 2 = F(3)\\ 1 = F(2) \end{bmatrix} $$

$$ \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} ^ k \times \begin{bmatrix} 1 = F(2)\\ 1 = F(1) \end{bmatrix} = \begin{bmatrix} 2 = F(k + 2)\\ 1 = F(k + 1) \end{bmatrix} $$

$$ \therefore \begin{bmatrix} F(n)\\ F(n - 1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^ {n - 2} \times \begin{bmatrix} 1 \\ 1 \end{bmatrix} $$