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

Чтобы узнать о дискретном эквиваленте преобразования Лапласа, см. Z-преобразование .

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

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

Определения

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

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

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

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

где $d(w,v)$ — расстояние в графе между вершинами 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 (v)-\phi (w)\right]$

где $\gamma _{wv}$ значение веса на краю $wv\in E$.

С дискретным лапласианом тесно связан оператор усреднения :

$(M\phi )(v)={\frac {1}{\deg v}}\sum _{w:\,d(w,v)=1}\phi (w).$

Сетка лапласианов

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

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

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

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

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

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

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

Более общий обзор операторов сетки дан в.

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

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

$\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 ) в сетке равен

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

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

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

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

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

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

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

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

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

1D-фильтр: ${\vec {D}}_{x}^{2}={\begin{bmatrix}1&-2&1\end{bmatrix}}$,

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

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

2D-фильтр: $\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 filter: $\mathbf {D} _{xyz}^{2}$ с использованием семиточечного трафарета определяется следующим образом:

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

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

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

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

$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-фильтр: $\mathbf {D} _{xy}^{2}={\begin{bmatrix}1&1&1\\1&-8&1\\1&1&1\end{bmatrix}}.$

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

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

$\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 дает наилучшее приближение вращательной симметрии. Что касается трехмерных сигналов, то показано что оператор Лапласа можно аппроксимировать двухпараметрическим семейством разностных операторов

$\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}),$

где

$(\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},$

$(\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}),$

$(\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}).$

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

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

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

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

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

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

Спектр

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

Теоремы

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

${\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}$,

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

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

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

что дает

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

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

Чтобы найти решение этого дифференциального уравнения, примените стандартные методы решения матричного дифференциального уравнения первого порядка . То есть напишите ${\textstyle \phi }$ как линейная комбинация собственных векторов ${\textstyle \mathbf {v} _{i}}$ L что (так ${\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}}$ ортогональны):

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

чье решение

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

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

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

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

Этот подход был применен для количественного моделирования теплопередачи на неструктурированных сетках.

В случае неориентированных графов это работает, потому что ${\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}$, с

$\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}$ вершины

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

где

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

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

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

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

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

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

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

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

N = 20; % The number of pixels along a dimension of the image
A = zeros(N, N); % The image
Adj = zeros(N * N, N * N); % The adjacency matrix

% Use 8 neighbors, and fill in the adjacency matrix
dx = [- 1, 0, 1, - 1, 1, - 1, 0, 1];
dy = [- 1, - 1, - 1, 0, 0, 1, 1, 1];
for x = 1:N
    for y = 1:N
        index = (x - 1) * N + y;
        for ne = 1:length(dx)
            newx = x + dx(ne);
            newy = y + dy(ne);
            if newx > 0 && newx <= N && newy > 0 && newy <= N
                index2 = (newx - 1) * N + newy;
                Adj(index, index2) = 1;
            end
        end
    end
end

% BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL EQUATION
Deg = diag(sum(Adj, 2)); % Compute the degree matrix
L = Deg - Adj; % Compute the laplacian matrix in terms of the degree and adjacency matrices
[V, D] = eig(L); % Compute the eigenvalues/vectors of the laplacian matrix
D = diag(D);

% Initial condition (place a few large positive values around and
% make everything else zero)
C0 = zeros(N, N);
C0(2:5, 2:5) = 5;
C0(10:15, 10:15) = 10;
C0(2:5, 8:13) = 7;
C0 = C0(:);

C0V = V'*C0; % Transform the initial condition into the coordinate system
% of the eigenvectors
for t = 0:0.05:5
    % Loop through times and decay each initial component
    Phi = C0V .* exp(- D * t); % Exponential decay for each component
    Phi = V * Phi; % Transform from eigenvector coordinate system to original coordinate system
    Phi = reshape(Phi, N, N);
    % Display the results and write to GIF file
    imagesc(Phi);
    caxis([0, 10]);
     title(sprintf('Diffusion t = %3f', t));
    frame = getframe(1);
    im = frame2im(frame);
    [imind, cm] = 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);
    end
end

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

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

$(P\phi )(v)=P(v)\phi (v).$

Затем $H=\Delta +P$ — дискретный оператор Шредингера , аналог непрерывного оператора Шредингера .

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

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

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

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

$G(v,w;\lambda )=\left\langle \delta _{v}\left|{\frac {1}{H-\lambda }}\right|\delta _{w}\right\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).$

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

Дополнительная информация: классификация ADE.

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

$\Delta \phi =\phi ,$

словами,

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

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

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

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

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

$\Delta \phi =\phi -2.$

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

См. также

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

Ссылки

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

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

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