Hispanopedia Wiki
Articulo de referencia

Operador de Laplace discreto

En matemáticas, el operador de Laplace discreto es un análogo del operador de Laplace continuo , definido de manera que tenga significado en un grafo o una cuadrícula discreta ....

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas, el operador de Laplace discreto es un análogo del operador de Laplace continuo , definido de manera que tenga significado en un grafo o una cuadrícula discreta . Para el caso de un grafo de dimensión finita (con un número finito de aristas y vértices), el operador de Laplace discreto se conoce más comúnmente como matriz laplaciana .

El operador de Laplace discreto aparece en problemas de física como el modelo de Ising y la gravedad cuántica de bucles , así como en el estudio de sistemas dinámicos discretos . También se utiliza en análisis numérico como sustituto del operador de Laplace continuo. Entre sus aplicaciones comunes se incluyen el procesamiento de imágenes [ 1 ] , donde se conoce como filtro de Laplace , y el aprendizaje automático para la agrupación y el aprendizaje semisupervisado en grafos de vecindad.

Definiciones

Laplacianos de grafos

Existen diversas definiciones del laplaciano discreto para grafos , que difieren en el signo y el factor de escala (a veces se promedia sobre los vértices vecinos, otras veces simplemente se suman; esto no supone ninguna diferencia para un grafo regular ). La definición tradicional del laplaciano de grafos, que se presenta a continuación, corresponde al laplaciano continuo negativo en un dominio con frontera libre.

DejarGRAMO=(V,mi){\displaystyle G=(V,E)}sea ​​un grafo con vérticesV{\displaystyle V}y bordesmi{\displaystyle E}. Dejarϕ:V→R{\displaystyle \phi \colon V\to \mathbb {R} }sea ​​una función de los vértices que toman valores en un anillo . Entonces, el laplaciano discretoΔ{\displaystyle \Delta }actuando enϕ{\displaystyle \phi }se define por

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

dónded(w,v){\displaystyle d(w,v)}es la distancia gráfica entre los vértices w y v. Por lo tanto, esta suma se realiza sobre los vecinos más cercanos del vértice v . Para un grafo con un número finito de aristas y vértices, esta definición es idéntica a la de la matriz laplaciana . Es decir,ϕ{\displaystyle \phi }se puede escribir como un vector columna ; y asíΔϕ{\displaystyle \Delta \phi }es el producto del vector columna y la matriz laplaciana, mientras que(Δϕ)(v){\displaystyle (\Delta \phi )(v)}es solo elv{\displaystyle v}entrada n-ésima del vector de producto.

Si el grafo tiene aristas ponderadas, es decir, una función de ponderaciónγ:mi→R{\displaystyle \gamma \colon E\to \mathbb {R} }Si se da, entonces la definición puede generalizarse a

(Δγϕ)(v)=∑w:d(w,v)=1γwv[ϕ(v)−ϕ(w)]{\displaystyle (\Delta _{\gamma }\phi )(v)=\sum _{w:\,d(w,v)=1}\gamma _{wv}\left[\phi (v)-\phi (w)\right]}

dóndeγwv{\displaystyle \gamma _{wv}}es el valor de peso en el bordewv∈mi{\displaystyle wv\in E}.

Estrechamente relacionado con el laplaciano discreto se encuentra el operador de promedio :

(METROϕ)(v)=1grados⁡v∑w:d(w,v)=1ϕ(w).{\displaystyle (M\phi )(v)={\frac {1}{\deg v}}\sum _{w:\,d(w,v)=1}\phi (w).}

Laplacianos de malla

Además de considerar la conectividad de nodos y aristas en un grafo, los operadores de Laplace de malla tienen en cuenta la geometría de una superficie (por ejemplo, los ángulos en los nodos). Para una malla triangular de variedad bidimensional, el operador de Laplace-Beltrami de una función escalartú{\displaystyle u}en un vérticei{\displaystyle i}puede aproximarse como

(Δtú)i≡12Ai∑j∈norte(i)(cuna⁡αij+cuna⁡βij)(túj−túi),{\displaystyle (\Delta u)_{i}\equiv {\frac {1}{2A_{i}}}\sum _{j\in N(i)}(\cot \alpha _{ij}+\cot \beta _{ij})(u_{j}-u_{i}),}

dóndenorte(i){\displaystyle N(i)}denota el vecindario dei{\displaystyle i}(a excepción dei{\displaystyle i}),αij{\displaystyle \alpha _{ij}}yβij{\displaystyle \beta _{ij}}son los dos ángulos opuestos al bordeij{\displaystyle ij}, yAi{\displaystyle A_{i}}es el área del vértice dei{\displaystyle i}; es decir, por ejemplo, un tercio de la suma de las áreas de los triángulos incidentes ai{\displaystyle i}El signo del operador discreto de Laplace-Beltrami es convencionalmente opuesto al signo del operador de Laplace ordinario . La fórmula de la cotangente anterior se puede derivar utilizando muchos métodos diferentes, entre los que se incluyen elementos finitos lineales por partes , volúmenes finitos y cálculo exterior discreto . [ 2 ]

Para facilitar el cálculo, el laplaciano se codifica en una matriz.L∈R|V|×|V|{\displaystyle L\in \mathbb {R} ^{|V|\times |V|}}de tal manera queLtú=(Δtú)i{\displaystyle Lu=(\Delta u)_{i}}. Dejardo{\displaystyle C}Sea la matriz cotangente (dispersa) con entradas

doij={12(cuna⁡αij+cuna⁡βij)ij es una ventaja, eso es j∈norte(i),−∑k∈norte(i)doiki=j,0de lo contrario{\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}}}

dóndenorte(i){\displaystyle N(i)}denota el vecindario dei{\displaystyle i}y dejarMETRO{\displaystyle M}Sea la matriz de masas diagonalMETRO{\displaystyle M}cuyoi{\displaystyle i}La entrada -ésima a lo largo de la diagonal es el área del vérticeAi{\displaystyle A_{i}}. EntoncesL=METRO−1do{\displaystyle L=M^{-1}C}es la discretización buscada del laplaciano.

En [ 3 ] se ofrece una visión general más amplia de los operadores de malla .

Diferencias finitas

Las aproximaciones del laplaciano , obtenidas mediante el método de diferencias finitas o el método de elementos finitos , también pueden denominarse laplacianos discretos . Por ejemplo, el laplaciano en dos dimensiones puede aproximarse utilizando el método de diferencias finitas de plantilla de cinco puntos , lo que da como resultado:

ΔF(incógnita,y)≈F(incógnita−h,y)+F(incógnita+h,y)+F(incógnita,y−h)+F(incógnita,y+h)−4F(incógnita,y)h2,{\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}}},}

donde el tamaño de la cuadrícula es h en ambas dimensiones, de modo que la plantilla de cinco puntos de un punto ( x , y ) en la cuadrícula es 

{(incógnita−h,y),(incógnita,y),(incógnita+h,y),(incógnita,y−h),(incógnita,y+h)}.{\displaystyle \{(x-h,y),(x,y),(x+h,y),(x,y-h),(x,y+h)\}.}

Si el tamaño de la cuadrícula h = 1, el resultado es el laplaciano discreto negativo en el grafo, que es la cuadrícula de red cuadrada . Aquí no hay restricciones sobre los valores de la función f ( x , y ) en el límite de la cuadrícula de red, por lo que este es el caso de ausencia de fuente en el límite, es decir, una condición de contorno de flujo nulo (también conocida como aislamiento o condición de contorno de Neumann homogénea ). El control de la variable de estado en el límite, como f ( x , y ) dada en el límite de la cuadrícula (también conocida como condición de contorno de Dirichlet ), rara vez se utiliza para laplacianos de grafos, pero es común en otras aplicaciones.

Los laplacianos discretos multidimensionales en cuadrículas regulares de cuboide rectangular tienen propiedades muy especiales, por ejemplo, son sumas de Kronecker de laplacianos discretos unidimensionales, véase suma de Kronecker de laplacianos discretos , en cuyo caso todos sus valores y vectores propios se pueden calcular explícitamente.

Método de elementos finitos

En este enfoque, el dominio se discretiza en elementos más pequeños, generalmente triángulos o tetraedros, aunque también son posibles otros elementos como rectángulos o cuboides. El espacio de soluciones se aproxima mediante funciones de forma de grado predefinido. La ecuación diferencial que contiene el operador de Laplace se transforma en una formulación variacional, y se construye un sistema de ecuaciones (problemas lineales o de valores propios). Las matrices resultantes suelen ser muy dispersas y pueden resolverse mediante métodos iterativos.

Procesamiento de imágenes

El operador de Laplace discreto se utiliza frecuentemente en el procesamiento de imágenes, por ejemplo, en aplicaciones de detección de bordes y estimación de movimiento. [ 4 ] El laplaciano discreto se define como la suma de las segundas derivadas y se calcula como la suma de las diferencias entre los vecinos más cercanos del píxel central. Dado que los filtros de derivada suelen ser sensibles al ruido en una imagen, el operador de Laplace a menudo va precedido de un filtro de suavizado (como un filtro gaussiano ) para eliminar el ruido antes de calcular la derivada. El filtro de suavizado y el filtro de Laplace suelen combinarse en un único filtro. [ 5 ]

Implementación mediante discretización del operador

Para señales unidimensionales, bidimensionales y tridimensionales, el laplaciano discreto se puede expresar como una convolución con los siguientes núcleos:

Filtro 1D:D→incógnita2=[1−21]{\displaystyle {\vec {D}}_{x}^{2}={\begin{bmatrix}1&-2&1\end{bmatrix}}},
Filtro 2D:Dincógnitay2=[0101−41010]{\displaystyle \mathbf {D} _{xy}^{2}={\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}}.

Dincógnitay2{\displaystyle \mathbf {D} _{xy}^{2}}corresponde a la fórmula de diferencias finitas ( plantilla de cinco puntos ) vista anteriormente. Es estable para campos que varían muy suavemente, pero para ecuaciones con soluciones que varían rápidamente se requiere una forma más estable e isotrópica del operador laplaciano, [ 6 ] como la plantilla de nueve puntos , que incluye las diagonales:

Filtro 2D:Dincógnitay2=[0,250,50,250,5−30,50,250,50,25]{\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}}},
Filtro 3D:Dincógnitayz2{\displaystyle \mathbf {D} _{xyz}^{2}}El uso de una plantilla de siete puntos viene dado por:
primer plano =[000010000]{\displaystyle {\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}}; segundo plano =[0101−61010]{\displaystyle {\begin{bmatrix}0&1&0\\1&-6&1\\0&1&0\end{bmatrix}}}; tercer plano =[000010000]{\displaystyle {\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}}.
y utilizando una plantilla de 27 puntos por: [ 7 ]
primer plano =126[232363232]{\displaystyle {\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}}; segundo plano =126[3636−886363]{\displaystyle {\frac {1}{26}}{\begin{bmatrix}3&6&3\\6&-88&6\\3&6&3\end{bmatrix}}}; tercer plano =126[232363232]{\displaystyle {\frac {1}{26}}{\begin{bmatrix}2&3&2\\3&6&3\\2&3&2\end{bmatrix}}}.
Filtro n D : Para el elementoaincógnita1,incógnita2,…,incógnitanorte{\displaystyle a_{x_{1},x_{2},\dots ,x_{n}}}del núcleoDincógnita1,incógnita2,…,incógnitanorte2,{\displaystyle \mathbf {D} _{x_{1},x_{2},\dots ,x_{n}}^{2},}
aincógnita1,incógnita2,…,incógnitanorte={−2nortesi s=norte,1si s=norte−1,0de lo contrario,{\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.}
donde x i es la posición (ya sea −1 , 0 o 1 ) del elemento en el núcleo en la dirección i , y s es el número de direcciones i para las cuales x i = 0 .

Nótese que la versión n D, que se basa en la generalización gráfica del laplaciano, supone que todos los vecinos están a la misma distancia y, por lo tanto, conduce al siguiente filtro 2D con diagonales incluidas, en lugar de la versión anterior:

Filtro 2D:Dincógnitay2=[1111−81111].{\displaystyle \mathbf {D} _{xy}^{2}={\begin{bmatrix}1&1&1\\1&-8&1\\1&1&1\end{bmatrix}}.}

Estos núcleos se deducen utilizando cocientes diferenciales discretos.

Se puede demostrar [ 8 ] [ 9 ] que la siguiente aproximación discreta del operador laplaciano bidimensional como una combinación convexa de operadores de diferencias

∇γ2=(1−γ)∇52+γ∇×2=(1−γ)[0101−41010]+γ[1/201/20−201/201/2]{\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}}}

para γ ∈ [0, 1] es compatible con propiedades de espacio de escalas discretas, donde específicamente el valor γ = 1/3 da la mejor aproximación de la simetría rotacional . [ 8 ] [ 9 ] [ 10 ] Con respecto a las señales tridimensionales, se muestra [ 9 ] que el operador laplaciano puede aproximarse mediante la familia de operadores de diferencias de dos parámetros.

∇γ1,γ22=(1−γ1−γ2)∇72+γ1∇+32+γ2∇×32),{\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}),}

dónde

(∇72F)0,0,0=F−1,0,0+F+1,0,0+F0,−1,0+F0,+1,0+F0,0,−1+F0,0,+1−6F0,0,0,{\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},}
(∇+32F)0,0,0=14(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+F0,−1,−1+F0,−1,+1+F0,+1,−1+F0,+1,+1−12F0,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}),}
(∇×32F)0,0,0=14(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−8F0,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}).}

Mediante el análisis de series de Taylor se puede demostrar que las combinaciones de valores deγ1{\displaystyle \gamma _{1}}yγ2{\displaystyle \gamma _{2}}para qué3γ1+6γ2=2{\displaystyle 3\gamma _{1}+6\gamma _{2}=2}Proporcionar las mejores aproximaciones de la simetría rotacional.

Implementación mediante reconstrucción continua

Una señal discreta, que comprende imágenes, puede considerarse como una representación discreta de una función continua.F(r¯){\displaystyle f({\bar {r}})}donde el vector de coordenadasr¯∈Rnorte{\displaystyle {\bar {r}}\in R^{n}}y el dominio de valor es realF∈R{\displaystyle f\in R}Por lo tanto, la operación de derivación es directamente aplicable a la función continua.F{\displaystyle f}. En particular, cualquier imagen discreta, con supuestos razonables sobre el proceso de discretización, por ejemplo, asumiendo funciones de banda limitada o funciones expandibles de ondículas, etc., puede reconstruirse mediante funciones de interpolación bien comportadas que subyacen a la formulación de reconstrucción, [ 11 ]

F(r¯)=∑k∈KFkμk(r¯){\displaystyle f({\bar {r}})=\sum _{k\in K}f_{k}\mu _{k}({\bar {r}})}

dóndeFk∈R{\displaystyle f_{k}\in R}son representaciones discretas deF{\displaystyle f}en la cuadrículaK{\displaystyle K}yμk{\displaystyle \mu _{k}}son funciones de interpolación específicas de la cuadrículaK{\displaystyle K}En una cuadrícula uniforme, como las imágenes, y para funciones de ancho de banda limitado, las funciones de interpolación son invariantes a los desplazamientos, lo que equivale a: μk(r¯)=μ(r¯−r¯k){\displaystyle \mu _{k}({\bar {r}})=\mu ({\bar {r}}-{\bar {r}}_{k})}conμ{\displaystyle \mu }siendo una función sinc apropiadamente dilatada definida ennorte{\displaystyle n}-dimensiones, es decirr¯=(incógnita1,incógnita2...incógnitanorte)T{\displaystyle {\bar {r}}=(x_{1},x_{2}...x_{n})^{T}}. Otras aproximaciones deμ{\displaystyle \mu }en cuadrículas uniformes, son funciones gaussianas dilatadas apropiadamente ennorte{\displaystyle n}-dimensiones. En consecuencia, el laplaciano discreto se convierte en una versión discreta del laplaciano del continuoF(r¯){\displaystyle f({\bar {r}})}

∇2F(r¯k)=∑k′∈KFk′(∇2μ(r¯−r¯k′))|r¯=r¯k{\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}}}

que a su vez es una convolución con el laplaciano de la función de interpolación en la cuadrícula uniforme (de imagen).K{\displaystyle K}Una ventaja de usar funciones gaussianas como funciones de interpolación es que producen operadores lineales, incluidos los laplacianos, que están libres de artefactos rotacionales del sistema de coordenadas en el queF{\displaystyle f}está representado porFk{\displaystyle f_{k}}, ennorte{\displaystyle n}-dimensiones, y son conscientes de la frecuencia por definición. Un operador lineal no solo tiene un rango limitado en elr¯{\displaystyle {\bar {r}}}dominio pero también un rango efectivo en el dominio de la frecuencia (alternativamente espacio de escala gaussiana) que puede controlarse explícitamente a través de la varianza de la gaussiana de manera sistemática. El filtrado resultante puede implementarse mediante filtros separables y representaciones de decimación (procesamiento de señales) / pirámide (procesamiento de imágenes) para una mayor eficiencia computacional ennorte{\displaystyle n}-dimensiones. En otras palabras, el filtro laplaciano discreto de cualquier tamaño puede generarse convenientemente como el laplaciano muestreado de Gauss con un tamaño espacial que se ajuste a las necesidades de una aplicación particular, controlado por su varianza. Los monomios, que son operadores no lineales, también pueden implementarse utilizando un enfoque de reconstrucción y aproximación similar, siempre que la señal esté suficientemente sobremuestreada. De este modo, se pueden realizar operadores no lineales como el Tensor de Estructura y el Tensor de Estructura Generalizado , que se utilizan en el reconocimiento de patrones por su optimalidad total de mínimos cuadrados en la estimación de la orientación.

Espectro

El espectro del laplaciano discreto en una malla infinita es de interés fundamental; dado que es un operador autoadjunto , tiene un espectro real. Por convenciónΔ=I−METRO{\displaystyle \Delta =I-M}enZ{\displaystyle Z}, el espectro se encuentra dentro[0,2]{\displaystyle [0,2]}(ya que el operador de promedio tiene valores espectrales en[−1,1]{\displaystyle [-1,1]}Esto también puede observarse aplicando la transformada de Fourier. Cabe destacar que el laplaciano discreto en una malla infinita tiene un espectro absolutamente continuo y, por lo tanto, carece de valores propios o funciones propias.

Teoremas

Si el grafo es una cuadrícula cuadrada infinita , entonces se puede demostrar que esta definición del laplaciano corresponde al laplaciano continuo en el límite de una cuadrícula infinitamente fina. Así, por ejemplo, en una cuadrícula unidimensional tenemos

∂2F∂incógnita2=límiteϵ→0[F(incógnita+ϵ)−F(incógnita)]−[F(incógnita)−F(incógnita−ϵ)]ϵ2.{\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}}}.}

Esta definición del laplaciano se utiliza comúnmente en el análisis numérico y en el procesamiento de imágenes . En el procesamiento de imágenes, se considera un tipo de filtro digital , más específicamente un filtro de bordes , llamado filtro de Laplace .

Ecuación discreta del calor

Suponerϕ{\textstyle \phi }describe una distribución de temperatura a través de un gráfico , dondeϕi{\textstyle \phi _{i}}es la temperatura en el vérticei{\textstyle i}Según la ley de enfriamiento de Newton , el calor transferido desde el nodoi{\textstyle i}al nodoj{\textstyle j}es proporcional aϕi−ϕj{\textstyle \phi _{i}-\phi _{j}}si nodosi{\textstyle i}yj{\textstyle j}están conectados (si no están conectados, no se transfiere calor). Entonces, para la conductividad térmicak{\textstyle k},

dϕidt=−k∑jAij(ϕi−ϕj)=−k(ϕi∑jAij−∑jAijϕj)=−k(ϕi grados⁡(vi)−∑jAijϕj)=−k∑j(δij grados⁡(vi)−Aij)ϕj=−k∑j(Lij)ϕj.{\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}}}

En notación matricial-vectorial,

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

lo cual da

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

Nótese que esta ecuación tiene la misma forma que la ecuación del calor , donde la matriz − L reemplaza al operador laplaciano.∇2{\textstyle \nabla ^{2}}; de ahí, el "laplaciano de grafos".

Para encontrar una solución a esta ecuación diferencial, aplique técnicas estándar para resolver una ecuación diferencial matricial de primer orden . Es decir, escribaϕ{\textstyle \phi }como una combinación lineal de vectores propiosvi{\textstyle \mathbf {v} _{i}}de L (de modo queLvi=λivi{\textstyle L\mathbf {v} _{i}=\lambda _{i}\mathbf {v} _{i}}) con coeficientes dependientes del tiempo,ϕ(t)=∑idoi(t)vi.{\textstyle \phi (t)=\sum _{i}c_{i}(t)\mathbf {v} _{i}.}

Sustituyendo en la expresión original (porque L es una matriz simétrica, sus vectores propios de norma unitariavi{\textstyle \mathbf {v} _{i}}son ortogonales):

0=d(∑idoi(t)vi)dt+kL(∑idoi(t)vi)=∑i[ddoi(t)dtvi+kdoi(t)Lvi]=∑i[ddoi(t)dtvi+kdoi(t)λivi]⇒0=ddoi(t)dt+kλidoi(t),{\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}}}

cuya solución es

doi(t)=doi(0)mi−kλit.{\displaystyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}.}

Como se mostró anteriormente, los valores propiosλi{\textstyle \lambda _{i}}Los valores de L son no negativos, lo que demuestra que la solución de la ecuación de difusión se aproxima a un equilibrio, ya que solo decae exponencialmente o permanece constante. Esto también demuestra que, dadoλi{\textstyle \lambda _{i}}y la condición inicialdoi(0){\textstyle c_{i}(0)}, la solución en cualquier momento t puede encontrarse. [ 12 ]

Para encontrardoi(0){\textstyle c_{i}(0)}para cadai{\textstyle i}en términos de la condición inicial generalϕ(0){\textstyle \phi (0)}, simplemente proyectarϕ(0){\textstyle \phi (0)}sobre los autovectores de norma unitariavi{\textstyle \mathbf {v} _{i}};

doi(0)=⟨ϕ(0),vi⟩.{\displaystyle c_{i}(0)=\left\langle \phi (0),\mathbf {v} _{i}\right\rangle .}

Este enfoque se ha aplicado al modelado cuantitativo de transferencia de calor en mallas no estructuradas. [ 13 ] [ 14 ]

En el caso de los grafos no dirigidos, esto funciona porqueL{\textstyle L}es simétrica y, por el teorema espectral , sus autovectores son todos ortogonales. Por lo tanto, la proyección sobre los autovectores deL{\textstyle L}es simplemente una transformación de coordenadas ortogonales de la condición inicial a un conjunto de coordenadas que decaen exponencialmente e independientemente unas de otras.

Comportamiento de equilibrio

Para entenderlímitet→∞ϕ(t){\textstyle \lim _{t\to \infty }\phi (t)}, los únicos términosdoi(t)=doi(0)mi−kλit{\textstyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}}que quedan son aquellos dondeλi=0{\textstyle \lambda _{i}=0}, desde

límitet→∞mi−kλit={0,siλi>01,siλ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}}}

En otras palabras, el estado de equilibrio del sistema está completamente determinado por el núcleo deL{\textstyle L}.

Dado que por definición,∑jLij=0{\textstyle \sum _{j}L_{ij}=0}, el vectorv1{\textstyle \mathbf {v} ^{1}}de todos los unos está en el núcleo. Si hayk{\textstyle k}componentes conectadas disjuntas en el grafo, entonces este vector de todos unos se puede dividir en la suma dek{\textstyle k}independienteλ=0{\textstyle \lambda =0}autovectores de unos y ceros, donde cada componente conexa corresponde a un autovector con unos en los elementos de la componente conexa y ceros en los demás.

La consecuencia de esto es que para una condición inicial dadaϕ(0){\textstyle \phi (0)}para un gráfico connorte{\textstyle N}vértices

límitet→∞ϕ(t)=⟨ϕ(0),v1⟩v1{\displaystyle \lim _{t\to \infty }\phi (t)=\left\langle \phi (0),\mathbf {v^{1}} \right\rangle \mathbf {v^{1}} }

dónde

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

Para cada elementoϕj{\textstyle \phi _{j}}deϕ{\textstyle \phi }, es decir, para cada vérticej{\textstyle j}En el gráfico, se puede reescribir como

límitet→∞ϕj(t)=1norte∑i=1norteϕi(0).{\displaystyle \lim _{t\to \infty }\phi _{j}(t)={\frac {1}{N}}\sum _{i=1}^{N}\phi _{i}(0).}

En otras palabras, en estado estacionario, el valor deϕ{\textstyle \phi }Converge al mismo valor en cada uno de los vértices del grafo, que es el promedio de los valores iniciales en todos los vértices. Dado que esta es la solución a la ecuación de difusión del calor, resulta intuitivamente lógico. Esperamos que los elementos vecinos del grafo intercambien energía hasta que esta se distribuya uniformemente entre todos los elementos conectados entre sí.

Ejemplo del operador en una cuadrícula

Este GIF muestra la progresión de la difusión, resuelta mediante la técnica del laplaciano gráfico. Se construye un gráfico sobre una cuadrícula, donde cada píxel está conectado a sus ocho píxeles vecinos. Los valores de la imagen se difunden gradualmente hacia sus vecinos a lo largo del tiempo a través de estas conexiones. Esta imagen en particular comienza con tres valores puntuales fuertes que se extienden lentamente a sus vecinos. Finalmente, todo el sistema alcanza el mismo valor en equilibrio.

Esta sección muestra un ejemplo de una función.ϕ{\textstyle \phi }Difusión a lo largo del tiempo mediante un gráfico. El gráfico de este ejemplo se construye sobre una cuadrícula discreta bidimensional, con puntos conectados a sus ocho vecinos. Se especifica que tres puntos iniciales tienen un valor positivo, mientras que el resto de los valores en la cuadrícula son cero. Con el tiempo, el decaimiento exponencial distribuye uniformemente los valores de estos puntos por toda la cuadrícula.

A continuación se proporciona el código fuente completo de Matlab utilizado para generar esta animación. En él se muestra el proceso de especificación de las condiciones iniciales, su proyección sobre los autovectores de la matriz laplaciana y la simulación del decaimiento exponencial de dichas condiciones iniciales proyectadas.

N = 20 ; % El número de píxeles a lo largo de una dimensión de la imagen A = zeros ( N , N ); % La imagen Adj = zeros ( N * N , N * N ); % La matriz de adyacencia% Usa 8 vecinos y completa la matriz de adyacencia dx = [ - 1 , 0 , 1 , - 1 , 1 , - 1 , 0 , 1 ]; dy = [ - 1 , - 1 , - 1 , 0 , 0 , 1 , 1 , 1 ]; para x = 1 : N para y = 1 : N índice = ( x - 1 ) * N + y ; para ne = 1 : longitud ( dx ) nuevox = x + dx ( ne ); nuevoy = y + dy ( ne ); si nuevox > 0 && nuevox <= N && nuevoy > 0 && nuevoy <= N índice2 = ( nuevox - 1 ) * N + nuevoy ; Adj ( índice , índice2 ) = 1 ; fin fin fin fin% A continuación se muestra el código clave que calcula la solución de la ecuación diferencial Deg = diag ( sum ( Adj , 2 )); % Calcula la matriz de grados L = Deg - Adj ; % Calcula la matriz laplaciana en términos de las matrices de grado y adyacencia [ V , D ] = eig ( L ); % Calcula los autovalores/vectores de la matriz laplaciana D = diag ( D );% Condición inicial (coloque algunos valores positivos grandes alrededor y % haga que todo lo demás sea cero) 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 ; % Transformar la condición inicial en el sistema de coordenadas % de los autovectores para t = 0 : 0.05 : 5 % Bucle a través de los tiempos y decaer cada componente inicial Phi = C0V .* exp ( - D * t ); % Decaimiento exponencial para cada componente Phi = V * Phi ; % Transformar del sistema de coordenadas del autovector al sistema de coordenadas original Phi = reshape ( Phi , N , N ); % Mostrar los resultados y escribir en el archivo GIF imagesc ( Phi ); caxis ([ 0 , 10 ]); title ( sprintf ( 'Difusión 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

Operador de Schrödinger discreto

DejarPAG:V→R{\displaystyle P\colon V\rightarrow R}sea ​​una función potencial definida en la gráfica. Nótese que P puede considerarse un operador multiplicativo que actúa diagonalmente sobreϕ{\displaystyle \phi }

(PAGϕ)(v)=PAG(v)ϕ(v).{\displaystyle (P\phi )(v)=P(v)\phi (v).}

EntoncesH=Δ+PAG{\displaystyle H=\Delta +P}es el operador de Schrödinger discreto , un análogo del operador de Schrödinger continuo .

Si el número de aristas que convergen en un vértice está uniformemente acotado y el potencial está acotado, entonces H está acotado y es autoadjunto .

Las propiedades espectrales de este hamiltoniano pueden estudiarse con el teorema de Stone ; esto es consecuencia de la dualidad entre conjuntos parcialmente ordenados y álgebras booleanas .

En redes regulares, el operador suele tener soluciones tanto de onda viajera como de localización de Anderson , dependiendo de si el potencial es periódico o aleatorio.

La función de Green del operador de Schrödinger discreto viene dada en el formalismo de la resolvente por

GRAMO(v,w;λ)=⟨δv|1H−λ|δw⟩{\displaystyle G(v,w;\lambda )=\left\langle \delta _{v}\left|{\frac {1}{H-\lambda }}\right|\delta _{w}\right\rangle }

dóndeδw{\displaystyle \delta _{w}}se entiende que es la función delta de Kronecker en el gráfico:δw(v)=δwv{\displaystyle \delta _{w}(v)=\delta _{wv}}; es decir, es igual a 1 si v = w y 0 en caso contrario.

Para fijow∈V{\displaystyle w\in V}yλ{\displaystyle \lambda }un número complejo, la función de Green considerada como una función de v es la solución única para

(H−λ)GRAMO(v,w;λ)=δw(v).{\displaystyle (H-\lambda )G(v,w;\lambda )=\delta _{w}(v).}

Clasificación ADE

Ciertas ecuaciones que involucran al laplaciano discreto solo tienen soluciones en los diagramas de Dynkin simplemente enlazados (todas las aristas con multiplicidad 1), y son un ejemplo de la clasificación ADE . Específicamente, las únicas soluciones positivas para la ecuación homogénea son:

Δϕ=ϕ,{\displaystyle \Delta \phi =\phi ,}

en palabras,

"El doble de cualquier etiqueta es la suma de las etiquetas de los vértices adyacentes."

Se encuentran en los diagramas de Dynkin ADE extendidos (afines), de los cuales hay 2 familias infinitas (A y D) y 3 excepciones (E). La numeración resultante es única salvo por escala, y si el valor más pequeño se establece en 1, los demás números son enteros, con un rango de hasta 6.

Los grafos ADE ordinarios son los únicos grafos que admiten un etiquetado positivo con la siguiente propiedad:

El doble de cualquier etiqueta menos dos es la suma de las etiquetas en vértices adyacentes.

En términos del laplaciano, las soluciones positivas de la ecuación no homogénea son:

Δϕ=ϕ−2.{\displaystyle \Delta \phi =\phi -2.}

La numeración resultante es única (la escala se especifica mediante el "2") y consta de números enteros; para E 8, varían de 58 a 270 y se han observado ya en 1968. [ 15 ]

Véase también

Referencias

  1. ↑ Leventhal, Daniel (otoño de 2011). "Procesamiento de imágenes" (PDF) . Universidad de Washington . Recuperado el 1 de diciembre de 2019 .
  2. ↑ Crane, K.; de Goes, F.; Desbrun, M.; Schröder, P. (2013). "Procesamiento de geometría digital con cálculo exterior discreto" . Cursos de ACM SIGGRAPH 2013. SIGGRAPH '13. Vol. 7. pp. 1– 126. doi : 10.1145/2504435.2504442 .  
  3. ↑ Reuter, M.; Biasotti, S.; Giorgi, D.; Patane, G.; Spagnuolo, M. (2009). "Operadores discretos de Laplace-Beltrami para análisis y segmentación de formas". Computers & Graphics . 33 (3): 381–390df. CiteSeerX 10.1.1.157.757 . doi : 10.1016/j.cag.2009.03.005 . 
  4. ↑ Forsyth, DA; Ponce, J. (2003). "Visión por computadora". Computers & Graphics . 33 (3): 381– 390. CiteSeerX 10.1.1.157.757 . doi : 10.1016/j.cag.2009.03.005 . 
  5. ↑ Matthys, Don (14 de febrero de 2001). "Filtro LoG" . Universidad de Marquette . Recuperado el 1 de diciembre de 2019 .
  6. ↑ Provatas, Nikolas; Elder, Ken (13 de octubre de 2010). Métodos de campo de fase en ciencia e ingeniería de materiales (PDF) . Weinheim, Alemania: Wiley-VCH Verlag GmbH & Co. KGaA. pág. 219. doi : 10.1002/9783527631520 . ISBN  978-3-527-63152-0.
  7. ↑ O'Reilly, H.; Beck, Jeffrey M. (2006). "Una familia de aproximaciones laplacianas discretas de plantilla grande en tres dimensiones" (PDF) . Revista internacional de métodos numéricos en ingeniería : 1–16 .
  8. 1 2 Lindeberg, T., "Espacio de escalas para señales discretas", PAMI(12), No. 3, marzo de 1990, pp. 234–254.
  9. 1 2 3 Lindeberg, T., Teoría del espacio de escalas en visión por computadora, Kluwer Academic Publishers, 1994 , ISBN 0-7923-9418-6.
  10. ↑ Patra, Michael; Karttunen, Mikko (2006). "Plantillas con error de discretización isotrópico para operadores diferenciales". Métodos numéricos para ecuaciones diferenciales parciales . 22 (4): 936– 953. doi : 10.1002/num.20129 . ISSN 0749-159X . S2CID 123145969 .  
  11. ↑ Bigun, J. (2006). Visión con dirección . Springer. doi : 10.1007/b138918 . ISBN 978-3-540-27322-6.
  12. ↑ Newman, Mark (2010). Redes: Una introducción . Oxford University Press. ISBN 978-0-19-920665-0.
  13. ↑ Yavari, R.; Cole, KD; Rao, PK (2020). "Transferencia de calor computacional con teoría de grafos espectrales: verificación cuantitativa" . International Journal of Thermal Sciences . 153 106383. Bibcode : 2020IJTS..15306383C . doi : 10.1016/j.ijthermalsci.2020.106383 .
  14. ↑ Cole, KD; Riensche, A.; Rao, PK (2022). "Funciones de Green discretas y teoría de grafos espectrales para modelado térmico computacionalmente eficiente" . International Journal of Heat and Mass Transfer . 183 122112. Bibcode : 2022IJHMT.18322112C . doi : 10.1016/j.ijheatmasstransfer.2021.122112 . S2CID 244652819 . 
  15. ↑ Bourbaki, Nicolas (2002) [1968], Groupes et algebres de Lie: Chapters 4–6 , Elements of Mathematics, traducido por Pressley, Andrew, Springer, ISBN 978-3-540-69171-6
  • Sunada, T. (2008). «Análisis geométrico discreto» . Análisis de grafos y sus aplicaciones . Actas de simposios de matemáticas puras. Vol.  77. Sociedad Matemática Americana. pp. 51–86 . ISBN  978-0-8218-9384-5.
  • Ollivier, Yann (2004). "Brecha espectral de un grafo" . Archivado del original el 23 de mayo de 2007.