¿Qué se esconde debajo de la complejidad en este trabajo el algoritmo?

Question

Así que, yo soy un científico de la computación (al menos, yo estoy trabajando para convertirse en uno..) y yo les hice una pregunta aquí sobre algunas de las matemáticas detrás del conjunto de Mandelbrot. Una respuesta que he recibido me señaló a este periódico. Pero como ya he dicho, yo soy un científico de la computación. Hay una gran cantidad de terminología que no entiendo en ese papel.

Mi pregunta es doble:

• ¿Cuál es el algoritmo descrito en este documento?
• ¿Qué debo hacer cuando se enfrenta con estos tipos de respuestas?

Answer 1

El papel de las preocupaciones de las dinámicas que surgen cuando repetimos un complejo polinomio que tiene una parabólica de punto fijo. La dinámica de cerca de una parabólica de punto fijo son muy lentos y, como resultado, el conjunto de Julia es difícil de calcular. El documento muestra que, a pesar de los desafíos, es posible calcular la imagen de un conjunto en una cantidad razonable de tiempo - concretamente, en el polinomio de tiempo.

Una parabólica de punto fijo es un punto fijo $z_0$ ( $f(z_0)=z_0$ ) tal que $|f'(z_0)|=1$ $f'(z_0)^n=1$ para algunos entero $n$. Desde $$f(z_0+h) \approx f(z_0) + f'(z_0)h = z_0 + f'(z_0)h,$$ un punto cercano a $z_0$ realmente no se mueva mucho a favor o $z_0$. El punto es ni atractivo ni de repulsión y de la dinámica es bastante lento cerca de ese punto. Si, por el contrario, $|f'(z_0)| = r < 1$, luego $$|f(z_0+h) - f(z_0)| \approx r|h|,$$ de modo que el punto de $z_0$ es atractivo y puntos cercanos se mueven rápidamente hacia la $z_0$ bajo iteración.

Para entender los retos y la solución, que ayuda a mirar un ejemplo concreto, como el conjunto de Julia de $f(z)=z+z^5$, que se ve así:

Hay un enfoque estándar para dibujar el llenado Julia conjunto de un polinomio. Los rellenos de Julia es, por definición, el conjunto de todos los números complejos $z_0$ con la propiedad de que la iteración de $z_0$ conduce a un almacén de la órbita. El conjunto Julia sí es el límite de llenado de la Julia. El conjunto de Julia es de interés debido a que es invariante bajo la acción del polinomio y la dinámica restringida al conjunto Julia son caóticas.

Usando esta definición, el método estándar para determinar si un punto de $z_0$ es en el llenado Julia conjunto de un polinomio es recorrer $f$ $z_0$ hasta que sucede una de dos cosas:

1. El valor absoluto de la iterar supera cierto valor pasado en el que sabemos que la órbita se desvía a $\infty$ ($\sqrt{2}$ los trabajos para este ejemplo), o
2. De superar algunos pre-especificado de rescate (tal vez 100 o 1000 o 100000).

En el primer caso, estamos seguros de que $z_0$ se encuentra fuera de los rellenos de Julia - nos de sombra el punto blanco. En el segundo caso, tenemos la fuerte sospecha de que $z_0$ es en los rellenos de Julia, pero no estamos seguros de como puede ser que simplemente no han reiterado suficiente. Nos sombra el punto negro.

Si realizamos este procedimiento de una densa malla de puntos en un rectangular de dominio del plano complejo, entonces podemos generar un aproximado de imagen de llenado de Julia - el más alto es el rescate y el más denso es el conjunto de puntos, mejor es la aproximación. Esta estrategia simple es muy fácil de implementar. He aquí una $500\times500$ imagen mediante un plan de rescate de 2000 en el número de iteraciones:

Hay una forma estándar para detectar el límite entre las dos regiones para producir el real Julia. Por desgracia, no es particularmente impresionante en la presente resolución:

Así que, ¿cómo podemos mejorar la situación? Un método podría ser simplemente aumentar el número de iteraciones. Por desgracia, esto simplemente no funciona. La razón es que el $z_0=0$ es una parabólica de punto fijo y la dinámica de $f$ cerca de allí son muy lentos. Cuántos recorre, por ejemplo, se aplica a mover$z_0=1/32$$1/16$? La respuesta es casi $2000000$! Y esto es sólo un punto de que es sólo un poco más cerca de cero. Necesitamos puntos mucho más cerca de cero para obtener una solución razonable.

La solución propuesta por Braverman tiene dos partes principales

1. El uso más inteligente de clasificación que sólo "se escapa o no". La clasificación se basa en la Leau-Fatou flor teorema.
2. Expandir $f^{2^n}(z)$ para obtener los polinomios de representación de alto orden se repite. Estos polinomios se utilizan sólo cerca del punto fijo y sólo un número relativamente pequeño de los términos del polinomio son realmente necesarias.

Podemos describir el más inteligente esquema de clasificación en el contexto de este ejemplo bastante fácilmente. Supongamos que repetimos $f(z)=z+z^5$ 100 veces. Resulta que la mayoría de los recorre han superado 2 en valor absoluto, o que han aterrizado en uno de los cuatro prominentes hojas adjuntas a la de origen. Nos sombra de los puntos que se escaparon de blanco y el resto de los puntos de acuerdo que de los cuadrantes de que el punto ha aterrizado en. El resultado se ve así:

Si luego de aplicar el límite de la técnica de la exploración a esto, tenemos la primera imagen de arriba.

Cabe señalar que muchas de las ideas de Braverman del papel han sido, en la práctica, el uso por algún tiempo. El punto de que el papel no es principalmente para presentar una buena técnica computacional, sino para demostrar que el algoritmo se puede ejecutar en el polinomio de tiempo. Como tal, es mucho más difícil de leer de lo que debe ser si su interés principal es simplemente cómo generar conjuntos de Julia de tales funciones.

Answer 2

Yo no puedo ayudar con la primera pregunta. El segundo pertenece a meta, pero yo sugeriría escaneado el documento, intentando adivinar si puede ayudar a su problema. Ahora piense acerca de cuánto trabajo necesita entender la terminología. ¿Vale? Si es así, hazlo. En este caso, mi vistazo sugiere que no ayuda mucho para lo que quieras, así que blow off o haga una pregunta aclaratoria.