For large size matrices, the resolution of linear systems $Ax=b$ is often done iteratively. The matrix $A$ is split as $A=M-N$, with $M$ invertible, and one performs $$x^{k+1}=M^{-1}(Nx^k+b).$$ The method is convergent if and only if the spectral radius $\rho(M^{-1}N)$ of the iteration matrix is strictly less than $1$.
The basic methods, taught in a first course of Numerical Analysis are named Jacobi and relaxation. Both are based upon the decomposition $A=D-E-F$, where $D$ is the diagonal, and $-E$ (resp. $-F$) is the strictly lower (resp. upper) triangular part. The iteration matrix for Jacobi is $J:=D^{-1}(E+F)$. That for the relaxation depends upon a complex number $\omega$: $$L_\omega=(D-\omega E)^{-1}((1-\omega)D+\omega F).$$ Because of the formula $\det L_\omega=(1-\omega)^n$, a necessary condition for the convergence of the relaxation method is that $\omega\in D(1;1)$ (the open disk of radius $1$, with center $1$).
This necessary condition is known to be sufficient in at least two cases (references are from the first edition of my book Matrices; Theory and Applications. GTM 216, Springer-Verlag, 2002).
- When $A$ is Hermitian positive definite (Thm 9.3.1).
- When $A$ is tridiagonal, the spectrum of $J$ is real and $\rho(J)<1$ (the Jacobi method converges). See Thm 9.4.1 and exercise 7 of the same chapter.
Question. Identify all the matrices $A$ (of course with an invertible diagonal $D$), such that the relaxation method converges for every parameter $\omega$ in the admissible disk $D(1;1)$.
