Let $A\in\mathbb{R}^{n\times n}$ is symmetric positive definite and consider solving linear system $Ax = b$. Show that the symmetric Gauss-Seidel iteration converges for any $x_0$.

Solution - Since $A$ is symmetric positive definite and $A = D - L - U$ is the usual partitioning into diagonal, strict lower and strict upper triangular elements, we have $$P_{sgs} = (D - L)D^{-1}(D - U) = CC^T$$ where $C$ is nonsingular lower triangular with positive diagonal elements and it follows that $P_{sgs}$ is symmetric positive definite. Since $A$ and $P$ are both symmetric positive definite, then we can use the result that if the symmetric matrix $2P - A$ is positive definite then the iteration converges. Computing $2P - A$ yields \begin{align*} 2\left[ (D-L)D^{-1}(D - U)\right] - A \end{align*}

Before I continue my professors solution has $U = L^T$ then after pushing around matrices $2P - A = A + 2LD^{-1}L^T$ in which we concludes that since this is the sum of two symmetric positive definite matrices and is therefore also symmetric positive definite. Therefore, Symmetric Gauss-Seidel iteration converges for any $x_0$.

It is not intuitive to me why he lets $U = L^T$ and the algebra or shifting of matrices that yield the solution does not make any sense to me at all. Any suggestions is greatly appreciated.


1 Answer 1


$U=L^{T}$ because the original matrix $A$ is symmetric. You should be able to do the algebraic simplification without too much trouble.


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.