Boundedness of the spectral radius of matrices $A^h$ as $h\to 0.$

Question

I need to know if the following matrix has a bounded spectral radius $\rho(A)$, as $h\to 0:$ $$A^h=\frac{1}{h^2}\begin{pmatrix} h^2-2h-2&2&0&0\dots &0\\ 1&h^2-2&1&0\dots &0\\ 0&1&h^2-2&1\dots &0\\ \dots&\dots&\dots&\dots\\ \dots&\dots& 1&h^2-2&1\\ \dots&\dots&\dots& 2&h^2-2h-2 \end{pmatrix}$$ where this is $(n+2)\times (n+2)$ matrix with $h = \dfrac{1}{n+1}.$ If anyone is curious, this came from an attempted finite difference method on the equation: $$u''+u = f(x),\quad 0<x<1$$ $$u'(0) = u(0), u'(1) = u(1).$$ As this is neither circulant, nor Toeplitz matrix, I have not found a nice way to compute its eigenvalues; hence the spectral radius.

This matrix is almost tridiagonal, so when I wrote it as $A^h = B+C$ with $B = \frac{1}{h^2}\text{tridiag}(1,-2,1)$ and $C$ some really sparse matrix, $\rho(B)$ is bounded so I have some reason to hope that $\rho(A)$ also stays bounded.

Answer 1

The eigenvalue equation in the middle rows reads as $$ u_{k-1}+(h^2-2)u_k+u_{k+1}=\lambda h^2u_k,~~~ k=1,...,n. $$ This has the general solution $$ u_k=aq^k+bq^{-k} $$ where $q$ solves the quadratic characteristic equation $$ q^2+((1-λ)h^2-2)q+1=0\iff q+q^{-1}=2+(λ-1)h^2 $$ Your first and last line result from realizing the boundary conditions via ghost cells $u_{-1}$ and $u_{n+2}$, where the boundary conditions then read as $$ u_1-u_{-1}=2hu_0\iff a(q-2h-q^{-1})+b(q^{-1}-2h-q)=0\\ u_{n+2}-u_n=2hu_{n+1}\iff aq^{n+1}(q-2h-q^{-1})+bq^{-n-1}(q^{-1}-2h-q)=0 $$ which requires $q^{2(n+1)}=1\iff q=\exp(i\frac{k\pi}{n+1})=\exp(i\pi h·k)$. For the corresponding eigenvalues one gets $$ λ_k=\frac{2\cos(\pi h·k)-2}{h^2}-1, ~~~k=0,...,n+1 $$ For small $k$ one has $λ_k\approx -\pi^2k^2-1$, the largest is $λ_{n+1}=-4(n+1)^2-1$.

For the stability of the method one is probably more interested in that the smallest eigenvalue has an absolute value larger than $1$, so the matrices $A^h$ stay away from the set of singular matrices. That the condition number diverges is the reason that one goes to more structured representations of the function like multi-grid or wavelet methods.

Answer 2

Your matrix belongs to the class of Generalized Locally Toeplitz (GLT) sequences (see for example https://www.springer.com/us/book/9783319536781).

The sequence of matrices $\{h^2A_n\}_n\sim_{GLT}f$ where $f$ is the spectral symbol.

We have $h^2A^h=h^2A_n=T_n(f)+R_n+N_n$ where

$T_n(f)$ is the Toeplitz matrix of order $n$ generated by $f(\theta)=-2+2\cos(\theta)$.

$R_n$ is a low rank matrix $o(n)$ having 1 in the two elements $(1,2)$ and $(n,n-1)$.

$N_n$ is a low norm matrix $\|N_n\|\to 0$ with the $h$ terms.

$\{T_n(f)\}_n\sim_{GLT}f$, $\{R_n\}_n\sim_{GLT}0$, $\{N_n\}_n\sim_{GLT}0$.

thus $\{T_n(f)+R_n+N_n\}_n\sim_{GLT}f+0+0=f$

The spectral radius is 4 (maximum of $|f(\theta)|, \theta \in [-\pi,\pi]$ ) for $h^2A^h$.

Edit: You do have one outlier eigenvalue, as theory predicts $o(n)$ of them, but as $n\to\infty$ this eigenvalue will tend to $-4$.

Edit 2: Added the scaling $h^2$.