The Gauss-Seidel method is an iterative technique used to solve a system of linear equations. Here’s how it works:
System of Equations: Consider a system of n linear equations represented as Ax = b, where:
A is an n × n matrix of coefficients.
x is a vector containing the unknowns we want to solve for.
b is a vector of constants on the right-hand side.
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.
Iteration Process:
Start with an initial guess for the solution vector x (often set to zeros or some other reasonable estimate).
For each equation i from 1 to n, compute the updated value of x_i using the following formula:
Repeat the process until the solution converges (i.e., the change in x becomes sufficiently small).
Advantages:
Unlike the Jacobi method, the Gauss-Seidel method uses updated values of x immediately, which can lead to faster convergence.
It works well for diagonally dominant matrices.
Pitfalls:
Convergence is not guaranteed for all matrices.
The method may diverge if the matrix A is not diagonally dominant.
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)
}
コメント