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

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

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

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


Содержание

Определение

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

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

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

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

Фильтр 1D: \vec{D}^2_x=\begin{bmatrix}1 & -2 & 1\end{bmatrix}


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

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

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


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

для первой плоскости = \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. Тогда дискретный лапласиан \Delta от \phi будет определяться как

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

где d(w,v) есть функция расстояния между вершинами графа. Эта сумма — на ближайших соседях вершины v. Для графа с конечным количеством вершин и рёбер это определение совпадает с матрицей Лапласа, то есть \phi может быть записано как вектор-столбец, \Delta\phi есть вектор-столбец, умноженный на матрицу Лапласа, а (\Delta \phi)(v) есть лишь запись векторного произведения для 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^2F}{\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 — ограниченный и самосопряжённый.

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

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

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

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

G(v,w;\lambda)=\langle\delta_v| \frac{1}{H-\lambda}| \delta_w\rangle

где \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).

См. также

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

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "Дискретный оператор Лапласа" в других словарях:

  • Оператор Собеля — Паровая машина в цвете …   Википедия

  • Оператор (физика) — У этого термина существуют и другие значения, см. Оператор.     Квантовая механика …   Википедия

  • Оператор физической величины — Квантовая механика Принцип неопределённости Введение ... Математическая формулировка ... Основа …   Википедия

  • МЕМБРАНА — (от лат. membrana кожица, перепонка) в акустике, гибкая тонкая плёнка, приведённая внеш. силами в состояние натяжения и обладающая вследствие этого упругостью. От М. следует отличать пластинку, упругость к рой зависит от её материала и толщины.… …   Физическая энциклопедия

  • СПЕКТРАЛЬНАЯ ТЕОРИЯ — дифференциальных операторов раздел общей спектральной теории операторов, к рый изучает спектральные свойства дифференциальных операторов в различных пространствах функций, особенно в гильбертовых пространствах измеримых функций. Пусть область в… …   Математическая энциклопедия

  • Передаточная функция — один из способов математического описания динамической системы. Используется в основном в теории управления, связи, цифровой обработке сигналов. Представляет собой дифференциальный оператор, выражающий связь между входом и выходом линейной… …   Википедия

  • ГОСТ 21878-76: Случайные процессы и динамические системы. Термины и определения — Терминология ГОСТ 21878 76: Случайные процессы и динамические системы. Термины и определения оригинал документа: Cross power spectral density function of stationary dependent random processes Определения термина из разных документов: Cross power… …   Словарь-справочник терминов нормативно-технической документации


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»