Discrete Laplace operator

From Wikipedia, the free encyclopedia

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. The discrete Laplace operator occurs in physics problems such as the Ising model and loop quantum gravity, as well as in the study of discrete dynamical systems. It is also used in numerical analysis as a stand-in for the continuous Laplace operator.

1 Definition
2 Theorems
3 Discrete Schrödinger operator
4 Discrete Green's function

[edit] Definition

Let G=(V,E) be a graph with vertices V and edges E. Let $\phi:V\rightarrow\mathbb{C}$ be a function mapping vertices to complex numbers. Then, the discrete Laplacian $Δ$ acting on $φ$ is defined by

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

where dist(w,v) is the distance operator on the graph. Thus, this sum is over the nearest neighbors of the vertex v.

If the graph has weighted edges, that is, a weighting function $\gamma:E\rightarrow\mathbb{C}$ is given, then the definition can be generalized to

$(\Delta_\gamma\phi)(v)=\sum_{w:\textrm{dist}(w,v)=1}\gamma_{wv}\left[\phi(w)-\phi(v)\right]$

where $γ w v$ is the weight value on the edge $wv\in E$ .

[edit] Theorems

If the graph is an infinite square lattice grid, then this definition of the Laplacian can be shown to correspond to the continuous Laplacian in the limit of an infinitely fine grid. Thus, for example, on a one-dimensional grid we have

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

This definition of the Laplacian is commonly used in numerical analysis and in image processing. In image processing, it is considered to be a type of digital filter, more specifically an edge filter, called the Laplace filter.

[edit] Discrete Schrödinger operator

Let $P:V\rightarrow\mathbb{R}$ be a potential function defined on the graph. Note that P can be considered to be a multiplicative operator acting diagonally on $φ$

(P φ)(v) = P (v)φ(v).

Then $H = Δ + P$ is the discrete Schrödinger operator, an analog of the continuous Schrödinger operator.

If the number of edges meeting at a vertex is uniformly bounded, and the potential is bounded, then H is bounded and self-adjoint.

The spectral properties of this Hamiltonian can be studied with Stone's theorem; this is a consequence of the duality between posets and boolean algebras.