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?

  • 2
    I don't understand: we have $\nabla^2(F[1],\ldots,F[4])^t=\begin{pmatrix}-2&1&0&0\\\ 1&-2&0&0\\\ 0&1&-2&1\\\ 0&0&1&-2\end{pmatrix}(F[1],\ldots,F[4])^t$, so we get a hermitian matrix.2012-01-14
  • 0
    @DavideGiraudo I do not understand your response. Could you expand your answer a bit? It's possible that you don't see what I'm doing. I'm not trying to take the Laplacian of general functions evaluated at some point F[n]. I'm discretizing the operator. Just to add a bit more: F[1] != F[2], in general.2012-01-14
  • 0
    @DavideGiraudo I could add that the amplitude and phase (if complex) of the entries will change depending on the value of F[n]...destroying hermiticity. It looks like you've taken the coefficients of the matrix entries instead of the definition.2012-01-14
  • 1
    @nick: Davide is correct. The discrete Laplacian should be represented by a matrix of numbers which shouldn't depend on the $F[n]$.2012-01-14
  • 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