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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
О дискретном эквиваленте преобразования Лапласа см. Z-преобразование.

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

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


Определение[править | править вики-текст]

Обработка изображений[править | править вики-текст]

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

Реализация в обработке изображений[править | править вики-текст]

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

Фильтр 1D:


Фильтр 2D:

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

Фильтр 2D:


Фильтр 3D:

для первой плоскости =  ; для второй  ; для третьей

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

На графах[править | править вики-текст]

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

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

где d(w,v) есть функция расстояния между вершинами графа. Эта сумма — на ближайших соседях вершины v. Для графа с конечным количеством вершин и рёбер это определение совпадает с матрицей Лапласа, то есть может быть записано как вектор-столбец, есть вектор-столбец, умноженный на матрицу Лапласа, а есть лишь запись векторного произведения для v.

Если рёбра графа имеют веса, то есть задана весовая функция , то определение можно записать как

где есть вес ребра .

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

Спектр[править | править вики-текст]

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

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

Теоремы[править | править вики-текст]

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

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

Дискретный оператор Шрёдингера[править | править вики-текст]

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

Тогда есть дискретный оператор Шрёдингера, аналог непрерывного оператора Шрёдингера.

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

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

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

Дискретная функция Грина[править | править вики-текст]

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

где понимается как символ Кронекера на графе: , то есть это равно 1, если v=w, и 0 иначе.

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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]