3
$\begingroup$

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.

$\endgroup$
  • 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$ – Christian Clason Jun 28 '16 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$ – Brian Borchers Jun 28 '16 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$ – Hsien-Ming Ku Jun 28 '16 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$ – Hsien-Ming Ku Jun 28 '16 at 21:02
  • $\begingroup$ Showing that $\| S^{-1}T \|_{\infty} < 1$ is sufficient to show convergence without computing the spectral radius. $\endgroup$ – Brian Borchers Jun 28 '16 at 21:05
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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