# Show the symmetric Gauss-Seidel converges for any $x_0$

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.

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