Ecuación de Eikonal


De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

La ecuación eikonal (del griego εἰκών, imagen [1] [2] ) es una ecuación diferencial parcial no lineal que se encuentra en problemas de propagación de ondas , cuando la ecuación de ondas se aproxima utilizando la teoría WKB . Es derivable de las ecuaciones electromagnéticas de Maxwell y proporciona un vínculo entre la óptica física (de ondas) y la óptica geométrica (de rayos) .

La ecuación eikonal tiene la forma

sujeto a , donde es un conjunto abierto con un límite de buen comportamiento , es una función con valores positivos, denota el gradiente y es la norma euclidiana . Aquí, el lado derecho se suministra normalmente como entrada conocida. Físicamente, la solución es el menor tiempo necesario para viajar desde el límite hasta el interior con la velocidad a .

En el caso especial cuando , la solución da la distancia firmada de . [ cita requerida ]

Un algoritmo computacional rápido para aproximar la solución a la ecuación eikonal es el método de marcha rápida .

Interpretación física

Problemas continuos del camino más corto

La solución a la ecuación de eikonal

se puede interpretar como la cantidad mínima de tiempo requerido para viajar desde a , donde es la velocidad de viaje y es una penalización por tiempo de salida. (Alternativamente, esto puede plantearse como un costo de salida mínimo al hacer el lado derecho y una penalización de costo de salida).

Suponiendo que existe en todos los puntos, es fácil demostrar que corresponde a un problema de control de tiempo óptimo utilizando el principio de optimalidad de Bellman y una expansión de Taylor. [3] Desafortunadamente, no se garantiza que exista en todos los puntos, y se necesitan técnicas más avanzadas para demostrarlo. Esto llevó al desarrollo de soluciones de viscosidad en la década de 1980 por Pierre-Louis Lions y Michael G. Crandall , [4] y Lions ganó una Medalla Fields por sus contribuciones.

Potencial electromagnético

El significado físico de la ecuación eikonal está relacionado con la fórmula

donde es la fuerza del campo eléctrico y es el potencial eléctrico. Existe una ecuación similar para el potencial de velocidad en el flujo de fluido y la temperatura en la transferencia de calor. El significado físico de esta ecuación en el ejemplo electromagnético es que cualquier carga en la región se empuja a moverse en ángulo recto con las líneas [ aclaración necesaria ] de potencial constante, y a lo largo de las líneas de fuerza determinadas por el campo del vector E y el signo del cargo.

La óptica de rayos y el electromagnetismo están relacionados por el hecho de que la ecuación eikonal da una segunda fórmula electromagnética de la misma forma que la ecuación de potencial anterior, donde la línea de potencial constante ha sido reemplazada por una línea de fase constante y las líneas de fuerza han sido reemplazadas. por vectores normales que salen de la línea de fase constante en ángulos rectos. La magnitud de estos vectores normales viene dada por la raíz cuadrada de la permitividad relativa. La línea de fase constante puede considerarse el borde de una de las ondas de luz que avanzan. Los vectores normales son los rayos que la luz viaja hacia abajo en la óptica de rayos.

Algoritmos computacionales

Desde la década de 1990 se han desarrollado varios algoritmos rápidos y eficientes para resolver la ecuación eikonal. Muchos de estos algoritmos aprovechan los algoritmos desarrollados mucho antes para problemas de ruta más corta en gráficos con longitudes de borde no negativas. [5] Estos algoritmos aprovechan la causalidad proporcionada por la interpretación física y normalmente discretizan el dominio utilizando una malla [6] [7] [8] [9] o una cuadrícula regular [10] [11] y calculan la solución en cada punto discretizado. Los solucionadores Eikonal en variedades trianguladas son. [6] [7]

El método de marcha rápida de Sethian (FMM) [10] [11] fue el primer algoritmo "rápido y eficiente" creado para resolver la ecuación de Eikonal. La descripción original discretiza el dominio en una cuadrícula regular y "lleva" la solución desde los valores "conocidos" a las regiones no descubiertas, reflejando con precisión la lógica del algoritmo de Dijkstra . Si está discretizado y tiene puntos de malla, entonces la complejidad computacional es donde el término proviene del uso de un montón (típicamente binario). Se pueden prescribir una serie de modificaciones a FMM, ya que se clasifica como un método de colocación de etiquetas. Además, FMM se ha generalizado para operar sobre mallas generales que discretizan el dominio.[6][7] [8] [9]

Los métodos de corrección de etiquetas , como el algoritmo de Bellman-Ford, también se pueden utilizar para resolver la ecuación discretizada de Eikonal también con numerosas modificaciones permitidas (por ejemplo, "Etiquetas pequeñas primero" [5] [12] o "Etiquetas grandes al final" [5] [13 ] ). También se han desarrollado métodos de dos colas [14] que son esencialmente una versión del algoritmo Bellman-Ford, excepto que se utilizan dos colas con un umbral utilizado para determinar a qué cola se debe asignar un punto de cuadrícula en función de la información local.

Los algoritmos de barrido como el método de barrido rápido (FSM) [15] son muy eficientes para resolver ecuaciones de Eikonal cuando las curvas características correspondientes no cambian de dirección con mucha frecuencia. [5] Estos algoritmos corrigen etiquetas pero no hacen uso de una cola o montón, sino que prescriben diferentes ordenamientos para que los puntos de cuadrícula se actualicen e iteren a través de estos ordenamientos hasta la convergencia. Se introdujeron algunas mejoras, como "bloquear" puntos de cuadrícula [14].durante un barrido si no recibe una actualización, pero en cuadrículas altamente refinadas y espacios de mayor dimensión todavía hay una gran sobrecarga debido a tener que pasar por cada punto de cuadrícula. Se han introducido métodos paralelos que intentan descomponer el dominio y realizar un barrido en cada subconjunto descompuesto. La implementación paralela de Zhao descompone el dominio en subconjuntos dimensionales y luego ejecuta un FSM individual en cada subconjunto. [16] La implementación paralela de Dextrixhe también descompone el dominio, pero paraleliza cada barrido individual para que los procesadores sean responsables de actualizar los puntos de cuadrícula en un hiperplano -dimensional hasta que todo el dominio esté completamente barrido. [17]

También se han introducido métodos híbridos que aprovechan la eficiencia de FMM con la simplicidad de FSM. Por ejemplo, el método de celda de pila (HCM) descompone el dominio en celdas y realiza FMM en el dominio de celda, y cada vez que se actualiza una "celda", se realiza FSM en el dominio de punto de cuadrícula local que se encuentra dentro de esa celda. [5] También se ha desarrollado una versión paralelizada de HCM. [18]

Aproximación numérica

Por simplicidad, suponga que está discretizado en una cuadrícula uniforme con espaciado .

Aproximación 2D en una cuadrícula cartesiana

Suponga que un punto de cuadrícula tiene valor . Un esquema de primer orden para aproximar las derivadas parciales es

donde

Debido a las propiedades consistentes, monótonas y causales de esta discretización [5] , es fácil demostrar que si y y luego

lo que significa

Esta solución siempre existirá mientras se satisfaga y sea más grande que ambos, y , mientras . Si , se debe realizar una actualización de menor dimensión asumiendo que una de las derivadas parciales es :

Aproximación n- D en una cuadrícula cartesiana

Suponga que un punto de la cuadrícula tiene valor . Repitiendo los mismos pasos que en el caso podemos usar un esquema de primer orden para aproximar las derivadas parciales. Sea el mínimo de los valores de los vecinos en las direcciones, donde es un vector base unitario estándar . La aproximación es entonces

Resolviendo esta ecuación cuadrática para los rendimientos:

Si el discriminante en la raíz cuadrada es negativo, entonces se debe realizar una actualización de menor dimensión (es decir, una de las derivadas parciales lo es ).

Si entonces realiza la actualización unidimensional

Si, entonces realice una actualización dimensional usando los valores para cada y elija el más pequeño.

Descripción matemática

Una ecuación eikonal es una de las formas

Se puede pensar en el plano como la condición inicial, pensando que también podríamos resolver la ecuación en un subconjunto de este plano, o en una superficie curva, con modificaciones obvias.

La ecuación eikonal se muestra en óptica geométrica , que es una forma de estudiar las soluciones de la ecuación de onda , donde y . En óptica geométrica, la ecuación eikonal describe los frentes de fase de las ondas. Bajo una hipótesis razonable sobre los datos "iniciales", la ecuación eikonal admite una solución local, pero una solución global uniforme (por ejemplo, una solución para todo el tiempo en el caso de la óptica geométrica) no es posible. La razón es que pueden desarrollarse cáusticos . En el caso de la óptica geométrica, esto significa que los frentes de onda se cruzan.

Podemos resolver la ecuación eikonal usando el método de características. Se debe imponer la hipótesis "no característica" a lo largo de la hipersuperficie inicial , donde H  =  H ( x , p ) yp  = ( p 1 , ..., p n ) es la variable que se reemplaza por ∇ u . Aquí x  = ( x 1 , ..., x n ) = ( t , x ′).

En primer lugar, resolver el problema , . Esto se hace definiendo curvas (y valores de en esas curvas) como

Tenga en cuenta que, incluso antes de que tengamos una solución , sabemos por debido a nuestra ecuación para .

El hecho de que estas ecuaciones tengan una solución para algún intervalo se deduce de los teoremas estándar de la EDO (utilizando la hipótesis no característica). Estas curvas completan un conjunto abierto alrededor del avión . Por tanto, las curvas definen el valor de en un conjunto abierto alrededor de nuestro plano inicial. Una vez definido como tal, es fácil de ver usando la regla de la cadena eso , y por lo tanto a lo largo de estas curvas.

Queremos que nuestra solución satisfaga , o más específicamente, para todos , asumiendo por un minuto que esto es posible, para cualquier solución debemos tener

y por lo tanto

En otras palabras, la solución se dará en una vecindad del plano inicial mediante una ecuación explícita. Sin embargo, dado que los diferentes caminos , partiendo de diferentes puntos iniciales pueden cruzarse, la solución puede volverse multivalorizada, en cuyo punto hemos desarrollado cáusticos. También tenemos (incluso antes de mostrar que es una solución)

Queda por mostrar que , lo que hemos definido en una vecindad de nuestro plano inicial, es el gradiente de alguna función . Esto seguirá si mostramos que el campo vectorial está libre de curvaturas. Considere el primer término en la definición de . Este término no tiene rizos, ya que es el gradiente de una función. En cuanto al otro término, observamos

El resultado sigue.

Aplicaciones

  • Una aplicación concreta es el cálculo de la atenuación de las ondas de radio en la atmósfera .
  • Encontrar la forma a partir del sombreado en la visión por computadora.
  • Óptica geométrica
  • Problemas continuos del camino más corto
  • Segmentación de imagen
  • Estudio de la forma del grano de un cohete propulsor sólido

Ver también

  • Ecuación de Hamilton – Jacobi – Bellman
  • Ecuación de Hamilton-Jacobi
  • Principio de Fermat

Referencias

  1. ^ El diccionario de inglés de Oxford. 2ª ed. 1989. OED Online. Prensa de la Universidad de Oxford. 4 de abril de 2000 http://dictionary.oed.com/cgi/entry/00292404
  2. ^ Evans, LC ecuaciones diferenciales parciales . AMS Textos de Posgrado en Matemáticas. Vol. 19. p. 93. |volume=tiene texto extra ( ayuda )
  3. ^ Clawson, Z .; Chacón, A .; Vladimirsky, A. (2014). "Restricción de dominio causal para ecuaciones de Eikonal". Revista SIAM de Computación Científica . 36 (5): A2478 – A2505. arXiv : 1309.2884 . doi : 10.1137 / 130936531 .
  4. ^ Bardi, M .; Capuzzo-Dolcetta, I. (1997). Soluciones óptimas de control y viscosidad de las ecuaciones de Hamilton – Jacobi – Bellman . Boston: Birkhäuser. ISBN 0-8176-3640-4.
  5. ^ a b c d e f Chacón, A .; Vladimirsky, A. (2012). "Métodos rápidos de dos escalas para ecuaciones eikonal". Revista SIAM de Computación Científica . 34 (2): A547 – A578. arXiv : 1110.6220 . doi : 10.1137 / 10080909X .
  6. ^ a b c Kimmel, R .; Sethian, JA (1998). "Calcular trayectorias geodésicas en colectores" . Actas de la Academia Nacional de Ciencias . 95 (15): 8431–8435. doi : 10.1073 / pnas.95.15.8431 . PMC 21092 . PMID 9671694 .  
  7. ^ a b c Bronstein, AM; Bronstein, MM; Kimmel, R. (2007). "Cálculo de mapas de distancia ponderada en variedades tridimensionales paramétricas". Revista de Física Computacional . 225 (1): 771–784. doi : 10.1016 / j.jcp.2007.01.009 .
  8. ^ a b Sethian, JA; Vladimirsky, A. (2000). "Métodos rápidos para el Eikonal y ecuaciones relacionadas de Hamilton-Jacobi en mallas no estructuradas" . Proc. Natl. Acad. Sci. USA . 97 (11): 5699–5703. doi : 10.1073 / pnas.090060097 . PMC 18495 . PMID 10811874 .  
  9. ↑ a b Yershov, DS; LaValle, SM (2012). "Simplicial Dijkstra y A * Algoritmos: de gráficos a espacios continuos". Robótica avanzada . 26 (17): 2065-2085. doi : 10.1080 / 01691864.2012.729559 .
  10. ↑ a b Sethian, JA (1996). "Un método de conjunto de niveles de marcha rápida para frentes que avanzan monótonamente" . Proc. Natl. Acad. Sci . 93 (4): 1591-1595. doi : 10.1073 / pnas.93.4.1591 . PMC 39986 . PMID 11607632 .  
  11. ↑ a b Tsitsiklis, JN (1995). "Algoritmos eficientes para trayectorias óptimas a nivel mundial". IEEE Trans. Autom. Control . 40 (9): 1528-1538. doi : 10.1109 / 9.412624 .
  12. ^ Bertsekas, DP (1993). "Un algoritmo de corrección de etiquetas simple y rápido para las rutas más cortas". Redes . 23 (8): 703–709. doi : 10.1002 / net.3230230808 . hdl : 1721,1 / 3256 .
  13. ^ Bertsekas, DP; Guerriero, F .; Musmanno, R. (1996). "Métodos de corrección de etiquetas asíncronas en paralelo para las rutas más cortas". Revista de teoría y aplicaciones de la optimización . 88 (2): 297–320. doi : 10.1007 / BF02192173 .
  14. ^ a b Bak, S .; McLaughlin, J .; Renzi, D. (2010). "Algunas mejoras para el método de barrido rápido". Revista SIAM de Computación Científica . 32 (5): 2853–2874. doi : 10.1137 / 090749645 .
  15. ^ Zhao, H. (2004). "Un método de barrido rápido para ecuaciones eikonal" . Matemáticas. Comp . 74 (250): 603–627. doi : 10.1090 / S0025-5718-04-01678-3 .
  16. ^ Zhao, H. (2007). "Implementaciones paralelas del método de barrido rápido". J. Comput. Matemáticas . 25 (4): 421–429. JSTOR 43693378 . 
  17. ^ Detrixhe, M .; Gibou, F .; Min, C. (2013). "Un método de barrido rápido paralelo para la ecuación de Eikonal". Revista de Física Computacional . 237 : 46–55. doi : 10.1016 / j.jcp.2012.11.042 .
  18. ^ Chacón, A .; Vladimirsky, A. (2015). "Un método paralelo de dos escalas para ecuaciones de Eikonal". Revista SIAM de Computación Científica . 37 (1): A156 – A180. arXiv : 1306.4743 . doi : 10.1137 / 12088197X .

Otras lecturas

  • París, DT; Hurd, FK (1969). Teoría básica electromagnética . McGraw-Hill. págs. 383–385. ISBN 0-07-048470-8.
  • Arnold, VI (2004). Conferencias sobre ecuaciones diferenciales parciales (2ª ed.). Saltador. págs. 2-3. ISBN 3-540-40448-1.

enlaces externos

  • La ecuación de eikonal linealizada
  • Traducción al inglés de "Das Eikonal" de Heinrich Bruns
Obtenido de " https://en.wikipedia.org/w/index.php?title=Eikonal_equation&oldid=1033346187 "