PROJECT

Question 1. The following are well-known methods of solving a system of linear equations:
·        Gaussian Elimination Method
·        Gauss-Seidel Iterative Method
(a)     Describe each of the above methods, with some suitable examples.    (3 Marks)

Gaussian Elimination

The simplest method for solving a linear system is Gaussian elimination, which uses three types of elementary row operations:

• Multiplying a row by a non-zero constant (kE_ij)
• Adding a multiple of one row to another ( E_ij + kE_kj)
• Exchanging two rows ( E_ij <--> kE_kj)

Each row operation corresponds to a step in the solution of the system of equations  where the equations are combined together. It is important to note that none of those operations changes the solution. There are two parts to this method: elimination and back-substitution. The purpose of the process of elimination is to eliminate the matrix entries below the main diagonal, using row operations, to obtain a upper triangular matrix with the augmented column. Then, you will be able to proceed with back-substitution to find the values of the unknowns.

The Gauss-Seidel Method

We are considering an iterative solution to the linear system

 

where is an sparse matrix, x and b are vectors of length n, and we are solving for x. Iterative solvers are an alternative to direct methods that attempt to calculate an exact solution to the system of equations. Iterative methods attempt to find a solution to the system of linear equations by repeatedly solving the linear system using approximations to the vector. Iterations continue until the solution is within a predetermined acceptable bound on the error.

Common iterative methods for general matrices include the Gauss-Jacobi and Gauss-Seidel, while conjugate gradient methods exist for positive definite matrices. Critical in the choice and use of iterative methods is the convergence of the technique. Gauss-Jacobi uses all values from the previous iteration, while Gauss-Seidel requires that the most recent values be used in calculations. The Gauss-Seidel method generally has better convergence than the Gauss-Jacobi method, although for dense matrices, the Gauss-Seidel method is inherently sequential. Better convergence means fewer iterations, and a faster overall algorithm, as long as the strict precedence rules can be observed. The convergence of the iterative method must be examined for the application along with algorithm performance to ensure that a useful solution to can be found.

The Gauss-Seidel method can be written as:

where:¯

is the unknown in during the iteration, and ,

is the initial guess for the unknown in ,

is the coefficient of in the row and column,

is the value in .

or

 

 where:¯

is the iterative solution to , ,

is the initial guess at ,

is the diagonal of ,

is the of strictly lower triangular portion of ,

is the of strictly upper triangular portion of ,

is right-hand-side vector.

The representation in equation 2 is used in the development of the parallel algorithm, while the equivalent matrix-based representation in equation 3 is used below in discussions of available parallelism.

This Gauss-Seidel method has better convergence.

As C programs the basic structure might be something like

   int i;
      const int N = ??;  //incomplete code
      double x[N], b[N];
      while ( ... ) //incomplete code
      {
         for ( i = 0; i < N; i++ )
            x[i] = (b[i] - x[i-1] - x[i+1]) * 0.5;
      }