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

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

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

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

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

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

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

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

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

Фильтр 1D:

{\vec {D}}_{x}^{2}={\begin{bmatrix}1&-2&1\end{bmatrix}}

Фильтр 2D:

\mathbf {D} _{xy}^{2}={\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}

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

Фильтр 2D:

\mathbf {D} _{xy}^{2}={\begin{bmatrix}1&1&1\\1&-8&1\\1&1&1\end{bmatrix}}

Фильтр 3D:

\mathbf {D} _{xyz}^{3}

для первой плоскости = ${\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}$ ; для второй ${\begin{bmatrix}0&1&0\\1&-6&1\\0&1&0\end{bmatrix}}$ ; для третьей ${\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}$

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

На графах править

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

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

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

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

(\Delta \phi )(v)=(L\cdot \phi )_{v}

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

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

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

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

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

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

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

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

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

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

{\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:V\rightarrow R$ есть потенциал, заданный на графе. Заметим, что P можно рассматривать и как мультипликативный оператор, действующий диагонально на $\phi$ :

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

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

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

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

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