= Gauss-Seidel iteration for a two-variable positive-definite system
{c}
{title2=$A=\begin{pmatrix}4&1\\1&3\end{pmatrix}$}
Consider the original <linear system>
$$
A\begin{pmatrix}x\\y\end{pmatrix}=b,\qquad A=\begin{pmatrix}4&1\\1&3\end{pmatrix},\qquad b=\begin{pmatrix}1\\2\end{pmatrix},\qquad \begin{pmatrix}x_*\\y_*\end{pmatrix}=\begin{pmatrix}1/11\\7/11\end{pmatrix}.
$$
Direct substitution verifies the solution. The <matrix> is a <symmetric positive-definite matrix>: <completing the square> in its <quadratic form> gives $4x^2+2xy+3y^2=4(x+y/4)^2+11y^2/4>0$ for every nonzero <vector>. It is also a <strictly diagonally dominant matrix>.
Starting from $(x^{(0)},y^{(0)})=(0,0)$, update the first row and then the second:
$$
x^{(k+1)}=\frac{1-y^{(k)}}4,\qquad y^{(k+1)}=\frac{2-x^{(k+1)}}3.
$$
The first sweep gives $x^{(1)}=1/4$ and $y^{(1)}=(2-1/4)/3=7/12$. The next gives $x^{(2)}=(1-7/12)/4=5/48$ and $y^{(2)}=(2-5/48)/3=91/144$. The second row uses $1/4$ during the first sweep, even though the initial first coordinate was zero.
\Image[/gauss-seidel-two-row-fresh-updates.png]
{title=Fresh and stale inputs in the first sweep of the original two-variable <linear system>}
With a stale first coordinate, the <Jacobi method> would instead give $(1/4,2/3)$ after the first sweep. Both methods have the same <fixed point>, but changing when coordinates become available changes the entire sequence of <vectors>.
Back to article page
