2
$\begingroup$

I'm trying to discretize the Laplacian operator, and represent it with a matrix, but I'm running into a problem: my result is not hermitian when it should be. Here are my calculations:

In one dimension...

$\nabla^{2} = \frac{\partial^{2}}{\partial x^{2}}$

Deriving the discrete representation of the Laplacian...

Forward Difference: $\frac{\partial}{\partial x} \rightarrow \frac{F[i+1]- F[i]}{\Delta}$

Reverse Difference: $\frac{\partial}{\partial x} \rightarrow \frac{F[i]- F[i-1]}{\Delta}$

Taking the derivative of the forward difference via the reverse difference definition:

$\nabla^{2} = \frac{\partial^{2}}{\partial x^{2}} \rightarrow \frac{F[i+1]-F[i]}{\Delta^{2}} - \frac{F[i]-F[i-1]}{\Delta^{2}} = \frac{F[i+1]-2F[i]+F[i-1]}{\Delta^{2}}$

Great, so let's put this in matrix form for N = 4 (indexed from 1 and omitting $\Delta^{2}$):

$\nabla^{2} \rightarrow \begin{matrix} -2F[1] & F[2] & 0 & 0 \\ F[1] & -2F[2] & F[3] & 0 \\ 0 & F[2] & -2F[3] & F[4] \\ 0 & 0 & F[3] & -2F[4] \end{matrix}$

It is quite clear that that matrix is not hermitian. The indices do not match after transposition. What am I missing?

  • 0
    The issue is the boundary conditions, for example Neumann vs. Dirichlet.2012-01-14

1 Answers 1

4

Let $G = (V, E)$ be a locally finite graph; this means that each vertex has finite degree. The Laplacian operator $\Delta$ acting on the space of functions $f : V \to \mathbb{R}$ is given by $(\Delta f)(v) = \sum_{v \to w} (f(w) - f(v))$

where $v \to w$ indicates an edge from the vertex $v$ to the vertex $w$. When $G = \mathbb{Z}$ with edges between adjacent integers, this gives $(\Delta f)(n) = f(n+1) - 2f(n) + f(n-1)$

as expected. On the space of compactly supported functions $f : V \to \mathbb{R}$ (those that are zero except at finitely many positions) there is a natural inner product given by $\langle f, g \rangle = \sum_v f(v) g(v)$

and the Laplacian is Hermitian with respect to this inner product. Indeed, $\langle f, \Delta g \rangle = \sum_{v \to w} (f(v) g(w) - f(v) g(v)) = \sum_{v \to w} (f(w) g(v) - f(v) g(v)) = \langle \Delta f, g \rangle.$ If you want to discretize the Laplacian on $\mathbb{R}$, the most convenient finite replacements are either the cycle graph $C_n$ with $n$ vertices or the path graph $P_n$ with $n$ vertices.

On a cycle graph with $n = 4$ the Laplacian is $\left[ \begin{array}{cccc} -2 & 1 & 0 & 1 \\\ 1 & -2 & 1 & 0 \\\ 0 & 1 & - 2 & 1 \\\ 1 & 0 & 1 & -2 \\\ \end{array} \right]$

whereas on a path graph with $n = 4$ the Laplacian is $\left[ \begin{array}{cccc} -1 & 1 & 0 & 0 \\\ 1 & -2 & 1 & 0 \\\ 0 & 1 & -2 & 1 \\\ 0 & 0 & 1 & -1 \\\ \end{array} \right].$

In both cases it is Hermitian as expected. I don't know how you got your matrices; among other things, they should be independent of the values of the function they're acting on.

  • 0
    I truly appreciate this detailed response.2012-01-15