Cómo resolver dos recurrencias dependientes entre sí

Question

Dejemos que

$F_n = a_1*F_{n-1} + b_1*F_{n-2} + c_1*G_{n-3}$

$G_n = a_2*G_{n-1} + b_2*G_{n-2} + c_2*F_{n-3}$

Se nos da $ a_1,b_1,c_1,a_2,b_2,c_2$ y $ F_0,F_1,F_2, G_0, G_1,G_2 $ . Tenemos que calcular cualquier $F_n$ y $G_n$ con un n dado.

El valor de n puede ser tan grande como 10^9. Así que tenemos que calcularlo con una complejidad de O(logn).

Answer 1

Si $V_n$ es el vector de columnas $(F_n,G_n)$ entonces las dos ecuaciones que definen la recurrencia pueden escribirse como una sola recurrencia "matricial":

$$V_n=\begin{bmatrix}a_1 & 0 \\ 0 & a_2 \end{bmatrix}V_{n-1}+\begin{bmatrix}b_1 & 0 \\ 0 & b_2 \end{bmatrix}V_{n-2}+\begin{bmatrix}0 & c_1 \\ c_2 & 0 \end{bmatrix}V_{n-3}\,.$$

Ahora intente proceder como en el caso unidimensional (por ejemplo, busque una solución para la recurrencia definitoria de los números de Fibonacci).

Answer 2

Al igual que en el caso de una sola ecuación, imagina que tienes una progresión geométrica con relación $r$ . Entonces tienes $$F_0r^3=a_1F_0r^2+b_1F_0r+c_1G_0 \\ G_0r^3=a_2G_0r^2+b_2G_0r+c_2F_0\\G_0=\frac {c_2}{r^3-a_2r^2-b_2r}F_0\\r^3=a_ir^2+b_1r+\frac {c_1c_2}{r^3-a_2r^2-b_2r}$$

Desgraciadamente, se trata de una ecuación de sexto grado, pero deberías ser capaz de encontrar las raíces (quizás numéricamente) y leer las asociadas $\frac FG$ para cada uno. Entonces tienes un $6 \times 6$ conjunto de ecuaciones simultáneas para feit el dado $F$ y $G$ 's

Answer 3

Dejemos que $F(s)=\sum\limits_{n\geqslant0}F_ns^n$ y $G(s)=\sum\limits_{n\geqslant0}G_ns^n$ entonces la primera recursión (presumiblemente válida para $n\geqslant3$ ) produce $$ F(s)=F_0+F_1s+F_2s^2+\sum_{n\geqslant3}(a_1F_{n-1}+b_1F_{n-2}+c_1G_{n-3})s^n, $$ es decir, $$ F(s)=F_0+F_1s+F_2s^2+a_1s(F(s)-F_0-F_1s)+b_1s^2(F(s)-F_0)+c_1s^3G(s), $$ o, $$ (1-a_1s-b_1s^2)F(s)-c_1s^3G(s)=P_1(s), $$ para algún polinomio $P_1(s)$ de grado como máximo $2$ . Igualmente, $$ -c_2s^3F(s)+(1-a_2s-b_2s^2)G(s)=P_2(s), $$ para algún polinomio $P_2(s)$ de grado como máximo $2$ . Se trata de un sistema lineal de Cramér en $(F(s),G(s))$ por lo que $F(s)$ y $G(s)$ son relaciones de $2\times2$ determinantes. El denominador $D(s)$ es el mismo para $F(s)$ y $G(s)$ y es $$ D(s)=(1-a_1s-b_1s^2)(1-a_2s-b_2s^2)-c_1c_2s^6. $$ La raíz positiva más pequeña $r$ de $D(s)$ indica el crecimiento de $F_n$ y $G_n$ en el sentido de que $r^nF_n$ y $r^nG_n$ convergen a límites finitos, en general no nulos.