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)

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.

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.

 where:¯
                              

   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;
      }