Jacobi method

In numerical linear algebra, the Jacobi method is an algorithm for determining the solutions of a system of linear equations with largest absolute values in each row and column dominated by the diagonal element. Each diagonal element is solved for, and an approximate value plugged in. The process is then iterated until it converges. This algorithm is a stripped-down version of the Jacobi transformation method of matrix diagonalization. The method is named after German mathematician Carl Gustav Jakob Jacobi.

Contents 1 Description 2 Algorithm 3 Convergence 4 Example 5 References 6 See also 7 External links

Description

Given a square system of n linear equations:

where:

Then A can be decomposed into a diagonal component D, and the remainder R:

The system of linear equations may be rewritten as:

and finally:

The Jacobi method is an iterative technique that solves the left hand side of this expression for x, using previous value for x on the right hand side. Analytically, this may be written as:

The element-based formula is thus:

Note that the computation of x_i^(k+1) requires each element in x^(k) except itself. Unlike the Gauss–Seidel method, we can't overwrite x_i^(k) with x_i^(k+1), as that value will be needed by the rest of the computation. This is the most meaningful difference between the Jacobi and Gauss–Seidel methods, and is the reason why the former can be implemented as a parallel algorithm, unlike the latter. The minimum amount of storage is two vectors of size n.

Algorithm

Choose an initial guess x⁰ to the solution

while convergence not reached do

for i := 1 step until n do

σ = 0

for j := 1 step until n do

if j != i then

end if

end (j-loop)

end (i-loop)

check if convergence is reached

end (while convergence condition not reached loop)

Convergence

The method will always converge if the matrix A is strictly or irreducibly diagonally dominant. Strict row diagonal dominance means that for each row, the absolute value of the diagonal term is greater than the sum of absolute values of other terms:

A second convergence condition is when the spectral radius of the iteration matrix

ρ(D ^{− 1}R) < 1.

The Jacobi method sometimes converges even if these conditions are not satisfied.

Recently, a double-loop technique was introduced to force convergence of the Jacobi algorithm to the correct solution even when the sufficient conditions for convergence do not hold. The double loop technique works for either positive definite or column independent matrices.^[1]

Example

A linear system shown as Ax=b is given by

and

We want to use the equation x^(k) = Tx^{(k − 1)} + C. Now you must find D ^{− 1} the inverse of the diagonal values of the matrix only and separate the strictly lower and the strictly upper parts of the matrix A, (note that this is not what is known as an LU decomposition of a matrix).

and

To find T we use the equation T = D ^{− 1}(L + U).

Now we have found T and we need to find C using the equation C = D ^{− 1}b.

Now we have T and C and we can use them iteratively X matrices. So, now you will have x⁽¹⁾ = Tx⁽⁰⁾ + C.

And now we can find x⁽²⁾.

Now that you have the X matrices you can test for convergence to approximate the solutions.

References

1. ^ Fixing the convergence of the Gaussian belief propagation algorithm. J. K. Johnson, D. Bickson and D. Dolev. In the International symposium on information theory (ISIT), July 2009. http://arxiv.org/abs/0901.4192

See also

• Gauss–Seidel method
• Successive over-relaxation
• Iterative method. Linear systems
• Gaussian Belief Propagation

External links

• This article incorporates text from the article Jacobi_method on CFD-Wiki that is under the GFDL license.

• Black, Noel; Moore, Shirley; and Weisstein, Eric W., "Jacobi method" from MathWorld.
• Jacobi Method from www.math-linux.com
• Module for Jacobi and Gauss–Seidel Iteration
• Numerical matrix inversion