Discrete Laplacian

I was wondering if anybody would explain (or please point me to a nice reference) as to why the ``discrete Laplacian" on a graph is actually called a Laplacian. Namely, how is it related to the standard Laplacian on $\mathbb{R}^n$ ? Is there a sense in which the discrete Laplacian on say, a square lattice, would converge to the standard Laplacian as the lattice spacing tends to $0$ ?

Solution 1:

I like the discussion in section 5.6 of Gilbert Strang's book Differential Equations and Linear Algebra. For a directed graph, the incidence matrix $A$ is a difference matrix --- so it is a discrete analog of the gradient $\nabla$. The graph Laplacian is $A^T A$, which is analogous to the (negative) Laplacian $\nabla^T \nabla = -\text{div} \nabla$.

Solution 2:

An example from the theory of electrical networks may illustrate the connection between the discrete and continuous Laplacian.

In brief, an electrical network can be modeled by a 1-complex: branches correspond to wires and nodes correspond to the connections between the wires. Consider a capacitive network in which each branch has a capacitor with capacitance $C_\alpha$ and possibly an initial charge $Q_\alpha$. A charge distribution on the capacitors $\mathbf Q$ is an element of $C_1$, the space of 1-chains of the complex; a voltage distribution across the branches $\mathbf V$ is an elements of $C^1$, the space of 1-cochains. Similarly, charge distributions on the nodes $\mathbf\rho\in C_0$ are 0-chains, while the node potentials $\mathbf\Phi\in C^0$ are 0-cochains.

Gauss’ law $\operatorname{\partial}\mathbf Q=-\mathbf\rho$ relates the two charge distributions, where $\partial:C_1\to C_0$ is the boundary operator for the complex. This just says that the total charge on a node is equal to the sum of the charges on the plates connected to it. The node potentials and branch voltages are related via Kirchhoff’s voltage law $\mathbf V=-\operatorname{d} \mathbf\Phi$ ($\operatorname{d}$ is the coboundary operator, the adjoint of $\partial$). Branch voltages and charges are related via the capacitances: $\mathbf Q=C\mathbf V$.

These three equations can be combined to obtain $$-\operatorname{\partial\, C\,d}\mathbf\Phi=-\mathbf\rho.$$ This is Poisson’s equation for discrete capacitive networks. The operator $-\operatorname{\partial\,C\,d}$ is the Laplacian $\Delta$. (If you set all of the capacitances to unity, you’ll get the Laplacian matrix for the digraph that represents the network.) There are discrete versions of boundary-value problems, and just as in the continuous case, they can be solved as a superposition of solutions to a Dirichlet problem and Poisson equation problem. There are discrete Green’s functions, and so on.

Let $A$ be a node and $u\in C^0$. If you write out the Laplacian explicity, you’ll find that $$(\Delta u)(A)=\sum_{\alpha:\partial\alpha=\pm(B-A)}C_\alpha(u(B)-u(A)),$$ where the sum is taken over all branches that have $A$ as a boundary. In particular, $u$ satisfies Laplace’s equation $\Delta u=0$ iff $$u(A)=\frac1{\sum C_\alpha}\sum C_\alpha u(B),$$ the sum taken over all nodes $B$ that are at the other ends of branches emanating from $A$. I.e., the value of $u$ at $A$ is the weighted average of its values at nearest neighbor nodes. This is analogous to the continuous case, in which the Laplacian operator basically measures the “average” change in a function’s value as you move away from a given point. So, in the continuous case, Laplace’s equation says that the value of $u$ at a point $P$ is the average of $u$ over a small (in two dimensions) circle centered at $P$.

There are other analogies besides these as you pass to the continuum. Node charges become charge density and the analog of $\mathbf Q$ is the dielectric displacement $\mathbf D$, which can be thought of as a two-form in three-dimensional space. Gauss’ law is then just the 3-D version of Stokes’ theorem (or, if you think of $\mathbf D$ as a vector field instead, the divergence theorem). There is also a connection between the capacitance matrix $C$, which in the discrete case provides the weights for the nearest-neighbor average of the Laplacian, and the dielectric property of the vacuum, which determines the Euclidean geometry of space, which in turn is needed to define the concept of a circle (sphere, &c) for the continuous Laplacian.