Cómo resolver relaciones de recurrencia en Python

Te sugerimos que revises esta resolución en un ambiente controlado antes de pasarlo a producción, un saludo.

Solución:

Tienes razón, esto se puede resolver usando álgebra lineal. Lo que he hecho a continuación es una traducción codificada simple. Sus ecuaciones para p(0) a p(3) están codificados reorganizándolos de modo que el lado derecho sea =0. Para p(4) y p(5) que aparecen en las relaciones de recurrencia como casos base, existe una =1 al lado derecho.

• -p(0) + p(2)/2 = 0

• p(i-1)/2 - p(i) + p(i+2)/2 = 0 para i > 0 y i < x

• p(i) = 1 si yo >= x

Aquí está el programa codificado para n=4

import numpy
a=numpy.array([[-1,   0, 0.5,  0,   0,   0], # 0
               [0.5, -1,   0,0.5,   0,   0], # 1
               [0,  0.5,  -1,  0, 0.5,   0], # 2
               [0,    0, 0.5, -1,   0, 0.5], # 3
               [0,    0,   0,  0,   1,   0], # 4
               [0,    0,   0,  0,   0,   1], # 5
              ])
b=numpy.array([0,0,0,0,1,1])
# solve ax=b
x = numpy.linalg.solve(a, b)
print x

Editaraquí está el código que construye la matriz programáticamente, solo probado para n=4!

n = 4

# construct a
diag = [-1]*n + [1]*2
lowdiag = [0.5]*(n-1) + [0]*2
updiag = [0.5]*n
a=numpy.diag(diag) + numpy.diag(lowdiag, -1) + numpy.diag(updiag, 2)

# solve ax=b
b=numpy.array([0]*n + [1]*2)
x = numpy.linalg.solve(a, b)

print a
print x[:n]

Esto produce

[[-1.   0.   0.5  0.   0.   0. ]
 [ 0.5 -1.   0.   0.5  0.   0. ]
 [ 0.   0.5 -1.   0.   0.5  0. ]
 [ 0.   0.   0.5 -1.   0.   0.5]
 [ 0.   0.   0.   0.   1.   0. ]
 [ 0.   0.   0.   0.   0.   1. ]]
[ 0.41666667  0.66666667  0.83333333  0.91666667]

que coincide con la solución en su comentario bajo su pregunta.

El problema aquí es que terminas en una recursión infinita sin importar dónde comiences, porque la recursión no es explícita, sino que termina generando sistemas de ecuaciones lineales para resolver. Si este fuera un problema que tuvieras que resolver usando Python, usaría Python para calcular los coeficientes de este sistema de ecuaciones y usaría la regla de Cramer para resolverlo.

Editar: Específicamente, sus incógnitas son p(0), …, p(x-1). Un vector fila de coeficientes desde el principio es (1, 0, -1/2, 0, …, 0) (de p(0)-p(2)/2=0), y todos los demás son de la forma (…, -1/2, 1, 0, -1/2, …). Hay x-1 de estos (uno para cada uno de p(1), …, p(x-1)) por lo que el sistema tiene una solución única o ninguna. Intuitivamente, parece que siempre debería haber una solución única.

Las dos últimas ecuaciones serían únicas ya que presentarían p(x) y p(x+1), por lo que se omitirían esos términos; el vector columna para el lado derecho de la regla de Cramer sería entonces (0, 0, …, 0, 1/2, 1/2), creo.

Numpy tiene soporte de matriz.

Esta no es una respuesta a la pregunta publicada, pero esta página es el principal éxito de Google para “resolver la relación de recurrencia en Python”, así que escribiré una respuesta.

Si tiene una recurrencia lineal y desea encontrar la fórmula recursiva, puede usar Sympy’s find_linear_recurrence función. Por ejemplo, suponga que tiene la siguiente secuencia: 0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970. Luego, el siguiente código produce la relación de recurrencia:

import sympy
from sympy.abc import n
L = [0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970]
print(sympy.sequence(L, (n, 1, len(L))).find_linear_recurrence(len(L)))

La salida es:

[3, 1]

Entonces sabes que A(n) = 3*A(n-1) + A(n-2).

Te mostramos reseñas y puntuaciones

Eres capaz de añadir valor a nuestro contenido informacional asistiendo con tu veteranía en las anotaciones.

---

---

Utiliza Nuestro Buscador