Si $f(x)=x^2-x-1$ y $f^n(x)=f(f(\cdots f(x)\cdots))$, encontrar todo $x$ que $f^{3n}(x)$ converge.

Question

Vamos $f:\mathbb{R}\to\mathbb{R}$ ser el polinomio definido por $$f(x)=x^2-x-1$$ y vamos a $$g_0(x)=f(x),\quad g_1(x)=f(f(x)),\quad\ldots\quad g_n(x)=f(f(f(\cdots f(x)\cdots)))$$ El positivo de la raíz de $f(x)$ es el famoso golden ratio $$\varphi=\frac{1+\sqrt{5}}{2}.$$

Problema: Encontrar todo $x\in\mathbb{R}$ para que el límite de $$\lim_{n\to\infty}g_{3n}(x)$$ existe.

La respuesta parece ser no es en absoluto trivial. Basado en los cálculos numéricos, suponemos que el límite existe si y sólo si $$x\in[-\sqrt{2},1+\sqrt{2}]-\mathbb{N}.$$ Pero para algunos $x$, la convergencia es muy extraño. Por ejemplo, mira este dibujo de la secuencia de $\{g_{3n}(0.18)\}$ para $0\leq n\leq 200$:

EDIT: Como se ha señalado por Zach Effman, parece ser que hay una estructura fractal que emergen de este problema. Para visualizar mejor, miré en el acotamiento de la secuencia de $\{g_n(z)\}$ para $z\in\mathbb{C}$. Más precisamente, he hecho una cuadrícula de puntos $z\in\mathbb{C}$, de color negro, si $\{|g_n(z)|\}$ está limitada a $z$ y más rápidamente que $\{|g_n(z)|\}$ diverge a infinito el más blanco de los píxeles. Una espectacular estructura fractal que emerge: ¿Alguien reconoce este fractal? Es este un conocido fractal?

El centro de esta imagen revela una muy buena estructura:

Answer 1

Como señaló mercio, su función $f(x)=x^2-x-1$ tiene tres ciclos de $$2 \cos \left(\frac{\pi }{7}\right) \mapsto 2 \sin\left(\frac{\pi }{14}\right) \mapsto -2 \sin\left(\frac{3 \pi }{14}\right) \mapsto 2 \cos \left(\frac{\pi }{7}\right).$$ Dicho de otra manera, estos puntos son puntos fijos de $F(x)=f(f(f(x)))$. Deje que nos indican estos puntos por $x_F^1$, $x_F^2$ y $x_F^3$. El ciclo es neutral ya que $F'(x_F^i)=$ 1 por cada $i$.

Ahora, supongamos que $x_0>1+\sqrt{2}$. A continuación, \begin{align} f(x_0) &= x_0^2 - x_0 - 1 \\ &= \left(1+\sqrt{2}\right)+\left(x_0 - (\sqrt{2}+1)\right) \left(x_0+\sqrt{2}\right). \end{align} Como resultado, la órbita de $x_0$ diverge para $\infty$. Además, si $x_0<-\sqrt{2}$, entonces $x_1=f(x_0)>1+\sqrt{2}$, así que (de nuevo) de la órbita se desvía a $\infty$.

Por lo tanto, vamos a $I=[-\sqrt{2},1+\sqrt{2}]$. Ciertamente sabemos que cada inicial de la semilla fuera de la $I$ diverge para $\infty$. Resulta que casi todos los puntos dentro de $I$ converge a la fija neutral órbita. El excepcional conjunto de puntos forma un conjunto de Cantor $C$ en $I$ y la dinámica de $f$ son caóticos en $C$. No es particularmente fácil de ver esto, sin embargo, algunos bastante alta potencia (pero conocido) teoremas.

Para obtener un mejor agarre en esto, vamos a graficar la función, junto con la recta $y=x$.

Vemos muy claramente que la función de los mapas de $[-\sqrt{2},1+\sqrt{2}]$ en sí mismo y hay un par de puntos fijos que cruzar la línea $y=x$ con pendiente mayor que uno en valor absoluto, de modo que la voluntad de ser repulsivo. Desde entonces, tenemos una órbita de periodo 3, vamos a incluir una parcela de $F(x)=f(f(f(x)))$.

Tenga en cuenta que hay 3 puntos donde la línea $y=x$ es tangente a la gráfica de $F(x)$. Estos son exactamente los puntos en el neutro de la órbita de periodo 3. Cada uno de estos es la mano izquierda el extremo de un intervalo de puntos en los que convergen a un punto fijo bajo iteración de $F$. He resaltado una de esas intervalo que contiene $1/2$ en rojo. Además, la inversa de la imagen de este intervalo de menos de $F$, consta de 6 más los intervalos que se asignan en el rojo intervalo. Los inversos de estos ceder más puntos que convergen en el centro de punto fijo bajo iteración de $F$, etc. Se puede hacer lo mismo para los otros puntos fijos. El complemento de todas estas abierto intervalos que contienen los puntos de convergencia a uno de los puntos fijos es exactamente el conjunto de Cantor de los puntos que no convergen a cualquiera de los puntos fijos.

Como mercio y Sheldon ha indicado, el groovy imagen fractal es exactamente el conjunto de Julia de $z^2-z-1$. Para enfatizar la relación entre este hecho y mi respuesta, veamos el conjunto Julia junto con la red de intervalo desde mi última imagen.

Por lo tanto, los intervalos de abarcar a los componentes de la Julia con simplemente conectado interior. El punto amarillo es su germen inicial de $x_0=0.18$. Como no es la contenida en cualquiera de los componentes más grandes de la Julia, me gustaría esperar a saltar a su alrededor antes de que finalmente se establece a una órbita.

También valdría la pena señalar que el verdadero fractal de Julia es el límite de la región negra - por lo tanto, se ve algo así:

Y he aquí un zoom en el componente principal.

Por último, tenemos aquí un período $3$ en la órbita del mapa real de $f$ y hay un muy famoso artículo titulado "Período de tres implica el caos". Los teoremas de que el papel son exactamente lo que uno necesita para demostrar definitivamente que $f$ es caótica de un conjunto de Cantor $C$. Yo creo que $C$ tiene medida cero; sin duda es denso en ninguna parte. Que explica por qué es difícil encontrar el punto en $C$ por experimento. Un punto elegido al azar en $I$ en forma genérica y (creo) converge casi seguramente a la neutral período de 3 órbita.

Por otro lado, es (en principio) es factible encontrar órbitas de gran primer período. Aquí Mathemetica código que se encuentra en una órbita de periodo de 41.

Clear[f];
f[x_] := x^2 - x - 1;
f[n_Integer, x_?NumericQ] := Nest[f, x, n];
per41 = x /. FindRoot[f[41, x] == x, {x, 0.1},
  WorkingPrecision -> 300]

(* Out: 
  0.09997111618903433899874853864417001759319794189148766236421781597929\
  2721939448495289732175832121442601846472892582352497849991420790365107\
  4378578596438323899498328663812648206777989645187097865648459105422784\
  2754855914820032740936983665825718876082741645285990326028932997157116\
  60320676920709780319319
*)

Tenga en cuenta que la alta precisión es necesaria, ya que habrá puntos de arbitraryily cerca de otros períodos. Aquí está una comprobación de validez:

Nest[f, per41, 41] - per41
(* Out: 0.*10^-283 *)

Answer 2

Aquí están algunos de los resultados parciales. Os muestro a continuación que sólo hay tres los posibles límites (cuando la secuencia es no constante), y para cada límite que encontrar un intervalo tal que si el valor inicial es en ese intervalo, entonces converge a ese límite.

La aplicación de Zach Effman del método $g=f^3$ en vez de $f$, tenemos

$$ g(x)-x=(x^2-2x-1)(x^3-x^2-2x+1)^2 \etiqueta{1} $$

Las raíces de $x^2-2x-1$ son

$$ \alpha_1=1-\sqrt{2},\ \ \alpha_2=1+\sqrt{2} \etiqueta{2} $$

Mientras que las raíces de $x^3-x^2-2x+1$ son

$$ \beta_1 \aprox -1.246,\ \ \beta_2 \aprox 0.445, \ \ \beta_3 \aprox 1.801 \etiqueta{3} $$

Tenemos

$$ g'(\alpha_1)=25-22\sqrt{2}\approx -6.11, \ \ g'(\alpha_2)=25+22\sqrt{2}\approx 56.11 \etiqueta{4} $$

Por lo tanto los puntos fijos son repulsivos. Por otro lado,

$$ g'(\beta_1)=g'(\beta_2)=g'(\beta_3)=1 $$

(a causa de la identidad $g'(x)-1=(x^3-x^2-2x+1)(8x^4 - 20x^3 - 4x^2 + 18x + 2)$)

No hay una única $\gamma_1<\beta_1$ tales que $g(\gamma_1)=\beta_1$. Es fácil a ver entonces que el intervalo de $I_1=[\gamma_1,\beta_1]$ es estable por $g$, y si $x\in I_1$, a continuación, la secuencia converge a $\beta_1$.

Del mismo modo : no hay una única $\gamma_2\(\beta_2,\beta_3)$ tal que $g(\gamma_2)=\beta_2$ y, a continuación, el intervalo de $I_2=[\beta_2,\gamma_2]$ es estable por $g$, y si $x\in I_2$, a continuación, la secuencia converge a $\beta_2$, y hay un costo de $\gamma_3>\beta_3$ tal que el intervalo de $I_3=[\beta_3,\gamma_3]$ es estable por $g$, y si $x\in I_3$, a continuación, la secuencia converge a $\beta_3$.

Answer 3

Esta respuesta está inspirada en los comentarios con Mercio. Primer mapa de el problema a un equivalente de $z \mapsto z^2+c\;$ Mandelbrot problema. Y, a continuación, podemos utilizar todas las conocidas herramientas para analizar el conjunto de Mandelbrot para analizar el Op del problema. Por ejemplo, ver el Lobo de Jung mandelbrot enlace, que incluye un programa de Mandelbrot con el aterrizaje de ray.

$a$z \mapsto z^2-\frac{7}{4}$$

Esta es una conjugación del problema original con z=x-1/2, y $g(x)=f(x)-1/2$ Para mayor claridad, llame a la nueva función $g(z)=z^2-7/4$. Calculamos el polinomio raíces de $g^{o3}(z)-z=0$, que los factores en un producto de dos ecuaciones cúbicas idénticas, y una cuadrática. Aquí nos muestran la parabólica, 3-cíclico de atraer a los puntos fijos, que son las raíces de la ecuación cúbica, seguido por las raíces de la 1-cíclico de la ecuación cuadrática.

$$8z^3 + 4z^2 - 18z - 1=0\; \left(r_1= -1.7469796037; r_2=-0.054958132087; r_3= 1.3019377358\right)$$ $$4z^2 - 4z - 7\; z=\left(r_4= -0.914213562373, r_5=1.91421356237 \right)$$

Si repetimos $z \mapsto g(z)$ un número infinito de veces, cada punto que se mantiene acotada en el conjunto de Julia para $c=-7/4$. Los puntos que están completamente dentro de un bug eventualmente se llega a un 3-cíclico de atraer período 3-ciclismo hacia los tres parabólica fija los puntos mencionados anteriormente. De lo contrario, si hay un punto que escape a $\infty$ arbitrariamente cerca de su punto, el punto en el que escogió usted está en el límite de la Julia. Y luego tenemos que averiguar el ángulo de rotación para el aterrizaje de rayos que aterriza en su punto, tal vez usando el Bottcher función.

Pero la forma más sencilla para manejar los puntos exactamente en el conjunto Julia límite es de buscar valores de $g^{on}(z)$ para finito de valores de n. Si $g^{on}(z)=r_1,r_2,r_3, r_4, r_5$ para algún valor finito de n, entonces el 3-ciclo de converge, ya que una vez que caes en uno de estos cinco puntos, la iteración $g^{o3}(z)$ no cambiar el punto. Aparte de estos cinco casos, la función $g^{o3}(z)$ finalmente no se repita, ni va a atraer hacia un punto de repetición. El ciclo de tres parabólico atraer puntos son sólo atracción para los puntos de conexión de la región; en otras palabras, dentro de un conjunto Julia error, y no en la frontera.

También se puede utilizar el Bottcher función para poner la iteración $z \mapsto z^2$ en correspondencia con la iteración $z \mapsto z^2-7/4$, ya que tanto las funciones de repetir hasta el infinito. Habrá una analítica Bottcher asignación de la función $\infty$ a cero. Y, a continuación, se genera el Bottcher función $g(z)$

$$\beta\left(\frac{1}{g(1/z)}\right) = \beta(z)^2$$

El Bottcher función de los mapas de la unidad de círculo hasta el límite de la Julia, por $c=-7/4$. Así que si tenemos un punto en el límite de la Julia, entonces el punto corresponde a un número en particular en el Boettcher conjunto de la forma $$\exp^{2\pi i r}$$ Donde r es el ángulo de rotación del punto z. Estamos particularmente interesados en estos ángulos de rotación: $$r = \left( \frac{\pm 1}{7}, \frac{\pm 2}{7}, \frac{\pm 4}{7}, \frac{\pm 1}{3}, 1 \right)$$

Desde el aterrizaje de los rayos con estos tres ángulos de rotación se corresponden con los tres parabólica fija los puntos mencionados anteriormente. r=1 corresponde a la solución z=1.91421356237, y r=$\pm 1/3$ corresponde a -0.914213562373. Observe que la iteración $z \mapsto z^2$ será el doble del ángulo de rotación r. Y si empezamos con r=1/7, entonces la iteración $z^2-7/4$ irá a través de un 3-ciclo de iteración (1/7,2/7,4/7. Hay dos aterrizaje de rayos para cada uno de los parabólico cúspides; así (-1/7,-2/7,-4/7) es idéntico. Además, tenemos los ángulos de rotación de $r=(\pm 1/3, 1)$, que corresponden a las dos soluciones para el principal punto fijo.

Si nos fijamos en el número racional para el ángulo de rotación, $\frac{p}{q}$, por el punto z, entonces podemos decir cómo se va a repetir. En particular, si $p=7\cdot 2^n$ o $p=3\cdot2^n$ o $p=2^n$, entonces el punto es un pre-periódico punto, y tras el correspondiente número de iteraciones, $g^{o3}(n)$ se repita exactamente. Todos los otros ángulos de rotación sobre el de la iteración $z \mapsto z^2 - 7/4$ no ir a uno de estos cinco puntos.

Answer 4

No es una respuesta completa, pero esto es lo que puede determinar de inmediato:

Lo que usted describe es un iterada de la función. Si la secuencia de $f^n(x)$ converge, entonces debemos tener $f(L) = L$ para el punto límite. Esto le da $x^2-x-1=x$ con raíces $1\pm\sqrt{2}$. En un punto fijo, el valor absoluto de la derivada de una función, $|f'(x)|$ determina el comportamiento local de la iterada de la secuencia. Si el valor absoluto de la derivada es menor que uno, el punto fijo es un atractor y puntos de partida cercanos convergen a la misma. Para la función aquí, $f'(x) = 2x-1$ dar $|f'(1-\sqrt{2})| = 2\sqrt{2}-1 \aprox 1.8$ y $|f'(1+\sqrt{2}) = 1+2\sqrt{2} \approx 3.8$. Por desgracia, los dos son mayores que uno. Esto significa que los puntos fijos son repellors: a partir de los puntos arbitrariamente cercanos a ellos se alejan.

Todo lo que puedo decir, entonces, es que el iterated function definitivamente converge para puntos de partida de $x_0 = 1\pm \sqrt{2}$, porque en estos casos la secuencia es constante. En realidad, eso no es del todo cierto: cualquier secuencia que golpea los puntos se mantienen constantes. Así, se podría preguntar, ¿cuáles son los puntos de $x$ tal que $f(x) = 1 \pm \sqrt{2}$? Son de $1\pm \sqrt{2}$ (por supuesto), así como $\pm\sqrt{2}$. La repetición de este, estos son los puntos que obtengo:

Me imagino que hay algún tipo de estructura fractal aquí.

Answer 5

Yo sólo intento resultados computacionales como los de ahora.

Primero me di cuenta que uno de $x$ valor fuera del intervalo que le dio una secuencia convergente, que me llevan a numéricamente prueba a mí mismo. Aquí es que el valor de:

Deje que $\alpha$ ser la raíz de $x^3 - x^2 - 2x + 1$ cerca $-1.24698$. Entonces para todo $n$, $g_{3n}(\alpha) = \beta$, donde $\beta$ es la raíz de $x^3 - x^2 - 2x + 1$ cerca $1.80194$.

A partir de mis propias pruebas, suponemos que el límite existe si y sólo si

$$ x \in [-\sqrt{2}, \; 1+\sqrt{2}] - S, $$

donde $S$ es el conjunto de puntos que forman un ciclo, es decir,

$$ S = \{x \in \mathbb{R} \mediados de g_{3k}(x) = g_0(x) \text{ para algunos } k, \; g_3(x) \neq g_0(x)\}. $$

Los miembros de la $S$ que corresponden a $k = 2$ aproximadamente

$$ \{-1.118, -1.09847, -1, -0.962622, -0.677575, -0.601782, -0.496701, -0.367928, -0.30512, -0.256588, -0.0360765, 0, 0.110737, 0.136684, 0.863316, 0.889263, 1, 1.03608, 1.25659, 1.30512, 1.36793, 1.4967, 1.60178, 1.67758, 1.96262, 2, 2.09847, 2.118\}. $$

Mi metodología se fija de $x$, hacer una tabla de los primeros 2000 valores de $g_{3n}$, encontrar la potencia de la función de mejor ajuste, y asumir la secuencia converge si y sólo si el exponente de la equipada con la función es negativa.

---

Si tienes curiosidad, aquí está el código de Mathematica he utilizado:

f[x_] := x^2 - x - 1
g3n[n_, x_] := g3n[n, x] = f[f[f[g3n[n - 1, x]]]]
g3n[0, x_] := f[x]

SequenceTable[z_] := Table[
  If[# === Overflow[], Throw[False], #]&[g3n[n, z]], 
  {n, 0, 2000}
]

NegativeExponentQ[z_?NumericQ] := Catch@Quiet[
  Negative[b /. {
      FindFit[N@Differences@SequenceTable[z], a x^b, {a, b}, x]]
    }, 
  {General::ovfl, FindFit::sszero}
]

BinarySearch[l_, h_, {err_, dir_}] := Block[{lo = l, mid, hi = h, GoodResultQ},
  GoodResultQ = If[dir < 0, Not, Identity];
  mid = (lo + hi)/2;
  While[hi - lo > err,
    If[GoodResultQ[NegativeExponentQ[mid]],
      lo = mid,
      hi = mid
    ];
    mid = (lo + hi)/2;
  ];
  mid
]

Y aquí están los comandos que me encontré y sus resultados:

Monitor[
  BinarySearch[-2.1`20, 0.1`20, {10^-10., -1}],
  {lo, mid, hi}
]

-1.4142134775087470189

Monitor[
  BinarySearch[0.1`20, 2.5`20, {10^-10., 1}],
  {lo, mid, hi}
]

2.4142135623493231833