stringtranslate.com

Ecuación eikonal

Una ecuación eikonal (del griego εἰκών, imagen [1] [2] ) es una ecuación diferencial parcial de primer orden no lineal que se encuentra en problemas de propagación de ondas .

La ecuación eikonal clásica en óptica geométrica es una ecuación diferencial de la forma

donde se encuentra en un subconjunto abierto de , es una función positiva, denota el gradiente y es la norma euclidiana . Se da la función y se buscan soluciones . En el contexto de la óptica geométrica , la función es el índice de refracción del medio.

De manera más general, una ecuación eikonal es una ecuación de la forma

donde es una función de variables. Aquí se da la función y es la solución. Si , entonces la ecuación ( 2 ) se convierte en ( 1 ).

Las ecuaciones eikonales surgen naturalmente en el método WKB [3] y en el estudio de las ecuaciones de Maxwell . [4] Las ecuaciones eikonales proporcionan un vínculo entre la óptica física (ondas) y la óptica geométrica (rayos) .

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

Historia

El término "eikonal" fue utilizado por primera vez en el contexto de la óptica geométrica por Heinrich Bruns . [5] Sin embargo, la ecuación real aparece antes en el trabajo seminal de William Rowan Hamilton sobre óptica geométrica . [6]

Interpretación física

Problemas continuos de camino más corto

Supongamos que es un conjunto abierto con un borde adecuadamente suave . La solución de la ecuación eikonal

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

En el caso especial cuando , la solución da la distancia con signo desde . [7]

Suponiendo que existe en todos los puntos, es fácil demostrar que corresponde a un problema de control óptimo en el tiempo utilizando el principio de optimalidad de Bellman y una expansión de Taylor. [8] Desafortunadamente, no está garantizado que exista en todos los puntos, y se necesitan técnicas más avanzadas para demostrarlo. Esto condujo al desarrollo de soluciones de viscosidad en la década de 1980 por Pierre-Louis Lions y Michael G. Crandall , [9] 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 intensidad del campo eléctrico y es el potencial eléctrico. Existe una ecuación similar para el potencial de velocidad en el flujo de fluidos 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 es empujada a moverse en ángulos rectos con las líneas [ aclaración necesaria ] de potencial constante y a lo largo de líneas de fuerza determinadas por el campo del vector E y el signo de la carga.

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 está 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 ( frente de onda ). Los vectores normales son los rayos por los que viaja la luz 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 algoritmos desarrollados mucho antes para problemas de ruta más corta en grafos con longitudes de aristas no negativas. [10] Estos algoritmos aprovechan la causalidad proporcionada por la interpretación física y, por lo general, discretizan el dominio utilizando una malla [11] [12] [13] [14] o una cuadrícula regular [15] [16] y calculan la solución en cada punto discretizado. Los solucionadores eikonales en superficies trianguladas fueron introducidos por Kimmel y Sethian en 1998. [11] [12]

El método de marcha rápida de Sethian (FMM) [15] [16] 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 "marcha" la solución desde los valores "conocidos" hasta 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 de donde proviene el término, el uso de un montón (normalmente binario). Se pueden prescribir varias modificaciones al FMM, ya que se clasifica como un método de establecimiento de etiquetas. Además, el FMM se ha generalizado para operar en mallas generales que discretizan el dominio. [11] [12] [13] [14]

Los métodos de corrección de etiquetas, como el algoritmo 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" [10] [17] o "Etiquetas grandes al final" [10] [18] ). También se han desarrollado métodos de dos colas [19] 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) [20], son muy eficientes para resolver ecuaciones de Eikonal cuando las curvas características correspondientes no cambian de dirección muy a menudo. [10] Estos algoritmos corrigen las etiquetas, pero no utilizan una cola o un montón, y en su lugar prescriben diferentes ordenamientos para que los puntos de la cuadrícula se actualicen e iteran a través de estos ordenamientos hasta la convergencia. Se introdujeron algunas mejoras, como el "bloqueo" de los puntos de la cuadrícula [19] durante un barrido si no recibe una actualización, pero en cuadrículas altamente refinadas y espacios de dimensiones superiores todavía hay una gran sobrecarga debido a tener que pasar por cada punto de la 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 de dimensiones y luego ejecuta un FSM individual en cada subconjunto. [21] La implementación paralela de Detrixhe también descompone el dominio, pero paraleliza cada barrido individual de modo que los procesadores son responsables de actualizar los puntos de la cuadrícula en un hiperplano dimensional hasta que todo el dominio esté completamente barrido. [22]

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 celdas de montón (HCM) descompone el dominio en celdas y realiza FMM en el dominio de celdas, y cada vez que se actualiza una "celda", se realiza FSM en el dominio de puntos de cuadrícula local que se encuentra dentro de esa celda. [10] También se ha desarrollado una versión paralelizada de HCM. [23]

Aproximación numérica

Para simplificar, supongamos que se discretiza en una cuadrícula uniforme con espaciamientos y en las direcciones x e y, respectivamente.

Aproximación 2D en una cuadrícula cartesiana

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

dónde

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

que se puede resolver como una ecuación cuadrática. En el caso límite de , esto se reduce a

Esta solución siempre existirá mientras se satisfaga y sea mayor que ambos, y , siempre que .

Si , se debe realizar una actualización de menor dimensión asumiendo que una de las derivadas parciales es :

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

Supongamos que un punto de la cuadrícula tiene valor . Repitiendo los mismos pasos que en el caso podemos utilizar 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 obtenemos:

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

Si luego realiza la actualización unidimensional

Si luego realiza una actualización dimensional utilizando los valores para cada y elija el más pequeño.

Descripción matemática

Una ecuación eikonal es una de la forma

El plano puede considerarse como la condición inicial, pensando en como 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 aparece en la ó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 no es posible una solución global uniforme (por ejemplo, una solución para todo el tiempo en el caso de la óptica geométrica). La razón es que pueden desarrollarse cáusticas . En el caso de la óptica geométrica, esto significa que los frentes de onda se cruzan.

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

Primero, resuelva 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 que debido a nuestra ecuación para .

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

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

y por lo tanto

En otras palabras, la solución estará dada en un entorno del plano inicial por una ecuación explícita. Sin embargo, dado que los diferentes caminos , partiendo de diferentes puntos iniciales, pueden cruzarse, la solución puede volverse multivaluada, en cuyo punto hemos desarrollado cáusticas. También tenemos (incluso antes de demostrar que es una solución)

Queda por demostrar que , que hemos definido en un entorno de nuestro plano inicial, es el gradiente de alguna función . Esto se deducirá si demostramos que el campo vectorial no tiene rotacional. Consideremos el primer término en la definición de . Este término, no tiene rotacional ya que es el gradiente de una función. En cuanto al otro término, notamos

El resultado es el siguiente:

Aplicaciones

Véase también

Referencias

  1. ^ Diccionario Oxford de inglés. 2.ª edición. 1989. OED Online. Oxford University Press. 4 de abril de 2000. http://dictionary.oed.com/cgi/entry/00292404
  2. ^ Evans, LC Ecuaciones diferenciales parciales . Textos de posgrado en matemáticas de la AMS. Vol. 19. pág. 93.
  3. ^ Dimassi, Mouez; Sjöstrand, Johannes (1999). Asintótica espectral en el límite semiclásico . Notas de la conferencia de la London Math Society 268. Cambridge University Press. ISBN 0-521-66544-2.
  4. ^ Rauch, Jeffrey (2012), Ecuaciones diferenciales parciales hiperbólicas y óptica geométrica , Estudios de posgrado en matemáticas, 133, American Mathematical Society, Bibcode :2012hpde.book.....R, ISBN 978-0-8218-7291-8
  5. ^ Bruns, Heinrich (1895). El Eikonal . S. Hirzel.
  6. ^ Hamilton, William Rowan (1828). "Teoría de sistemas de rayos". Transactions of the Royal Irish Academy . 15 : 69–174.
  7. ^ Sakai, Takashi. "Sobre variedades de Riemann que admiten una función cuyo gradiente es de norma constante". Kodai Mathematical Journal 19.1 (1996): 39-51.
  8. ^ Clawson, Z.; Chacon, A.; Vladimirsky, A. (2014). "Restricción del dominio causal para ecuaciones eikonales". Revista SIAM de informática científica . 36 (5): A2478–A2505. arXiv : 1309.2884 . Código Bibliográfico :2014SJSC...36A2478C. doi :10.1137/130936531. S2CID  17226196.
  9. ^ Bardi, M.; Capuzzo-Dolcetta, I. (1997). Control óptimo y soluciones de viscosidad de las ecuaciones de Hamilton-Jacobi-Bellman . Boston: Birkhäuser. ISBN 0-8176-3640-4.
  10. ^ abcdef Chacon, A.; Vladimirsky, A. (2012). "Métodos rápidos de dos escalas para ecuaciones eikonales". Revista SIAM de Computación Científica . 34 (2): A547–A578. arXiv : 1110.6220 . Código Bibliográfico :2012SJSC...34A.547C. doi :10.1137/10080909X. S2CID  6404391.
  11. ^ abc Kimmel, R.; Sethian, JA (1998). "Cálculo de trayectorias geodésicas en variedades". Actas de la Academia Nacional de Ciencias . 95 (15): 8431–8435. Bibcode :1998PNAS...95.8431K. doi : 10.1073/pnas.95.15.8431 . PMC 21092 . PMID  9671694. 
  12. ^ abc Bronstein, AM; Bronstein, MM; Kimmel, R. (2007). "Cálculo de mapas de distancia ponderados en variedades paramétricas tridimensionales". Journal of Computational Physics . 225 (1): 771–784. Bibcode :2007JCoPh.225..771B. doi :10.1016/j.jcp.2007.01.009.
  13. ^ ab Sethian, JA; Vladimirsky, A. (2000). "Métodos rápidos para las ecuaciones de Eikonal y de Hamilton-Jacobi relacionadas en mallas no estructuradas". Proc. Natl. Sci. EE. UU . . 97 (11): 5699–5703. Bibcode :2000PNAS...97.5699S. doi : 10.1073/pnas.090060097 . PMC 18495 . PMID  10811874. 
  14. ^ ab Yershov, DS; LaValle, SM (2012). "Algoritmos simples de Dijkstra y A*: de gráficos a espacios continuos". Advanced Robotics . 26 (17): 2065–2085. doi :10.1080/01691864.2012.729559. S2CID  17573584.
  15. ^ ab Sethian, JA (1996). "Un método de nivelación de marcha rápida para frentes que avanzan monótonamente". Proc. Natl. Sci . 93 (4): 1591–1595. Bibcode :1996PNAS...93.1591S. doi : 10.1073/pnas.93.4.1591 . PMC 39986 . PMID  11607632. 
  16. ^ ab Tsitsiklis, JN (1995). "Algoritmos eficientes para trayectorias globalmente óptimas". IEEE Trans. Autom. Control . 40 (9): 1528–1538. doi :10.1109/9.412624. hdl : 1721.1/3340 .
  17. ^ Bertsekas, DP (1993). "Un algoritmo de corrección de etiquetas simple y rápido para caminos más cortos". Redes . 23 (8): 703–709. doi :10.1002/net.3230230808. hdl : 1721.1/3256 .
  18. ^ Bertsekas, DP; Guerriero, F.; Musmanno, R. (1996). "Métodos de corrección de etiquetas asincrónicas paralelas para caminos más cortos". Journal of Optimization Theory and Applications . 88 (2): 297–320. doi :10.1007/BF02192173. hdl : 1721.1/3390 . S2CID  13172492.
  19. ^ ab 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. Bibcode :2010SJSC...32.2853B. doi :10.1137/090749645.
  20. ^ Zhao, H. (2004). "Un método de barrido rápido para ecuaciones eikonales". Matemáticas. Comp . 74 (250): 603–627. doi : 10.1090/S0025-5718-04-01678-3 .
  21. ^ Zhao, H. (2007). "Implementaciones paralelas del método de barrido rápido". J. Comput. Math . 25 (4): 421–429. JSTOR  43693378.
  22. ^ Detrixhe, M.; Gibou, F.; Min, C. (2013). "Un método de barrido rápido paralelo para la ecuación de Eikonal". Journal of Computational Physics . 237 : 46–55. Bibcode :2013JCoPh.237...46D. doi :10.1016/j.jcp.2012.11.042.
  23. ^ Chacon, 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 . Código Bibliográfico :2015SJSC...37A.156C. doi :10.1137/12088197X.

Lectura adicional

Enlaces externos