Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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?
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.
