Convirtiendo ecuaciones recursivas en matrices

Question

¿Cómo convertimos ecuaciones recursivas en formas de matriz? Por ejemplo, considera esta ecuación recursiva (Serie de Fibonacci): $$F_n = F_{n-1} + F_{n-2}$$

Y resulta que lo siguiente es cierto

$$\begin{bmatrix}1&1\\1&0\end{bmatrix}^n = \begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}$$

¿Alguien puede por favor decirme cómo derivamos una matriz base para ecuaciones recursivas? ¿Cómo podemos determinar el orden de la matriz para la ecuación recursiva, así como los elementos de la matriz?

Answer 1

Si $F_n$ es una función lineal de $F_{n-1}, F_{n-2},\dots, F_{n-k}$ con coeficientes constantes, entonces necesitarás una matriz de $k \times k$ para representar la recurrencia. Intuitivamente, esto se debe a que el "estado" de la recurrencia son los $k$ valores anteriores: necesitas exactamente esos valores para calcular el siguiente.

En cuanto a encontrar la matriz, necesitas encontrar $A$ tal que (en el caso de una recurrencia de segundo orden):

$$\begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = A \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix}.$$

La segunda fila de $A$ es clara: $F_{n-1} = F_{n-1}$, así que la segunda fila debería ser $\begin{bmatrix} 1 & 0 \end{bmatrix}$. La recurrencia en sí misma vive en la primera fila; en el caso de Fibonacci tenemos $F_n = F_{n-1} + F_{n-2}$, entonces la primera fila es $\begin{bmatrix} 1 & 1 \end{bmatrix}.$

Answer 2

Imagina que tienes una relación recursiva, por ejemplo $a_n=\alpha a_{n-1}+ \beta a_{n-2}$. Intentas encontrar una matriz $A$ tal que:

$$A \begin{bmatrix}a_{n} \\ a_{n-1}\end{bmatrix}=\begin{bmatrix}a_{n+1} \\ a_{n}\end{bmatrix}$$

Será una matriz de $2 \times 2$. Sea $A=\begin{bmatrix}a && b \\ c && d\end{bmatrix}$, entonces:

$$A\begin{bmatrix}a_{n} \\ a_{n-1}\end{bmatrix}=\begin{bmatrix}a \cdot a_{n}+b \cdot a_{n-1} \\ c \cdot a_{n}+d \cdot a_{n-1}\end{bmatrix}$$

Quieres tener:

$$a \cdot a_{n}+b \cdot a_{n-1}=a_{n+1}=\alpha a_{n}+ \beta a_{n-1}$$

$$c \cdot a_{n}+d \cdot a_{n-1}=a_{n}$$

Si resuelves este sistema de ecuaciones obtienes:

$$A=\begin{bmatrix}\alpha && \beta \\ 1 && 0\end{bmatrix}$$

Puedes utilizar este método para otras relaciones recursivas, por ejemplo $a_n=\alpha a_{n-1}+ \beta a_{n-2}+\gamma a_{n-3}$ o cualquier número de componentes.

Answer 3

Simplemente evalúa el producto de matrices y verás que $$ \begin{align} \begin{pmatrix} F_{k+2}& F_{k+1}\\F_{k+1}& F_{k} \end{pmatrix} &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{k+1}& F_{k} \\ F_{k} &F_{k-1} \end{pmatrix} \end{align} . $$ desde Número de Fibonacci/Forma de matriz...

Un enfoque similar funciona para polinomios de Chebychev $T_{n+1}(t) = 2xT_n(t) - T_{n-1}(t)$:

$$ \pmatrix{T_{n+1}(t)\cr T_n(t)} = \pmatrix{2t & -1\cr 1 & 0\cr}^n \pmatrix{t\cr 1\cr} $$

Answer 4

Una forma de probar esto es mediante una inducción matemática.

Supongo que estás usando la convención de que $F_0=0$, $F_1=1$ y $F_2=1.

Entonces, $\begin{bmatrix}1&1\\1&0\end{bmatrix}=\begin{bmatrix}F_2&F_1\\F_1&F_0\end{bmatrix}.

Supongamos que $\begin{bmatrix}1&1\\1&0\end{bmatrix}^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}.

Luego, utilizando $F_{n+2}=F_{n+1}+F_n$, puedes ver que

$\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n+1}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}=\begin{bmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_n\end{bmatrix>$

y esto completa la prueba.