The

jacobi 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:

b_{i} = a_{i1}x_{1} + a_{i2}x_{2} + ... + a_{ii}x_{i} + ... + a_{in}x_{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_{i1}x_{1} - a_{i2}x_{2} - ... - a_{in}x_{n})

(not including a_{ii}x_{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.