# How to show that Gauss-Seidel iterative method is equivalent to successively setting each component of residual vector to zero?

As stated in the title, it's said in the book that Gauss-Seidel iterative method is equivalent to successively setting each component of residual vector to zero. After rearranging G-S scheme, I got the following relation regarding the update of residual:

$$r^{(k+1)} = U(D-L)^{-1}r^{(k)},$$

but I still can't see why this conclusion holds. Any help?

• If $D,L,U$ mean what I think they mean, it should be $(D-L)^{-1}U$, not $U(D-L)^{-1}$. – Federico Poloni Dec 9 '17 at 20:41
• Oh yes, for Ax=b, D, L and U are respectively the diagonal, lower triangular and upper triangular of A! – user123 Dec 9 '17 at 21:43
• Can you reference the book you're mentioning? – nicoguaro Dec 10 '17 at 1:35
• @nicoguaro Oh yes, I am referring to chapter 2 of the 'A multigrid tutorial‘ book. – user123 Dec 10 '17 at 2:44

Given approximated solution $\mathbf x^{(k)}$, we define the residual vector $\mathbf r^{(k)} := \mathbf b - \mathbf A\,\mathbf x^{(k)}$. Now we want to update $x^{(k)}_i \rightarrow x^{(k+1)}_i$ in such a way so that the $i$th component of the new residual vanishes: $$r^{(k+1)}_i = b_i - \sum_{j=1}^n a_{ij}\,x^{(k+1)}_j = 0, \\ b_i - \left(\sum_{j=1}^{i-1} a_{ij}\,x^{(k+1)}_j + a_{ii}\,x^{(k+1)}_i + \sum_{j=i+1}^n a_{ij}\,x^{(k+1)}_j\right) = 0, \\ x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j=1}^{i-1} a_{ij}\,x^{(k+1)}_j - \sum_{j=i+1}^n a_{ij}\,x^{(k+1)}_j\right).$$ Assuming that all the other components stay the same, we may rewrite this formula as $$x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j=1}^{i-1} a_{ij}\,x^{(k)}_j - \sum_{j=i+1}^n a_{ij}\,x^{(k)}_j\right).$$ Now, if we introduce matrix notation $\mathbf A = \mathbf L + \mathbf D + \mathbf U$ with strictly lower, diagonal, and strictly upper parts of the original matrix, we may rewrite the last equation as $$\mathbf L\,\mathbf x^{(k)} + \mathbf D\,\mathbf x^{(k+1)} + \mathbf U\,\mathbf x^{(k)} = \mathbf b, \\ \mathbf x^{(k+1)} = -\mathbf D^{-1}\left(\mathbf L + \mathbf U\right)\mathbf x^{(k)} + \mathbf D^{-1}\,\mathbf b;$$ this is well-known Jacobi method.
Note that at the $i$th step we have already updated components $1, 2, \dots, i-1$, so let’s use these updated values: $$x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j=1}^{i-1} a_{ij}\,x^{(k+1)}_j - \sum_{j=i+1}^n a_{ij}\,x^{(k)}_j\right),$$ or $$\mathbf L\,\mathbf x^{(k+1)} + \mathbf D\,\mathbf x^{(k+1)} + \mathbf U\,\mathbf x^{(k)} = \mathbf b, \\ \mathbf x^{(k+1)} = -(\mathbf D + \mathbf L)^{-1}\,\mathbf U\,\mathbf x^{(k)} + (\mathbf D + \mathbf L)^{-1}\,\mathbf b.$$ This is Gauss–Seidel method.
• This is true. Jacobi annihilates $i$th component of the residual assuming all the other components of the soln vector stay unchanged; Gauss–Seidel does the same but uses $(k+1)$th step (already updated) components of the soln vector. – 56th Dec 10 '17 at 3:22