# eigenvalue analysis vs fourier analysis for stability and their equivalence

I have a question regarding stability analysis for constant coefficient pde. Suppose I am looking at the pde $$u_t= au_{xx}$$ So the first approach is to compute the amplification factor, and this is so-called Fourier approach. Call it $Q(\zeta)$ and for explicit method plugging the test function $e^{ijhw}$ I have for $\zeta=hw$ that $$Q(\zeta)=1-4a\tau/h^2sin^2(\zeta/2)$$ On the other hand, the eigenvalue analysis for matrix $I+\tau A$, where $A$ is the discrete aproximation of $au_{xx}$ gives the eigenvalues of the matrix $I+\tau A$ that are exactly the same as the amplification factor $Q(\zeta)$.

Are they always the same, are these approaches equivalent? So, I can calculate either one and make sure it is bounded by $1$?

And second question. Since $A$ is symmetric, it implies $\max \lambda_i=||I+\tau A||_2$. However, if I use non uniform grid then $\max |\lambda_i| \leq ||I+\tau A||_2$ and thus neither of the two would guarantee stability because I can only show that $\max |\lambda_i|\leq 1$. What would be a sufficient condition for stability then in the case of a nonuniform grid?

If $A$ is a circulant matrix, then its eigenvectors are of the form $v_{j,w} = e^{ijhw}$; i.e., they are discrete Fourier modes. So Fourier analysis (or von Neumann analysis, as it's usually called) and eigenvalue analysis are equivalent if and only if you're dealing with a circulant matrix.

The maximum eigenvalue modulus and the Euclidean norm are equal if $A$ is a normal matrix. If $A$ is non-normal, then the Euclidean norm can be larger, as you say. A sufficient condition for stability is, of course, $\|I+\tau A\|_2 \le 1$. There are other sufficient conditions, depending on what kind of stability you mean. The most important kind of stability for PDE discretizations is Lax-Richtmeyer stability, which in your case would mean $$\|(I+\tau A)^n\|< C$$ for all $n\tau<T$, where $C$ is a constant that may depend on $T$ but not on $n$ or $\tau$. For a discussion, see e.g. Chapter 9 of Leveque's text.

Proving this kind of stability for a non-uniform grid discretization will probably be difficult. In practice, it is usually sufficient to consider the stability criterion based on a uniform grid, e.g. $\Delta t \le (\Delta x)^2/2$ and apply it but with $\Delta x$ replaced by the minimum of $\Delta x$ over the whole grid.

• David, one more question related to the first answer: if I have a variable coefficient pde I don't have a circulant matrix and thus I can't even apply Fourier analysis as the eigenvectors are not Fourier modes anymore. But I can still use eigenvalue analysis, which is a very hard task though if it is a big matrix, is that correct? More than that, it would be only a necessary condition, not sufficient because it is an estimate for the spectral radius not the norm. Please correct me if I am wrong. – Kamil Jul 11 '12 at 13:11
• @Medan You're correct on both points. – David Ketcheson Jul 11 '12 at 14:24
• David, regarding your answer to the second question: this is when you have stability constraint. Can I say the same argument for unconditionally stable method on non-uniform grid? Is that sufficient to consider uniform grid for the method, such as Crank Nicolson and somehow extend the argument to the non uniform grid? – Kamil Jul 12 '12 at 1:28