Instantly share code, notes, and snippets.

# man-sean/gs_vs_j.md Secret

Last active March 15, 2023 14:24
Gauss–Seidel v.s. Jacobi under row-column permutation

We want to solve $Ax=b$ using Jacobi method (J) or Gauss–Seidel (GS) method with row-column permutation (i.e., $B=P^TAP$) and without.

We learned that J is guaranteed to converge if A is diagonally-dominant (DD) and GS is guaranteed to converge if $A$ is DD or symmetric and positive-definite (SPD). Please note that J and GS may converge even if $A$ is not DD or SPD (i.e. those are not if-and-only-if statements).

If $A$ is DD than $B$ is DD as the permutation keeps diagonal entries on the diagonal.

If $A$ is SPD that $B$ is SPD as the permutation is a similarity transformation (hence $\text{eig}(A)=\text{eig}(B)$ and $B$ is PD) that also maintain symmetry (hence $B$ is SPD).

The remaining question is what happens if $A$ is not DD or SPD? Let's look at the iteration matrix $T$ of each method.

For Jacobi:

$$A = D_A + L_A + U_A \longrightarrow B = P^T D_A P + P^T (L_A + U_A) P$$

hence:

$$T_A = - D_A^{-1} (L_A + U_A), \quad T_B = - (P^T D_A P)^{-1} (P^T (L_A + U_A) P)$$

The important part here is that even after permutation $(L_A + U_A)$ keeps its general form (zeros on the diagonal). From here we can show that $T_A$ is similar to $T_B$ hence J will converge for $A$ if-and-only-if J will converge for $B$: $$T_B = - (P^T D_A P)^{-1} (P^T (L_A + U_A) P) = P^T (-D_A^{-1}(L_A + U_A)) P = P^T T_A P$$

For Gauss-Seidel:

$$A = D_A + L_A + U_A \longrightarrow B = P^T (D_A + L_A) P + P^T U_A P$$

note that this time we can't say that $P^T (D_A + L_A) P$ keeps its general form (lower-triangular) nor does $P^T U_A P$ (as upper-triangular), hence we can't write $T_B$ using the terms $D_A, L_A, U_A$ as before. In fact, we can construct a counter-example where GS does not converge for $A$ but does for $B$ or vice-versa.