Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$, 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-Seidel, the update of $x_i$ takes effect immediately, ie., 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$ is 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 coordiantes, ie., unique solutions?

You could assume that the initial $x_0=y$ has a non-unique coordinates. If the uniqueness cannot be resolved this way, I would appreciate a suggestion on the coordinate visiting order to increase the chance on achieving uniqueness (ie. non-coincidence of some coordinates).

The main motivation behind the above is: there exist a proof that, at the local minimum, certain function has to yield different coordinates. On the other hand, if the minimization to the function is Gauss-Seidel in a $single$ iteration, then the resulting solution might have coinciding points, hence it does not correspond to locally minimal solution. In the literature I have on disposal, however, it is claimed this will not happen, at least not theoretically. I therefore explore.

share|improve this question
You may want to add some motivation why you're interested in the distinctness of the coordinates. –  joriki Mar 26 '12 at 14:16
@joriki I edited the question; hopefully, the motivation is clearer. I have to state that I'm very frequently confused by the claims made in some academic works, that are in contrast with others. –  user506901 Mar 26 '12 at 19:08
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.