Recently, I obtain a linear system, $Ax = b$, where $A$ is a nonsingular, strictly diagonally dominant $M$-matrix. Then I also got a matrix splitting $A = S - T$, where $S$ is also a nonsingular, strictly diagonally dominant $M$-matrix. So I establish a stationary iteration scheme as follows, $$Sx^{(k+1)} = Tx^{(k)} + b.$$ According to numerical results, it seems that this iterative scheme is always convergent. Is it rational from theoretical analysis? So, can we prove the convergence of this iterative scheme? i.e., show $\rho(S^{-1}T) < 1$, where $\rho(\cdot)$ is the spectral radius.

  • 3
    $\begingroup$ Note that a sufficient (but not necessary) condition is $\|S^{-1}T\|<1$ for some matrix norm, which might be easier to show. If you want a better answer, you need to tell us more (much more) about $A$, $S$ and $T$. $\endgroup$ Commented Jun 28, 2016 at 18:57
  • $\begingroup$ What makes you think that this is true for all $A$ and $S$ that are M-matrices? Or, are you asking what techniques might be used to figure this out for a particular $S$ and $T$? $\endgroup$ Commented Jun 28, 2016 at 20:05
  • $\begingroup$ Yeah, this is from a finite difference scheme for PDEs, then $Ax = b$, then I find that $S$ is an efficient preconditioner for this resulted systems, $S\approx A$, even I find that $S$ is also a M-matrix, so I want to set up a stationary iteration method based on $A = S - T$, then this stationary iteration may be used as a new smoother for Multigird methods, that is why I can set both $S$ and $A$ are M-matrix. Here I think that, 1) Every efficient matrix splitting (or decomposition) implies that there is a kind of preconditioning techniques available for us; 2). Every preconditioning ---> ,. $\endgroup$ Commented Jun 28, 2016 at 20:48
  • $\begingroup$ @ChristianClason, in fact, I can prove that $\|S^{-1} T\|_{\infty} < 1$, but I should set the (finite difference) grid size $h < constant$. $\endgroup$ Commented Jun 28, 2016 at 21:02
  • $\begingroup$ Showing that $\| S^{-1}T \|_{\infty} < 1$ is sufficient to show convergence without computing the spectral radius. $\endgroup$ Commented Jun 28, 2016 at 21:05

1 Answer 1


You can prove convergence by satisfying the spectral radius relationship you note, choosing $S$ and $T$ such that $\rho(S^{-1}T) < 1$.

This comes about by first writing two equations based on your operator splitting:

$$ Sx = Tx + b$$ $$ Sx^{(k+1)} = Tx^{(k)} + b $$

where $x$ is exact solution and $x^{(k)}$ is the $k^{th}$ iteration's solution.

Now assume error can be defined as: $e^{(k)} = x - x^{(k)}$. Based on this relationship and the two equations above, you end up with:

$$ Se^{(k+1)} = Te^{(k)} $$ $$ e^{(k+1)} = (S^{-1}T) e^{(k)} $$

Based on the resulting equation, the condition that needs to be met for $e^{(k+1)}$ to converge as $k \rightarrow \infty$ is for $\rho(S^{-1}T) < 1$, as you mentioned. How you prove this spectral radius inequality depends on the form of $S^{-1}T$ based on your choices for $S$ and $T$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.