Direct and Indirect Methods: Gauss and Jacobi

Direct Methods

1a) Gauss Elimination Method

The Gauss Elimination method consists of converting a matrix into an equivalent matrix with zeros below the main diagonal of A. The first equation will have n variables, the second n-1, and so on until the final equation, which will have only one variable. Once the zeros are achieved, the values of the variables are found by starting with the last variable and substituting back up to the first. This solves the system.

1b) Gauss-Jordan Method

The Gauss-Jordan method consists of obtaining a diagonal matrix instead of just an upper triangular matrix. Variables are obtained directly from the resulting system, without substitutions. This saving in the final step comes at the cost of slightly increasing the complexity of the algorithm in the intermediate step, as we also create zeros for the elements above the main diagonal.

Indirect Methods

2a) Jacobi Method

The Jacobi method involves converting the original system into another, similar to the Gauss formula. Since we don't have the exact solution, we assume initial values. We obtain a set of values from these initial values, repeatedly applying the formulas until a maximum number of iterations is reached, or until the value obtained in one step is equal (except for a very small epsilon) to the value obtained in the preceding step.

The codification of a procedure using this method, SOLUTION(A, n, X), starts with an arbitrary initial vector, e.g., X = [0, 0, 0, ..., 0]. At each step "k", a new vector X is obtained, which is a closer approximation to the accurate solution.

It can be shown that the method converges if the matrix is diagonally dominant; that is, for all rows, the element on the main diagonal is, in absolute value, greater than the sum of the absolute values of the other elements in that row. This is understandable because, if this condition is met, the sum term in the formula is small compared to the independent term, making the independent term dominant in the iterations.

2b) Gauss-Seidel Method

In the Jacobi method, each vector of the sequence is calculated simultaneously. A possible acceleration of convergence is to use the newly calculated values of x in the calculation of the following component before finishing the iteration. Instead of using all values of X₀ in the first iteration, we use them for the first component and then use the updated value in the following calculation of the current iteration. The same is done with the rest of the components.

This method converges if and only if the Jacobi method converges. The two methods discussed are applicable when dealing with matrices of considerable dimensions or those with many zeros (e.g., diagonal matrices by boxes with a very large "n").