As a result, if B Jacobi and B GS are the iteration matrices of the 2 x 2 Jacobi and Gauss-Seidel Methods, respectively, then || B GS|| = || B Jacobi|| 2.įor example, if || B Jacobi|| = 0.5, then || B GS|| = (0.5) 2 = 0.25. Also notice that the magnitude of the non-zero eigenvalue for the Gauss-Seidel Method is the square of either of the two eigenvalues for the Jacobi Method. The eigenvalues and corresponding eigenvectors for the Jacobi and Gauss-Seidel Methods are shown in the following table. Consequently, a major goal in designing an iterative method is that the corresponding iteration matrix B has eigenvalues that are as small (close to 0) as possible. The magnitude of || B|| is directly related to the magnitude of the eigenvalues of B. That is, the rate of convergence would be 0.5. When the methods do work, how quickly will the approximations approach the true solution? That is, what will the rate of convergence be?Īnswer: The rate will be the same as the rate at which || B|| k converges to 0.įor example, if || B|| = 0.5, then size of the error e ( k) = x − x ( k) would be cut approximately in half by each additional iteration. When will each of these methods work? That is, under what conditions will they produce a sequence of approximations x (0), x (1), x (2), … that converges to the true solution x ?Īnswer: When the eigenvalues of the corresponding iteration matrix are both less than 1 in magnitude.īecause || e ( k) || ≤ || B|| k || e 0||, the second question is also answered.

We have now answered the first question posed on the preceding page, at least for 2 x 2 systems: More general cases for larger systems are discussed in more detail in any good numerical analysis or numerical linear algebra text. For n x n systems, things are more complicated. This includes cases in which B has complex eigenvalues.

The 2 x 2 Jacobi and Gauss-Seidel iteration matrices always have two distinct eigenvectors, so each method is guaranteed to converge if all of the eigenvalues of B corresponding to that method are of magnitude < 1. It turns out that, if an n x n iteration matrix B has a full set of n distinct eigenvectors, then || B|| = | λ max|, where λ max is the eigenvalue of B of greatest magnitude.

Notice that for both methods the diagonal elements of A must be non-zero: a 11 ≠ 0 and a 22 ≠ 0. As we noted on the preceding page, the Jacobi and Gauss-Seidel Methods are both of the form We continue our analysis with only the 2 x 2 case, since the Java applet to be used for the exercises deals only with this case.

Gauss seidel sor python