Русская Википедия:Дискретный оператор Лапласа
- О дискретном эквиваленте преобразования Лапласа см. Z-преобразование.
В математике дискретный оператор Лапласа — аналог непрерывного оператора Лапласа, определяемого как отношения на графе или дискретной сетке. В случае конечномерного графа (имеющего конечное число вершин и рёбер) дискретный оператор Лапласа имеет более общее название: матрица Лапласа.
Понятие о дискретном операторе Лапласа происходит из таких физических проблем, как модель Изинга и петлевая квантовая гравитация, а также из изучения динамических систем. Этот оператор используется также в вычислительной математике как аналог непрерывного оператора Лапласа. Будучи известным как фильтр Лапласа, часто находит приложение в обработке изображений. Кроме того, оператор используется в машинном обучении для кластеризации и полуавтоматического обучения на графах соседства.
Определение
Обработка изображений
Дискретный оператор Лапласа часто используется в обработке изображений, например в задаче выделения границ или в приложениях оценки движения. Дискретный лапласиан определяется как сумма вторых производных и вычисляется как сумма перепадов на соседях центрального пиксела.
Реализация в обработке изображений
Для одномерных, двухмерных и трёхмерных сигналов дискретный лапласиан можно задать как свёртку со следующими ядрами:
- Фильтр 1D: <math>\vec{D}^2_x=\begin{bmatrix}1 & -2 & 1\end{bmatrix}</math>
- Фильтр 2D: <math>\mathbf{D}^2_{xy}=\begin{bmatrix}0 & 1 & 0\\1 & -4 & 1\\0 & 1 & 0\end{bmatrix}</math>
или с диагоналями:
- Фильтр 2D: <math>\mathbf{D}^2_{xy}=\begin{bmatrix}1 & 1 & 1\\1 & -8 & 1\\1 & 1 & 1\end{bmatrix}</math>
- Фильтр 3D: <math>\mathbf{D}^3_{xyz} </math>
для первой плоскости = <math>\begin{bmatrix}0 & 0 & 0\\0 & 1 & 0\\0 & 0 & 0\end{bmatrix}</math> ; для второй <math>\begin{bmatrix}0 & 1 & 0\\1 & -6 & 1\\0 & 1 & 0\end{bmatrix}</math> ; для третьей <math>\begin{bmatrix}0 & 0 & 0\\0 & 1 & 0\\0 & 0 & 0\end{bmatrix}</math>
Эти ядра выводятся с помощью дискретных частных производных.
На графах
Есть разные определения дискретного лапласиана, различающиеся знаком и масштабным коэффициентом (иногда средние на соседних вершинах, иногда просто сумма; это не имеет значения для регулярного графа).
Пусть G=(V,E) будет графом с вершинами V и рёбрами E. Зададим функцию значений <math>\phi\colon V\to R</math> из вершин графа в кольцо <math>R</math>. Тогда дискретный лапласиан <math>\Delta</math> от <math>\phi</math> будет определяться как
- <math>(\Delta \phi)(v)=\sum_{w:d(w,v)=1}\left[\phi(w)-\phi(v)\right]</math>
где d(w,v) есть функция расстояния между вершинами графа. Эта сумма — на ближайших соседях вершины v. Вершины конечного графа можно пронумеровать, тогда отображение <math>\phi</math> может быть записано как вектор-столбец, элементами которого являются значения отображения: <math>\phi_v = \phi(v)</math>. Данное выше определение лапласиана также может быть переписано в векторной форме с использованием матрицы Лапласа <math>L</math>:
- <math>(\Delta \phi)(v) = (L\cdot\phi)_v</math>
Если рёбра графа имеют веса, то есть задана весовая функция <math>\gamma\colon E\to R</math>, то определение можно записать как
- <math>(\Delta_\gamma\phi)(v)=\sum_{w:d(w,v)=1}\gamma_{wv}\left[\phi(w)-\phi(v)\right]</math>
где <math>\gamma_{wv}</math> есть вес ребра <math>wv\in E</math>.
Близко лежит определение усредняющего оператора:
- <math>(M\phi)(v)=\frac{1}{\deg v}\sum_{w:d(w,v)=1}\phi(w)</math>
Спектр
Спектр дискретного лапласиана представляет ключевой интерес; когда он имеет самосопряжённый спектр, он действителен. Если <math>\Delta = I - M</math>, то спектр лежит в отрезке <math>[0,2]</math> (в то время как у усредняющего оператора его спектральные значения в <math>[-1,1]</math>) и содержит ноль (для постоянных функций). Наименьшее ненулевое собственное число <math>\lambda_1</math> называют спектральной щелью. Обычно различают и понятие о спектральном радиусе, определяемом обычно как наибольшее собственное число.
Собственные вектора не зависят от условностей (для регулярных графов), и они схожи с собственными векторами усредняющего оператора (различаясь добавлением), хотя собственные значения могут различаться в зависимости от соглашения.
Теоремы
Если граф представляет собой бесконечную квадратную решётку, то его определение лапласиана можно связать с непрерывным лапласианом через предел бесконечной решётки. К пример, в одномерном случае мы имеем
- <math>\frac{\partial^2F}{\partial x^2} =
\lim_{\epsilon \rightarrow 0}
\frac{[F(x+\epsilon)-F(x)]+[F(x-\epsilon)-F(x)]}{\epsilon^2}.
</math>
Это определение лапласиана часто используется в вычислительной математике и обработке изображений. В последнем случае оно рассматривается как разновидность цифрового фильтра, как граничный фильтр, называемый фильтром Лапласа.
Дискретный оператор Шрёдингера
Пусть <math>P:V\rightarrow R</math> есть потенциал, заданный на графе. Заметим, что P можно рассматривать и как мультипликативный оператор, действующий диагонально на <math>\phi</math>:
<math>(P\phi)(v)=P(v)\phi(v).</math>
Тогда <math>H=\Delta+P</math> есть дискретный оператор Шрёдингера, аналог непрерывного оператора Шрёдингера.
Если количество рёбер вершины равномерно ограничено, то H — ограниченный и самосопряжённый.
Спектральные свойства его гамильтониана могут быть получены из теоремы Стоуна; это следствие из двойственности между частично упорядоченными множествами и булевой алгеброй.
На регулярных решётках оператор обычно имеет и бегущую волну, и решения локализации Андерсона — в зависимости от периодичности или случайности потенциала.
Дискретная функция Грина
Функция Грина дискретного оператора Шрёдингера задана резольвентой линейного оператора:
- <math>G(v,w;\lambda)=\langle\delta_v| \frac{1}{H-\lambda}| \delta_w\rangle </math>
где <math>\delta_w</math> понимается как символ Кронекера на графе: <math>\delta_w(v)=\delta_{wv}</math>, то есть это равно 1, если v=w, и 0 иначе.
Для фиксированного <math>w\in V</math> и комплексного <math>\lambda</math>, функция Грина рассматривается как функция от v, уникальное решение уравнения
- <math>(H-\lambda)G(v,w;\lambda)=\delta_w(v).</math>
См. также
Ссылки
