¿Qué condición debe cumplirse para que una función recursiva pueda transformarse en una multiplicación matricial? Educación te da un futuro mejor

Antes de llegar a la respuesta real, debemos analizar más de cerca el cálculo de dicha secuencia. Imagine que estamos escribiendo un programa de computadora que se ejecuta para siempre e imprime toda la secuencia. Esto se puede hacer fácilmente: solo usaremos la definición recursiva una y otra vez.

Ahora intentemos optimizar un poco el programa anterior. Lo que estamos tratando de optimizar es la cantidad de memoria que usa. El programa optimizado solo recordará las cosas que realmente necesita para generar los elementos futuros y olvidará todo lo demás.

Así es como se ve un programa tan optimizado para la secuencia de Fibonacci:

print(0) print(1) a, b = 0, 1 while True: a, b = b, a+b print(b)

Tenga en cuenta que en este ejemplo no es suficiente recordar el elemento anterior de la secuencia. La definición recursiva [matemáticas] (F_n = F_ {n-1} + F_ {n-2}) [/ matemáticas] necesita los dos elementos anteriores para calcular el siguiente, así que eso es precisamente lo que tenemos que almacenar. En nuestro caso, usamos las variables a, b para almacenarlas.

Esto nos lleva al tema que quería presentar aquí: el concepto de un estado.

Imagine que nuestro programa de impresión de secuencias ya lleva un tiempo funcionando y acaba de imprimir un elemento de la secuencia. Hagamos una pausa en el programa y veámoslo, más precisamente, en los valores que están almacenados actualmente en todas las variables utilizadas por el programa. Esto es lo que llamaremos el estado actual de la computación.

En otras palabras, el estado del cálculo es simplemente el contenido de la memoria de la computadora inmediatamente después de imprimir un elemento de la secuencia.

¿Y qué estamos haciendo durante el cálculo? En cada iteración, hacemos algunos cálculos que actualizan el estado. No solo estamos produciendo una secuencia de números, estamos produciendo una secuencia de estados. Y una vez que tengamos este entendimiento, estamos listos para responder la pregunta que se nos hace.

Para que podamos calcular los elementos de una secuencia definida recurrentemente usando la multiplicación de matrices, necesitamos las siguientes propiedades:

El estado debe consistir en un número constante de variables.
Por ejemplo, una recurrencia que usa todos los elementos anteriores para calcular el siguiente no puede transformarse directamente en la multiplicación de matrices. A veces es posible, pero debe reescribir la definición en una definición equivalente con esta propiedad.
En cada iteración debemos usar la misma secuencia de operaciones para calcular el nuevo estado del anterior.
Por ejemplo, una recurrencia donde los términos pares e impares de una secuencia se calculan usando diferentes fórmulas no se puede transformar directamente en la multiplicación de matrices, pero la modificación requerida es simple. Lo que es peor, las secuencias en las que la fórmula cambia en función de los términos anteriores están definitivamente fuera. Un ejemplo de tal secuencia es la secuencia de Collatz.
Cada variable en el nuevo estado debe ser una combinación lineal de las variables en el estado anterior.
Por ejemplo, la función factorial está fuera. ¡No podemos multiplicar ny (n-1)! calcular n! . Lo único que podemos representar mediante la multiplicación de matrices son las combinaciones lineales: al calcular el nuevo valor de una variable, puede tomar todas las variables antiguas, multiplicar cada una de ellas por una constante adecuada y sumar los resultados. Nada más está permitido.

(Nuevamente, esta parte puede ser un poco complicada. A veces, si escribe el programa con el estado más pequeño posible, la transformación del estado antiguo al nuevo no será lineal, pero puede hacerse lineal si se considera un estado más grande. Esto se muestra en un ejemplo a continuación).

Y eso es. Vale la pena señalar que el conjunto de requisitos mencionados anteriormente no es tan restrictivo como podría parecer a primera vista. A continuación hay algunos ejemplos de recurrencias que se pueden describir usando la multiplicación de matrices.

[matemáticas] a_n = 3a_ {n-3} – a_ {n-7} [/ matemáticas]
Sencillo. El estado contiene los últimos 7 elementos.
[matemáticas] b_n = b_ {n-1} + 2b_ {n-2} + 7 [/ matemáticas]
Un poco complicado Si hay constantes involucradas, la solución más simple es incluir una constante (generalmente el número 1) como parte del estado. Por lo tanto, en este caso el estado sería (a, b, 1) donde a, b son los dos valores anteriores. Si (a, b, 1) es el estado anterior, el estado nuevo será (b, 2 * a + 1 * b + 7 * 1, 1).
[matemáticas] c_n = 2c_ {n-1} – c_ {n-3} + 5n [/ matemáticas]
Un término lineal tampoco es un problema. En este caso, el estado contendría los tres valores anteriores, la constante 1 y la n actual. Al calcular el nuevo estado, necesitamos aumentar n a n + 1 (que es una combinación lineal de 1 yn), y necesitamos calcular el nuevo valor (que también es una combinación lineal de los valores en el estado anterior) .
[matemáticas] d_n = d_ {n-2} + 7n ^ 3 – 3 [/ matemáticas]
No podemos tener solo 1 y [matemáticas] n ^ 3 [/ matemáticas] en el estado, no sabríamos cómo actualizarlo: la transformación de [matemáticas] n ^ 3 [/ matemáticas] a [matemáticas] (n + 1) ^ 3 [/ math] no es lineal. Tampoco podemos tener solo 1 yn en el estado, la computación [matemática] n ^ 3 [/ matemática] desde n tampoco es lineal.
El truco es usar un estado más grande: (dos valores anteriores, 1, n , [matemática] n ^ 2 [/ matemática], [matemática] n ^ 3 [/ matemática]). Ahora todas las transformaciones necesarias son lineales: por ejemplo, [math] (n + 1) ^ 2 [/ math] se puede calcular como una combinación lineal de [math] n ^ 2 [/ math], n , y 1 con el coeficientes 1, 2 y 1.
[matemáticas] e_n = e_ {n-1} + e_ {n-3} + (-1) ^ n [/ matemáticas]
Esta recurrencia viola nuestro segundo requisito, pero podemos aplicar fácilmente nuestra técnica a la secuencia [math] e’_n = e_ {2n} [/ math].
[matemáticas] f_n = f_ {n-1} + 3f_ {n-2} + 2 ^ n [/ matemáticas]
[matemáticas] g_n = 3g_ {n-1} + \ sum_ {i \ lt n-1} g_i [/ matemáticas]
Un programa sencillo que genera esta secuencia no tendría un estado de tamaño constante, ya que necesitaría recordar todos los valores anteriores. Podemos arreglar eso escribiendo un programa más inteligente que solo almacene su suma .
[matemáticas] h_n = h_ {n-1} + i_ {n-2} + 7 [/ matemáticas]
[matemáticas] i_n = 2i_ {n-1} – h_ {n-2} + n [/ matemáticas]
¿Dos secuencias definidas cada una en términos de la otra? No es un problema en absoluto, siempre que el estado total tenga un tamaño constante, podemos calcular ambos a la vez.

PD: Si no está familiarizado con este tema, puede que se pregunte: ¿Por qué nos importa? ¿Es útil representar una secuencia recurrente usando la multiplicación de matrices? La respuesta es positiva. Lo principal que importa: la multiplicación de matrices es asociativa.

Supongamos que para nuestra secuencia tenemos una matriz A tal que old_state * A = new_state. Entonces, por ejemplo, podríamos calcular el estado en tres pasos desde el estado actual de la siguiente manera:
((estado * A ) * A ) * A

Sin embargo, gracias a la asociatividad que acabo de mencionar, podemos reescribir eso como:
estado * [matemáticas] A ^ 3 [/ matemáticas]

Y, en general, el estado después de n pasos se puede calcular a partir del estado inicial multiplicándolo por [matemáticas] A ^ n [/ matemáticas]. Y la enésima potencia de una matriz se puede calcular de manera eficiente (exponenciación por cuadratura), lo que nos permite un acceso eficiente al enésimo elemento, ¡sin tener que calcular todos los anteriores!

Además, las propiedades algebraicas de la matriz A nos pueden decir todo tipo de cosas buenas acerca de la recurrencia: por ejemplo, estimaciones simples de la tasa de crecimiento, o incluso fórmulas de forma cerrada como la Fórmula del número de Fibonacci de Binet.