Hay una formula de forma cerrada para la secuencia recursiva: $x_n = x_{n-1} + \alpha\sqrt{x_{n-1}}$

Question

Vi este enlace para ver la forma cerrada de la fórmula para una secuencia recursiva (Cómo derivar una forma cerrada de un simple recursividad?)

Sin embargo, ¿qué pasa si mi fórmula es: $$x_n = x_{n-1} + \alpha\sqrt{x_{n-1}} \quad \text{ and } \quad x_0 = \beta \quad \text{ and }\quad\alpha,\beta> 0$$

Hay una solución de forma cerrada para determinar el valor de $x_n$ para un determinado $n$?

Bonus: Si hay una solución de forma cerrada, hay una relación inversa? Es decir, si uno se da un valor de $y$, se puede deducir el más cercano a $n$ tal que $x_n$ es el más cercano a $y$ en comparación con cualquier otro posible $x_n$ valor?

Yo no podía entender los mathemical fórmula para cualquiera de las dos preguntas. Ya estamos CS ingenieros, sabemos que se puede crear una tabla de búsqueda para el primer 1 millón valores de$n$, y que deben trabajar para nosotros. (Podría decirse que es una solución razonable, ya que tenemos que calcular el $x_n$ 100 millones de valores de $n$ (de modo que, obviamente, $n$ será el mismo miles de veces y así precomputing no es una mala idea.) Pero aún así, sería "limpiador" si hay una forma cerrada solución analítica a la anterior secuencia recursiva que podríamos usar/considerar.

Answer 1

La pregunta de la prima resulta ser más fáciles de resolver que el problema real. Nota el problema puede escribirse como

$$x_{n+1}-x_n=\alpha\sqrt{x_n}$$

Considere la posibilidad de una variación de este:

$$\frac{dy}{dt}=\underbrace{\lim_{h\to0}{y(t+h)-y(t)\over h}}_{\approx~y(t+1)-y(t)}=\alpha\sqrt{y(t)}$$

Esto se resuelve fácilmente utilizando el cálculo y da

$$y(t)=\left(\frac{\alpha t}2+\sqrt{y(0)}\right)^2$$

Por lo tanto, la solución a tu problema está dado aproximadamente por

$$x_n\approx\left(\frac{\alpha n}2+\sqrt\beta\right)^2$$

Tenga en cuenta que:

$$y(t+1)-y(t)=\alpha\left(\frac{\alpha t}2+\sqrt{y(0)}\right)+\frac{\alpha^2}4$$

$$\alpha\sqrt{y(t)}=\frac{\alpha^2t}2+\alpha\sqrt{y(0)}$$

Es decir,

$$y(t+1)-y(t)=\alpha\sqrt{y(t)}+\frac{\alpha^2}4$$

Por lo que la aproximación es bastante decente cerca.

Por lo tanto, la inversa de la $z_n$ está dado por

$$z_n\approx\frac2\alpha\left(\sqrt n-\sqrt\beta\right)$$

Answer 2

Algunas notas sobre el comportamiento asintótico de la secuencia de preguntas.

• Usted es iterar la función $f(x) = x + \alpha \sqrt{x}$. Para los positivos $\alpha$, obviamente, esto va a producir un crecimiento de la secuencia, y no es difícil ver que va a crecer hasta el infinito.
• Si definimos $g(x) = \sqrt{x^2 + \alpha x}$, se puede comprobar que $f(x^2) = g(x)^2$.
• La definición de $y_n = \sqrt{x_n}$, se puede ver que $y_n = g(y_{n-1})$.

Considere la posibilidad de la expansión (válido para un gran $x$)

$$g(x) = \sqrt{x^2 + \alpha x} = x \sqrt{1 + \frac{\alpha }{x}} = x \left( 1 + \frac{\alpha}{2x} - \frac{\alpha^2}{8x^2} + o(x^{-2})\right)$$ $$= x + \frac{\alpha}{2} - \frac{\alpha^2}{8x} + o(x^{-1})$$

Así, podemos inferir que, para un gran $n$

$$y_n \approx \frac{\alpha n}{2}$$

La alimentación de este de nuevo en la asintótica de expansión, se puede mostrar que:

$$y_n \approx \frac{\alpha}{4}(2n - \log n)$$

Se derivan de los términos adicionales en esta expansión es posible, pero no necesariamente esclarecedor.

Entonces, uno puede inferir que, para un gran $n$,

$$x_n \approx \frac{\alpha^2}{16}\left(2n - \log n\right)^2$$

Esto en realidad no toque la dependencia de la $\beta$, lo cual es más difícil de abordar por el estudio de asymptotics.

Answer 3

Aquí es una prueba de que $0\leq x_n \leq c (n+1)^2$$c = \max[\frac{\alpha^2}{4}, x_0]$, asumiendo $x_0>0$.

Prueba (inducción): Supongamos $0\leq x_n \leq c(n+1)^2$ es cierto para un número entero no negativo $n$ (se sostiene claramente por $n=0$). Podemos demostrar esto también se aplica a las $n+1$. Claramente $x_{n+1}\geq 0$. Entonces, tenemos $$\begin{align} x_{n+1} &= x_n + \alpha \sqrt{x_n} \\ &\leq c(n+1)^2 + \alpha c^{1/2}(n+1) \quad \mbox{[since it holds for %#%#%]}\\ &\leq (c^{1/2}(n+1) + \frac{\alpha}{2})^2 \\ &=(c^{1/2}n + c^{1/2} + \frac{\alpha}{2})^2 \\ &\overset{(a)}{\leq}(c^{1/2}n + 2c^{1/2})^2\\ &=c(n+2)^2 \end{align}$$ donde (a) sostiene que debido a $n$ (desde $c^{1/2} + \frac{\alpha}{2} \leq 2c^{1/2}$ fue elegido para asegurar $c$). $c \geq \frac{\alpha^2}{4}$

---

EDIT: Aquí está un enlace con un coeficiente de $\Box$, independientemente de $\alpha^2/4$ (a lo largo de las líneas de la discusión en los comentarios de abajo).

Reclamo: $x_0$ todos los $x_n \leq g(n+b)^2$,$n \in \{0, 1, 2, ...\}$$g=\alpha^2/4$.

Prueba (inducción): Supongamos el caso de $b = \frac{2\sqrt{x_0}}{\alpha}$ (de hecho es cierto para $n \in \{0, 1, 2...\}$). Vamos a comprobar para $n=0$. Tenemos: $$\begin{align} x_{n+1} &= x_n + \alpha \sqrt{x_n} \\ &\leq g(n+b)^2 + \alpha g^{1/2}(n+b) \\ &= g(n+b)^2 + 2g(n+b) \quad \mbox{[since %#%#%]}\\ &= g(n+1+b)^2 - g\\ &\leq g(n+1+b)^2 \end{align}$$ $n+1$

Answer 4

Aha! Así que esta es una respuesta a un comentario que @SimplyBeautifulArt hecho. Es posible resolver

$$y(t+1) - y(t) = \alpha \sqrt{y}$$

Para $t\in\mathbb{R}^+$, y podemos tener $y(0) = \beta$ cualquier $\beta \in \mathbb{R}^+$. Sólo pensé que sería bueno para el estado, tales problemas son resolubles. Lamentablemente es computacionalmente una pesadilla , pero es posible.

Preste mucha atención.

Empezar con la ecuación

$$g(\xi) = \xi + \alpha \sqrt{\xi}$$

El problema que yo tenía es que esta funcion no es holomorphic en un barrio de $0$, por lo que estaba recibiendo respuestas divergentes. Pero, si queremos invertir, que no conseguir uno.

La solución para $\xi$$g(\xi) = \xi + \alpha \sqrt{\xi}$, da

$$\xi = \frac{\alpha^2}{2} - \frac{\alpha\sqrt{\alpha^2+4g(\xi)}}{2} + g(\xi)$$

Deje $f(x) = \frac{\alpha^2}{2} - \frac{\alpha\sqrt{\alpha^2+4x}}{2} + x$, e $f(0) = 0$$f'(0) = 0$. Afortunadamente $f$ es holomorphic en un barrio de $0$ ahora tan larga como $\alpha > 0$. También se deduce que

$$f(g(x)) = x$$

Debido a esto nuestra función puede ser conjugado a $x^n$, determinar el $n$ es equivalente a determinar el orden de las cero de $f$ a cero. O que

$$f(x) = h^{-1}(h(x)^n)$$

para $|x| < \delta$ pequeña y un buen únicas $h$. Vamos $$f^{\circ t}(x) = h^{-1}(h(x)^{n^t})$$

tal que $f(f^{\circ t}(x)) = f^{\circ t+1}(x)$. Y, lo que es más importante,

$$g(f^{\circ t}(x)) = f^{\circ t-1}(x)$$ . Vamos

$$y(t) = f^{\circ -t}(x)$$ which is defined on $\mathbb{R}$ by analytic continuation for $0 < x < \delta$, y

$$g(y(t)) = y(t+1)$$

Aquí viene la magia

$$g(y(t)) = y(t) + \alpha \sqrt{y(t)} = y(t+1)$$

y

$$y(t+1) - y(t) = \Delta y = \alpha \sqrt{y}$$

Búsqueda de $\tilde{y}$ tal que $\tilde{y}(0) = \beta$ implica simplemente cambiando el valor de $t$. Tenga en cuenta que $y$ es analítica como bien y tiende a $0$ $t \to -\infty$ y tiende a $\infty$$t \to \infty$.

Eso es lo que estaba buscando!