Jacobi iteration

Row i of a system of linear equations Ax=b can be written as:

b_i = a_i1x₁ + a_i2x₂ + ... + a_iix_i + ... + a_inx_n

Now, let us pretend that we have all the values of x, excpet for x_i. We can solve for x_i from the above equation:

x_i = 1/a_ii * (b_i - a_i1x₁ - a_i2x₂ - ... - a_inx_n)
(not including a_iix_i)

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.