I have the following problem:
For the problem $u_t = a\, u_{xx}$ with $a > 0$, consider the following finite difference scheme:
$$ \frac{u_j^{k+1}-u_j^k}{\Delta t} = \frac{a}{2}\left(\frac{u_{j-1}^{k+1} - 2u_j^{k+1} + u_{j+1}^{k+1}}{\Delta x^2} \right) + \frac{a}{2}\left(\frac{u_{j-1}^{k} - 2u_j^{k} + u_{j+1}^{k}}{\Delta x^2} \right) $$
- Find conditions for convergence in infinity norm.
Here is my reasoning:
Let $A \in \mathbb{R^{MxM}}$ be the tridiagonal matrix:
$A = \begin{pmatrix} 2 & -1 & \dots & \dots& 0 \\ -1 & 2& 1& \dots &0 \\ \vdots & \vdots& \ddots & \ddots& \vdots\\ 0 & 0 & \dots &-1 &2\end{pmatrix}$
Let $\alpha = \frac{a\Delta t}{2\Delta x}$
Then the system can be written in matrix form as $$ (I + \alpha A) \cdot U^{(n+1)} = (I - \alpha A) \cdot U^{(n)} \\\iff U^{(n+1)} = \left[(I + \alpha A)^{-1}(I - \alpha A)\right]^n \cdot U^{(0)} $$
Therefore, the system converges in infinity norm if $\left||(1 + \alpha A)^{-1}(I - \alpha A)|\right|_\infty < 1$.
However, I don't get how to calculate $\left||(1 + \alpha A)^{-1}(I - \alpha A)|\right|_\infty$ without explicitly inverting the matrix, and since it is of arbitrary size, inverting it does not seem feasible to me. I guess I'm just missing something? I've seen similar posts here, but wasn't able to use them to solve this. I hope this isn't a duplicate!
I assume that boundary conditions are $u_0^{n+1} = u_{M+1}^{n+1} = 0$.
The general case can be found in this paper which can be briefly summarized as
Together this means that for any value $\alpha > 0$ the scheme is convergent in the infinity norm. When $\alpha \leq 3/4$ the convergence is monotonic ($\|U^{n+1}\|_\infty \leq \|U^{n}\|_\infty$ which means that perturbations are damped in the infinity norm). When $\alpha > 3/4$ the convergence is not monotonic (which mean that perturbations may grow in the infinity norm, but are bounded by growth coefficient equal to 4.325).
Here is a simple proof for $\color{red}{\alpha \leq 1/2}$ case.
I'll start with $(I + \alpha A) U^{n+1} = (I - \alpha A) U^n$. Let's write it elementwise: $$ -\alpha u^{n+1}_{j-1} + (1 + 2 \alpha)u^{n+1}_{j} -\alpha u^{n+1}_{j+1} = \alpha u^{n}_{j-1} + (1 - 2 \alpha)u^{n}_{j} + \alpha u^{n}_{j+1} $$ Now move the off-diagonal elements to the right side: $$ (1 + 2 \alpha)u^{n+1}_{j} = \alpha u^{n+1}_{j-1} + \alpha u^{n+1}_{j+1} + \alpha u^{n}_{j-1} + (1 - 2 \alpha)u^{n}_{j} + \alpha u^{n}_{j+1} $$
Let's estimate the absolute value of the left side: $$ |(1 + 2 \alpha)u^{n+1}_{j}| = |\alpha u^{n+1}_{j-1} + \alpha u^{n+1}_{j+1} + \alpha u^{n}_{j-1} + (1 - 2 \alpha)u^{n}_{j} + \alpha u^{n}_{j+1} | \leq \\ \\ \leq |\alpha u^{n+1}_{j-1}| + |\alpha u^{n+1}_{j+1}| + |\alpha u^{n}_{j-1}| + |(1 - 2 \alpha)u^{n}_{j}| + |\alpha u^{n}_{j+1}|. $$ Provided that $\color{red}{(1 - 2\alpha) \geq 0}$ we can take that multiplier out $$ (1 + 2 \alpha)|u^{n+1}_{j}| \leq \alpha |u^{n+1}_{j-1}| + \alpha |u^{n+1}_{j+1}| + \alpha |u^{n}_{j-1}| + (1 - 2 \alpha) |u^{n}_{j}| + \alpha |u^{n}_{j+1}|. $$ Now taking maximum over $j = 1, \dots, M$ from the both sides we obtain $$ (1 + 2\alpha) ||U^{n+1}||_\infty \leq \alpha \max_{j=0,\dots,M-1} |u^{n+1}_j| + \alpha \max_{j=2,\dots,M+1} |u^{n+1}_j| + {} \\ {} + \alpha \max_{j=0,\dots,M-1} |u^{n}_j| + (1 - 2\alpha) ||U^n||_\infty + \alpha \max_{j=2,\dots,M+1} |u^{n}_j|. $$ All maximums are bounded with corresponding $||U||_\infty$ so $$ (1 + 2\alpha) ||U^{n+1}||_\infty \leq \alpha ||U^{n+1}||_\infty + \alpha ||U^{n+1}||_\infty + \alpha ||U^n||_\infty + (1 - 2\alpha) ||U^n||_\infty + \alpha ||U^n||_\infty = {} \\ {} = 2 \alpha ||U^{n+1}||_\infty + ||U^n||_\infty. $$ Canceling $2 \alpha ||U^{n+1}||_\infty$ from the both sides we get the desired stability property $$ ||U^{n+1}||_\infty \leq ||U^n||_\infty. $$ We proved that $||(I + \alpha A)^{-1} (I - \alpha A)||_\infty \leq 1$ which is sufficient for stability and convergence.