Método de marcha rápida

Algoritmo para resolver problemas de valores en la frontera de la ecuación de Eikonal

El método de marcha rápida ^[1] es un método numérico creado por James Sethian para resolver problemas de valores en la frontera de la ecuación de Eikonal :

${\displaystyle |\nabla u(x)|=1/f(x){\text{ for }}x\in \Omega }$

${\displaystyle u(x)=0{\text{ for }}x\in \partial \Omega }$

Normalmente, un problema de este tipo describe la evolución de una superficie cerrada en función del tiempo con la velocidad en la dirección normal en un punto de la superficie de propagación. Se especifica la función de velocidad y el tiempo en el que el contorno cruza un punto se obtiene resolviendo la ecuación. Alternativamente, se puede considerar como la cantidad mínima de tiempo que tomaría llegar a partir del punto . El método de marcha rápida aprovecha esta interpretación de control óptima del problema para construir una solución a partir de la "información conocida", es decir, los valores límite. ${\displaystyle u}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle u(x)}$ ${\displaystyle \partial \Omega }$ ${\displaystyle x}$

El algoritmo es similar al algoritmo de Dijkstra y utiliza el hecho de que la información sólo fluye hacia afuera desde el área de siembra. Este problema es un caso especial de métodos de conjunto de niveles . Existen algoritmos más generales pero normalmente son más lentos.

Extensiones para resolver dominios no planos (triangulados)

${\displaystyle |\nabla _{S}u(x)|=1/f(x),}$

para la superficie y , fueron presentados por Ron Kimmel y James Sethian . ${\displaystyle S}$ ${\displaystyle x\in S}$

• 
  Laberinto como función de velocidad, camino más corto.
• 
  Plantillas múltiples de mapas de distancia con puntos de origen aleatorios

Algoritmo

Primero, supongamos que el dominio ha sido discretizado en una malla. Nos referiremos a los puntos de malla como nodos. Cada nodo tiene un valor correspondiente . ${\displaystyle x_{i}}$ ${\displaystyle U_{i}=U(x_{i})\approx u(x_{i})}$

El algoritmo funciona igual que el algoritmo de Dijkstra, pero difiere en cómo se calculan los valores de los nodos. En el algoritmo de Dijkstra, el valor de un nodo se calcula utilizando uno solo de los nodos vecinos. Sin embargo, al resolver la PDE en , se utilizan entre y de los nodos vecinos . ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle 1}$ ${\displaystyle n}$

Los nodos se etiquetan como hasta ahora (aún no visitados), considerados (visitados y valor asignado provisionalmente) y aceptados (visitados y valor asignado permanentemente).

1. Asigne a cada nodo el valor de y etiquételos hasta el momento ; para todos los nodos configurados y etiquetados como aceptados . ${\displaystyle x_{i}}$ ${\displaystyle U_{i}=+\infty }$ ${\displaystyle x_{i}\in \partial \Omega }$ ${\displaystyle U_{i}=0}$ ${\displaystyle x_{i}}$
2. Para cada nodo lejano , utilice la fórmula de actualización de Eikonal para calcular un nuevo valor para . Si luego establece y etiqueta como se considera . ${\displaystyle x_{i}}$ ${\displaystyle {\tilde {U}}}$ ${\displaystyle {\tilde {U}}<U_{i}}$ ${\displaystyle U_{i}={\tilde {U}}}$ ${\displaystyle x_{i}}$
3. Sea el nodo considerado con el valor más pequeño . Etiquetar como aceptado . ${\displaystyle {\tilde {x}}}$ ${\displaystyle U}$ ${\displaystyle {\tilde {x}}}$
4. Para cada vecino que no sea aceptado, calcule un valor tentativo . ${\displaystyle x_{i}}$ ${\displaystyle {\tilde {x}}}$ ${\displaystyle {\tilde {U}}}$
5. Si entonces se establece . Si fue etiquetado hasta el momento , actualice la etiqueta para considerarlo . ${\displaystyle {\tilde {U}}<U_{i}}$ ${\displaystyle U_{i}={\tilde {U}}}$ ${\displaystyle x_{i}}$
6. Si existe un nodo considerado , regrese al paso 3. De lo contrario, finalice.

Ver también

• Método de ajuste de niveles
• Método de barrido rápido
• Algoritmo de Bellman-Ford

Enlaces externos

• Métodos tipo Dijkstra para la ecuación de Eikonal JN Tsitsiklis, 1995
• El método de marcha rápida y sus aplicaciones por James A. Sethian
• Métodos de marcha rápida con múltiples plantillas
• Implementación de Matlab de marcha rápida con múltiples plantillas
• Detalles de implementación de los métodos de marcha rápida
• Método de Marcha Rápida Generalizada de Forcadel et al. [2008] para aplicaciones en segmentación de imágenes.
• Implementación en Python del método de marcha rápida
• Consulte el Capítulo 8 en Diseño y optimización de elementos nanoópticos acoplando la fabricación al comportamiento óptico Archivado el 20 de agosto de 2013 en Wayback Machine.

Notas

1. JA Sethian. Un método de establecimiento de niveles de marcha rápida para frentes que avanzan monótonamente, proc. Nacional. Acad. Sci., 93, 4, págs. 1591-1595, 1996. [1]