What is the method for checking stability of finite differencing schemes?

[eckiller]

Hi,

I am in an undergrad numerical analysis course. Our instructor lectured on some material not found in the book. Specifically, he talked about a way to check stability of finite differencing schemes (for PDE) by studying how each Fourier mode evolves in time. Then you can find an "amplification factor" which can tell you when the method is stable.
Sorry if this is vague, but does it sound familiar to anyone? I would like to know the technical name for this process so I can do further research about it because I do not really understand at present. Also, if anyone knows of any books that cover it, I'd like to know their titles.

Thanks in advance.

 

[PerennialII]

Most likely the "amplification factor" in question is at least similar to the ones applied in most numerical time integration methods. The amplification factor/matrix etc. is the 'deciding' factor in determining the stability of the solution during incrementation, its unconditional / conditional stability etc. depending on the PDE formulation ... different PDE solution methods have typically similar time integration schemes in this respect so no real matter whether its extracted from finite element, finite difference or some other form of iterative solution process (well, basically it's a finite difference application "in time").

I'd suggest searching for "time-integration", you've the correct term ... all books on numerical methods that deal with areas requiring time - integration are possible sources (==lots). 'Basic' finite element volumes, whatever you might have at your disposal, have usually this pretty well covered. (If you want we can consider the specific application in more detail.)

 

[LeBrad]

I think I know what you're talking about.

Say you're working with the equation

$$\frac{\partial u}{\partial t} = C* \frac{\partial^2 u}{\partial x^2}$$

which has a discretized form like so (superscripts are time steps and subscripts are spatial steps)

$$\frac{u^{n+1}-u^n}{\Delta t} = \frac{C}{\Delta x^2} (u^n_{i+1} - 2u^n_i + u^n_{i-1})$$

Then assume a solution of the form

$$\hat{U}(t) = e^{ikx}$$

Plug it into the discretized equation.


$$\frac{\hat{U}^{n+1}-\hat{U}^n}{\Delta t} e^{ikx} = \frac{C}{\Delta x^2} \hat{U}^n ( e^{ik(x+\Delta x)} - 2e^{ikx} + e^{ik(x-\Delta x)})$$

Pull out exp(ikx) on the right and move some stuff from the left to the right to get

$$\hat{U}^{n+1} e^{ikx}= \hat{U}^n e^{ikx}+ \frac{C \Delta t}{\Delta x^2}\hat{U}^n e^{ikx} (e^{ik\Delta x} -2 + e^{-ik\Delta x})$$

Now cancel the exponential and group the rest into a constant alpha and you have.

$$\hat{U}^{n+1} = \alpha \hat{U}^n$$

So you see that the solution at the next timestep is the solution from the previous timestep multiplied by some constant, or amplification factor. If alpha is larger than one, as time evolves the solution with grow and grow. Hence it is unstable.

You can see that alpha depends on dt/dx^2 in this case, so if you're looking for a rough first guess of timestep size to make it stable, set dt equal to half of your largest spatial derivative, dx^2/2 in this case.

I think I remember this being referred to as semi-discrete Fourier analysis. You can try searching for that if this is what you're talking about.

 

[Clausius2]

I think this stuff is called the "Von Neumman Stability Analysis".

 

[LeBrad]

I think this stuff is called the "Von Neumman Stability Analysis".

Yes, that's definitely it.