アイコナール方程式

Non-linear partial differential equation encountered in problems of wave propagation

アイコナール方程式（ギリシャ語のεἰκώνに由来、図^{[1] [2]}）は、波動伝播の問題で遭遇する非線形 1階偏微分方程式です

幾何光学における古典的なアイコナール方程式は、次のような微分方程式である。

${\displaystyle |\nabla u(x)|=n(x)}$

1

ここで、はの開集合にあり、は正関数、 勾配 を表し、はユークリッドノルムです。関数は与えられ、解を求めます。幾何光学の文脈では、関数は媒質の屈折率です ${\displaystyle x}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle n(x)}$ ${\displaystyle \nabla }$ ${\displaystyle |\cdot |}$ ${\displaystyle n}$ ${\displaystyle u}$ ${\displaystyle n}$

より一般的には、アイコナール方程式は次の形式の方程式である。

${\displaystyle H(x,\nabla u(x))=0}$

2

ここでは変数の関数です。ここで関数 は与えられており、 は解です。 の場合、式( 2 )は式( 1 ) になります ${\displaystyle H}$ ${\displaystyle 2n}$ ${\displaystyle H}$ ${\displaystyle u}$ ${\displaystyle H(x,y)=|y|-n(x)}$

アイコナール方程式はWKB法^[3]やマクスウェル方程式の研究で自然に生じる。^{[4]アイコナール方程式は}物理（波動）光学と幾何（光線）光学を結びつける。

アイコナール方程式の解を近似する高速計算アルゴリズムの 1 つに、高速マーチング法があります。

歴史

「アイコナール」という用語は、ハインリッヒ・ブルンスによって幾何光学の文脈で初めて使用されました。^{[5]しかし、実際の式は、}ウィリアム・ローワン・ハミルトンの幾何光学に関する重要な著作に以前から登場しています。^[6]

物理的解釈

連続最短経路問題

が適切に滑らかな境界を持つ開集合であると仮定する。アイコナール方程式の解は ${\displaystyle \Omega }$ ${\displaystyle \partial \Omega }$

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

${\displaystyle u(x)=q(x){\text{ for }}x\in \partial \Omega }$

は、からまでの移動に必要な最小時間として解釈できます。ここで、は移動速度、 は退出時間ペナルティです。（あるいは、右側のと退出コストペナルティを作成することで、これは最小退出コストとして提示することもできます。） ${\displaystyle x}$ ${\displaystyle \partial \Omega }$ ${\displaystyle f:{\bar {\Omega }}\to (0,+\infty )}$ ${\displaystyle q:\partial \Omega \to [0,+\infty )}$ ${\displaystyle C(x)/f(x)}$ ${\displaystyle q}$

の特別な場合では、解はからの 符号付き距離を与える。^[7] ${\displaystyle f=1}$ ${\displaystyle \partial \Omega }$

がすべての点において存在すると仮定すれば、ベルマンの最適性原理とテイラー展開を用いて、が時間最適制御問題に対応することを証明するのは容易である。 ^[8]残念ながら、がすべての点において存在するとは保証されておらず、これを証明するにはより高度な技術が必要となる。このことが、1980年代にピエール＝ルイ・ライオンズとマイケル・G・クランドールによる粘性解法の開発につながり、^[9]ライオンズはその貢献によりフィールズ賞を受賞した。 ${\displaystyle \nabla u(x)}$ ${\displaystyle u(x)}$ ${\displaystyle \nabla u(x)}$

電磁ポテンシャル

アイコナール方程式の物理的な意味は、次の式に関連しています

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

ここで、は電界強度、は電位です。流体の流れにおける速度ポテンシャルと熱伝達における温度についても同様の式があります。電磁気学の例におけるこの式の物理的な意味は、領域内の電荷は定電位線（^{[説明が必要]）}に対して直角に、そしてEベクトルの場と電荷の符号によって決まる力線に沿って移動するということです。 ${\displaystyle \mathbf {E} }$ ${\displaystyle V}$

光線光学と電磁気学は、アイコナール方程式が上記のポテンシャル方程式と同じ形の第二の電磁気方程式を与えるという事実によって関連しています。この方程式では、定電位線が定位相線に置き換えられ、力線が定位相線から直角に伸びる法線ベクトルに置き換えられています。これらの法線ベクトルの大きさは、比誘電率の平方根によって与えられます。定位相線は、進行する光波（波面）の端と考えることができます。法線ベクトルは、光線光学において光が下方に伝わる光線です。

計算アルゴリズム

1990年代以降、アイコナール方程式を解くための高速で効率的なアルゴリズムがいくつか開発されてきました。これらのアルゴリズムの多くは、非負の辺長を持つグラフ上の最短経路問題のためにずっと以前に開発されたアルゴリズムを利用しています。 ^[10]これらのアルゴリズムは、物理的解釈によって提供される因果関係を利用し、通常はメッシュ^{[11] [12] [13] [14 ]}または正方格子^{[15] [16]}を使用して領域を離散化し、各離散化された点における解を計算します。三角形状の曲面上のアイコナールソルバーは、1998年にKimmelとSethianによって導入されました。^{[11] [12]}

セシアンの高速マーチング法（FMM）^{[15] [16]}は、アイコナール方程式を解くために考案された最初の「高速かつ効率的な」アルゴリズムでした。当初の記述では、領域を規則的なグリッドに離散化し、解を「既知の」値から未発見の領域へと「マーチング」するという、ダイクストラのアルゴリズムのロジックを正確に反映していました。離散化されメッシュポイントを持つ場合、計算複雑度はヒープ（通常は2値）の使用に由来します。FMMはラベル設定法に分類されるため、様々な修正が可能です。さらに、FMMは領域を離散化する一般的なメッシュ上で動作するように一般化されています。^{[11] [12] [13] [14]} ${\displaystyle \Omega \subset \mathbb {R} ^{n}}$ ${\displaystyle \Omega }$ ${\displaystyle M}$ ${\displaystyle O(M\log M)}$ ${\displaystyle \log }$

ベルマン・フォード法などのラベル修正法も、離散化アイコナール方程式を解くために用いることができ、様々な修正が可能である（例えば、「小さなラベルを優先する」^{[10] [17]}や「大きなラベルを最後に置く」^{[10] [18]}など）。2キュー法も開発されており^[19]、これは基本的にベルマン・フォード法の一種であるが、2つのキューを用い、局所情報に基づいてグリッドポイントをどのキューに割り当てるかを決定する閾値を用いる。

高速スイープ法（FSM）^[20]などのスイープアルゴリズムは、対応する特性曲線の方向があまり変化しない場合、アイコナール方程式を解くのに非常に効率的です。^[10]これらのアルゴリズムはラベル補正を行いますが、キューやヒープは使用せず、代わりに更新するグリッドポイントの順序を規定し、収束するまでこれらの順序を反復します。スイープ中に更新が行われない場合にグリッドポイントを「ロック」する^[19]などの改良点が導入されましたが、高度に細分化されたグリッドや高次元空間では、すべてのグリッドポイントを通過する必要があるため、依然として大きなオーバーヘッドが存在します。領域を分解し、分解された各サブセットに対してスイープを実行する並列手法が導入されています。Zhaoの並列実装では、領域を次元サブセットに分解し、各サブセットに対して個別のFSMを実行します。^[21] Detrixheの並列実装もドメインを分解しますが、個々のスイープを並列化して、ドメイン全体が完全にスイープされるまで、プロセッサが次元超平面のグリッドポイントを更新する責任を負います。 ^[22] ${\displaystyle n}$ ${\displaystyle (n-1)}$

FMMの効率性とFSMの簡便性を組み合わせたハイブリッド手法も導入されている。例えば、ヒープセル法（HCM）は、領域をセルに分割し、セル領域に対してFMMを実行する。そして、「セル」が更新されるたびに、そのセル内のローカルグリッドポイント領域に対してFSMを実行する。^[10] HCMの並列化バージョンも開発されている。^[23]

数値近似

簡単のため、x方向とy方向にそれぞれ 間隔と間隔を持つ均一な格子に離散化されていると仮定します ${\displaystyle \Omega }$ ${\displaystyle h_{x}}$ ${\displaystyle h_{y}}$

直交座標グリッド上の2D近似

格子点が値 を持つと仮定する。偏微分を近似する一次スキームは次の通りである。 ${\displaystyle x_{ij}}$ ${\displaystyle U_{ij}=U(x_{ij})\approx u(x_{ij})}$

${\displaystyle \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}}}}$

どこ

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

この離散化の一貫性、単調性、因果性により^[10]、そしてそしてならば、 ${\displaystyle U_{X}=\min(U_{i-1,j},U_{i+1,j})}$ ${\displaystyle U_{Y}=\min(U_{i,j-1},U_{i,j+1})}$ ${\displaystyle |U_{X}/h_{x}-U_{Y}/h_{y}|\leq 1/f_{ij}}$

${\displaystyle \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}}}}$

これは二次方程式として解くことができる。 の極限の場合、これは次のように簡約される。 ${\displaystyle h_{x}=h_{y}=h}$

${\displaystyle 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}}}\right)}}.}$

この解は、が満たされ、 および の両方よりも大きい限り、常に存在します。 また、 である限り存在します。 ${\displaystyle |U_{X}-U_{Y}|\leq {\sqrt {2}}h/f_{ij}}$ ${\displaystyle U_{X}}$ ${\displaystyle U_{Y}}$ ${\displaystyle |U_{X}-U_{Y}|\leq h/f_{ij}}$

の場合、偏導関数の1つが であると仮定して、低次元の更新を実行する必要があります。 ${\displaystyle |U_{X}/h_{x}-U_{Y}/h_{y}|\geq 1/f_{ij}}$ ${\displaystyle 0}$

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

n直交座標格子上の2次元近似

格子点の値が であると仮定します。 の場合と同じ手順を繰り返すことで、偏微分を近似するために1次スキームを使用できます。を 方向の近傍の値の最小値とし、 を標準単位基底ベクトルとします。近似は次のようになります ${\displaystyle x}$ ${\displaystyle U=U(x)\approx u(x)}$ ${\displaystyle n=2}$ ${\displaystyle U_{i}}$ ${\displaystyle \pm \mathbf {e} _{i}}$ ${\displaystyle \mathbf {e} _{i}}$

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

この二次方程式を解くと次のようになります。 ${\displaystyle U}$

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

平方根の判別式が負の場合、低次元の更新を実行する必要があります（つまり、偏導関数の 1 つが）。 ${\displaystyle 0}$

1次元更新を実行する場合 ${\displaystyle n=2}$

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

次に、すべての値を使用して次元の更新を実行し、最小のものを選択します。 ${\displaystyle n\geq 3}$ ${\displaystyle n-1}$ ${\displaystyle \{U_{1},\ldots ,U_{n}\}\setminus \{U_{i}\}}$ ${\displaystyle i=1,\ldots ,n}$

数学的記述

アイコナール方程式は、次の形式のいずれかです。

${\displaystyle H(x,\nabla u(x))=0}$

${\displaystyle u(0,x')=u_{0}(x'),{\text{ for }}x=(x_{1},x')}$

平面は、次のように考えることで初期条件と考えることができます。 また、明らかな修正を加えることで、この平面の部分集合上、または曲面上で方程式を解くこともできます ${\displaystyle x=(0,x')}$ ${\displaystyle x_{1}}$ ${\displaystyle t.}$

アイコナール方程式は幾何光学に現れます。幾何光学は、波動方程式 （ここでおよび）の解を研究する方法です。幾何光学において、アイコナール方程式は波の位相面を記述します。「初期」データに関する合理的な仮定の下では、アイコナール方程式は局所解を許容しますが、大域的に滑らかな解（例えば幾何光学の場合における全時間に対する解）は不可能です。これは、コースティックス（火線）が発生する可能性があるためです。幾何光学の場合、これは波面が交差することを意味します。 ${\displaystyle c^{2}|\nabla _{x}u|^{2}=|\partial _{t}u|^{2}}$ ${\displaystyle c(x)}$ ${\displaystyle u(x,t)}$

アイコナール方程式は特性法を用いて解くことができます。初期超曲面に沿って「非特性」仮説を課す必要があります。ここで、H  =  H ( x , p ) であり、 p  = ( p ₁ ,..., p _n ) は ∇ uに置き換えられる変数です。ここで、x  = ( x ₁ ,..., x _n ) = ( t , x ′ ) です。 ${\displaystyle \partial _{p_{1}}H(x,p)\neq 0}$ ${\displaystyle x=(0,x')}$

まず、問題 を解きます。これは、曲線（およびそれらの曲線上の の値）を次のように定義することによって行われます。 ${\displaystyle H(x,\xi (x))=0}$ ${\displaystyle \xi (x)=\nabla u(x),x\in H}$ ${\displaystyle \xi }$

${\displaystyle {\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)).}$ 解を得る前であっても、の方程式により がわかることに注意してください。 ${\displaystyle u}$ ${\displaystyle \nabla u(x)}$ ${\displaystyle x=(0,x')}$ ${\displaystyle H}$

これらの方程式がある区間で解を持つことは、標準的な常微分方程式の定理（非特性仮説を用いる）から明らかである。これらの曲線は平面 の周りの開集合を満たす。したがって、これらの曲線は、最初の平面 の周りの開集合における の値を定義する。このように定義すれば、連鎖律を用いて、したがってこれらの曲線に沿って であることが容易に分かる。 ${\displaystyle 0\leq s<s_{1}}$ ${\displaystyle x=(0,x')}$ ${\displaystyle \xi }$ ${\displaystyle \partial _{s}H(x(s),\xi (s))=0}$ ${\displaystyle H=0}$

我々は、解がを満たすことを望んでいます。より具体的には、 に対して、 です。これ が可能であると仮定すると、任意の解に対して、が成り立つはずです。 ${\displaystyle u}$ ${\displaystyle \nabla u=\xi }$ ${\displaystyle s}$ ${\displaystyle (\nabla u)(x(s))=\xi (x(s)).}$ ${\displaystyle u(x)}$

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

したがって

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

言い換えれば、解は初期平面の近傍において明示的な方程式によって与えられます。しかし、異なる初期点から始まる異なる経路が交差する可能性があるため、解は多値になる可能性があり、その時点でコースティクスを展開します。また、（が解であることを示す前であっても） ${\displaystyle u}$ ${\displaystyle x(t)}$ ${\displaystyle u}$

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

残っているのは、初期平面の近傍で定義した が、ある関数 の勾配であることを示すことです。これは、ベクトル場が回転しない（curl free）ことを示せば明らかです。 の定義の最初の項を考えてみましょう。この項 は関数の勾配であるため、回転しません。他の項については、次のことに留意してください。 ${\displaystyle \xi }$ ${\displaystyle u}$ ${\displaystyle \xi }$ ${\displaystyle \xi }$ ${\displaystyle \xi (x(0))=\nabla u(x(0))}$

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

結果は以下の通りです。

応用

• 具体的な応用としては、大気中の電波減衰の計算があります。
• コンピューター ビジョンで陰影から形状を見つける。
• 幾何光学
• 連続最短経路問題
• 画像セグメンテーション
• 固体燃料ロケット粒子の形状に関する研究

参照

• ハミルトン・ヤコビ・ベルマン方程式
• ハミルトン・ヤコビ方程式
• フェルマーの原理

参考文献

1. オックスフォード英語辞典. 第2版. 1989年. OEDオンライン. オックスフォード大学出版局. 2000年4月4日 http://dictionary.oed.com/cgi/entry/00292404
2. エヴァンス、LC 「偏微分方程式」AMS大学院数学テキスト第19巻93頁。
3. Dimassi, Mouez; Sjöstrand, Johannes (1999).半古典極限におけるスペクトル漸近解析. ロンドン数学会講演録268. ケンブリッジ大学出版局. ISBN 0-521-66544-2。
4. ラウフ、ジェフリー (2012)、「双曲型偏微分方程式と幾何光学」、数学大学院研究、133、アメリカ数学会、書誌コード:2012hpde.book.....R、ISBN 978-0-8218-7291-8
5. ブルンス、ハインリッヒ (1895). Das Eikonal . S. Hirzel
6. ハミルトン、ウィリアム・ローワン (1828). 「光線体系の理論」.アイルランド王立アカデミー紀要. 15 : 69–174 .
7. 酒井 隆. 「勾配が定数ノルムの関数を許容するリーマン多様体について」古代数学ジャーナル 19.1 (1996): 39-51.
8. Clawson, Z.; Chacon, A.; Vladimirsky, A. (2014). 「アイコナール方程式の因果領域制限」. SIAM Journal on Scientific Computing . 36 (5): A2478 – A2505 . arXiv : 1309.2884 . Bibcode :2014SJSC...36A2478C. doi :10.1137/130936531. S2CID  17226196.
9. Bardi, M.; Capuzzo-Dolcetta, I. (1997).ハミルトン・ヤコビ・ベルマン方程式の最適制御と粘性解ボストン: Birkhäuser. ISBN 0-8176-3640-4。
10. Chacon, A.; Vladimirsky, A. (2012). 「アイコナール方程式のための高速2スケール法」. SIAM Journal on Scientific Computing . 34 (2): A547 – A578 . arXiv : 1110.6220 . Bibcode :2012SJSC...34A.547C. doi :10.1137/10080909X. S2CID  6404391
11. Kimmel, R.; Sethian, JA (1998). 「多様体上の測地線経路の計算」. Proceedings of the National Academy of Sciences . 95 (15): 8431– 8435. Bibcode :1998PNAS...95.8431K. doi : 10.1073/pnas.95.15.8431 . PMC 21092. PMID 9671694  . 
12. Bronstein, AM; Bronstein, MM; Kimmel, R. (2007). 「パラメトリック3次元多様体における重み付き距離マップ計算」. Journal of Computational Physics . 225 (1): 771– 784. Bibcode :2007JCoPh.225..771B. doi :10.1016/j.jcp.2007.01.009.
13. Sethian, JA; Vladimirsky, A. (2000). 「非構造メッシュ上のアイコナール方程式および関連するハミルトン・ヤコビ方程式の高速解法」Proc. Natl. Acad. Sci. USA . 97 (11): 5699– 5703. Bibcode :2000PNAS...97.5699S. doi : 10.1073/pnas.090060097 . PMC 18495. PMID 10811874  . 
14. Yershov, DS; LaValle, SM (2012). 「単純ダイクストラ法とA*アルゴリズム：グラフから連続空間へ」. Advanced Robotics . 26 (17): 2065– 2085. doi :10.1080/01691864.2012.729559. S2CID  17573584.
15. Sethian, JA (1996). 「単調に前進する前線のための高速マーチングレベルセット法」Proc. Natl. Acad. Sci . 93 (4): 1591– 1595. Bibcode :1996PNAS...93.1591S. doi : 10.1073/pnas.93.4.1591 . PMC 39986. PMID  11607632 . 
16. Tsitsiklis, JN (1995). 「大域的最適軌道のための効率的なアルゴリズム」. IEEE Trans. Autom. Control . 40 (9): 1528– 1538. doi :10.1109/9.412624. hdl : 1721.1/3340 .
17. Bertsekas, DP (1993). 「最短経路のためのシンプルで高速なラベル修正アルゴリズム」. Networks . 23 (8): 703– 709. doi :10.1002/net.3230230808. hdl : 1721.1/3256 .
18. Bertsekas, DP; Guerriero, F.; Musmanno, R. (1996). 「最短経路のための並列非同期ラベル修正法」. Journal of Optimization Theory and Applications . 88 (2): 297– 320. doi :10.1007/BF02192173. hdl : 1721.1/3390 . S2CID  13172492.
19. Bak, S.; McLaughlin, J.; Renzi, D. (2010). 「高速スイープ法のいくつかの改良点」SIAM Journal on Scientific Computing . 32 (5): 2853– 2874. Bibcode :2010SJSC...32.2853B. doi :10.1137/090749645.
20. Zhao, H. (2004). 「アイコナール方程式の高速スイープ法」. Math. Comp . 74 (250): 603– 627. doi : 10.1090/S0025-5718-04-01678-3 .
21. Zhao, H. (2007). 「高速スイープ法の並列実装」. J. Comput. Math . 25 (4): 421– 429. JSTOR  43693378.
22. Detrixhe, M.; Gibou, F.; Min, C. (2013). 「アイコナール方程式のための並列高速スイープ法」. 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). 「アイコナール方程式のための並列2スケール法」. SIAM Journal on Scientific Computing . 37 (1): A156 – A180 . arXiv : 1306.4743 . Bibcode :2015SJSC...37A.156C. doi :10.1137/12088197X.

さらに詳しい情報

• パリス, DT; ハード, FK (1969). 『基礎電磁気理論』. マグロウヒル. pp.  383– 385. ISBN 0-07-048470-8。
• アーノルド、VI (2004).偏微分方程式講義（第2版）. シュプリンガー. pp.  2-3 . ISBN 3-540-40448-1。

外部リンク

• 線形化アイコナール方程式
• ハインリヒ・ブルンス著「Das Eikonal」の英訳

Retrieved from "https://en.wikipedia.org/w/index.php?title=Eikonal_equation&oldid=1289977600"