Дискретный оператор Лапласа

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Дискретный оператор Лапласа»  -  новости  · газеты  · книги  · ученый  · JSTOR ( декабрь 2007 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Для дискретного эквивалента преобразования Лапласа см. Z-преобразование .

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

Дискретный оператор Лапласа встречается в физических задачах, таких как модель Изинга и петлевая квантовая гравитация , а также при исследовании дискретных динамических систем . Он также используется в численном анализе в качестве замены непрерывного оператора Лапласа. Общие приложения включают в себя обработку изображений , ^[1] , где он известен как фильтр Лапласа , и в машинном обучении для кластеризации и полуобучаемое обучения на окрестности графов.

Определения [ править ]

Графические лапласианы [ править ]

Существуют различные определения дискретного лапласиана для графов , различающиеся знаком и масштабным коэффициентом (иногда одно усредняет по соседним вершинам, иногда просто суммирует; это не имеет значения для обычного графа ). Традиционное определение лапласиана графа, данное ниже, соответствует отрицательному непрерывному лапласиану на области со свободной границей.

Позвольте быть графом с вершинами и ребрами . Позвольте быть функцией вершин, принимающих значения в кольце . Тогда, дискретный лапласиан , действующий на определяется${\ Displaystyle G = (V, E)}$${\ displaystyle V}$${\ displaystyle E}$${\ Displaystyle \ phi \ двоеточие от V \ до R}$${\ displaystyle \ Delta}$${\ displaystyle \ phi}$

${\ Displaystyle (\ Delta \ phi) (v) = \ sum _ {w: \, d (w, v) = 1} \ left [\ phi (v) - \ phi (w) \ right]}$

где - расстояние графа между вершинами w и v. Таким образом, эта сумма берется по ближайшим соседям вершины v . Для графа с конечным числом ребер и вершин это определение идентично определению матрицы Лапласа . То есть может быть записан как вектор-столбец; и это произведение вектора-столбца и матрицы Лапласа, в то время как это просто v- я запись вектора произведения.${\ Displaystyle д (ш, в)}$${\ displaystyle \ phi}$${\ displaystyle \ Delta \ phi}$${\ Displaystyle (\ Дельта \ фи) (v)}$

Если граф имеет взвешенные ребра, то есть задана весовая функция , то определение можно обобщить на${\ Displaystyle \ gamma \ двоеточие от E \ до R}$

${\ displaystyle (\ Delta _ {\ gamma} \ phi) (v) = \ sum _ {w: \, d (w, v) = 1} \ gamma _ {wv} \ left [\ phi (v) - \ phi (w) \ right]}$

где - значение веса на грани .${\ displaystyle \ gamma _ {wv}}$${\ displaystyle wv \ in E}$

С дискретным лапласианом тесно связан оператор усреднения :

${\ displaystyle (M \ phi) (v) = {\ frac {1} {\ deg v}} \ sum _ {w: \, d (w, v) = 1} \ phi (w).}$

Сетчатые лапласианы [ править ]

Помимо рассмотрения связности узлов и ребер в графе, операторы сетки Лапласа учитывают геометрию поверхности (например, углы в узлах). Для треугольной сетки многообразия оператор Лапласа-Бельтрами скалярной функции в вершине может быть аппроксимирован как${\ displaystyle u}$${\ displaystyle i}$

${\displaystyle (\Delta u)_{i}\approx {\frac {1}{2A_{i}}}\sum _{j}(\cot \alpha _{ij}+\cot \beta _{ij})(u_{i}-u_{j}),}$

где сумма берется по всем смежным вершинам из , и является два углом напротив края , и это область вершины из ; то есть одна треть суммированных площадей треугольников, инцидентных . Приведенная выше формула котангенса может быть получена с помощью множества различных методов, среди которых кусочно-линейные конечные элементы , конечные объемы (см. ^[2] для вывода) и дискретное внешнее исчисление (см. [1] ).${\displaystyle j}$${\displaystyle i}$${\displaystyle \alpha _{ij}}$${\displaystyle \beta _{ij}}$${\displaystyle ij}$${\displaystyle A_{i}}$${\displaystyle i}$${\displaystyle i}$

Для облегчения вычислений лапласиан кодируется в матрице, такой что . Пусть - (разреженная) матрица котангенса с элементами${\displaystyle L\in \mathbb {R} ^{|V|\times |V|}}$${\displaystyle Lu=(\Delta u)_{i}}$${\displaystyle C}$

${\displaystyle C_{ij}={\begin{cases}-{\frac {1}{2}}(\cot \alpha _{ij}+\cot \beta _{ij})&ij{\text{ is an edge}},\\-\sum \limits _{k\in N(i)}C_{ik}&i=j,\\0&{\text{otherwise,}}\end{cases}}}$Где обозначает окрестность . ${\displaystyle N(i)}$${\displaystyle i}$

И пусть будет диагональной матрицей масс , -й элемент которой по диагонали - это площадь вершины . Тогда - искомая дискретизация лапласиана.${\displaystyle M}$ ${\displaystyle M}$${\displaystyle i}$${\displaystyle A_{i}}$${\displaystyle L=M^{-1}C}$

Более общий обзор сеточных операторов приведен в ^[3].

Конечные различия [ править ]

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

${\displaystyle \Delta f(x,y)\approx {\frac {f(x-h,y)+f(x+h,y)+f(x,y-h)+f(x,y+h)-4f(x,y)}{h^{2}}},}$

где размер сетки равен h в обоих измерениях, так что пятиточечный шаблон точки ( x ,  y ) в сетке равен

${\displaystyle \{(x-h,y),(x,y),(x+h,y),(x,y-h),(x,y+h)\}.}$

Если размер сетки h = 1, результатом будет отрицательный дискретный лапласиан на графике, который представляет собой сетку квадратной решетки . Здесь нет ограничений на значения функции f ( x , y ) на границе решетки, таким образом, это случай отсутствия источника на границе, то есть граничное условие отсутствия потока (также известное как изоляция , или однородное граничное условие Неймана ). Управление переменной состояния на границе, как f ( x , y ), заданное на границе сетки (также известное как граничное условие Дирихле), редко используется для лапласианов графов, но часто встречается в других приложениях.

Многомерные дискретные лапласианы на прямоугольных кубоидных регулярных сетках обладают очень особыми свойствами, например, они являются суммами Кронекера одномерных дискретных лапласианов, см. Сумма Кронекера дискретных лапласианов , и в этом случае все ее собственные значения и собственные векторы могут быть вычислены явно.

Метод конечных элементов [ править ]

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

Обработка изображений [ править ]

Дискретный оператор Лапласа часто используется при обработке изображений, например, в приложениях для обнаружения границ и оценки движения. ^[4] Дискретный лапласиан определяется как сумма вторых производных оператора Лапласа # Выражения координат и вычисляется как сумма разностей по ближайшим соседям центрального пикселя. Поскольку производные фильтры часто чувствительны к шуму в изображении, оператору Лапласа часто предшествует сглаживающий фильтр (например, фильтр Гаусса), чтобы удалить шум перед вычислением производной. Сглаживающий фильтр и фильтр Лапласа часто объединяются в один фильтр. ^[5]

Реализация через операторную дискретизацию [ править ]

Для одно-, двух- и трехмерных сигналов дискретный лапласиан может быть задан в виде свертки со следующими ядрами:

1D - фильтр ,${\displaystyle {\vec {D}}_{x}^{2}={\begin{bmatrix}1&-2&1\end{bmatrix}}}$

2D фильтр .${\displaystyle \mathbf {D} _{xy}^{2}={\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}}$

${\displaystyle \mathbf {D} _{xy}^{2}}$соответствует формуле конечных разностей ( пятиточечный шаблон ), рассмотренной ранее. Он устойчив для очень плавно меняющихся полей, но для уравнений с быстро меняющимися решениями требуется более устойчивая и изотропная форма оператора Лапласа ^[6], такая как шаблон из девяти точек , который включает диагонали:

2D - фильтр ,${\displaystyle \mathbf {D} _{xy}^{2}={\begin{bmatrix}0.25&0.5&0.25\\0.5&-3&0.5\\0.25&0.5&0.25\end{bmatrix}}}$

3D-фильтр: при использовании семиточечного трафарета определяется:${\displaystyle \mathbf {D} _{xyz}^{2}}$

первый самолет = ; второй самолет = ; третий самолет = .${\displaystyle {\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}}$${\displaystyle {\begin{bmatrix}0&1&0\\1&-6&1\\0&1&0\end{bmatrix}}}$${\displaystyle {\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}}$

и используя 27-точечный трафарет : ^[7]

первый самолет = ; второй самолет = ; третий самолет = .${\displaystyle {\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}}$${\displaystyle {\frac {1}{26}}{\begin{bmatrix}3&6&3\\6&-88&6\\3&6&3\end{bmatrix}}}$${\displaystyle {\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}}$

n D фильтр : для элементаядра${\displaystyle a_{x_{1},x_{2},\dots ,x_{n}}}$${\displaystyle \mathbf {D} _{x_{1},x_{2},\dots ,x_{n}}^{2},}$

${\displaystyle a_{x_{1},x_{2},\dots ,x_{n}}=\left\{{\begin{array}{ll}-2n&{\text{if }}s=n,\\1&{\text{if }}s=n-1,\\0&{\text{otherwise,}}\end{array}}\right.}$

где x _i - позиция ( -1 , 0 или 1 ) элемента в ядре в i -м направлении, а s - количество направлений i, для которых x _i = 0 .

Обратите внимание, что версия n D, основанная на графическом обобщении лапласиана, предполагает, что все соседи находятся на равном расстоянии, и, следовательно, приводит к следующему 2D-фильтру с включенными диагоналями, а не к версии выше:

2D фильтр: ${\displaystyle \mathbf {D} _{xy}^{2}={\begin{bmatrix}1&1&1\\1&-8&1\\1&1&1\end{bmatrix}}.}$

Эти ядра выводятся с помощью дискретных дифференциальных частных.

Можно показать ^{[8] [9],} что следующая дискретная аппроксимация двумерного оператора Лапласа в виде выпуклой комбинации разностных операторов

${\displaystyle \nabla _{\gamma }^{2}=(1-\gamma )\nabla _{5}^{2}+\gamma \nabla _{\times }^{2}=(1-\gamma ){\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}+\gamma {\begin{bmatrix}1/2&0&1/2\\0&-2&0\\1/2&0&1/2\end{bmatrix}}}$

для γ ∈ [0, 1] совместим с дискретными свойствами масштабного пространства, где, в частности, значение γ = 1/3 дает наилучшее приближение вращательной симметрии. ^{[8] [9] [10]} Что касается трехмерных сигналов, то показано ^[9], что оператор Лапласа может быть аппроксимирован двухпараметрическим семейством разностных операторов

${\displaystyle \nabla _{\gamma _{1},\gamma _{2}}^{2}=(1-\gamma _{1}-\gamma _{2})\,\nabla _{7}^{2}+\gamma _{1}\,\nabla _{+^{3}}^{2}+\gamma _{2}\,\nabla _{\times ^{3}}^{2}),}$

где

${\displaystyle (\nabla _{7}^{2}f)_{0,0,0}=f_{-1,0,0}+f_{+1,0,0}+f_{0,-1,0}+f_{0,+1,0}+f_{0,0,-1}+f_{0,0,+1}-6f_{0,0,0},}$

${\displaystyle (\nabla _{+^{3}}^{2}f)_{0,0,0}={\frac {1}{4}}(f_{-1,-1,0}+f_{-1,+1,0}+f_{+1,-1,0}+f_{+1,+1,0}+f_{-1,0,-1}+f_{-1,0,+1}+f_{+1,0,-1}+f_{+1,0,+1}+f_{0,-1,-1}+f_{0,-1,+1}+f_{0,+1,-1}+f_{0,+1,+1}-12f_{0,0,0}),}$

${\displaystyle (\nabla _{\times ^{3}}^{2}f)_{0,0,0}={\frac {1}{4}}(f_{-1,-1,-1}+f_{-1,-1,+1}+f_{-1,+1,-1}+f_{-1,+1,+1}+f_{+1,-1,-1}+f_{+1,-1,+1}+f_{+1,+1,-1}+f_{+1,+1,+1}-8f_{0,0,0}).}$

Реализация путем непрерывной реконструкции [ править ]

Дискретный сигнал, содержащий изображения, можно рассматривать как дискретное представление непрерывной функции , где вектор координат и область значений действительны . Следовательно, операция деривации напрямую применима к непрерывной функции . В частности, любое дискретное изображение с разумными предположениями о процессе дискретизации, например, с учетом функций с ограниченной полосой или расширяемых вейвлетов функций и т. Д., Может быть восстановлено с помощью корректных функций интерполяции, лежащих в основе формулировки реконструкции, ^[11]${\displaystyle f({\bar {r}})}$${\displaystyle {\bar {r}}\in R^{n}}$${\displaystyle f\in R}$${\displaystyle f}$

${\displaystyle f({\bar {r}})=\sum _{k\in K}f_{k}\mu _{k}({\bar {r}})}$

где - дискретные представления на сетке и - функции интерполяции, специфичные для сетки . На равномерную сетке, такие как изображения, так и для узкополосных функций, функции интерполяции сдвига инвариантен На сумме с быть соответствующим образом расширен синком функции определяется в -Размерах то есть . Другими приближениями на однородных сетках являются соответственно расширенные функции Гаусса в -мерности. Соответственно, дискретный лапласиан становится дискретной версией лапласиана непрерывного${\displaystyle f_{k}\in R}$${\displaystyle f}$${\displaystyle K}$${\displaystyle \mu _{k}}$${\displaystyle K}$${\displaystyle \mu _{k}({\bar {r}})=\mu ({\bar {r}}-{\bar {r}}_{k})}$${\displaystyle \mu }$${\displaystyle n}$${\displaystyle {\bar {r}}=(x_{1},x_{2}...x_{n})^{T}}$${\displaystyle \mu }$${\displaystyle n}$${\displaystyle f({\bar {r}})}$

${\displaystyle \nabla ^{2}f({\bar {r}}_{k})=\sum _{k'\in K}f_{k'}(\nabla ^{2}\mu ({\bar {r}}-{\bar {r}}_{k'}))|_{{\bar {r}}={\bar {r}}_{k}}}$

которая, в свою очередь, представляет собой свертку с лапласианом функции интерполяции на равномерной (изображающей) сетке . Преимущество использования как функции Гаусса , интерполяции является то , что они дают линейные операторы, в то числе лапласианов, которые свободны от артефактов вращения системы координат , в которой представлены с помощью , в -Размерах и по частоте знает по определению. Линейный оператор имеет не только ограниченный диапазон в области, но также эффективный диапазон в частотной области (альтернативно гауссовское масштабное пространство), которым можно явно управлять с помощью дисперсии гауссиана принципиальным образом. Результирующая фильтрация может быть реализована с помощью разделяемых фильтров и децимации (обработки сигналов) /${\displaystyle K}$${\displaystyle f}$${\displaystyle f_{k}}$${\displaystyle n}$${\displaystyle {\bar {r}}}$пирамиды (обработка изображений) для повышения эффективности вычислений в -размерностях. Другими словами, дискретный лапласианский фильтр любого размера может быть удобно сгенерирован как дискретизированный лапласиан гауссиана с пространственным размером, соответствующим потребностям конкретного приложения и контролируемым его дисперсией. Мономы, которые являются нелинейными операторами, также могут быть реализованы с использованием аналогичного подхода к реконструкции и аппроксимации при условии, что сигнал достаточно передискретизирован. Таким образом, могут быть реализованы такие нелинейные операторы, как тензор структуры и обобщенный тензор структуры, которые используются при распознавании образов для их полной оптимальности методом наименьших квадратов при оценке ориентации.${\displaystyle n}$

Спектр [ править ]

Ключевой интерес представляет спектр дискретного лапласиана на бесконечной сетке; поскольку это самосопряженный оператор , он имеет вещественный спектр. Для конвенции о , спектр лежит в пределах (как оператор усреднения имеет спектральные значения в ). Это также можно увидеть, применив преобразование Фурье. Обратите внимание, что дискретный лапласиан на бесконечной сетке имеет чисто абсолютно непрерывный спектр и, следовательно, не имеет собственных значений или собственных функций.${\displaystyle \Delta =I-M}$${\displaystyle Z}$${\displaystyle [0,2]}$${\displaystyle [-1,1]}$

Теоремы [ править ]

Если граф представляет собой бесконечную квадратную решетку , то можно показать, что это определение лапласиана соответствует непрерывному лапласиану в пределе бесконечно тонкой сетки. Так, например, на одномерной сетке имеем

${\displaystyle {\frac {\partial ^{2}F}{\partial x^{2}}}=\lim _{\epsilon \rightarrow 0}{\frac {[F(x+\epsilon )-F(x)]+[F(x-\epsilon )-F(x)]}{\epsilon ^{2}}}.}$

Это определение лапласиана обычно используется в численном анализе и при обработке изображений . При обработке изображений он считается типом цифрового фильтра , а точнее краевым фильтром , называемым фильтром Лапласа .

Дискретный оператор Шредингера [ править ]

Позвольте быть потенциальной функцией, определенной на графике. Обратите внимание, что P можно рассматривать как мультипликативный оператор, действующий по диагонали на${\displaystyle P\colon V\rightarrow R}$${\displaystyle \phi }$

${\displaystyle (P\phi )(v)=P(v)\phi (v).}$

Тогда это дискретный оператор Шредингера , аналог непрерывного оператора Шредингера .${\displaystyle H=\Delta +P}$

Если количество ребер, пересекающихся в вершине, равномерно ограничено, а потенциал ограничен, то H ограничен и самосопряжен .

В спектральные свойства этого гамильтониана могут быть изучены с теоремой Стоуна ; это следствие двойственности множеств и булевых алгебр .

На регулярных решетках оператор обычно имеет решения как бегущей волны, так и решения локализации Андерсона , в зависимости от того, является ли потенциал периодическим или случайным.

Дискретная функция Грина [ править ]

Функция Грина дискретного оператора Шредингера задается в резольвентном формализме формулой

${\displaystyle G(v,w;\lambda )=\left\langle \delta _{v}\left|{\frac {1}{H-\lambda }}\right|\delta _{w}\right\rangle }$

где понимается дельта- функция Кронекера на графике :; то есть, он равен 1, если v = w, и 0 в противном случае.${\displaystyle \delta _{w}}$${\displaystyle \delta _{w}(v)=\delta _{wv}}$

Для фиксированного и комплексного числа функция Грина, рассматриваемая как функция v, является единственным решением${\displaystyle w\in V}$${\displaystyle \lambda }$

${\displaystyle (H-\lambda )G(v,w;\lambda )=\delta _{w}(v).}$

Классификация ADE [ править ]

Некоторые уравнения, включающие дискретный лапласиан, имеют решения только на диаграммах Дынкина с простыми кружевами (все ребра кратны 1) и являются примером классификации ADE . В частности, единственные положительные решения однородного уравнения:

${\displaystyle \Delta \phi =\phi ,}$

в словах,

«Дважды любая метка - это сумма меток на соседних вершинах»,

находятся на расширенных (аффинных) диаграммах Дынкина ADE, из которых есть 2 бесконечных семейства (A и D) и 3 исключения (E). Результирующая нумерация уникальна до масштаба, и если наименьшее значение установлено равным 1, остальные числа являются целыми числами в диапазоне до 6.

Обычные графы ADE - единственные графы, допускающие положительную разметку со следующим свойством:

Дважды любая метка минус два является суммой меток на соседних вершинах.

В терминах лапласиана положительные решения неоднородного уравнения:

${\displaystyle \Delta \phi =\phi -2.}$

Полученная нумерация уникальна (масштаб указывается цифрой «2») и состоит из целых чисел; для E ₈ они колеблются от 58 до 270 и наблюдались еще в 1968 году ^[12].

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

• Спектральный анализ формы
• Электрическая сеть
• Сумма Кронекера дискретных лапласианов
• Дискретное исчисление

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

• Т. Сунада , Дискретный геометрический анализ, Труды симпозиумов по чистой математике (ред. П. Экснер, Дж. П. Китинг, П. Кучмент, Т. Сунада, А. Тепляев), 77 (2008), 51-86

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

• Определение и применение к спектральной щели