Unique coordinates (solutions) in a single Gauss-Seidel iteration

Question

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$ are weighted Laplacian matrices (symmetric, positive semi-definite; negative off-diagonal entries, with rows(collumns) summing (in absolute values) to positive diagonal entries; matrix eigenvalue $0$ corresponds to $1_n$ eigenvector of the nullspace), and $x,y\in\mathbb{R}^{n\times 2}$ are vectors with the unknown $x$. The solution has the form $$x_i^{[k+1]} = \left.\left(b_i - \sum_{j=1}^{i-1}a_{ij}x_j^{[k+1]} - \sum_{j=i+1}^{n}a_{ij}x_j^{[k]}\right)\middle/a_{ii}\right.,$$ where $b_i$ is the $i^{th}$ entry of $Ly$. Note that, with Gauss-Seidl, the update of $x_i$ takes effect immediately, i.e., calculation for the following $x_{i+1}$ is based on the new value of $x_i$ that has been computed just before.

Now, suppose an iteration consists of a single update of all $x_i$ in some arbitrary order. In other words, each $x_i$ is considered only once (and is updated only once) in an iteration. My question is: could it be guaranteed that after a single iteration with initial $x^{[0]}=y$, the solution $x^{[1]}$ has all unique coordinates, i.e., there are not two rows of $x^{[1]}$ that are equal?

You could assume that the initial $x^{[0]}=y$ has non-unique coordinates. If the uniqueness cannot be resolved this way, I would appreciate a suggestion on the coordinate traversal order to increase the chance of achieving uniqueness (i.e., no two coordinates take the same value).

Answer 1

The order in which you update the new solution has a big impact on the values produced from the initial data to the first approximation. Some updated values will be the same as the jacobi iteration, while others will contain the latest information a la Gauss-Seidel. Given a specific ordering, there may be two values that are the same if the initial vector $x_0$ has non-unique values. But for two different orderings, if the the solution vector is large, and the order of updating the gauss-seidel formula is random, the more unlikely it is that you will produce similar 1st iterations. I'm not sure if there is a proof for that different orderings produce unique 1st iterations, but even if it is possible for them to be non-unique, the probability is very unlikely.

Answer 2

Application of Gauss-Seidel is a nonsingular affine operator (for matrices and orderings in which Gauss-Seidel is convergent), let's call the linear part $G$. That is, with $A = L + D + U$, we have $x_1 = (L+D)^{-1}(b - U x_0) = \tilde b + G x_0$. Without loss of generality, let's take $b = 0$, in which case $\tilde b = (L+D)^{-1} b = 0$, thus $x_1 = G x_0$ with $G = (L+D)^{-1} U$ nonsingular.

If I understand your question, you are asking whether observing $G x_0 = G y_0$ (i.e. identical results after one iteration of Gauss-Seidel) implies that $x_0 = y_0$. Well, $G (x_0 - y_0) = 0$ is only possible if $x_0 - y_0 = 0$ or if $G$ is singular.

Note that Gauss-Seidel may damp some modes very fast so you can get iterates that are very close even though the initial vectors were different.

Answer 3

This question is ill-posed. Gauss-Seidel is an iterative method for solving a linear system of equations that is guaranteed to converge for certain matrices. If the solution to the linear system of equations contains non-unique values, then Gauss-Seidel will converge to non-unique values. The iteration number and order of applying the updates are irrelevant.