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

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

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

${displaystyle | abla u (x) | = {frac {1} {f (x)}}, quad xin Omega}$

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

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

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

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

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

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

${displaystyle left | abla u (x) ight | = {frac {1} {f (x)}} {ext {for}} xin Omega subset mathbb {R} ^ {n},}$

${displaystyle u (x) = q (x) {ext {for}} xin частичная омега}$

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

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

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

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

${displaystyle mathbf {E} = -abla V,}$

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

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

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

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

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

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

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

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

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

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

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

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

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

где

${displaystyle u_ {x} (x_ {ij}) приблизительно D_ {ij} ^ {pm x} U = {frac {U_ {ipm 1, j} -U_ {ij}} {pm h}} quad {ext {и }} quad u_ {y} (x_ {ij}) приблизительно D_ {ij} ^ {pm y} U = {frac {U_ {i, jpm 1} -U_ {ij}} {pm h}}.}$

В силу непротиворечивости, монотонности и причинных свойств этой дискретизации^[5] легко показать, что если ${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}} ight) ^ {2} + left ({frac {U_ {ij} -U_ {V}} {h}} ight) ^ {2} = {гидроразрыв {1} {f_ {ij} ^ {2}}}}$

что значит

${displaystyle U_ {ij} = {frac {U_ {H} + U_ {V}} {2}} + {frac {1} {2}} {sqrt {(U_ {H} + U_ {V}) ^ { 2} -2 слева (U_ {H} ^ {2} + U_ {V} ^ {2} - {frac {h ^ {2}} {f_ {ij} ^ {2}}} ight)}}.}$

Это решение будет существовать всегда, пока ${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}}}.}$

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

Предположим, что точка сетки ${displaystyle x}$ имеет ценность ${displaystyle U = U (x) приблизительно 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}} ight) ^ {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} ight) ^ {2} -nleft (sum _ {j = 1} ^ {n} U_ {j} ^ {2} - {frac {h ^ {2}} {f_ {i } ^ {2}}} ight)}}.}$

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

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

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

Если ${displaystyle ngeq 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, abla u (x)) = 0}$

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

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

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

Уравнение эйконала можно решить методом характеристик. Приходится выдвигать гипотезу "нехарактерности". ${displaystyle partial _ {p_ {1}} H (x, p) eq 0}$ вдоль начальной гиперповерхности ${displaystyle x = (0, x ')}$, где ЧАС = ЧАС(Икс,п) и п = (п₁,...,п_п) - это переменная, которая заменяется на ∇ты. Здесь Икс = (Икс₁,...,Икс_п) = (т,Икс′).

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

${displaystyle {точка {x}} (s) = abla _ {xi} H (x (s), xi (s)), ;;;; {точка {xi}} (s) = - abla _ {x} H (x (s), xi (s)).}$

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

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

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

${displaystyle {frac {d} {ds}} u (x (s)) = abla 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} abla _ {x} H (x (s), xi (x (s))), DS. }$

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

${displaystyle {frac {partial ^ {2}} {частично x_ {k}, частично x_ {j}}} H = {frac {partial ^ {2}} {частично x_ {j}, частично x_ {k}}} ЧАС.}$

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

Приложения

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

Смотрите также

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

Рекомендации

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

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

внешняя ссылка

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