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

Аналог непрерывного операто Лапласа

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

Дискретный оператор Лапласа встречается в физических задачах, таких как модель Изинга и петлевая квантовая гравитация , а также при исследовании дискретных динамических систем . Он также используется в численном анализе в качестве замены непрерывного оператора Лапласа. Общие приложения включают обработку изображений ^[1] , где он известен как фильтр Лапласа , а также машинное обучение для кластеризации и полуконтролируемого обучения на графах окрестностей.

Определения

Граф лапласианов

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

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

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

где – расстояние в графе между вершинами w и v. Таким образом, эта сумма рассчитана по ближайшим соседям вершины v . Для графа с конечным числом ребер и вершин это определение идентично определению матрицы Лапласа . То есть его можно записать как вектор-столбец; и то же самое является произведением вектора-столбца и матрицы Лапласа, а это всего лишь v- я запись вектора-произведения. ${\displaystyle d(w,v)}$ ${\displaystyle \phi }$ ${\displaystyle \Delta \phi }$ ${\displaystyle (\Delta \phi )(v)}$

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

${\displaystyle (\Delta _{\gamma }\phi )(v)=\sum _{w:\,d(w,v)=1}\gamma _{wv}\left[\phi (v)-\phi (w)\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 u}$ ${\displaystyle i}$

${\displaystyle (\Delta u)_{i}\equiv {\frac {1}{2A_{i}}}\sum _{j}(\cot \alpha _{ij}+\cot \beta _{ij})(u_{j}-u_{i}),}$

где сумма рассчитана по всем соседним вершинам , и являются двумя углами, противоположными краю , и является площадью вершины ; то есть, например, одна треть суммированных площадей треугольников, инцидентных . Важно отметить, что знак дискретного оператора Лапласа-Бельтрами условно противоположен знаку обычного оператора Лапласа . Приведенную выше формулу котангенса можно вывести с использованием множества различных методов, среди которых кусочно-линейные конечные элементы , конечные объемы и дискретное внешнее исчисление ^[2] (загрузка PDF: [1]). ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle \alpha _{ij}}$ ${\displaystyle \beta _{ij}}$ ${\displaystyle ij}$ ${\displaystyle A_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$

Для облегчения вычислений лапласиан кодируется в матрице такой, что . Пусть – (разреженная) котангенс-матрица с элементами ${\displaystyle L\in \mathbb {R} ^{|V|\times |V|}}$ ${\displaystyle Lu=(\Delta u)_{i}}$ ${\displaystyle C}$

${\displaystyle C_{ij}={\begin{cases}{\frac {1}{2}}(\cot \alpha _{ij}+\cot \beta _{ij})&ij{\text{ is an edge, that is }}j\in N(i),\\-\sum \limits _{k\in N(i)}C_{ik}&i=j,\\0&{\text{otherwise}}\end{cases}}}$

Где обозначает окрестность . ${\displaystyle N(i)}$ ${\displaystyle i}$

И пусть — диагональная матрица масс , -я запись которой по диагонали — это площадь вершины . Тогда осуществляется искомая дискретизация лапласиана. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle i}$ ${\displaystyle A_{i}}$ ${\displaystyle L=M^{-1}C}$

Более общий обзор операторов сетки дан в ^{[3] .}

Конечные разности

Аппроксимации лапласиана , полученные методом конечных разностей или методом конечных элементов , также можно назвать дискретными лапласианами . Например, лапласиан в двух измерениях можно аппроксимировать с помощью метода конечных разностей пятиточечного трафарета , что приводит к

${\displaystyle \Delta f(x,y)\approx {\frac {f(x-h,y)+f(x+h,y)+f(x,y-h)+f(x,y+h)-4f(x,y)}{h^{2}}},}$

где размер сетки h в обоих измерениях, так что пятиточечный трафарет точки ( x ,  y ) в сетке равен

${\displaystyle \{(x-h,y),(x,y),(x+h,y),(x,y-h),(x,y+h)\}.}$

Если размер сетки h = 1, результатом является отрицательный дискретный лапласиан на графике, который представляет собой сетку квадратной решетки . Здесь нет ограничений на значения функции f ( x , y ) на границе решетчатой ​​сетки, таким образом, это случай отсутствия источника на границе, то есть граничное условие отсутствия потока (также известное как изоляция , или однородное граничное условие Неймана ). Управление переменной состояния на границе, как f ( x , y ), заданной на границе сетки (также известное как граничное условие Дирихле ), редко используется для лапласианов графа, но распространено в других приложениях.

Многомерные дискретные лапласианы на прямоугольных кубовидных регулярных сетках обладают совершенно особыми свойствами, например, они представляют собой суммы Кронекера одномерных дискретных лапласианов, см. Сумма Кронекера дискретных лапласианов , и в этом случае все его собственные значения и собственные векторы могут быть явно вычислены.

Метод конечных элементов

В этом подходе область дискретизируется на более мелкие элементы, часто треугольники или тетраэдры, но возможны и другие элементы, такие как прямоугольники или кубоиды. Затем пространство решений аппроксимируется с использованием так называемых форм-функций заранее определенной степени. Дифференциальное уравнение, содержащее оператор Лапласа, затем преобразуется к вариационной формулировке и строится система уравнений (линейных задач или задач на собственные значения). Полученные матрицы обычно очень разрежены и могут быть решены итерационными методами.

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

Дискретный оператор Лапласа часто используется при обработке изображений, например, в приложениях обнаружения границ и оценки движения. ^[4] Дискретный лапласиан определяется как сумма вторых производных операторов Лапласа#Координатных выражений и рассчитывается как сумма разностей по ближайшим соседям центрального пикселя. Поскольку производные фильтры часто чувствительны к шуму в изображении, оператору Лапласа часто предшествует сглаживающий фильтр (например, фильтр Гаусса), чтобы удалить шум перед вычислением производной. Сглаживающий фильтр и фильтр Лапласа часто объединяют в один фильтр. ^[5]

Реализация посредством операторной дискретизации

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

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}}}$

${\displaystyle \mathbf {D} _{xy}^{2}}$соответствует формуле конечных разностей ( пятиточечный трафарет ), рассмотренной ранее. Он устойчив для очень плавно меняющихся полей, но для уравнений с быстро меняющимися решениями требуется более устойчивая и изотропная форма оператора Лапласа, ^[6] такая как девятиточечный шаблон , включающий в себя диагонали:

2D-фильтр: , ${\displaystyle \mathbf {D} _{xy}^{2}={\begin{bmatrix}0.25&0.5&0.25\\0.5&-3&0.5\\0.25&0.5&0.25\end{bmatrix}}}$

3D-фильтр: использование семиточечного трафарета определяется следующим образом: ${\displaystyle \mathbf {D} _{xyz}^{2}}$

первый самолет = ; вторая плоскость = ; третий самолет = . ${\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}}}$

и используя 27-точечный трафарет: ^[7]

первый самолет = ; вторая плоскость = ; третий самолет = . ${\displaystyle {\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}}$ ${\displaystyle {\frac {1}{26}}{\begin{bmatrix}3&6&3\\6&-88&6\\3&6&3\end{bmatrix}}}$ ${\displaystyle {\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}}$

n D фильтр : Для элементаядра ${\displaystyle a_{x_{1},x_{2},\dots ,x_{n}}}$ ${\displaystyle \mathbf {D} _{x_{1},x_{2},\dots ,x_{n}}^{2},}$

${\displaystyle a_{x_{1},x_{2},\dots ,x_{n}}=\left\{{\begin{array}{ll}-2n&{\text{if }}s=n,\\1&{\text{if }}s=n-1,\\0&{\text{otherwise,}}\end{array}}\right.}$

где x _i — позиция (либо −1 , 0 или 1 ) элемента в ядре в i -м направлении, а s — количество направлений i, для которых x _i = 0 .

Обратите внимание, что версия n D, основанная на графическом обобщении лапласиана, предполагает, что все соседи находятся на одинаковом расстоянии, и, следовательно, приводит к следующему 2D-фильтру с включенными диагоналями, а не к версии выше:

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

Эти ядра выводятся с использованием дискретных дифференциальных коэффициентов.

Можно показать ^{[8] [9]} , что следующая дискретная аппроксимация двумерного оператора Лапласа как выпуклой комбинации разностных операторов

${\displaystyle \nabla _{\gamma }^{2}=(1-\gamma )\nabla _{5}^{2}+\gamma \nabla _{\times }^{2}=(1-\gamma ){\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}+\gamma {\begin{bmatrix}1/2&0&1/2\\0&-2&0\\1/2&0&1/2\end{bmatrix}}}$

для γ ∈ [0, 1] совместимо со свойствами дискретного масштабного пространства, где, в частности, значение γ = 1/3 дает наилучшее приближение вращательной симметрии. ^{[8] [9] [10]} Что касается трехмерных сигналов, показано ^[9] , что оператор Лапласа может быть аппроксимирован двухпараметрическим семейством разностных операторов

${\displaystyle \nabla _{\gamma _{1},\gamma _{2}}^{2}=(1-\gamma _{1}-\gamma _{2})\,\nabla _{7}^{2}+\gamma _{1}\,\nabla _{+^{3}}^{2}+\gamma _{2}\,\nabla _{\times ^{3}}^{2}),}$

где

${\displaystyle (\nabla _{7}^{2}f)_{0,0,0}=f_{-1,0,0}+f_{+1,0,0}+f_{0,-1,0}+f_{0,+1,0}+f_{0,0,-1}+f_{0,0,+1}-6f_{0,0,0},}$

${\displaystyle (\nabla _{+^{3}}^{2}f)_{0,0,0}={\frac {1}{4}}(f_{-1,-1,0}+f_{-1,+1,0}+f_{+1,-1,0}+f_{+1,+1,0}+f_{-1,0,-1}+f_{-1,0,+1}+f_{+1,0,-1}+f_{+1,0,+1}+f_{0,-1,-1}+f_{0,-1,+1}+f_{0,+1,-1}+f_{0,+1,+1}-12f_{0,0,0}),}$

${\displaystyle (\nabla _{\times ^{3}}^{2}f)_{0,0,0}={\frac {1}{4}}(f_{-1,-1,-1}+f_{-1,-1,+1}+f_{-1,+1,-1}+f_{-1,+1,+1}+f_{+1,-1,-1}+f_{+1,-1,+1}+f_{+1,+1,-1}+f_{+1,+1,+1}-8f_{0,0,0}).}$

Реализация посредством непрерывной реконструкции

Дискретный сигнал, содержащий изображения, можно рассматривать как дискретное представление непрерывной функции , где вектор координат и область значений действительны . Таким образом, операция деривации напрямую применима к непрерывной функции . В частности, любое дискретное изображение с разумными предположениями о процессе дискретизации, например, при условии, что функции с ограниченной полосой частот или расширяемые вейвлет-функции и т. д. могут быть восстановлены с помощью хорошо работающих интерполяционных функций, лежащих в основе формулировки реконструкции, ^[11] ${\displaystyle f({\bar {r}})}$ ${\displaystyle {\bar {r}}\in R^{n}}$ ${\displaystyle f\in R}$ ${\displaystyle f}$

${\displaystyle f({\bar {r}})=\sum _{k\in K}f_{k}\mu _{k}({\bar {r}})}$

где - дискретные представления на сетке и - функции интерполяции, специфичные для сетки . На однородной сетке, такой как изображения, и для функций с ограниченной полосой пропускания, функции интерполяции являются инвариантными к сдвигу и представляют собой соответствующим образом расширенную функцию sinc , определенную в -размерностях, т.е. Другие аппроксимации на равномерных сетках представляют собой соответствующим образом расширенные функции Гаусса в -мерностях. Соответственно, дискретный лапласиан становится дискретной версией лапласиана непрерывной ${\displaystyle f_{k}\in R}$ ${\displaystyle f}$ ${\displaystyle K}$ ${\displaystyle \mu _{k}}$ ${\displaystyle K}$ ${\displaystyle \mu _{k}({\bar {r}})=\mu ({\bar {r}}-{\bar {r}}_{k})}$ ${\displaystyle \mu }$ ${\displaystyle n}$ ${\displaystyle {\bar {r}}=(x_{1},x_{2}...x_{n})^{T}}$ ${\displaystyle \mu }$ ${\displaystyle n}$ ${\displaystyle f({\bar {r}})}$

${\displaystyle \nabla ^{2}f({\bar {r}}_{k})=\sum _{k'\in K}f_{k'}(\nabla ^{2}\mu ({\bar {r}}-{\bar {r}}_{k'}))|_{{\bar {r}}={\bar {r}}_{k}}}$

которая, в свою очередь, является сверткой с лапласианом интерполяционной функции на равномерной (изображительной) сетке . Преимущество использования гауссианов в качестве функций интерполяции заключается в том, что они дают линейные операторы, включая лапласианы, которые свободны от артефактов вращения системы координат, в которой они представлены через -размерности , и по определению учитывают частоту. Линейный оператор имеет не только ограниченный диапазон в области, но и эффективный диапазон в частотной области (альтернативно гауссово масштабное пространство), которым можно принципиально управлять явно через дисперсию гауссианы. Результирующая фильтрация может быть реализована с помощью разделяемых фильтров и представлений прореживания (обработка сигналов) / пирамиды (обработка изображений) для повышения эффективности вычислений в -размерностях. Другими словами, дискретный фильтр Лапласа любого размера может быть удобно сгенерирован как дискретный лапласиан гауссиана с пространственным размером, соответствующим потребностям конкретного приложения и контролируемым его дисперсией. Мономы, которые являются нелинейными операторами, также могут быть реализованы с использованием аналогичного подхода реконструкции и аппроксимации при условии, что сигнал достаточно передискретизирован. Таким образом, могут быть реализованы такие нелинейные операторы, как Структурный тензор и Обобщенный структурный тензор , которые используются в распознавании образов из-за их полной оптимальности по методу наименьших квадратов при оценке ориентации. ${\displaystyle K}$ ${\displaystyle f}$ ${\displaystyle f_{k}}$ ${\displaystyle n}$ ${\displaystyle {\bar {r}}}$ ${\displaystyle n}$

Спектр

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

Теоремы

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

${\displaystyle {\frac {\partial ^{2}F}{\partial x^{2}}}=\lim _{\epsilon \rightarrow 0}{\frac {[F(x+\epsilon )-F(x)]-[F(x)-F(x-\epsilon )]}{\epsilon ^{2}}}.}$

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

Дискретное уравнение теплопроводности

Предположим , описывается распределение температуры по графу , где – температура в вершине . Согласно закону охлаждения Ньютона , теплота, передаваемая от узла к узлу, пропорциональна тому , если узлы и соединены (если они не соединены, тепло не передается). Тогда для теплопроводности ${\textstyle \phi }$ ${\textstyle \phi _{i}}$ ${\textstyle i}$ ${\textstyle i}$ ${\textstyle j}$ ${\textstyle \phi _{i}-\phi _{j}}$ ${\textstyle i}$ ${\textstyle j}$ ${\textstyle k}$

${\displaystyle {\begin{aligned}{\frac {d\phi _{i}}{dt}}&=-k\sum _{j}A_{ij}\left(\phi _{i}-\phi _{j}\right)\\&=-k\left(\phi _{i}\sum _{j}A_{ij}-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\left(\phi _{i}\ \deg(v_{i})-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\sum _{j}\left(\delta _{ij}\ \deg(v_{i})-A_{ij}\right)\phi _{j}\\&=-k\sum _{j}\left(L_{ij}\right)\phi _{j}.\end{aligned}}}$

В матрично-векторной записи

${\displaystyle {\begin{aligned}{\frac {d\phi }{dt}}&=-k(D-A)\phi \\&=-kL\phi ,\end{aligned}}}$

который дает

${\displaystyle {\frac {d\phi }{dt}}+kL\phi =0.}$

Обратите внимание, что это уравнение принимает ту же форму, что и уравнение теплопроводности , где матрица −L заменяет оператор Лапласа ; отсюда и «граф лапласиан». ${\textstyle \nabla ^{2}}$

Чтобы найти решение этого дифференциального уравнения, примените стандартные методы решения матричного дифференциального уравнения первого порядка . То есть запишите как линейную комбинацию собственных векторов L (так что ) с зависящими от времени коэффициентами, ${\textstyle \phi }$ ${\textstyle \mathbf {v} _{i}}$ ${\textstyle L\mathbf {v} _{i}=\lambda _{i}\mathbf {v} _{i}}$ ${\textstyle \phi (t)=\sum _{i}c_{i}(t)\mathbf {v} _{i}.}$

Подключаемся к исходному выражению (поскольку L — симметричная матрица, ее собственные векторы единичной нормы ортогональны): ${\textstyle \mathbf {v} _{i}}$

${\displaystyle {\begin{aligned}0={}&{\frac {d\left(\sum _{i}c_{i}(t)\mathbf {v} _{i}\right)}{dt}}+kL\left(\sum _{i}c_{i}(t)\mathbf {v} _{i}\right)\\{}={}&\sum _{i}\left[{\frac {dc_{i}(t)}{dt}}\mathbf {v} _{i}+kc_{i}(t)L\mathbf {v} _{i}\right]\\{}={}&\sum _{i}\left[{\frac {dc_{i}(t)}{dt}}\mathbf {v} _{i}+kc_{i}(t)\lambda _{i}\mathbf {v} _{i}\right]\\\Rightarrow 0={}&{\frac {dc_{i}(t)}{dt}}+k\lambda _{i}c_{i}(t),\\\end{aligned}}}$

чье решение

${\displaystyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}.}$

Как было показано ранее, собственные значения L неотрицательны, показывая, что решение уравнения диффузии приближается к равновесию, поскольку оно только экспоненциально затухает или остается постоянным . Это также показывает, что при заданном и начальном условии решение может быть найдено в любой момент времени t . ^[12] ${\textstyle \lambda _{i}}$ ${\textstyle \lambda _{i}}$ ${\textstyle c_{i}(0)}$

Чтобы найти для каждого из них общие начальные условия , просто спроецируйте их на собственные векторы единичной нормы ; ${\textstyle c_{i}(0)}$ ${\textstyle i}$ ${\textstyle \phi (0)}$ ${\textstyle \phi (0)}$ ${\textstyle \mathbf {v} _{i}}$

${\displaystyle c_{i}(0)=\left\langle \phi (0),\mathbf {v} _{i}\right\rangle }$.

Этот подход был применен для количественного моделирования теплопередачи на неструктурированных сетках. ^{[13] [14]}

В случае неориентированных графов это работает, поскольку он симметричен и по спектральной теореме все его собственные векторы ортогональны. Таким образом, проекция на собственные векторы представляет собой просто преобразование ортогональных координат начального состояния в набор координат, которые затухают экспоненциально и независимо друг от друга. ${\textstyle L}$ ${\textstyle L}$

Равновесное поведение

Чтобы понять , остаются только те термины , где , поскольку ${\textstyle \lim _{t\to \infty }\phi (t)}$ ${\textstyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}}$ ${\textstyle \lambda _{i}=0}$

${\displaystyle \lim _{t\to \infty }e^{-k\lambda _{i}t}={\begin{cases}0,&{\text{if}}&\lambda _{i}>0\\1,&{\text{if}}&\lambda _{i}=0\end{cases}}}$

Другими словами , состояние равновесия системы полностью определяется ядром . ${\textstyle L}$

Поскольку по определению вектор всех единиц находится в ядре. Если в графе есть непересекающиеся компоненты связности , то этот вектор всех единиц можно разбить на сумму независимых собственных векторов единиц и нулей, где каждому компоненту связности соответствует собственный вектор с единицами в элементах компонента связности и нулями в других местах. . ${\textstyle \sum _{j}L_{ij}=0}$ ${\textstyle \mathbf {v} ^{1}}$ ${\textstyle k}$ ${\textstyle k}$ ${\textstyle \lambda =0}$

Следствием этого является то, что при заданном начальном условии для графа с вершинами ${\textstyle c(0)}$ ${\textstyle N}$

${\displaystyle \lim _{t\to \infty }\phi (t)=\left\langle c(0),\mathbf {v^{1}} \right\rangle \mathbf {v^{1}} }$

где

${\displaystyle \mathbf {v^{1}} ={\frac {1}{\sqrt {N}}}[1,1,\ldots ,1]}$

Для каждого элемента , т.е. для каждой вершины графа, его можно переписать как ${\textstyle \phi _{j}}$ ${\textstyle \phi }$ ${\textstyle j}$

${\displaystyle \lim _{t\to \infty }\phi _{j}(t)={\frac {1}{N}}\sum _{i=1}^{N}c_{i}(0)}$.

Другими словами, в устойчивом состоянии значение сходится к одному и тому же значению в каждой вершине графа, которое является средним значением начальных значений во всех вершинах. Поскольку это решение уравнения диффузии тепла, это интуитивно понятно. Мы ожидаем, что соседние элементы графа будут обмениваться энергией до тех пор, пока эта энергия не распределится равномерно по всем элементам, которые связаны друг с другом. ${\textstyle \phi }$

Пример оператора в сетке

Этот GIF-изображение показывает прогресс диффузии, решенный с помощью метода лапласиана графа. Граф строится на сетке, где каждый пиксель графика связан с 8 граничащими с ним пикселями. Значения на изображении затем плавно распространяются к своим соседям с течением времени через эти связи. Этот конкретный образ начинается с трех сильных сторон, которые медленно распространяются на своих соседей. Вся система в конечном итоге достигает одного и того же значения в состоянии равновесия.

В этом разделе показан пример функции , распространяющейся во времени по графику. График в этом примере построен на двумерной дискретной сетке, точки которой соединены со своими восемью соседями. Три начальные точки заданы как имеющие положительное значение, а остальные значения в сетке равны нулю. Со временем экспоненциальное затухание приводит к равномерному распределению значений в этих точках по всей сетке. ${\textstyle \phi }$

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

Н = 20 ; % Количество пикселей по размеру изображения A = нули ( N , N ); % Изображение Adj = нули ( N * N , N * N ); % Матрица смежности               % Используйте 8 соседей и заполните матрицу смежности dx = [ - 1 , 0 , 1 , - 1 , 1 , - 1 , 0 , 1 ]; dy = [ - 1 , - 1 , - 1 , 0 , 0 , 1 , 1 , 1 ]; для x = 1 : N для y = 1 : N индекс = ( x - 1 ) * N + y ; для ne = 1 : длина ( dx ) newx = x + dx ( ne ); новый = y + dy ( ne ); if newx > 0 && newx <= N && newy > 0 && newy <= N index2 = ( newx - 1 ) * N + newy ; Adj ( индекс , индекс2 ) = 1 ; конец конец конец конец                                                                                      % НИЖЕ ПРИВЕДЕН КЛЮЧЕВОЙ КОД, КОТОРЫЙ ВЫЧИСЛЯЕТ РЕШЕНИЕ ДИФФЕРЕНЦИАЛЬНОГО УРАВНЕНИЯ Deg = diag ( sum ( Adj , 2 )); % Вычислить матрицу степеней L = Deg - Adj ; % Вычислить матрицу Лапласа через матрицы степени и смежности [ V , D ] = eig ( L ); % Вычислить собственные значения/векторы матрицы Лапласа D = Diag ( D );               % Начальное условие (поместите вокруг несколько больших положительных значений и % обнулите все остальное) C0 = нули ( N , N ); С0 ( 2 : 5 , 2 : 5 ) = 5 ; С0 ( 10:15 , 10:15 ) = 10 ; _ _ _ _ С0 ( 2 : 5 , 8:13 ) = 7 ; _ _ С0 = С0 (:);              C0V = V '* C0 ; % Преобразовать начальное условие в систему координат % собственных векторов для t = 0 : 0,05 : 5 % Пройти по времени и затухать каждый начальный компонент Phi = C0V .* exp ( - D * t ); % Экспоненциальное затухание для каждого компонента Phi = V * Phi ; % Преобразование из системы координат собственного вектора в исходную систему координат Phi = reshape ( Phi , N , N ); % Отображение результатов и запись в GIF-файл imagesc ( Phi ); какксис ([ 0 , 10 ]); title ( sprintf ( 'Diffusion t = %3f' , t )); кадр = getframe ( 1 ); im = Frame2im ( кадр ); [ imind , см ] = rgb2ind ( im , 256 ); if t == 0 imwrite ( imind , cm , 'out.gif' , 'gif' , 'Loopcount' , inf , 'DelayTime' , 0.1 ); else imwrite ( imind , cm , 'out.gif' , 'gif' , 'WriteMode' , 'append' , 'DelayTime' , 0.1 ); конец конец                                                                  

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

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

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

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

Если число ребер, сходящихся в вершине, равномерно ограничено и потенциал ограничен, то H ограничено и самосопряжено .

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

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

Функция Грина дискретного оператора Шредингера задается в резольвентном формализме выражением

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

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

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

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

Классификация ADE

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

${\displaystyle \Delta \phi =\phi ,}$

в словах,

«Дважды любая метка равна сумме меток на соседних вершинах».

находятся на расширенных (аффинных) диаграммах Дынкина ADE, из которых имеется 2 бесконечных семейства (A и D) и 3 исключения (E). Результирующая нумерация уникальна в пределах масштаба, и если наименьшее значение установлено равным 1, остальные числа будут целыми числами в диапазоне до 6.

Обычные графы ADE — единственные графы, допускающие положительную разметку со следующим свойством:

Дважды любая метка минус две — это сумма меток на соседних вершинах.

В терминах лапласиана положительные решения неоднородного уравнения:

${\displaystyle \Delta \phi =\phi -2.}$

Результирующая нумерация уникальна (масштаб указывается цифрой «2») и состоит из целых чисел; для E ₈ они варьируются от 58 до 270 и наблюдались еще в 1968 г. ^[15]

Смотрите также

• Спектральный анализ формы
• Электрическая сеть
• Кронекеровская сумма дискретных лапласианов
• Дискретное исчисление

Рекомендации

1. Левенталь, Даниэль (осень 2011 г.). «Обработка изображений» (PDF) . Университет Вашингтона . Проверено 1 декабря 2019 г.
2. Крейн, К.; де Гус, Ф.; Дебрун, М.; Шредер, П. (2013). «Цифровая геометрическая обработка с дискретным внешним исчислением». Курсы ACM SIGGRAPH 2013 . СИГРАФ '13. Том. 7. С. 1–126. дои : 10.1145/2504435.2504442.
3. Рейтер, М.; Биазотти, С.; Георгий, Д.; Патане, Г.; Спаньоло, М. (2009). «Дискретные операторы Лапласа-Бельтрами для анализа формы и сегментации». Компьютеры и графика . 33 (3): 381–390df. CiteSeerX 10.1.1.157.757 . дои : 10.1016/j.cag.2009.03.005. 
4. Форсайт, Д.А.; Понсе, Дж. (2003). "Компьютерное зрение". Компьютеры и графика . 33 (3): 381–390. CiteSeerX 10.1.1.157.757 . дои : 10.1016/j.cag.2009.03.005. 
5. Мэттис, Дон (14 февраля 2001 г.). «Лог-фильтр». Университет Маркетта . Проверено 1 декабря 2019 г.
6. Проватас, Николас; Старейшина, Кен (13 октября 2010 г.). Методы фазового поля в материаловедении и инженерии (PDF) . Вайнхайм, Германия: Wiley-VCH Verlag GmbH & Co. KGaA. п. 219. дои : 10.1002/9783527631520. ISBN 978-3-527-63152-0.
7. О'Рейли, Х.; Бек, Джеффри М. (2006). «Семейство дискретных лапласовых аппроксимаций с большим трафаретом в трех измерениях» (PDF) . Международный журнал численных методов в технике : 1–16.
8. Линдеберг, Т., «Масштабное пространство для дискретных сигналов», PAMI (12), № 3, март 1990 г., стр. 234–254.
9. Линдеберг, Т., Теория масштабного пространства в компьютерном зрении, Kluwer Academic Publishers, 1994, ISBN 0-7923-9418-6 . 
10. Патра, Майкл; Карттунен, Микко (2006). «Трафареты с ошибкой изотропной дискретизации для дифференциальных операторов». Численные методы решения уравнений в частных производных . 22 (4): 936–953. дои : 10.1002/номер.20129. ISSN  0749-159X. S2CID  123145969.
11. Бигун, Дж. (2006). Видение с направлением . Спрингер. дои : 10.1007/b138918. ISBN 978-3-540-27322-6.
12. Ньюман, Марк (2010). Сети: Введение . Издательство Оксфордского университета. ISBN 978-0199206650.
13. Явари, Р.; Коул, К.Д.; Рао, ПК (2020). «Вычислительный теплообмен с теорией спектральных графов: количественная проверка». Международный журнал тепловых наук . 153 : 106383. doi : 10.1016/j.ijthermalsci.2020.106383 .
14. Коул, К.Д.; Риенше, А.; Рао, ПК (2022). «Дискретные функции Грина и теория спектральных графов для эффективного вычислительного теплового моделирования». Международный журнал тепломассообмена . 183 : 122112. doi : 10.1016/j.ijheatmasstransfer.2021.122112 . S2CID  244652819.
15. Бурбаки, Николя (2002) [1968], Groupes et algebres de Lie: Главы 4–6, Элементы математики, перевод Прессли, Эндрю, Спрингера, ISBN 978-3-540-69171-6

• Сунада, Т. (2008). «Дискретный геометрический анализ». Анализ графиков и его приложения. Труды симпозиумов по чистой математике. Том. 77. Американское математическое общество. стр. 51–86. ISBN 978-0-8218-9384-5.

Внешние ссылки

• Оливье, Янн (2004). «Спектральная щель графа». Архивировано из оригинала 23 мая 2007 г.