Stability of Crank-Nicholson method

[Nusc]

Homework Statement

If p(A^-1 B) < 1 then the Crank-Nicholson method is stable for all eigenvalues.Where p is the spectral radius.

Homework Equations

Stability requires that A*U_j=B*U_{j-1} which gives
U_j = A^-1 B U_{j-1}

The Attempt at a Solution

Where do I start?

 

[LeBrad]

Where do I start?

By defining A,B, and the problem more clearly. Are you saying you need to prove that if p(A^-1 B)<1, then the Crank-Nicholson method applied to some equation involving A and B is stable?

 

[Nusc]

Yes.
So for A*U_j = B*U_{j-1} we have:
The finite difference matrix for A:

1+lamda -lamda/2 ... 0
-lamda/2 1+lamda ... 0
0 ...
... -lamda/2
0 ... -lamda/2 1+lamda

Some tridiagonal matrix.
Similarly for B
B:

1-lamda +lamda/2 ... 0
+lamda/2 1-lamda ... 0
0 ...
... +lamda/2
0 ... +lamda/2 1-lamda

This is in general. I'm not sure if this is correct because I assume we need to do it for another problem.

 

[LeBrad]

If your equation is
Au_j = Bu_{j-1},
then
u_j = A^{-1}Bu_{j-1}
and
u_{j+1} = A^{-1}Bu_{j}= \left(A^{-1}B\right)A^{-1}Bu_{j-1},
and
u_{j+2} = A^{-1}Bu_{j-1}u_{j+1} = \left(A^{-1}B\right)^3u_{j-1}.
You can continue this on forever to get the term after n steps as
u_{j+n} = \left(A^{-1}B\right)^{n+1}u_{j-1}.

Now factor A^{-1}B by eigenvalue decomposition to obtain
A^{-1}B = TDT^{-1}
where D is a diagonal matrix containing the eigenvalues and T contains the corresponding eigenvectors.
Note that
\left(A^{-1}B\right)^2 = \left(TDT^{-1}\right)^2 = TDT^{-1}TDT^{-1}= TD^2T^{-1}
And similarly,
\left( A^{-1}B \right)^n = TD^nT^{-1}

Now if you plug this into the previous equation, you find that
u_{j+n} = \left(A^{-1}B\right)^{n+1}u_{j-1} = TD^{n+1}T^{-1}u_{j-1}

The system is stable if the solution u_{j+n} is bounded for all n. Since D is a diagonal matrix, D^{n+1} is just the diagonal elements raised to the n+1th power. So what happens if a number bigger than one is raised to a large power? And what about when the number is smaller than one? This is why you have the condition on the size of the eigenvalues.

 

[Nusc]

If a number bigger than one is raised to a large power, then the system will become unstable.
If a number smaller than one is raised to a large power, then the system will become stable.

Hence the method is unconditionally stable.

Is that correct?