Crank-Nicholson

[Nusc]

1. The problem statement, all variables and given/known data
If p(A^-1 B) < 1 then the Crank-Nicholson method is stable for all eigenvalues.


Where p is the spectral radius.

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


3. 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 in to 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?