Cómo convertir esta ecuación en forma de matriz

Question

$$F(x)=aF(x-k+1)+bF(x-k+2)+cF(x-k+4)$$

donde $F(x)=1$ si $x<k$ .

$a,b,c,k$ son conocidos (y positivos) y $x$ es elegido.

Quiero resolver esta recurrencia utilizando una matriz, pero no sé cómo configurarla correctamente.

Answer 1

Bien, utilizaré una notación diferente a la tuya (porque estoy más acostumbrado). Pondré $x_n = F(n)$ por lo que su ecuación se convierte en $$x_n = a x_{n-k+1} + b x_{n-k+2} + c x_{n-k+4}.$$

Ahora, pon $$\mathbf x_n = \begin{pmatrix} x_n \\ x_{n-1} \\ \vdots \\ x_{n-k+2} \end{pmatrix}$$ y dada su ecuación, tenemos: $$\mathbf x_n = \underbrace{ \begin{pmatrix} 0 & 0 & 0 & \cdots & c & b & 0 & a \\ 1 & 0 & 0 & \cdots \\ 0 & 1 & 0 & \cdots \\ 0 & 0 & 1 & \cdots \\ 0 & 0 & 0 & \ddots \\ 0 & 0 & 0 & \cdots & &\cdots & 1 & 0 \end{pmatrix} }_{=C} \mathbf x_{n-1} $$

Ahora, su condición $F(n) = 1$ si $n < k$ , se convierte en $a_1 = a_2 = \cdots = a_{k-1} = 1$ por lo que nuestra ecuación de partida es $\mathbf x_k = C\mathbf{1}$ , donde $\mathbf{1}$ es un vector de sólo unos.

Ahora podemos escribir: $$ \mathbf x_n = C\mathbf x_{n-1} = \dots = C^{n-k}\mathbf x_k = C^{n-k+1} \mathbf{1} $$

Ahora el proceso general puede ser encontrar una eigendecomposición de $C$ , es decir, los vectores propios $\mathbf v_i$ con valores propios $\lambda_i$ , escriba $\mathbf 1$ como una combinación lineal de los vectores propios: $$\mathbf 1 = \sum_i c_i \mathbf v_i$$ y entonces se puede calcular $$\mathbf x_n = C^{n-k+1} \mathbf 1 = C^{n-k+1} \left( \sum_i c_i \mathbf v_i \right) = \sum_i \lambda_i^{n-k+1} c_i \mathbf v_i$$ con bastante facilidad.