Уравнение эйконала

Уравнение эйконала (от греческого εἰκών, image ^{[1] [2]} ) - нелинейное уравнение в частных производных, встречающееся в задачах распространения волн , когда волновое уравнение аппроксимируется с использованием теории ВКБ . Он выводится из уравнений электромагнетизма Максвелла и обеспечивает связь между физической (волновой) оптикой и геометрической (лучевой) оптикой .

Уравнение эйконала имеет вид

${\ Displaystyle | \ набла и (х) | = {\ гидроразрыва {1} {е (х)}}, \ четырехъядерный х \ ин \ омега}$

при условии , где - открытое множество с хорошей границей, - функция с положительными значениями, обозначает градиент и является евклидовой нормой . Здесь правая часть обычно предоставляется как известный ввод. Физически решение является кратчайшим временем , необходимым для проезда от границы до внутреннего с быть скоростью .${\ displaystyle u | _ {\ partial \ Omega} = 0}$${\ displaystyle \ Omega}$${\ Displaystyle \ mathbb {R} ^ {п}}$${\ displaystyle f (x)}$${\ displaystyle \ nabla}$${\ displaystyle | \ cdot |}$${\ displaystyle f (x)}$${\ Displaystyle и (х)}$ ${\ displaystyle \ partial \ Omega}$${\ displaystyle x}$${\ displaystyle \ Omega,}$${\ displaystyle f (x)}$${\ displaystyle x}$

В частном случае, когда решение дает расстояние со знаком от . ^{[ необходима цитата ]}${\ displaystyle f = 1}$${\ displaystyle \ partial \ Omega}$

Одним из быстрых вычислительных алгоритмов для аппроксимации решения уравнения эйконала является метод быстрого марша .

Физическая интерпретация [ править ]

Непрерывные задачи поиска кратчайшего пути [ править ]

Решение уравнения эйконала

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

${\ Displaystyle и (х) = д (х) {\ текст {для}} х \ в \ частичном \ Omega}$

может быть интерпретировано как минимальное количество времени , необходимое для перемещения от до , где является скорость движения, и является выход-штрафное время. (В качестве альтернативы это можно представить как минимальную стоимость выхода, сделав правую сторону и штраф за выход.)${\ displaystyle x}$${\ displaystyle \ partial \ Omega}$${\ displaystyle f: {\ bar {\ Omega}} \ to (0, + \ infty)}$${\ displaystyle q: \ partial \ Omega \ to [0, + \ infty)}$${\ Displaystyle С (х) / е (х)}$${\ displaystyle q}$

Предполагая, что это существует во всех точках, легко доказать, что это соответствует задаче оптимального по быстродействию управления, используя принцип оптимальности Беллмана и разложение Тейлора. ^[3] К сожалению, не гарантируется, что он существует во всех точках, и для доказательства этого необходимы более продвинутые методы. Это привело к разработке решений вязкости в 1980 году Пьер-Луи Львы и Майкл Г. Crandall , ^[4] и Lions выиграл медаль Филдса за его вклад.${\ Displaystyle \ набла и (х)}$${\ Displaystyle и (х)}$${\ Displaystyle \ набла и (х)}$

Электромагнитный потенциал [ править ]

Физический смысл уравнения эйконала связан с формулой

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

где - напряженность электрического поля, - электрический потенциал. Есть аналогичное уравнение для потенциала скорости в потоке жидкости и температуры при теплопередаче. Физический смысл этого уравнения в электромагнитном примере заключается в том, что любой заряд в области толкается, чтобы двигаться под прямым углом к ​​линиям ^{[ требуется пояснение ]} постоянного потенциала и вдоль силовых линий, определяемых полем вектора E и знак обвинения.${\displaystyle \mathbf {E} }$${\displaystyle V}$

Лучевая оптика и электромагнетизм связаны тем, что уравнение эйконала дает вторую электромагнитную формулу той же формы, что и уравнение потенциала, приведенное выше, где линия постоянного потенциала заменена линией постоянной фазы, а силовые линии заменены векторами нормалей, выходящими из линии постоянной фазы под прямым углом. Величина этих нормальных векторов определяется квадратным корнем из относительной диэлектрической проницаемости. Линию постоянной фазы можно рассматривать как край одной из приближающихся световых волн. Нормальные векторы - это лучи, по которым свет распространяется в лучевой оптике.

Вычислительные алгоритмы [ править ]

С 1990-х годов было разработано несколько быстрых и эффективных алгоритмов решения уравнения эйконала. Многие из этих алгоритмов используют преимущества алгоритмов, разработанных намного раньше для задач поиска кратчайшего пути на графах с неотрицательной длиной ребер. ^[5] Эти алгоритмы используют причинно-следственную связь, предоставляемую физической интерпретацией, и обычно дискретизируют область с помощью сетки ^{[6] [7] [8] [9]} или регулярной сетки ^{[10] [11]} и вычисляют решение в каждом дискретная точка. Решатели эйконала на триангулированных многообразиях есть. ^{[6] [7]}

SETHIAN - х быстро маршевый (FMM) ^{[10] [11]} был первым «быстрый и эффективный» алгоритм , созданный для решения уравнения эйконала. В исходном описании область дискретизируется в регулярную сетку и «марширует» решение от «известных» значений к неоткрытым областям, точно отражая логику алгоритма Дейкстры . Если дискретизирован и имеет точки сетки, то вычислительная сложность заключается в том, что термин происходит от использования кучи (обычно двоичной). В FMM может быть предписан ряд модификаций, поскольку он классифицируется как метод установки этикеток. Кроме того, FMM был обобщен для работы с общими сетками, которые дискретизируют область.^[6]${\displaystyle \Omega \subset \mathbb {R} ^{n}}$${\displaystyle \Omega }$${\displaystyle M}$${\displaystyle O(M\log M)}$${\displaystyle \log }$^{[7] [8] [9]}

Методы исправления меток, такие как алгоритм Беллмана – Форда, также могут использоваться для решения дискретизированного уравнения Эйконала с многочисленными разрешенными модификациями (например, «сначала маленькие метки» ^{[5] [12]} или «большие метки в последнюю очередь» ^{[5] [13 ] ]} ). Также были разработаны методы с двумя очередями ^[14] , которые по сути являются версией алгоритма Беллмана-Форда, за исключением того, что используются две очереди с порогом, используемым для определения, какой очереди должна быть назначена точка сетки на основе локальной информации.

Алгоритмы развертки, такие как метод быстрой развертки (FSM) ^[15] , очень эффективны для решения уравнений Эйконала, когда соответствующие характеристические кривые не меняют направление очень часто. ^[5] Эти алгоритмы корректируют метки, но не используют очередь или кучу, а вместо этого предписывают разные порядки для обновляемых точек сетки и повторяют эти порядки до сходимости. Были внесены некоторые улучшения, такие как «блокировка» точек сетки ^[14]во время развертки if не получает обновления, но на сетках с высокой степенью детализации и пространствах более высокой размерности по-прежнему возникают большие накладные расходы из-за необходимости проходить через каждую точку сетки. Были введены параллельные методы, которые пытаются декомпозировать домен и выполнять поиск по каждому декомпозированному подмножеству. Параллельная реализация Чжао разбивает домен на -мерные подмножества, а затем запускает отдельный автомат для каждого подмножества. ^[16] Параллельная реализация Dextrixhe также разбивает область на части, но распараллеливает каждую отдельную развертку, так что процессоры несут ответственность за обновление точек сетки в -мерной гиперплоскости до тех пор, пока не будет развернут весь домен. ^[17]${\displaystyle n}$${\displaystyle (n-1)}$

Также были введены гибридные методы , которые используют эффективность FMM с простотой FSM. Например, метод ячеек кучи (HCM) разбивает домен на ячейки и выполняет FMM в домене ячеек, и каждый раз, когда "ячейка" обновляется, FSM выполняется в локальном домене точки сетки, который находится внутри этой ячейки. ^[5] Также была разработана распараллеленная версия HCM. ^[18]

Численное приближение [ править ]

Для простоты предположим, что это дискретизировано в однородную сетку с интервалом .${\displaystyle \Omega }$${\displaystyle h}$

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}}\quad {\text{ and }}\quad u_{y}(x_{ij})\approx D_{ij}^{\pm y}U={\frac {U_{i,j\pm 1}-U_{ij}}{\pm h}}.}$

Благодаря согласованным, монотонным и причинным свойствам этой дискретизации ^[5] легко показать, что if and and then${\displaystyle U_{H}=\min(U_{i-1,j},U_{i+1,j})}$${\displaystyle U_{V}=\min(U_{i,j-1},U_{i,j+1})}$${\displaystyle |U_{H}-U_{V}|\leq h/f_{ij}}$

${\displaystyle \left({\frac {U_{ij}-U_{H}}{h}}\right)^{2}+\left({\frac {U_{ij}-U_{V}}{h}}\right)^{2}={\frac {1}{f_{ij}^{2}}}}$

что значит

${\displaystyle U_{ij}={\frac {U_{H}+U_{V}}{2}}+{\frac {1}{2}}{\sqrt {(U_{H}+U_{V})^{2}-2\left(U_{H}^{2}+U_{V}^{2}-{\frac {h^{2}}{f_{ij}^{2}}}\right)}}.}$

Это решение всегда будет существовать до тех пор, пока удовлетворяется и больше, чем оба, и , пока . Если необходимо выполнить обновление более низкой размерности, предполагая, что одна из частных производных равна :${\displaystyle |U_{H}-U_{V}|\leq {\sqrt {2}}h/f_{ij}}$${\displaystyle U_{H}}$${\displaystyle U_{V}}$${\displaystyle |U_{H}-U_{V}|\leq h/f_{ij}}$${\displaystyle |U_{H}-U_{V}|\geq h/f_{ij}}$${\displaystyle 0}$

${\displaystyle U_{ij}=\min(U_{H},U_{V})+{\frac {h}{f_{ij}}}.}$

n -D приближение на декартовой сетке [ править ]

Предположим, что точка сетки имеет значение . Повторяя те же шаги, что и в случае, мы можем использовать схему первого порядка для аппроксимации частных производных. Пусть будет минимум значений соседей по направлениям, где - стандартный единичный базисный вектор . Тогда приближение${\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)}}.}$

Если дискриминант квадратного корня отрицательный, то необходимо выполнить обновление более низкой размерности (т. Е. Одна из частных производных ).${\displaystyle 0}$

Если затем выполнить одномерное обновление${\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}$

Математическое описание [ править ]

В этом разделе есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Этот раздел написан как исследовательская статья или научный журнал, в котором могут использоваться излишне технические термины, или же он может быть написан не как энциклопедическая статья . Пожалуйста, помогите улучшить его , переписав в энциклопедическом стиле . ( Июнь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) Этот раздел может быть слишком техническим, чтобы его могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Июнь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) В этот раздел включен список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить этот раздел, добавив более точные цитаты. ( Июнь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) Этот раздел, возможно, содержит оригинальные исследования . Пожалуйста, улучшите его , проверив сделанные утверждения и добавив встроенные цитаты . Заявления, содержащие только оригинальные исследования, следует удалить. ( Июнь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Уравнение эйконала имеет вид

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

Осталось показать , что мы определили в окрестности нашей исходной плоскости градиент некоторой функции . Это последует, если мы покажем, что векторное поле не скручивается. Рассмотрим первый член в определении . Этот член свободен от скручивания, поскольку является градиентом функции. Что касается другого члена, отметим${\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.}$

Результат следует.

Приложения [ править ]

• Конкретное применение - вычисление ослабления радиоволн в атмосфере .
• Определение формы по штриховке в компьютерном зрении.
• Геометрическая оптика
• Непрерывные задачи кратчайшего пути
• Сегментация изображения
• Исследование формы твердотопливного ракетного зерна

См. Также [ править ]

• Уравнение Гамильтона – Якоби – Беллмана.
• Уравнение Гамильтона – Якоби
• Принцип Ферма

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Париж, ДТ; Херд, Ф.К. (1969). Основы электромагнитной теории . Макгроу-Хилл. С. 383–385. ISBN 0-07-048470-8.
• Арнольд, В.И. (2004). Лекции по дифференциальным уравнениям с частными производными (2-е изд.). Springer. С. 2–3. ISBN 3-540-40448-1.

Внешние ссылки [ править ]

• Линеаризованное уравнение эйконала
• Английский перевод "Das Eikonal" Генриха Брунса