Prove that the Jacobi iteration method applying to Ax=b is convergent for any initial x (0), provided that A is strictly diagonally dominant?

Answer 1

Answer: The Jacobi iteration method is an iterative method used to solve a system of linear equations Ax = b. This method is based on the idea that an approximate solution can be obtained by iteratively solving each equation for one of its unknowns while the other unknowns are kept fixed. In order for the Jacobi iteration method to converge, we must prove that it is convergent for any initial x (0) provided that A is strictly diagonally dominant.

Let A be an n-by-n matrix and b be a vector in Rn. We assume that A is strictly diagonally dominant. This means that the absolute value of each diagonal element of A is greater than the sum of the absolute values of the non-diagonal elements in the same row. This can be expressed mathematically as:

|a_jj| > ∑ |a_ij| , where i ≠ j and i, j = 1,2, ..., n.

Now, let x(0) be the initial vector in Rn. The Jacobi iteration method for solving Ax = b is given by:

x_j^{k+1} = (b_j - ∑_{i=1,i≠j}^{n}a_ijx_i^k) / a_jj , where j = 1,2, ..., n.

We can prove that the Jacobi iteration method is convergent for any initial x (0), provided that A is strictly diagonally dominant, by using the following theorem.

Theorem: Let A be an n-by-n matrix and b be a vector in Rn. Assume that A is strictly diagonally dominant and let x(0) be the initial vector in Rn. Then, the Jacobi iteration method is convergent for any initial x (0).

Proof: We will prove the theorem by using the Banach fixed point theorem. Let X be the set of all vectors x in Rn and define a mapping T : X → X as follows:

T(x) = (b_1 - ∑{i=1,i≠1}^{n}a_1ix_i) / a_11 , (b_2 - ∑{i=1,i≠2}^{n}a_2ix_i) / a_22 , ... , (b_n - ∑_{i=1,i≠n}^{n}a_nix_i) / a_nn .

We will prove that T is a contraction mapping. To do this, we need to show that there exists a constant c >= 0 such that for all x, y in X, we have

||T(x) - T(y)|| ≤ c||x - y|| , where ||.|| is the Euclidean norm.

From the definition of T, we have

T(x) - T(y) = (b_1 - ∑{i=1,i≠1}^{n}a_1ix_i) / a_11 - (b_1 - ∑{i=1,i≠1}^{n}a_1iy_i) / a_11 , (b_2 - ∑{i=1,i≠2}^{n}a_2ix_i) / a_22 - (b_2 - ∑{i=1,i≠2}^{n}a_2iy_i) / a_22 , ... , (b_n - ∑{i=1,i≠n}^{n}a_nix_i) / a_nn - (b_n - ∑{i=1,i≠n}^{n}a_niy_i) / a_nn .

Now, we can use the triangle inequality to get

||T(x) - T(y)|| ≤ ∑{j=1}^{n} |(b_j - ∑{i=1,i≠j}^{n}a_jix_i) / a_jj - (b_j - ∑_{i=1,i≠j}^{n}a_jiy_i) / a_jj| .

Using the definition of T and the fact that A is strictly diagonally dominant, we can further simplify this to

||T(x) - T(y)|| ≤ ∑{j=1}^{n} |a_jj(x_j - y_j)| / |a_jj| ≤ ∑{j=1}^{n} |a_jj||x_j - y_j| / |a_jj| ≤ ∑_{j=1}^{n} |x_j - y_j| = ||x - y|| .

Thus, we have shown that ||T(x) - T(y)|| ≤ ||x - y||, which implies that T is a contraction mapping. Therefore, by the Banach fixed point theorem, the Jacobi iteration method is convergent for any initial x (0).

This completes the proof.