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

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

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

Определение

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

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

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

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

Фильтр 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}}}$

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

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

Фильтр 3D: ${\displaystyle \mathbf {D} _{xyz}^{3}}$

для первой плоскости = ${\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}}}$

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

На графах

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

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

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

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

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

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

${\displaystyle (\Delta _{\gamma }\phi )(v)=\sum _{w:d(w,v)=1}\gamma _{wv}\left[\phi (w)-\phi (v)\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 \Delta =I-M}$ , то спектр лежит в отрезке ${\displaystyle [0,2]}$ (в то время как у усредняющего оператора его спектральные значения в ${\displaystyle [-1,1]}$ ) и содержит ноль (для постоянных функций). Наименьшее ненулевое собственное число ${\displaystyle \lambda _{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}}}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки