iteration, also called jacobi relaxation
, is one of the oldest iterative method for solving systems of linear equations
Row i of a system of linear equations Ax=b can be written as:
bi = ai1x1 + ai2x2 + ... + aiixi + ... + ainxn
Now, let us pretend that we have all the values of x, excpet for xi. We can solve for xi from the above equation:
xi = 1/aii * (bi - ai1x1 - ai2x2 - ... - ainxn)
(not including aiixi)
Of course, in reality, we usually don't have all the other x's. But what we can do is guess all the x's, and generate a new set of x's from the equation above. Once we have a new set of x's, we can generate again a new set of x's... and repeat the process until we have the correct answer.
In many cases, this will result in better and better estimates for x. This algorithm will not work for all matrices though, one obvious exclusion is any matrix with a zero in the diagonal.