Optimización de parámetros para recursiva de la secuencia de Cauchy

Question

Tengo el siguiente secuencia recursiva estoy analizando:

$$V_0 = 50, V_1 = (1-10k)V_0,$$

$$V_{n+1} = (1-10k)V_n - 5kV_{n-1}$$

where $k > 0$ is a parameter that I'm investigating by running simulations in R.

(This is from the "docking problem" in Meerschaert's "Mathematical Modeling").

$\langle V \rangle$ isn't Cauchy for all $k$. The sequence seems to diverge if $k > 0.18$ or so.

My analysis is to examine how fast the sequence converges as $k$ varies. I did this by simulating the sequence and picking the first $n$ for which $|V_n| < 0.1$

Here's a plot of said $n$ as a function of $k$. The horizontal axis are various $k$'s, and the vertical axis is the first $n$ for which $|V_n| < 0.1$ with that $k$ as the parameter.

My question is: What is this function? Why does it behave the way it does?

How do I find local minima of this function other than by simulation?

And what is the exact $k$ at which the sequence $\langle V \rangle$, deja de ser de Cauchy?

Answer 1

¿Te acuerdas de: Dado $${x^2} + p \cdot x + q = 0$$ y $$D = {p^2} - 4q$$ tenemos las raíces $$x = \left\{ {\begin{array}{*{20}{c}} {\frac{{ - p - \sqrt D }}{2}} \\ {\frac{{ - p + \sqrt D }}{2}} \end{array}} \right.$$

Como una aplicación, consideramos Fibbonacci-números: $$\begin{gathered} {f_0} = 1,{f_1} = 1 \hfill \\ {f_n} = {f_{n - 1}} + {f_{n - 2}} \hfill \\ \end{reunieron} $$ y $${f_n} = {f_{n - 1}} + {f_{n - 2}} \Leftrightarrow {f_n} - {f_{n - 1}} - {f_{n - 2}} = 0$$ Construimos qudratic $${x^2} = x + 1 \Leftrightarrow {x^2} - x - 1 = 0$$ con $$p = - 1,q = - 1,D = {p^2} - 4 \cdot q = 1 + 4 = 5$$ y obtener raíces $$x = \left\{ {\begin{array}{*{20}{c}} {\frac{{1 - \sqrt D }}{2}} \\ {\frac{{1 + \sqrt D }}{2}} \end{array}} \right.$$ Con estas raíces, podemos escribir: $${f_n} = \frac{1}{{\sqrt D }} \cdot \left( {{{\left( {\frac{{1 + \sqrt D }}{2}} \right)}^{n + 1}} - {{\left( {\frac{{1 - \sqrt D }}{2}} \right)}^{n + 1}}} \right) = \frac{1}{{\sqrt 5 }} \cdot \left( {{{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)}^{n + 1}} - {{\left( {\frac{{1 - \sqrt 5 }}{2}} \right)}^{n + 1}}} \right)$$ Hemos resuelto las reccurence!

Ahora vamos a aplicar esto a su problema. Los pasos son exactamente los mismos. Dado: $$\begin{gathered} A(k) = 1 - 10 \cdot k,{V_0} = P \hfill \\ {V_1}(k) = A(k) \cdot {V_0} \hfill \\ {V_n}(k) = A(k) \cdot {V_{n - 1}}(k) - 5 \cdot k \cdot {V_{n - 2}}(k) \hfill \\ \end{reunieron} $$ Entonces $${V_n}(k) - A(k) \cdot {V_{n - 1}}(k) + 5 \cdot k \cdot {V_{n - 2}}(k) = 0$$ con cuadrática $${x^2} - A(k) \cdot x + 5 \cdot k = 0$$ Aquí $$p = - A(k),q = 5 \cdot k,D(k) = A{(k)^2} - 20 \cdot k$$ Con las raíces $$x = \left\{ {\begin{array}{*{20}{c}} {\frac{{A(k) - \sqrt D }}{2}} \\ {\frac{{A(k) + \sqrt D }}{2}} \end{array}} \right.$$ Ahora nos fijamos, como antes: $${p_k}(n) = \frac{1}{{\sqrt {D(k)} }}\left( {{{\left( {\frac{{A(k) + \sqrt {D(k)} }}{2}} \right)}^{n + 1}} - {{\left( {\frac{{A(k) - \sqrt {D(k)} }}{2}} \right)}^{n + 1}}} \right)$$ y tenemos: $${V_n}(k) = {p_k}(n) \cdot {V_0}$$ Hemos resuelto las reccurence. Hasta ahora. Qué con esto? Perfecta respuesta es dada por @Alex Ravsky!

Answer 2

Parece que el siguiente.

A pesar de sus gráficos sugieren detrministic comportamiento caótico, como la secuencia generada por la logística del mapa, pero este no es el caso, porque es un habitual de segundo orden de recurrencia, por lo que sus gráficos muestran un efecto del enfoque computacional.

Está claro que la secuencia de $\{V_n\}$ está determinada únicamente por el recurrente fórmulas y las condiciones iniciales. Considere el polinomio característico $$p(\lambda)=\lambda^2+(10k-1)\lambda+5k$$ de la recurrencia. Tiene discriminante

$D=100k^2-40k+1$ (con raíces $k=\frac{2\pm \sqrt{3}}{10}$)

y las raíces

$\lambda_1=\frac{1-10k+\sqrt{D}}2$ $\lambda_2=\frac{1-10k-\sqrt{D}}2$ .

Si $D\ne 0$$\lambda_1\ne\lambda_2$, por lo que debemos buscar la fórmula para una secuencia $\{V_n\}$ en forma

$$V_n=C_1\lambda_1^n+ C_2\lambda_2^n,$$

donde $C_i$ (complejo) constantes. El conjunto de las soluciones de la recurrencia es una de dos dimensiones del espacio lineal, con la base que consta de las progresiones geométricas $\{\lambda_1^n\}$, $\{\lambda_2^n\}$. Así que la búsqueda de la secuencia de $\{V_n\}$ como una combinación lineal de la base de las secuencias con el fin de satisfacer las condiciones iniciales:

$\casos{V_0=C_1\lambda_1^0+ C_2\lambda_2^0=C_1+C_2\\ (1-10k)V_0=V_1=C_1\lambda_1^1+ C_2\lambda_2^1= C_1\lambda_1+ C_2\lambda_2}$.

Este sistema tiene una única solución a $C_1=\frac{V_0\lambda_1}{\sqrt{D}}$$C_2=\frac{-V_0\lambda_2}{\sqrt{D}}$. Así

$$V_n=V_0\frac{\lambda_1^{n+1}-\lambda_2^{n+1}}{\sqrt{D}}.$$

Ahora vamos a examinar la convergencia de la secuencia de $\{V_n\}$, e incluso caída de la restricción $k>0$.

Si $D>0$ (que es el si $k<\frac{2-\sqrt{3}}{10}\approx 0.03$ o $k>\frac{2+\sqrt{3}}{10}\approx 0.37$), a continuación, tanto las raíces de $\lambda_i$ son reales y diferentes. Así que la secuencia $\{V_n\}$ converge iff

tanto en $-1<\lambda_1, \lambda_2\le 1$ fib

$-2<1-10k-\sqrt{D}<1-10k+\sqrt{D}\le 2$ fib

$\sqrt{D}<1+10k$ $\sqrt{D}\le 3-10k$ fib

$100k^2-40k+1<(1+10k)^2$ $k<0.3$ $100k^2-40k+1\le (3-10k)^2$ fib

$k>0$ $k<0.3$ $k\le 0.4$ fib

$0<k<0.3$.

Desde $0.3<\frac{2+\sqrt{3}}{10}\approx 0.37$, la secuencia de $\{V_n\}$ converge iff $0<k<\frac{2-\sqrt{3}}{10}\approx 0.03$.

Si $D<0$ (que es el si $0.03\approx\frac{2-\sqrt{3}}{10}<k<\frac{2+\sqrt{3}}{10}\approx 0.37$), a continuación, tanto las raíces de $\lambda_i$ no son reales. Desde $\lambda_2=\overline{\lambda_1}$, luego

$$V_n=C\operatorname {Im} \lambda_1^{n+1},$$ where $C$ is a constant which does not depend on $n$. So the sequence $\{V_n\}$ diverges if $|\lambda_1|\ge 1$ and converges if $|\lambda_1|<1$. Since $|\lambda_1|=|\lambda_2|$ and $|\lambda_1\lambda_2|=|5k|=5k$, the sequence $\{V_n\}$ diverges iff $0.2=\frac 15 \le k<\frac{2+ \sqrt{13}}{20}\approx 0.28$ and converges iff $0.03\approx\frac{2-\sqrt{3}}{10}<k<\frac 15=0.2$.

Si $D=0$ (que es el si $k=\frac{2\pm \sqrt{3}}{10}$), a continuación,$\lambda_1=\lambda_2=\lambda=\frac{1-10k}2\ne 0$, por lo que debemos buscar la fórmula para una secuencia $\{V_n\}$ en forma

$$V_n=C_1\lambda^n+ C_2n\lambda^n,$$

donde $C_i$ (complejo) constantes. El conjunto de las soluciones de la recurrencia es una de dos dimensiones del espacio lineal, con la base que consta de las secuencias $\{\lambda^n\}$, $\{n\lambda^n\}$. Así que la búsqueda de la secuencia de $\{V_n\}$ como una combinación lineal de la base de las secuencias con el fin de satisfacer las condiciones iniciales:

$\casos{V_0=C_1\lambda^0+ C_2\cdot 0\cdot \lambda^0=C_1\\ (1-10k)V_0=V_1=C_1\lambda^1+ C_2\cdot 1\cdot \lambda^1= C_1\lambda+ C_2\lambda}$.

Este sistema tiene una única solución a $C_1=C_2=\frac{V_0}2$. Así

$$V_n= \frac{V_0(1+n)\lambda^n}2.$$

Igualdad de $D=0$ implica $\lambda=\frac{-1\mp\sqrt{3}}2$. Si $\lambda=\frac{-1+\sqrt{3}}2$, $|\lambda|<1$ y la secuencia de $\{V_n\}$ converge a cero. Si $\lambda=\frac{-1-\sqrt{3}}2$, $|\lambda|>1$ y la secuencia de $\{V_n\}$ diverge.

Respuesta Final: La secuencia de $\{V_n\}$ converge iff $0<k<\frac 15=0.2$

Añadido. Sí, puedo investigar esta situación de forma más precisa. Por tanto, parece que el siguiente.

Recuerdo que si la secuencia polinomio tiene dos diferentes (real) las raíces de $\lambda_1$ $\lambda_2$ que es el si $D>0$ que es el si $k<\frac{2-\sqrt{3}}{10}\approx 0.03$ o $k>\frac{2+\sqrt{3}}{10}\approx 0.37$

$$V_n=V_0\frac{\lambda_1^{n+1}-\lambda_2^{n+1}}{\sqrt{D}}.$$

Como hemos mostrado, la secuencia de $\{V_n\}$ converge iff $0<k<\frac{2-\sqrt{3}}{10}\approx 0.03$. En el segundo caso tenemos las siguientes.

Desde $0<\lambda_1\lambda_2=5k<1$, tenemos que tanto las raíces tienen el mismo signo. Así

$\lambda=\lambda_1=\frac{1-10k+\sqrt{D}}2$ $\mu=\lambda_2\frac{1-10k-\sqrt{D}}2$ . Desde $10k<1$,$1>\lambda>\mu>0$.

Por lo $\{V_n\}$ es una secuencia de números positivos y es una diferencia de dos progresiones geométricas con coeficientes positivos. La evidencia empírica sugiere que la secuencia de $\{V_n\}$ monótonamente y disminuye rápidamente. Véase, por ejemplo, el siguiente gráfico para $k=0.01$:

Para demostrar la monotonía de la secuencia de $\{V_n\}$ podemos diferenciar $V_n$ con respecto al $n$:

$$\frac{\partial{V}}{\partial{n}}=\frac{V_0}{\sqrt{D}}\left(\lambda^n\ln\lambda-\mu^n\ln\mu\right).$$

Por lo $\frac{\partial{V}}{\partial{n}}<0$ fib $\lambda^n\ln\lambda<\mu^n\ln\mu$ fib $\left(\frac{\lambda}{\mu}\right)^n\log_\mu \lambda<0$, lo cual es cierto, porque $1>\lambda>\mu>0$.