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

Уравнение эйконала (от греческого εἰκών, изображение ) — нелинейное уравнение в частных производных первого порядка , встречающееся в задачах распространения волн .

Классическое уравнение эйконала в геометрической оптике представляет собой дифференциальное уравнение вида

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

где $x$ лежит в открытом подмножестве $\mathbb {R} ^{n}$, $n(x)$ это положительная функция, $\nabla$ обозначает градиент , а $|\cdot |$ является евклидовой нормой . Функция $n$ дано и ищут решения $u$.В контексте геометрической оптики функция $n$ – показатель преломления среды.

В более общем смысле уравнение эйконала — это уравнение вида

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

где $H$ является функцией $2n$ переменные. Здесь функция $H$ дано, и $u$ это решение.Если $H(x,y)=|y|-n(x)$, то уравнение ( 2 ) становится ( 1 ).

Уравнения эйконала естественным образом возникают в методе ВКБ и изучение уравнений Максвелла . Уравнения Эйконала обеспечивают связь между физической (волновой) оптикой и геометрической (лучевой) оптикой .

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

История

Термин «эйконал» впервые был использован в контексте геометрической оптики Генрихом Брунсом . Однако, настоящее уравнение появляется ранее в плодотворной работе Уильяма Роуэна Гамильтона по геометрической оптике .

Физическая интерпретация

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

Предположим, что $\Omega$ представляет собой открытое множество с достаточно гладкой границей $\partial \Omega$. Решение уравнения эйконала

$\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$

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

В частном случае, когда $f=1$, решение дает расстояние со знаком от $\partial \Omega$.

Предполагая, что $\nabla u(x)$ существует во всех точках, легко доказать, что $u(x)$ соответствует задаче оптимального по быстродействию управления с использованием принципа оптимальности Беллмана и расширения Тейлора. К сожалению, не гарантируется, что $\nabla u(x)$ существует во всех точках, и чтобы доказать это, необходимы более совершенные методы. Это привело к разработке решений по вязкости в 1980-х годах Пьером-Луи Лионсом и Майклом Г. Крэндаллом . и Лайонс выиграл медаль Филдса за свой вклад.

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

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

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

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

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

Вычислительные алгоритмы

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

Сетиана Метод быстрого марша (FMM) был первым «быстрым и эффективным» алгоритмом, созданным для решения уравнения Эйконала. Исходное описание дискретизирует домен $\Omega \subset \mathbb {R} ^{n}$ в регулярную сетку и «проводит» решение от «известных» значений к неоткрытым областям, точно отражая логику алгоритма Дейкстры . Если $\Omega$ дискретизирован и имеет $M$ точек сетки, то вычислительная сложность равна $O(M\log M)$ где $\log$ Термин происходит от использования кучи (обычно двоичной). В FMM можно внести ряд модификаций, поскольку он классифицируется как метод установки меток. Кроме того, FMM был обобщен для работы с общими сетками, которые дискретизируют область.

Методы коррекции меток, такие как алгоритм Беллмана – Форда, также могут использоваться для решения дискретизированного уравнения Эйконала, также с многочисленными разрешенными модификациями (например, «Сначала маленькие метки» или «Большие этикетки в последнюю очередь» ). Также были разработаны методы двух очередей. по сути, это версия алгоритма Беллмана-Форда, за исключением того, что используются две очереди с порогом, используемым для определения того, какой очереди должна быть назначена точка сетки, на основе локальной информации.

Алгоритмы развертки, такие как метод быстрой развертки (FSM). очень эффективны для решения уравнений Эйконала, когда соответствующие характеристические кривые не очень часто меняют направление. Эти алгоритмы корректируют метки, но не используют очередь или кучу, а вместо этого предписывают разные порядки для обновляемых точек сетки и перебирают эти порядки до сходимости. Были введены некоторые улучшения, такие как «блокировка» точек сетки. во время развертки if не получает обновления, но на сильно уточненных сетках и в пространствах более высокой размерности по-прежнему возникают большие накладные расходы из-за необходимости проходить через каждую точку сетки. Были введены параллельные методы, которые пытаются разложить предметную область и выполнить очистку каждого разложенного подмножества. Параллельная реализация Чжао разбивает предметную область на $n$-мерные подмножества, а затем запускает отдельный автомат для каждого подмножества. Параллельная реализация Detrixhe также разлагает домен, но распараллеливает каждый отдельный проход, так что процессоры отвечают за обновление точек сетки в $(n-1)$-мерная гиперплоскость до тех пор, пока вся область не будет полностью пройдена.

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

Численное приближение

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

2D-аппроксимация на декартовой сетке

Предположим, что точка сетки $x_{ij}$ имеет ценность $U_{ij}=U(x_{ij})\approx u(x_{ij})$. Схема первого порядка для аппроксимации частных производных:

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

где

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

Из-за непротиворечивости, монотонности и причинности этой дискретизации легко показать, что если $U_{X}=\min(U_{i-1,j},U_{i+1,j})$ и $U_{Y}=\min(U_{i,j-1},U_{i,j+1})$ и $|U_{X}/h_{x}-U_{Y}/h_{y}|\leq 1/f_{ij}$ затем

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

которое можно решить как квадратичное. В предельном случае $h_{x}=h_{y}=h$, это сводится к

$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)}}.$

Это решение будет существовать всегда, пока $|U_{X}-U_{Y}|\leq {\sqrt {2}}h/f_{ij}$ удовлетворен и больше обоих, $U_{X}$ и $U_{Y}$, пока $|U_{X}-U_{Y}|\leq h/f_{ij}$ .

Если $|U_{X}/h_{x}-U_{Y}/h_{y}|\geq 1/f_{ij}$, обновление меньшей размерности должно быть выполнено, предполагая, что одна из частных производных равна $0$:

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

n -D аппроксимация на декартовой сетке

Предположим, что точка сетки $x$ имеет ценность $U=U(x)\approx u(x)$. Повторяя те же действия, что и в $n=2$ В этом случае мы можем использовать схему первого порядка для аппроксимации частных производных. Позволять $U_{i}$ быть минимальным из значений соседей в $\pm \mathbf {e} _{i}$ направления, где $\mathbf {e} _{i}$ — стандартный единичный базисный вектор . Тогда приближение

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

Решая это квадратное уравнение для $U$ дает:

$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)}}.$

Если дискриминант в квадратном корне отрицательный, то необходимо выполнить обновление меньшей размерности (т. е. одна из частных производных равна $0$).

Если $n=2$ затем выполните одномерное обновление

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

Если $n\geq 3$ затем выполните $n-1$ обновление размеров с использованием значений $\{U_{1},\ldots ,U_{n}\}\setminus \{U_{i}\}$ для каждого $i=1,\ldots ,n$ и выбери самый маленький.

Математическое описание

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

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

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

Самолет $x=(0,x')$ можно рассматривать как начальное состояние, думая о $x_{1}$ как $t.$ Мы также могли бы решить уравнение на подмножестве этой плоскости или на искривленной поверхности с очевидными изменениями.

Уравнение эйконала появляется в геометрической оптике , которая является способом изучения решений волнового уравнения. $c^{2}|\nabla _{x}u|^{2}=|\partial _{t}u|^{2}$, где $c(x)$ и $u(x,t)$. В геометрической оптике уравнение эйконала описывает фазовые фронты волн. При разумной гипотезе о «начальных» данных уравнение эйконала допускает локальное решение, но глобальное гладкое решение (например, решение для всех времен в случае геометрической оптики) невозможно. Причина в том, что могут образоваться каустики . В случае геометрической оптики это означает, что волновые фронты пересекаются.

Решить уравнение эйконала можно методом характеристик. Приходится навязывать «нехарактерную» гипотезу $\partial _{p_{1}}H(x,p)\neq 0$ вдоль начальной гиперповерхности $x=(0,x')$, где H = H ( x , p ) и p = ( p ₁ ,..., p _n ) — переменная, которая заменяется на ∇ u . Здесь x = ( x ₁ ,..., x _n ) = ( t , x ′).

Сначала решите проблему $H(x,\xi (x))=0$, $\xi (x)=\nabla u(x),x\in H$. Это делается путем определения кривых (и значений $\xi$ на этих кривых) как

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

$x(0)=x_{0},\;\;\;\;\xi (x(0))=\nabla u(x(0)).$ Обратите внимание, что еще до того, как мы получим решение $u$, мы знаем $\nabla u(x)$ для $x=(0,x')$ благодаря нашему уравнению для $H$.

Эти уравнения имеют решение для некоторого интервала $0\leq s<s_{1}$ следует из стандартных теорем ОДУ (с использованием нехарактеристической гипотезы). Эти кривые заполняют открытое множество вокруг плоскости. $x=(0,x')$. Таким образом, кривые определяют значение $\xi$ в открытом наборе про наш исходный самолет. После такого определения легко увидеть, используя правило цепочки, что $\partial _{s}H(x(s),\xi (s))=0$, и поэтому $H=0$ вдоль этих кривых.

Мы хотим наше решение $u$ удовлетворить $\nabla u=\xi$или, точнее, для каждого $s$, $(\nabla u)(x(s))=\xi (x(s)).$ Предположим на минутку, что это возможно, для любого решения $u(x)$ мы должны иметь

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

и поэтому

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

Другими словами, решение $u$ будет задана в окрестности исходной плоскости явным уравнением. Однако, поскольку разные пути $x(t)$, начиная с разных начальных точек, могут пересекаться, решение может стать многозначным, и в этот момент мы разработали каустику.У нас также есть (еще до того, как было показано, что $u$ это решение)

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

Осталось показать, что $\xi$, который мы определили в окрестности нашей исходной плоскости, является градиентом некоторой функции $u$. Это произойдет, если мы покажем, что векторное поле $\xi$ не имеет скручиваний. Рассмотрим первый член определения $\xi$. Этот термин, $\xi (x(0))=\nabla u(x(0))$ не имеет скручивания, поскольку является градиентом функции. Что касается другого термина, отметим

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

Результат следующий.

Приложения

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

См. также

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

Дальнейшее чтение

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

Внешние ссылки

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