Eikonal ekvation

En eikonal ekvation (från grekiska εἰκών, bild) är en icke-linjär första ordningens partiell differentialekvation som man stöter på i problem med vågutbredning .

Den klassiska eikonalekvationen i geometrisk optik är en differentialekvation av formen

$|\nabla u(x)|=n(x)$

 

 

 

 

()

där $x$ ligger i en öppen delmängd av $\mathbb {R} ^{n}$ , $n(x)$ är en positiv funktion, $\nabla$ anger gradienten och $|\cdot |$ är den euklidiska normen . Funktionen $n$ ges och man söker lösningar $u$ . I samband med geometrisk optik är funktionen $n$ mediets brytningsindex .

Mer generellt är en ekonal ekvation en ekvation av formen

$H(x,\nabla u(x))=0$

 

 

 

 

()

där $H$ är en funktion av $2n$ variabler. Här ges funktionen ${\displaystyle H} , och$$u$ är lösningen. Om $H(x,y)=|y|-n(x)$ , då blir ekvation ( 2 ) ( 1 ).

Eikonala ekvationer uppstår naturligt i WKB-metoden och studiet av Maxwells ekvationer . Eikonala ekvationer ger en länk mellan fysisk (våg)optik och geometrisk (stråle)optik .

En snabb beräkningsalgoritm för att approximera lösningen till eikonalekvationen är den snabba marschmetoden .

Historia

Termen "eikonal" användes först i kontexten av geometrisk optik av Heinrich Bruns . Den faktiska ekvationen dyker dock upp tidigare i William Rowan Hamiltons framträdande arbete om geometrisk optik .

Fysisk tolkning

Kontinuerliga problem med kortaste vägen

Antag att $\Omega$ är en öppen mängd med lämpligt jämn gräns $\partial \Omega$ . Lösningen till den ekonala ekvationen

$\left|\nabla u(x)\right|={\frac {1}{f(x)}}{\text{ för }} x\in \Omega \subset \mathbb {R} ^{n},$

$u(x)=q(x){\text{ för } }x\in \partial \Omega$

kan tolkas som den minimala tid som krävs för att resa från $x$ till $\partial \Omega$ , där $f:{\bar {\Omega }}\to (0,+\infty )$ är färdhastigheten, och $q:\partial \Omega \to [0,+\infty )$ är en utgångstidsstraff. (Alternativt kan detta framställas som en minimal kostnad för att avsluta genom att göra högersidan $C(x)/f(x)$ och $q$ till en utträdeskostnadsavgift.)

I specialfallet när $f=1$ , ger lösningen teckenavståndet från $\partial \Omega$ .

Genom att anta att $\nabla u(x)$ finns på alla punkter är det lätt att bevisa att $u(x)$ motsvarar ett tidsoptimalt kontrollproblem med Bellmans optimalitetsprincip och en Taylor-expansion. Tyvärr är det inte garanterat att $\nabla u(x)$ finns på alla punkter, och mer avancerade tekniker är nödvändiga för att bevisa detta. Detta ledde till utvecklingen av viskositetslösningar på 1980-talet av Pierre-Louis Lions och Michael G. Crandall , och Lions vann en Fields-medalj för sina insatser.

Elektromagnetisk potential

Den fysiska innebörden av ekonala ekvationen är relaterad till formeln

$\mathbf {E} =-\nabla V,$

där $\mathbf {E}$ är den elektriska fältstyrkan, och $V$ är den elektriska potentialen. Det finns en liknande ekvation för hastighetspotential i vätskeflöde och temperatur i värmeöverföring. Den fysiska innebörden av denna ekvation i det elektromagnetiska exemplet är att varje laddning i området trycks för att röra sig i rät vinkel mot linjerna [ med konstant potential, och längs kraftlinjer som bestäms av fältet för E -vektorn och tecken på anklagelsen.

Stråloptik och elektromagnetism hänger samman med det faktum att den ekonala ekvationen ger en andra elektromagnetisk formel av samma form som potentialekvationen ovan där linjen med konstant potential har ersatts av en linje med konstant fas, och kraftlinjerna har ersatts genom att normala vektorer kommer ut ur konstantfaslinjen i rät vinkel. Storleken på dessa normalvektorer ges av kvadratroten av den relativa permittiviteten. Linjen med konstant fas kan betraktas som kanten på en av de framåtgående ljusvågorna ( vågfront ). De normala vektorerna är de strålar som ljuset färdas ner i stråloptik.

Beräkningsalgoritmer

Flera snabba och effektiva algoritmer för att lösa ekonalekvationen har utvecklats sedan 1990-talet. Många av dessa algoritmer drar fördel av algoritmer som utvecklats mycket tidigare för kortaste vägproblem på grafer med icke-negativa kantlängder. Dessa algoritmer drar fördel av kausaliteten som tillhandahålls av den fysiska tolkningen och diskretiserar typiskt domänen med hjälp av ett mesh eller vanligt rutnät och beräknar lösningen vid varje diskretiserad punkt. Eikonallösare på triangulerade grenrör är.

Sethians snabbmarschmetod (FMM) var den första "snabba och effektiva" algoritmen som skapades för att lösa Eikonal-ekvationen. Den ursprungliga beskrivningen diskretiserar domänen $\Omega \subset \mathbb {R} ^{n}$ till ett vanligt rutnät och "marscherar" lösningen från "kända" värden till de oupptäckta regionerna, exakt speglar logiken i Dijkstras algoritm . Om $\Omega$ är diskretiserad och har $M$ meshpoints, då är beräkningskomplexiteten $O(M\log M)$ där $\ log$ term kommer från användningen av en heap (vanligtvis binär). Ett antal modifieringar kan föreskrivas för FMM eftersom det klassificeras som en märkningssätt. Dessutom har FMM generaliserats för att fungera på allmänna nät som diskretiserar domänen.

Etikettkorrigeringsmetoder som Bellman–Ford-algoritmen kan också användas för att lösa den diskretiserade Eikonal-ekvationen också med många modifieringar tillåtna (t.ex. "Small Labels First" eller "Large Labels Last"). Två-kömetoder har också utvecklats som i huvudsak är en version av Bellman-Ford-algoritmen förutom att två köer används med en tröskel som används för att bestämma vilken kö en gridpoint ska tilldelas baserat på lokal information.

Svepningsalgoritmer som den snabba svepmetoden (FSM) är mycket effektiva för att lösa Eikonal-ekvationer när motsvarande karakteristiska kurvor inte ändrar riktning särskilt ofta. Dessa algoritmer är etikettkorrigerande men använder sig inte av en kö eller hög, utan föreskriver istället olika ordningsföljder för att rutnätspunkterna ska uppdateras och itererar genom dessa ordningsföljder tills de konvergerar. Vissa förbättringar infördes som att "låsa" rutnätspunkter under ett svep om inte får en uppdatering, men på mycket raffinerade rutnät och högre dimensionella utrymmen finns det fortfarande en stor overhead på grund av att man måste passera genom varje rutnätspunkt. Parallella metoder har introducerats som försöker dekomponera domänen och utföra svepning på varje nedbruten delmängd. Zhaos parallella implementering bryter ner domänen i $n$ -dimensionella delmängder och kör sedan en individuell FSM på varje delmängd. Dextrixhes parallella implementering bryter också ner domänen, men parallelliserar varje enskilt svep så att processorer är ansvariga för att uppdatera gridpoints i ett ( $\displaystyle (n-1)}$ -dimensionellt hyperplan tills hela domänen är helt svept.

Hybridmetoder har också introducerats som drar fördel av FMM:s effektivitet med FSM:s enkelhet. Till exempel sönderdelar Heap Cell Method (HCM) domänen till celler och utför FMM på celldomänen, och varje gång en "cell" uppdateras utförs FSM på den lokala gridpoint-domänen som ligger inom den cellen. En parallelliserad version av HCM har också utvecklats.

Numerisk uppskattning

Antag för enkelhets skull att $\Omega$ diskretiseras till ett enhetligt rutnät med mellanrum $h_{x}$ och $h_{y}$ i x- respektive y-riktningarna.

2D approximation på ett kartesiskt rutnät

Antag att en rutnätspunkt $x_{ij}$ har värdet $U_{ij}=U(x_{ij})\ ungefär u(x_{ij})$ . Ett första ordningens schema för att approximera de partiella derivaten är

$\max \left(D_{ij}^{-x}U,-D_{ij}^{+x}U,0\right)^{2}+\max \left(D_{ij}^{-y}U ,-D_{ij}^{+y}U,0\right)^{2}\ =\ {\frac {1}{f_{ij}^{2}}}$

var

$u_{x}(x_{ij})\approx D_{ij}^{\pm x}U={\frac {U_{i\pm 1,j}-U_{ij}}{\pm h_ {x}}}\quad {\text{ och }}\quad u_{y}(x_{ij})\approx D_{ij}^{\pm y}U={\frac {U_{i,j\ pm 1}-U_{ij}}{\pm h_{y}}}.$

På grund av de konsekventa, monotona och kausala egenskaperna hos denna diskretisering är det lätt att visa att om $U_{X}=\min( U_{i-1,j},U_{i+1,j})$ och $U_{Y}=\min( U_{i,j-1},U_{i,j+1})$ och $|U_{X}/h_{x}-U_{Y}/h_{y}|\leq 1/f_{ij}$ sedan

$\left({\frac {U_{ij}-U_{X}}{ h_{x}}}\right)^{2}+\left({\frac {U_{ij}-U_{Y}}{h_{y}}}\right)^{2}={\frac { 1}{f_{ij}^{2}}}$

som kan lösas som en kvadratisk. I begränsningsfallet $h_{x}=h_{y}=h$ reduceras detta till

$U_{ij}={\frac {U_{X}+U_{Y}}{2}}+{\frac {1}{2}}{\sqrt {(U_{X}+U_{Y })^{2}-2\left(U_{X}^{2}+U_{Y}^{2}-{\frac {h^{2}}{f_{ij}^{2}}} \höger)}}.$

Denna lösning kommer alltid att finnas så länge som $|U_{X}-U_{Y}|\leq {\sqrt {2}}h/f_{ij}$ är uppfylld och är större än båda, $U_{X}$ och $U_{Y}$ , så länge som $|U_{X}-U_{Y}|\leq h/f_{ij}$ .

Om ${\displaystyle |U_{X}/h_{x}-U_{Y}/h_{y}|\geq 1/f_{ij}} , en lägre$ dimensionell uppdatering måste utföras genom att anta en av de partiella derivatorna är $0$ :

$U_{ij}=\min \left(U_{X}+{\frac {h_{x}}{f_{ij}}},U_{Y}+{\frac {h_{y}}{ f_{ij}}}\right).$

n -D approximation på ett kartesiskt rutnät

Antag att en rutnätspunkt $x$ har värdet $U=U(x)\approx u(x)$ . Genom att upprepa samma steg som i $n=2$ kan vi använda ett första ordningens schema för att approximera de partiella derivatorna. Låt $U_{i}$ vara minimum av värdena för grannarna i ${\displaystyle \pm \mathbf {e} _{i}}-$ riktningarna, där $\mathbf {e} _{i}$ är en standardenhetsbasisvektor . Uppskattningen är då

$\sum _{j=1}^{n}\left({\frac {U-U_{j}}{h}}\right)^{2}\ =\ {\frac {1}{ f_{i}^{2}}}.$

Att lösa denna andragradsekvation för $U$ ger:

$U={\frac {1}{n}}\sum _{j=1}^{n}U_{j}+{\frac {1}{n}}{\sqrt {\left(\ summa _{j=1}^{n}U_{j}\höger)^{2}-n\left(\summa _{j=1}^{n}U_{j}^{2}-{\ frac {h^{2}}{f_{i}^{2}}}\right)}}.$

Om diskriminanten i kvadratroten är negativ måste en lägre dimensionell uppdatering utföras (dvs en av de partiella derivatorna är {\ $displaystyle 0} )$ .

Om $n=2$ utför sedan den endimensionella uppdateringen

$U={\frac {h}{f_{i}}}+\min _{j=1,\ldots ,n}U_{j}.$

Om $n\geq 3$ utför sedan en $n-1$ dimensionsuppdatering med värdena $\{U_ {1},\ldots ,U_{n}\}\setminus \{U_{i}\}$ för varje $i=1,\ldots ,n$ och välj den minsta.

Matematisk beskrivning

En ekonal ekvation är en av formerna

$H(x,\nabla u(x))=0$

$u(0,x')=u_{0}(x'),{\text{ för }}x=(x_{1},x')$

Planet $x=(0,x')$ kan ses som utgångsvillkoret genom att tänka på $x_{1}$ som $t.$ Vi skulle också kunna lösa ekvationen på en delmängd av detta plan, eller på en krökt yta, med uppenbara modifikationer.

Eikonalekvationen dyker upp i geometrisk optik , vilket är ett sätt att studera lösningar av vågekvationen ${\displaystyle c^{2}|\nabla _{x}u|^{2}=|\partial _{t}u|^{2}} , där$ c $\displaystyle c(x) }$ och $u(x,t)$ . Inom geometrisk optik beskriver den ekonala ekvationen vågornas fasfronter. Under rimlig hypotes om de "initiella" data, medger ekonalekvationen en lokal lösning, men en global jämn lösning (t.ex. en lösning för alla tider i det geometriska optikfallet) är inte möjlig. Anledningen är att kaustik kan utvecklas. I det geometriska optikfallet betyder detta att vågfronter korsar varandra.

Vi kan lösa den ekonala ekvationen med hjälp av karakteristikmetoden. Man måste införa den "icke-karakteristiska" hypotesen $\partial _{p_{1}}H(x,p)\neq 0$ längs den initiala hyperytan $x=(0,x')$ , där H = H ( x , p ) och p = ( p ₁ ,..., p _n ) är variabeln som ersätts av ∇ u . Här x = ( x ₁ ,..., x _n ) = ( t , x ').

Lös först problemet $H(x,\xi (x))=0$ , $\ xi (x)=\nabla u(x),x\in H$ . Detta görs genom att definiera kurvor (och värden på $\xi$ på dessa kurvor) som

${\dot {x}}(s)=\nabla _{\xi }H(x(s),\xi (s)),\;\;\;\;{\dot {\xi } }(s)=-\nabla _{x}H(x(s),\xi (s)).$

${\displaystyle x(0)=x_{0},\;\;\;\;\xi (x(0))=\nabla u(x(0)).} Observera att även innan vi har en$ lösning $u$ , vi vet $\nabla u(x)$ för $x=(0,x')$ på grund av vår ekvation för ${ \displaystyle H}$ .

Att dessa ekvationer har en lösning för något intervall $0\leq s<s_{1}$ följer av standard ODE-satser (med den icke-karakteristiska hypotesen). Dessa kurvor fyller ut en öppen uppsättning runt planet $x=(0,x')$ . Således definierar kurvorna värdet på $\xi$ i en öppen uppsättning kring vårt initiala plan. När den väl har definierats som sådan är det lätt att se med kedjeregeln att $\partial _{s}H(x(s),\xi (s) )=0$ , och därför $H=0$ längs dessa kurvor.

Vi vill att vår lösning $u$ ska uppfylla ${\displaystyle \nabla u=\xi } ,$ eller mer specifikt, för varje $s$ , $(\nabla u)(x(s))=\xi (x(s)).$ Om vi ​​antar att detta är möjligt under en minut, för vilken lösning som helst $u(x)$ vi måste ha

${\frac {d}{ds}}u(x( s))=\nabla u(x(s))\cdot {\dot {x}}(s)=\xi \cdot {\frac {\partial H}{\partial \xi }},$

och därför

$u(x(t))=u(x(0))+\int _{0}^{t}\xi (x(s))\cdot {\dot {x}}(s)\ ,ds.$

Med andra ord kommer lösningen $u$ att ges i en omgivning av initialplanet av en explicit ekvation. Men eftersom de olika vägarna $x(t)$ , med utgångspunkt från olika initiala punkter kan korsas, kan lösningen bli flervärdig, vid vilken punkt vi har utvecklat kaustik. Vi har också (även innan vi visade att $u$ är en lösning)

$\xi (x(t))=\xi (x(0))-\int _{0}^{t}\nabla _{x}H(x(s),\xi (x(s) )))\,ds.$

Det återstår att visa att ${\displaystyle \xi } ,$ som vi har definierat i ett område av vårt initiala plan, är gradienten för någon funktion u {\ $u}$ . Detta kommer att följa om vi visar att vektorfältet $\xi$ är krullfritt. Betrakta den första termen i definitionen av $\xi$ . Denna term, $\xi (x(0))=\nabla u(x(0))$ är krullfri eftersom den är en funktions gradient . När det gäller den andra termen, noterar vi

${\frac {\partial ^{2}}{\partial x_{k}\,\partial x_{j}}}H={\frac {\partial ^{2}}{\partial x_{j }\,\partial x_{k}}}H.$

Resultatet följer.

Ansökningar

• En konkret tillämpning är beräkningen av radiovågsdämpning i atmosfären .
• Hitta formen från skuggning i datorseende.
• Geometrisk optik
• Kontinuerliga kortaste vägproblem
• Bildsegmentering
• Studie av formen för ett fast drivmedelsraketkorn

Se även

• Hamilton–Jacobi–Bellmans ekvation
• Hamilton–Jacobis ekvation
• Fermats princip
• Enkelriktad vågekvation

Vidare läsning

•   Paris, DT; Hurd, FK (1969). Grundläggande elektromagnetisk teori . McGraw-Hill. s. 383–385. ISBN 0-07-048470-8 .
•   Arnold, VI (2004). Föreläsningar om partiella differentialekvationer (2:a uppl.). Springer. s. 2–3. ISBN 3-540-40448-1 .

externa länkar

• Den linjäriserade ekonala ekvationen
• Engelsk översättning av "Das Eikonal" av Heinrich Bruns