5.3. The Jacobi method

A = (a_ij ), = (b₁ , ..., b_n ), = (x₁ , ..., x_n )

Choose

If D on regular (D ^{- 1}, i.e., each a_ii 0), then

A = <=> = - D ^{- 1}C + D ^{- 1}

and we obtain the iteration formula

(4)

^{(k + 1)} = G ^(k) + ,    G = - D ^{- 1}C,    = D ^{- 1}

Denoting ^(k) = (x₁ ^(k), ..., x_n ^(k)) we have (4) <=>

x1(k+1) : xn(k+1)

= - (1/a11) 0 0 0 (1/a22) 0 : ··· 0 0 (1/ann)

0 a12 ··· a1n a21 0 a23 ··· a2n : ··· an1 0

x1 (k) : xn (k)

+ (1 / a11 ) 0 ··· 0 (1 / ann )

b1 : : bn

so that the components are

(5)

x_i ^{(k + 1)} = - (1 / a_ii ) a_ij x_j ^(k) + (1 / a_ii ) b_i

and this can be used when programming the Jacobi iteration. Use of (4) involves unnecessary multiplications by 0's.

When using the || ||-norm, the condition ||G|| < 1 for convergence takes the form

||G|| < 1	<=>	|gij | < 1
	<=>	| (aij / aii ) | < 1

(6)

<=>      | a_ij | < | a_ii | ,    i = 1, ..., n.

The Jacobi iteration converges, if A is strictly diagonally dominant.

Note. The Jacobi method is more useful than, for example, the Gaussian elimination, if 1) A is large, 2) most entries of A are zero , 3) A is strictly diagonally dominant. This is the case, for example, with certain matrices in connection with boundary value problems of partial differential equations.

The choice x_i ⁽⁰⁾ = 0, i = 1, ..., n (or x_i ⁽⁰⁾ = (b_i / a_ii ) ) is good, since the solution is

x_i = - (a_ij / a_ii ) x_j + (b_i / a_ii ),

=> x_i ~(b_i / a_ii ), since | a_ii | > > | a_ij | , j i so that the first iteration satisfies x_i ⁽¹⁾ = (b_i / a_ii ) ~ x_i .

Example 1: A strictly diagonally dominant coefficient matrix