Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Davide Giraudo Jan 14 '12 at 19:42
    
@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. –  nick_name Jan 14 '12 at 19:44
    
@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. –  nick_name Jan 14 '12 at 19:52
    
The issue is the boundary conditions, for example Neumann vs. Dirichlet. –  user22950 Jan 14 '12 at 20:48
1  
@nick: Davide is correct. The discrete Laplacian should be represented by a matrix of numbers which shouldn't depend on the $F[n]$. –  Qiaochu Yuan Jan 14 '12 at 20:51

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
I truly appreciate this detailed response. –  nick_name Jan 15 '12 at 18:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.