top of page
Search
cedarcantab

Linear Equations: Gauss-Seidel

Updated: Apr 8



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. Repeat the process until the solution converges (i.e., the change in x becomes sufficiently small).

  1. 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.

  2. 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)

}





7 views0 comments

Recent Posts

See All

p2 naive broadphase

var Broadphase = require('../collision/Broadphase'); module.exports = NaiveBroadphase; /** * Naive broadphase implementation. Does N^2...

sopiro motor constranit

import { Matrix2, Vector2 } from "./math.js"; import { RigidBody } from "./rigidbody.js"; import { Settings } from "./settings.js";...

コメント


記事: Blog2_Post
bottom of page