¿Por qué de problemas no-lineales de relaciones de recurrencia "desesperada"?

Question

Me llegó a través de un no-lineal de la relación de recurrencia quiero resolver, y la mayoría de los lugares que buscar ayuda va a decir cosas como "es imposible resolver no-lineal de las relaciones de recurrencia en general." Hay un riguroso razón o un ejemplo ilustrativo de por qué este es el caso? Me parece que la respuesta correcta sería "simplemente no sabemos cómo resolverlos", o "no hay solución con el uso de funciones elementales," pero podría ser una solución en la forma de, digamos, un infinito producto o una serie o algo.

Sólo para finalizar, la recurrencia de la relación que estoy mirando es (un poco más que los no-lineal, y esta es una versión simplificada):

$p_n = a_n b_n\\ a_n = a_{n-1} + c \\ b_n = b_{n-1} + d$

Y $a_0 > 0, b_0 > 0, c,d$ fijo constantes

Answer 1

Aunque es posible resolver seleccionada no-lineal de las relaciones de recurrencia si le sucede a ser la suerte, en general todo tipo de peculiar y difícil de caracterizar cosas pueden suceder.

Un ejemplo se encuentra en los sistemas caóticos. Estos son extremadamente sensibles a las condiciones iniciales, lo que significa que el comportamiento después de muchas iteraciones es muy sensible a pequeñas variaciones en las condiciones iniciales, y por lo tanto, cualquier fórmula que expresan la relación va a crecer increíblemente grande. Estas ecuaciones en recurrencia puede ser increíblemente simple, con x_n+1 = 4x_n(1-x_n) con x₀ entre 0 y 1 como uno de los clásicos ejemplos simples (es decir, simplemente cuadrática).

Didier ya ha dado el conjunto de Mandelbrot ejemplo-del mismo modo simple para expresar, y del mismo modo difícil de caracterizar analíticamente (por ejemplo, por dar un número finito de forma cerrada de la solución).

Por último, tenga en cuenta que para resolver todos los no-lineal de la recurrencia de la relación implicaría que se podría resolver la suspensión problema, ya que uno podría codificar un programa como estados iniciales y el funcionamiento de la máquina de Turing como las relaciones de recurrencia. Así que sin duda es desesperada en el caso más general. (Que muy restringido casos admiten soluciones, es todavía una pregunta interesante.)

Answer 2

Un bien conocido ejemplo es el conjunto de Mandelbrot. Considere la posibilidad de una secuencia $(a_n)$ definido por $a_0=0$$a_{n+1}=a_n^2+c$, para algún parámetro de $c$, y pedir a la pregunta aparentemente inocente:

Para que los valores de $c$ es la secuencia de las $(a_n)$ delimitada?

Se puede observar que la recursividad es simplemente cuadrática en lugar de affine (el grado de $a_n$ en la fórmula de la $a_{n+1}$ es de 2 en lugar de 1). La respuesta, o más bien, algunos elementos de la respuesta, se han abierto todo un campo matemático.

Answer 3

Pero polinomio de recurrencia pueden ser asignados a los lineales de las recurrencias. Por ejemplo, para $a_{n+1} = a_n^2 + c$ deje $b_{m,n} =a_n^m$. Entonces por la fórmula binominal:

$$b_{m,n} = (a_{n-1}^2+c)^m = \sum_{j = 0}^mc^{m-j}{m \elegir j}a_{n-1}^{2j} = \sum_{j = 0}^mc^{m-j}{m\elegir j}b_{2j,n-1}$$

y aunque es un dos variables lineales recurrencia puede utilizar muchos de los mismos tipos de estrategias para resolver como si fuera una variable (de hecho, para cualquier número de variables que puede utilizar los mismos métodos, como si se tratara de una variable). Así que ¿cuál es el problema?