most recent 30 from http://mathoverflow.net 2013-06-19T05:15:55Z http://mathoverflow.net/feeds/question/80793 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80793/is-gauss-seidel-guaranteed-to-converge-on-semi-positive-definite-matrices noam 2011-11-13T03:24:12Z 2011-11-13T21:09:27Z

<p>I know that the Gauss-Seidel method is guaranteed to converge given that the matrix you want to solve is positive definite. I've looked at the proofs of convergence, and it appears that one cannot change the assumption so that the smallest eigenvalue is zero, without coming up with a totally new proof. This makes sense, since of course a PSD matrix is singular. </p> <p>However, assuming that $b$, the right hand side of the equation $A \cdot x = b$ is in $A$'s image (and that $A$ is PSD) is Gauss-Seidel guaranteed to converge? </p>

http://mathoverflow.net/questions/80793/is-gauss-seidel-guaranteed-to-converge-on-semi-positive-definite-matrices/80794#80794 psd 2011-11-13T03:31:34Z 2011-11-13T03:31:34Z

<p>According to section 17.6 of "Solving PDEs in C++: numerical methods in a unified object-oriented approach" Gauss-Seidel does not necessarily converge when the matrix is indefinite.</p>

http://mathoverflow.net/questions/80793/is-gauss-seidel-guaranteed-to-converge-on-semi-positive-definite-matrices/80831#80831 suVRit 2011-11-13T17:17:57Z 2011-11-13T17:17:57Z

<p>Here are some general comments (drawn from the nice book: <a href="http://books.google.com/books?id=epilvM5MMxwC&amp;dq=nick+higham+error&amp;source=gbs_navlinks_s" rel="nofollow">Accuracy and stability of numerical algorithms</a> by N. J. Higham) that might prove helpful.</p> <p>Suppose $A$ is singular. Split $A=M-N$, where $M$ is nonsingular. Iterate</p> <p>$$Mx_{k+1}=Nx_k+b.$$</p> <p>Define the "action" matrix $H=M^{-1}N$, using which the above iteration becomes $$x_{k+1} = Hx_k + M^{-1}b.$$</p> <p>Now, unroll this loop starting at $x_1$, to get</p> <p>$$x_{k+1} = H^kx_1 + \sum_{j=0}^{k-1} H^jM^{-1}b.$$</p> <p>For the sequence $(x_k)$ to be convergent, a necessary condition is that the sequence $(H^k)$ converges. This, in turn can be ensured if $rank(I-H) = rank( (I-H)^2 )$. Eventually, though, the limit of $(x_k)$ will depend on where we started, i.e., $x_1$.</p>

http://mathoverflow.net/questions/80793/is-gauss-seidel-guaranteed-to-converge-on-semi-positive-definite-matrices/80845#80845 Denis Serre 2011-11-13T21:09:27Z 2011-11-13T21:09:27Z

<p>This is an interesting question, to which the answer is <strong>positive</strong>.</p> <p>Here is the proof. Of course, for the method to make sense, we must assume that the diagonal $D>0$. The notations below are borrowed from Section 12.3.2 of my book <em>Matrices</em> (2nd edition, Springer-Verlag, GTM <strong>216</strong>). Let $G=(D-E)^{-1}E^T$ the iteration matrix. One checks easily that $\ker A$ is the eigenspace of $G$, associated with the eigenvalue $\lambda=1$. The corresponding eigenspace for $G^T$ is $(D-E)^T\ker A$, fro which we find that $G$ has the invariant subspace $(D-E)^{-1}R(A)$. This can be verified directly with the help of the formula $G(D-E)^{-1}A=(D-E)^{-1}AG$. It turns out that $1$ is semi-simple: if $Gw=w+V$ and $Gv=0$, we obtain $v^T(D+A)v=0$, hence $v=0$. Therefore $${\mathbb R}^n=\ker A\oplus (D-E)^{-1}R(A)$$ is a decomposition into $G$-invariant subspaces.</p> <p>There remains to prove that for every vector $x^0$, the sequence $x^m:=G^mx^0$ is convergent. Let us decompose $x^m=y^m+z^m$, according to the invariant subspaces above. We have $y^m=y^0$, so this part is obviously convergent. There remains to prove that the spectral radius of the restriction $g$ of $G$ to $(D-E)^{-1}R(A)$ is smaller than $1$. This is proved exactly the same way as in Lemma 20 of the reference. We have to prove that if $x\in(D-E)^{-1}R(A)$, then $(Gx^T)A(Gx)\le x^TAx$, and equality implies $x=0$. With $y=(D-E)^{-1}Ax$, we have $$(Gx^T)A(Gx)-x^TAx=-y^TDy\le0.$$ If the right-hand side vanishes, then $y=0$, which means $x\in\ker A$, hence $x=0$. Q.E.D</p>