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

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

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

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

Определение

Обработка изображений

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

Реализация в обработке изображений

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

Фильтр 1D: ${\overrightarrow{D}}_x^2=\left[\begin{array}{ccc}1& -2& 1\end{array}\right]$

Фильтр 2D: ${𝐃}_{xy}^2=\left[\begin{array}{ccc}0& 1& 0\\ 1& -4& 1\\ 0& 1& 0\end{array}\right]$

или с диагоналями:

Фильтр 2D: ${𝐃}_{xy}^2=\left[\begin{array}{ccc}1& 1& 1\\ 1& -8& 1\\ 1& 1& 1\end{array}\right]$

Фильтр 3D: ${𝐃}_{xyz}^3$

для первой плоскости = $\left[\begin{array}{ccc}0& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}\right]$ ; для второй $\left[\begin{array}{ccc}0& 1& 0\\ 1& -6& 1\\ 0& 1& 0\end{array}\right]$ ; для третьей $\left[\begin{array}{ccc}0& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}\right]$

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

На графах

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

Пусть G=(V,E) будет графом с вершинами V и рёбрами E. Зададим функцию значений $\varphi :V\to R$ из вершин графа в кольцо $R$. Тогда дискретный лапласиан $\mathrm{\Delta }$ от $\varphi$ будет определяться как

$(\mathrm{\Delta }\varphi )(v)=\sum _{w:d(w,v)=1}[\varphi (w)-\varphi (v)]$

где d(w,v) есть функция расстояния между вершинами графа. Эта сумма — на ближайших соседях вершины v. Вершины конечного графа можно пронумеровать, тогда отображение $\varphi$ может быть записано как вектор-столбец, элементами которого являются значения отображения: ${\varphi }_v=\varphi (v)$. Данное выше определение лапласиана также может быть переписано в векторной форме с использованием матрицы Лапласа $L$:

$(\mathrm{\Delta }\varphi )(v)=(L\cdot \varphi {)}_v$

Если рёбра графа имеют веса, то есть задана весовая функция $\gamma :E\to R$, то определение можно записать как

$({\mathrm{\Delta }}_{\gamma }\varphi )(v)=\sum _{w:d(w,v)=1}{\gamma }_{wv}[\varphi (w)-\varphi (v)]$

где ${\gamma }_{wv}$ есть вес ребра $wv\in E$.

Близко лежит определение усредняющего оператора:

$(M\varphi )(v)=\frac{1}{\mathrm{deg}v}\sum _{w:d(w,v)=1}\varphi (w)$

Спектр

Спектр дискретного лапласиана представляет ключевой интерес; когда он имеет самосопряжённый спектр, он действителен. Если $\mathrm{\Delta }=I-M$, то спектр лежит в отрезке $[0,2]$ (в то время как у усредняющего оператора его спектральные значения в $[-1,1]$) и содержит ноль (для постоянных функций). Наименьшее ненулевое собственное число ${\lambda }_1$ называют спектральной щелью. Обычно различают и понятие о спектральном радиусе, определяемом обычно как наибольшее собственное число.

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

Теоремы

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

$\frac{{\partial }^{2}F}{\partial x^2}=\underset{ϵ\to 0}{lim}\frac{[F(x+ϵ)-F(x)]+[F(x-ϵ)-F(x)]}{{ϵ}^2}.$

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

Дискретный оператор Шрёдингера

Пусть $P:V\to R$ есть потенциал, заданный на графе. Заметим, что P можно рассматривать и как мультипликативный оператор, действующий диагонально на $\varphi$:

$(P\varphi )(v)=P(v)\varphi (v).$

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

Если количество рёбер вершины равномерно ограничено, то H — ограниченный и самосопряжённый.

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

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

Дискретная функция Грина

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

$G(v,w;\lambda )=⟨{\delta }_v|\frac{1}{H-\lambda }|{\delta }_w⟩$

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

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

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

См. также

• Матрица Лапласа

Ссылки

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