Why does consecutive averaging not lead to a good solution to a linear system?

Question

I have been working on a program which requires me to get a solution for a huge system of linear equations (3,132 variables and 3030 equations). I was having trouble finding a previous implementation to solve this, so I thought up this method:

1. Guess a value for every variable
2. For each variable, consecutively:
3. compute the value it would need to be to solve each equation in the system
4. Set the variable to the average of those values and go onto the next variable

For example:

Say your system is $$ x+y+z=4 \\ 2x+4y+8z=15 $$ You start by guessing $x$, $y$, and $z$ are all one. The mean squared error of this "solution" is 1.

Start by focusing on $x$. $$ x+1+1=4 \\ 2x+4+8=15 $$ Through simple algebra, you can see that $x$ should be 2 and 1.5 in each equation, respectively. So you average those, and say x is 1.75. The mean squared error of this solution is 0.156, so the new solution is better. You update your guess, and continue doing this with each variable until the solution was sufficiently close or was no longer improving.

I never expected this to be a good way to solve this problem. I thought it would often get stuck in local minima and be slow. However, when I implemented this, it was not just ineffective, it was counterproductive. After each pass through the variables the mean squared error increased, not decreased, and I can not figure out why. Theoretically, each step should make the solution better, so why does it seem to make the solution worse?

Thank you in advance for your help.

Answer 1

If we take your very example, starting with $x=y=z=1$, but proceed to perform the same step on $z$: $$ 1+1+z=4 \implies z = 2\\ 2+4+8z=15 \implies z = 1.125 $$ so, as you describe, we should take $z = (2 + 1.125)/2 = 1.5625$

But hold on! $$ 1+1+1.5625 - 4 = -0.4375 \\ 2+4+8\times 1.5625 - 15 = 3.5 \quad\text{ouch!} $$ and now the error increased! Well, herein lies the problem. That averaging thing for computing the next value just doesn't have anything to do with the solution. It basically fails to account for the coefficients (in this case, 1 vs 8).

You should consider looking into least-square solution using perhaps the Conjugate gradient method, which is in a similar "spirit" as your homemade solver.