Matrice Fibonacci

Introducere

Șirul lui Fibonacci este definit astfel:

$$F_n = \begin{cases} 1& \text{dacă } n = 1 \text{ sau } n = 2 ,\\ F_{n-1} + F_{n-2} & \text{dacă } n > 2. \end{cases}$$

Pentru a determina al n-termen a șirului putem folosi diverse metode. Acest articol prezintă un algoritm de complexitate $O(n)$ care determină al n-lea termen.

Prezentul articol prezintă un algoritm de complexitate logaritmică, bazat pe înmulțirea rapidă a matricelor.

Matrice Fibonacci

Considerăm următoarea matrice: $Q = \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right)$. Dacă extindem șirul lui Fibonacii cu încă un element, $F_0 = 0$, observăm că: $Q = \left( \begin{matrix} F_2& F_1\\ F_1& F_0\end{matrix} \right)$. Să calculăm $Q^2$ și $Q^3$:

$$\begin{align} Q^2 & = Q \times Q \\ & = \left( \begin{matrix} F_2& F_1\\ F_1& F_0\end{matrix} \right) \times \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right)\\ & = \left( \begin{matrix} F_2 \cdot 1 + F_1 \cdot 1& F_2 \cdot 1 + F_1 \cdot 0 \\ F_1 \cdot 1 + F_0 \cdot 1& F_1 \cdot 1 + F_0 \cdot 0 \end{matrix} \right) \\ & = \left( \begin{matrix} F_2 + F_1 & F_2 \\ F_1 + F_0 & F_1 \end{matrix} \right) \\ & = \left( \begin{matrix} F_3 & F_2 \\ F_2 & F_1 \end{matrix} \right) \\ \end{align}$$

Similar:

$$\begin{align} Q^3 & = Q^2 \times Q \\ & = \left( \begin{matrix} F_3 & F_2\\ F_2 & F_1\end{matrix} \right) \times \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right)\\ & = \left( \begin{matrix} F_3 \cdot 1 + F_2 \cdot 1& F_3 \cdot 1 + F_2 \cdot 0 \\ F_2 \cdot 1 + F_1 \cdot 1& F_2 \cdot 1 + F_1 \cdot 0 \end{matrix} \right) \\ & = \left( \begin{matrix} F_3 + F_2 & F_3 \\ F_2 + F_1 & F_2 \end{matrix} \right) \\ & = \left( \begin{matrix} F_4 & F_3 \\ F_3 & F_2 \end{matrix} \right) \\ \end{align}$$

Observăm că $Q^n = \left( \begin{matrix} F_{n+1}& F_n\\ F_n& F_{n-1}\end{matrix} \right)$, lucru ușor de demonstrat prin inducție matematică.

Concluzie: Dacă $Q = \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right)$, atunci $Q^n = \left( \begin{matrix} F_{n+1}& F_n\\ F_n& F_{n-1}\end{matrix} \right)$.

Algoritm

Pentru a determina $F_n$, considerăm matricea $Q = \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right)$, pe care o ridicăm la puterea n. Pentru a efectua repede calculele, folosim exponențierea rapidă.

Problema #Fibonacci2 cere determinarea celui de-al n-lea termen al șirului lui Fibonacii, modulo 666013. Succes!

Bibliografie

• http://mathworld.wolfram.com/FibonacciQ-Matrix.html