stringtranslate.com

ecuación de 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 . La función está dada 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 de Eikonal surgen naturalmente en el método WKB [3] y en el estudio de las ecuaciones de Maxwell . [4] Las ecuaciones de Eikonal proporcionan un vínculo entre la óptica física (de ondas) y la óptica geométrica (de rayos) .

Un algoritmo computacional rápido para aproximar la solución a la ecuación de 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 anteriormente en el trabajo fundamental de William Rowan Hamilton sobre óptica geométrica . [6]

Interpretación física

Problemas continuos del camino más corto

Supongamos que es un conjunto abierto con un límite adecuadamente suave . La solución a la ecuación de eikonal.

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

En el caso especial en el que , la solución proporciona la distancia con signo desde . [7]

Suponiendo que esto existe en todos los puntos, es fácil demostrar que corresponde a un problema de control óptimo en el tiempo utilizando el principio de optimización de Bellman y una expansión de Taylor. [8] 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 parte de 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 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 es empujada a moverse en ángulo recto con las líneas [ se necesita aclaración ] 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 de eikonal proporciona 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 ángulo recto. 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 luminosas que avanza ( 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 de Eikonal. Muchos de estos algoritmos aprovechan algoritmos desarrollados mucho antes para problemas de camino más corto en gráficos con longitudes de borde no negativas. [10] Estos algoritmos aprovechan la causalidad proporcionada por la interpretación física y típicamente discretizan el dominio usando una malla [11] [12] [13] [14] o una cuadrícula regular [15] [16] y calculan la solución en cada punto discretizado. Se introdujeron los solucionadores Eikonal en superficies trianguladas. [11] [12]

El método de marcha rápida (FMM) de Sethian [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 precisamente 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 del uso de un montón (normalmente binario). Se pueden prescribir varias modificaciones al FMM, ya que está clasificado como un método de establecimiento de etiquetas. Además, FMM se ha generalizado para operar sobre mallas generales que discretizan el dominio. [11] [12] [13] [14]

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" [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 ​​altamente eficientes para resolver ecuaciones de Eikonal cuando las curvas características correspondientes no cambian de dirección con mucha frecuencia. [10] Estos algoritmos corrigen etiquetas, pero no utilizan una cola o un montón, sino que prescriben diferentes ordenamientos para los puntos de cuadrícula que se actualizarán e iterarán a través de estos ordenamientos hasta la convergencia. Se introdujeron algunas mejoras, como "bloquear" 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 dimensionales 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 sean 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 celda de montón (HCM) descompone el dominio en celdas y realiza FMM en el dominio de celda, y cada vez que se actualiza una "celda", FSM se realiza en el dominio de punto 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 está discretizado en una cuadrícula uniforme con espaciamientos y en las direcciones xey, respectivamente.

Aproximación 2D en una cuadrícula cartesiana

Supongamos que un punto de 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 cuadrática. En el caso límite de , esto se reduce a

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

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

Aproximación 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 de base unitaria estándar . La aproximación es entonces

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

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

Si luego realiza la actualización unidimensional

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

Descripción matemática

Una ecuación eikonal es una de la forma

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 de eikonal aparece en óptica geométrica , que es una forma de estudiar 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 hipótesis razonables sobre los datos "iniciales", la ecuación eikonal admite una solución local, pero una solución global suave (por ejemplo, una solución para todos los tiempos en el caso de la óptica geométrica) no es posible. La razón es que se pueden formar sustancias cáusticas . En el caso de la óptica geométrica, esto significa que los frentes de onda se cruzan.

Podemos resolver la ecuación de eikonal usando el método de las características. Se debe 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 reemplaza por ∇ u . Aquí x  = ( x 1 ,..., x n ) = ( t , x ′).

Primero, resuelve el problema . Esto se hace definiendo curvas (y valores de en esas curvas) como

Tenga en cuenta que incluso antes de tener una solución , conocemos for debido a nuestra ecuación for .

El hecho de que estas ecuaciones tengan una solución para algún intervalo se desprende 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 . Así, las curvas definen el valor de en un conjunto abierto alrededor de nuestro plano inicial. Una vez definida como tal, es fácil ver usando 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 sea posible, para cualquier solución debemos tener

y por lo tanto

En otras palabras, la solución vendrá dada en una vecindad del plano inicial mediante una ecuación explícita. Sin embargo, dado que los diferentes caminos , que parten de diferentes puntos iniciales, pueden cruzarse, la solución puede volverse multivaluada, momento en el que hemos desarrollado cáusticas. También tenemos (incluso antes de mostrar que es una solución)

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

El resultado sigue.

Aplicaciones

Ver también

Referencias

  1. ^ El diccionario de inglés de Oxford. 2da ed. 1989. DEO en línea. Prensa de la Universidad de Oxford. 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; Sjostrand, Johannes (1999). Asintóticas espectrales en el límite semiclásico . Matemáticas de Londres. Notas de conferencias de la sociedad 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, Sociedad Matemática Estadounidense, 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". Transacciones de la Real Academia Irlandesa . 15 : 69-174.
  7. ^ Sakai, Takashi. "Sobre variedades de Riemann que admiten una función cuyo gradiente es de norma constante". Revista matemática Kodai 19.1 (1996): 39-51.
  8. ^ Clawson, Z.; Chacón, A.; Vladimirsky, A. (2014). "Restricción del dominio causal para ecuaciones de Eikonal". Revista SIAM de Computación Científica . 36 (5): A2478–A2505. arXiv : 1309.2884 . Código Bib : 2014SJSC...36A2478C. doi :10.1137/130936531. S2CID  17226196.
  9. ^ 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.
  10. ^ abcdef Chacón, 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 Bib : 2012SJSC...34A.547C. doi :10.1137/10080909X. S2CID  6404391.
  11. ^ abc Kimmel, R.; Sethian, JA (1998). "Cálculo de rutas geodésicas en colectores". Procedimientos de la Academia Nacional de Ciencias . 95 (15): 8431–8435. Código bibliográfico : 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 distancias ponderadas en variedades tridimensionales paramétricas". Revista de Física Computacional . 225 (1): 771–784. Código bibliográfico : 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 Hamilton-Jacobi relacionadas en mallas no estructuradas". Proc. Nacional. Acad. Ciencia. EE.UU . 97 (11): 5699–5703. Código bibliográfico : 2000PNAS...97.5699S. doi : 10.1073/pnas.090060097 . PMC 18495 . PMID  10811874. 
  14. ^ ab Yershov, DS; LaValle, SM (2012). "Algoritmos simpliciales de Dijkstra y A *: de gráficos a espacios continuos". Robótica Avanzada . 26 (17): 2065–2085. doi :10.1080/01691864.2012.729559. S2CID  17573584.
  15. ^ ab Sethian, JA (1996). "Un método de establecimiento de niveles de marcha rápida para frentes que avanzan monótonamente". Proc. Nacional. Acad. Ciencia . 93 (4): 1591-1595. Código bibliográfico : 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". Traducción IEEE. Automático. 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; Guerrero, F.; Musmanno, R. (1996). "Métodos de corrección de etiquetas asincrónicas paralelas para rutas más cortas". Revista de teoría y aplicaciones de optimización . 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. Código Bib : 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. Computación. Matemáticas . 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". Revista de Física Computacional . 237 : 46–55. Código Bib : 2013JCoPh.237...46D. doi :10.1016/j.jcp.2012.11.042.
  23. ^ 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 . Código Bib : 2015SJSC...37A.156C. doi :10.1137/12088197X.

Otras lecturas

enlaces externos