Linear Equations: Gauss-Seidel

The Gauss-Seidel method is an iterative technique used to solve a system of linear equations. Here’s how it works:

1. System of Equations: Consider a system of n linear equations represented as Ax = b, where:

   1. A is an n × n matrix of coefficients.

   2. x is a vector containing the unknowns we want to solve for.

   3. b is a vector of constants on the right-hand side.

2. Basic Idea: The Gauss-Seidel method solves the equations one at a time, updating the values of x sequentially. It uses previously computed results as soon as they are available.

3. Iteration Process:

   1. Start with an initial guess for the solution vector x (often set to zeros or some other reasonable estimate).

   2. For each equation i from 1 to n, compute the updated value of x_i using the following formula:
      

1. 
   

   1. Repeat the process until the solution converges (i.e., the change in x becomes sufficiently small).

2. Advantages:

   1. Unlike the Jacobi method, the Gauss-Seidel method uses updated values of x immediately, which can lead to faster convergence.

   2. It works well for diagonally dominant matrices.

3. Pitfalls:

   1. Convergence is not guaranteed for all matrices.

   2. The method may diverge if the matrix A is not diagonally dominant.

   3. The order of equation updates matters; changing the order can affect convergence.

Gauss Seidel method

Each iteration of the Gauss-Seidel method, takes the form

Note how we have n+1 terms on the right hand side, and compare against the Jacobi method. In comparison to the Jacobi method, the Gauss-Seidel method implements the strategy of always using the latest available value of a particular variable,

This can be rearranged as

or in matrix form

Thus, in general, the Gauss-Seidel method involves iterations of the form

where D, L and U are as defined above. Pre-multiplying by D^−1 gives

Splitting Method

The Gauss-Seidel and the Jacobi methods can both be derived more quickly.

We split the lead matrix A into a strictly upper triangular matrix U, a strictly lower triangular matrix L, and a diagonal matrix D

In this method, the LCP or MLCP is reduced to a system of linear equations by removing the conditions on x and setting the slack variables to zero, i.e. w = 0,

The system Ax=b then becomes

If we subtract (L+U)x from both sides

Dx = (L+U)x + b

=>

which is the Jacobi method.

If we subtract Ux from both sides we get:

(D+L)x = -Ux + b

=>

which is the Gauss-Seidel method

Since the expression has been derived from splitting the A matrix, the methods are sometimes described as being based on matrix splitting.

function seidel(a, x ,b) {

var n = a.length;

// calculate x, y , z

for (let j=0; j<n; j++) {

// temp variable d to store b[j]

var d = b[j]

// to calculate respective xi, yi, zi

for (let i=0; i< n; i++) {

if (j != i) d-=a[j][i] * x[i]

// updating the value of our solution

}

x[j] = d / a[j][j]

}

// returning our updated solution

return x

}

// int(input())input as number of variable to be solved

var n = 3

var a = []

var b = []

// initial solution depending on n(here n=3)

a = [[4, 1, 2],[3, 5, 1],[1, 1, 3]]

x = [0, 0, 0];

b = [4,7,3]

console.log(x)

// run for m times depending on m the error value

for (let i=0; i<25; i++) {

x = seidel(a, x, b);

//print each time the updated solution

console.log(x)

}

https://www.youtube.com/watch?v=eJmm04MCGFw