# Equació eikonal

Una equació eikonal (del grec εἰκών, imatge) és una equació diferencial parcial no lineal de primer ordre que es troba en problemes de propagació d'ones.
L'equació eikonal clàssica en òptica geomètrica és una equació diferencial de la forma
$|\nabla u(x)|=n(x)$ (1)
on $x$ es troba en un subconjunt obert de $\mathbb {R} ^{n}$, $n(x)$ és una funció positiva, $\nabla$ denota el gradient, i $|\cdot |$ és la norma euclidiana. La funció $n$ es dóna i es busca solucions $u$. En el context de l'òptica geomètrica, la funció $n$ és l'índex de refracció del medi.
De manera més general, una equació eikonal és una equació de la forma
    $H(x,\nabla u(x))=0$         (2)
on $H$ és una funció de $2n$ variables. Aquí la funció $H$ es dóna, i $u$ és la solució. Si $H(x,y)=|y|-n(x)$, aleshores l'equació (2) es converteix en (1).
Les equacions eikonals sorgeixen de manera natural en el mètode WKB i l'estudi de les equacions de Maxwell. Les equacions eikonals proporcionen un vincle entre l'òptica física (ona) i l'òptica geomètrica (raig).
Un algorisme computacional ràpid per aproximar la solució de l'equació eikonal és el mètode de marxa ràpida.

## Història

El terme "eikonal" va ser utilitzat per primera vegada en el context de l'òptica geomètrica per Heinrich Bruns. Tanmateix, l'equació real apareix abans en el treball seminal de William Rowan Hamilton sobre l'òptica geomètrica.

## Interpretació física
### Problemes continus del camí més curt

Suposem que $\Omega$ és un conjunt obert amb un límit adequadament suau $\partial \Omega$. La solució de l'equació eikonal
    $\left|\nabla u(x)\right|={\frac {1}{f(x)}}{\text{ for }}x\in \Omega \subset \mathbb {R} ^{n},$
    $u(x)=q(x){\text{ for }}x\in \partial \Omega$
es pot interpretar com la quantitat mínima de temps necessari per viatjar $x$ a $\partial \Omega$, on $f:{\bar {\Omega }}\to (0,+\infty )$ és la velocitat del viatge, i $q:\partial \Omega \to [0,+\infty )$ és una penalització de temps de sortida. (Alternativament, això es pot plantejar com un cost mínim de sortida fent el costat dret $C(x)/f(x)$ i $q$ una penalització per cost de sortida.)
En el cas especial quan $f=1$, la solució dóna la distància amb signe des de $\partial \Omega$.

## Potencial electromagnètic

El significat físic de l'equació eikonal està relacionat amb la fórmula
$\mathbf {E} =-\nabla V,$
on $\mathbf {E}$ és la intensitat del camp elèctric, i $V$ és el potencial elèctric. Hi ha una equació similar per al potencial de velocitat en el flux de fluid i la temperatura en la transferència de calor. El significat físic d'aquesta equació a l'exemple electromagnètic és que qualsevol càrrega de la regió s'empeny per moure's en angle recte amb les línies de potencial constant, i al llarg de línies de força determinades pel camp del vector E i el signe de la càrrega.
L'òptica de raigs i l'electromagnetisme estan relacionats pel fet que l'equació eikonal dóna una segona fórmula electromagnètica de la mateixa forma que l'equació de potencial anterior on la línia de potencial constant s'ha substituït per una línia de fase constant i les línies de força s'han substituït. per vectors normals que surten de la línia de fase constant en angle recte. La magnitud d'aquests vectors normals ve donada per l'arrel quadrada de la permitivitat relativa. La línia de fase constant es pot considerar la vora d'una de les ones de llum que avança (front d'ona). Els vectors normals són els raigs que la llum viatja cap avall en l'òptica de raigs.

## Algorismes computacionals

Des de la dècada de 1990 s'han desenvolupat diversos algorismes ràpids i eficients per resoldre l'equació eikonal. Molts d'aquests algorismes s'aprofiten dels algorismes desenvolupats molt abans per als problemes de camí més curt en gràfics amb longituds d'arestes no negatives. Aquests algorismes aprofiten la causalitat proporcionada per la interpretació física i solen discretitzar el domini mitjançant una malla o una graella regular i calculen la solució en cada punt discretitzat. Kimmel i Sethian van introduir els solucionadors Eikonal en superfícies triangulades el 1998.
El mètode de marxa ràpida (FMM) de Sethian va ser el primer algorisme "ràpid i eficient" creat per resoldre l'equació d'Eikonal. La descripció original discretitza el domini $\Omega \subset \mathbb {R} ^{n}$ en una graella regular i "marxa" la solució des de valors "coneguts" a les regions no descobertes, reflectint precisament la lògica de l'algorisme de Dijkstra. Si $\Omega$ està discretitzat i té $M$ punts de malla, llavors la complexitat computacional és $O(M\log M)$ on el $\log$ El terme prové de l'ús d'un munt (normalment binari). Es poden prescriure una sèrie de modificacions a FMM, ja que es classifica com a mètode d'establiment d'etiquetes. A més, s'ha generalitzat FMM per operar en malles generals que discretitzen el domini.
Els mètodes de correcció d'etiquetes com l'algorisme de Bellman-Ford també es poden utilitzar per resoldre l'equació d'Eikonal discretitzada també amb nombroses modificacions permeses (p. ex. "Etiquetes petites primer" o "Etiquetes grans per darrer" ). També s'han desenvolupat mètodes de dues cues que són essencialment una versió de l'algorisme de Bellman-Ford, excepte que s'utilitzen dues cues amb un llindar que s'utilitza per determinar a quina cua s'ha d'assignar un punt de graella en funció de la informació local.
Els algorismes d'escombrat com el mètode d'escombrat ràpid (FSM) són molt eficients per resoldre equacions d'Eikonal quan les corbes característiques corresponents no canvien de direcció molt sovint. Aquests algorismes corregeixen l'etiqueta, però no fan ús d'una cua ni d'un munt, sinó que prescriuen diferents ordres perquè els punts de la quadrícula s'actualitzin i s'iterin a través d'aquests ordenaments fins a la convergència. Es van introduir algunes millores com ara "bloquejar" els punts de la quadrícula durant un escombrat si no rep una actualització, però en quadrícules molt refinades i espais de dimensions superiors encara hi ha una gran sobrecàrrega a causa d'haver de passar per tots els punts de la quadrícula. S'han introduït mètodes paral·lels que intenten descompondre el domini i realitzar un escombrat a cada subconjunt descompost. La implementació paral·lela de Zhao descompon el domini en $n$ -dimensionals i després executa un FSM individual a cada subconjunt. La implementació paral·lela de Detrixhe també descompon el domini, però paral·lelitza cada escombrat individual perquè els processadors siguin responsables d'actualitzar els punts de la quadrícula en un $(n-1)$ hiperpla -dimensional fins que tot el domini estigui completament escombrat.
També s'han introduït mètodes híbrids que aprofiten l'eficiència de FMM amb la senzillesa de FSM. Per exemple, el Mètode de cèl·lules Heap (HCM) descompon el domini en cel·les i realitza FMM al domini cel·lular, i cada vegada que s'actualitza una "cel·la" es realitza FSM al domini de punt de graella local que es troba dins d'aquesta cel·la. També s'ha desenvolupat una versió paral·lelitzada d'HCM.

## Aplicacions

* Una aplicació concreta és el càlcul de l'atenuació de les ones de ràdio a l'atmosfera.
* Trobar la forma a partir de l'ombrejat en visió per ordinador.
* Òptica geomètrica
* Problemes continus del camí més curt
* Segmentació d'imatges
* Estudi de la forma d'un gra de coet propulsor sòlid

## Referències

* ↑ Evans, L. C.. Partial Differential Equations (en anglès). 19, p. 93 (AMS Graduate Texts in Mathematics).
* ↑ Dimassi, Mouez. Spectral asymptotics in the semi-classical limit (en anglès). Cambridge University Press, 1999 (London Math. Society Lecture Notes 268.). ISBN 0-521-66544-2.
* ↑ Bruns, Heinrich. Das Eikonal (en anglès). S. Hirzel, 1895.
* ↑ Hamilton, William Rowan Transactions of the Royal Irish Academy, 15, 1828, pàg. 69–174.
* ↑ Chacon, A.; Vladimirsky, A. SIAM Journal on Scientific Computing, 34, 2, 2012, pàg. A547–A578. arXiv: 1110.6220. Bibcode: 2012SJSC...34A.547C. DOI: 10.1137/10080909X.
* 1 2 Kimmel, R.; Sethian, J. A. Proceedings of the National Academy of Sciences, 95, 15, 1998, pàg. 8431–8435. Bibcode: 1998PNAS...95.8431K. DOI: 10.1073/pnas.95.15.8431. PMC: 21092. PMID: 9671694 [Consulta: free].
* 1 2 Bronstein, A. M.; Bronstein, M. M.; Kimmel, R. Journal of Computational Physics, 225, 1, 2007, pàg. 771–784. Bibcode: 2007JCoPh.225..771B. DOI: 10.1016/j.jcp.2007.01.009.
* ↑ Sethian, J. A.; Vladimirsky, A. Proc. Natl. Acad. Sci. USA, 97, 11, 2000, pàg. 5699–5703. Bibcode: 2000PNAS...97.5699S. DOI: 10.1073/pnas.090060097. PMC: 18495. PMID: 10811874 [Consulta: free].
* ↑ Yershov, D. S.; LaValle, S. M. Advanced Robotics, 26, 17, 2012, pàg. 2065–2085. DOI: 10.1080/01691864.2012.729559.
* ↑ Sethian, J. A. Proc. Natl. Acad. Sci., 93, 4, 1996, pàg. 1591–1595. Bibcode: 1996PNAS...93.1591S. DOI: 10.1073/pnas.93.4.1591. PMC: 39986. PMID: 11607632 [Consulta: free].
* ↑ Tsitsiklis, J. N. IEEE Trans. Autom. Control, 40, 9, 1995, pàg. 1528–1538. DOI: 10.1109/9.412624.
* ↑ Sethian, J. A. Proc. Natl. Acad. Sci., 93, 4, 1996, pàg. 1591–1595. Bibcode: 1996PNAS...93.1591S. DOI: 10.1073/pnas.93.4.1591. PMC: 39986. PMID: 11607632 [Consulta: free].
* ↑ Tsitsiklis, J. N. IEEE Trans. Autom. Control, 40, 9, 1995, pàg. 1528–1538. DOI: 10.1109/9.412624.
* ↑ Kimmel, R.; Sethian, J. A. Proceedings of the National Academy of Sciences, 95, 15, 1998, pàg. 8431–8435. Bibcode: 1998PNAS...95.8431K. DOI: 10.1073/pnas.95.15.8431. PMC: 21092. PMID: 9671694 [Consulta: free].
* ↑ Bronstein, A. M.; Bronstein, M. M.; Kimmel, R. Journal of Computational Physics, 225, 1, 2007, pàg. 771–784. Bibcode: 2007JCoPh.225..771B. DOI: 10.1016/j.jcp.2007.01.009.
* ↑ Sethian, J. A.; Vladimirsky, A. Proc. Natl. Acad. Sci. USA, 97, 11, 2000, pàg. 5699–5703. Bibcode: 2000PNAS...97.5699S. DOI: 10.1073/pnas.090060097. PMC: 18495. PMID: 10811874 [Consulta: free].
* ↑ Yershov, D. S.; LaValle, S. M. Advanced Robotics, 26, 17, 2012, pàg. 2065–2085. DOI: 10.1080/01691864.2012.729559.
* 1 2 Chacon, A.; Vladimirsky, A. SIAM Journal on Scientific Computing, 34, 2, 2012, pàg. A547–A578. arXiv: 1110.6220. Bibcode: 2012SJSC...34A.547C. DOI: 10.1137/10080909X.
* ↑ Bertsekas, D. P. Networks, 23, 8, 1993, pàg. 703–709. DOI: 10.1002/net.3230230808.
* ↑ Bertsekas, D. P.; Guerriero, F.; Musmanno, R. Journal of Optimization Theory and Applications, 88, 2, 1996, pàg. 297–320. DOI: 10.1007/BF02192173.
* ↑ Bak, S.; McLaughlin, J.; Renzi, D. SIAM Journal on Scientific Computing, 32, 5, 2010, pàg. 2853–2874. Bibcode: 2010SJSC...32.2853B. DOI: 10.1137/090749645.
* ↑ Zhao, H. Math. Comp., 74, 250, 2004, pàg. 603–627. DOI: 10.1090/S0025-5718-04-01678-3 [Consulta: free].
* ↑ Chacon, A.; Vladimirsky, A. SIAM Journal on Scientific Computing, 34, 2, 2012, pàg. A547–A578. arXiv: 1110.6220. Bibcode: 2012SJSC...34A.547C. DOI: 10.1137/10080909X.
* ↑ Bak, S.; McLaughlin, J.; Renzi, D. SIAM Journal on Scientific Computing, 32, 5, 2010, pàg. 2853–2874. Bibcode: 2010SJSC...32.2853B. DOI: 10.1137/090749645.
* ↑ Zhao, H. J. Comput. Math., 25, 4, 2007, pàg. 421–429. JSTOR: 43693378.
* ↑ Detrixhe, M.; Gibou, F.; Min, C. Journal of Computational Physics, 237, 2013, pàg. 46–55. Bibcode: 2013JCoPh.237...46D. DOI: 10.1016/j.jcp.2012.11.042.
* ↑ Chacon, A.; Vladimirsky, A. SIAM Journal on Scientific Computing, 34, 2, 2012, pàg. A547–A578. arXiv: 1110.6220. Bibcode: 2012SJSC...34A.547C. DOI: 10.1137/10080909X.
* ↑ Chacon, A.; Vladimirsky, A. SIAM Journal on Scientific Computing, 37, 1, 2015, pàg. A156–A180. arXiv: 1306.4743. Bibcode: 2015SJSC...37A.156C. DOI: 10.1137/12088197X.