The Jacobi method is an iterative algorithm used to find solutions for a system of linear equations. Let’s break it down:
Problem Setup:
Consider a square system of n linear equations represented as Ax = b, where:
A is the coefficient matrix.
x is the vector of unknowns (our solution).
b is the right-hand side vector.
We want to approximate the solution vector x.
Algorithm Overview:
The Jacobi method iteratively refines the solution by updating each component of x based on the current approximation.
It assumes that the system is strictly diagonally dominant (meaning the absolute value of the diagonal element is greater than the sum of absolute values of other terms in the same row).
Matrix Decomposition:
Decompose matrix A into three components:
D: Diagonal component (contains the diagonal elements of A).
L: Lower triangular part (contains the strictly lower triangular elements of A).
U: Upper triangular part (contains the strictly upper triangular elements of A).
We have: A = D + L + U.
Iteration Process:
Initialize an initial guess vector x(0) (often set to zeros or some other reasonable guess).
For each iteration k:
Update each component of x using the following formula:
xi(k+1) = (bi - σ) / aii
where σ is the sum of products of off-diagonal elements and their corresponding components of x.
Repeat until convergence (when the solution stabilizes).
Convergence:
The standard convergence condition is that the spectral radius of the iteration matrix (formed by dividing D by A) is less than 1.
Strict row diagonal dominance ensures convergence, but the Jacobi method may still converge even if this condition isn’t strictly satisfied.
Note that it does not converge for every symmetric positive-definite matrix.
Jacobi method
The Jacobi method is probably the simplest iterative method for solving a (square) linear system Ax=b.
To help with the understanding of the method, let's look at a small 3x3 example.
Nothing that there are no zeros ion the leading diagonal, we can solve for the first row for x, the second row for y and the third row for z, as follows.
In the absence of better information, we can begin with x0=y0=z0=0, as our initial guess.
Feeding these values into the above guess, your get your next set of approimtion, x1, y1, z1.
You repeat the process and with each iteration, xn, yn, zn, will get closer to the actual solution.
This can be rearranged as
The set of equations above can be rearranged as
which can be erxpressed in matrix form as
Thus in general, Jacobi method involves iteration of the form:
where D is a 3 × 3 matrix containing the diagonal part of A, and L and U are 3 × 3 matrices containing the (strictly) lower and (strictly) upper triangular parts of A. (Note that the L and U matrices here have nothing to do with those in the factorization A = LU.)
Premultiplying by D−1 gives:
function jacobiMethod(A, b, x0, maxIterations, tolerance) {
const n = A.length;
const x = [...x0]; // Initialize the solution vector
for (let iteration = 0; iteration < maxIterations; iteration++) {
const xNew = new Array(n).fill(0); // Initialize the updated solution vector
for (let i = 0; i < n; i++) {
let sum = 0;
for (let j = 0; j < n; j++) {
if (i !== j) {
sum += A[i][j] * x[j];
}
}
xNew[i] = (b[i] - sum) / A[i][i];
}
// Check for convergence
let error = 0;
for (let i = 0; i < n; i++) {
error += Math.abs(xNew[i] - x[i]);
}
if (error < tolerance) {
return xNew; // Converged
}
x.splice(0, n, ...xNew); // Update the solution vector
}
return x; // Return the approximate solution
}
// Example usage:
const A = [
[4, 1, -1],
[3, 5, 2],
[1, 1, 3]
];
const b = [7, 8, 5];
const initialGuess = [0, 0, 0];
const maxIterations = 1000;
const tolerance = 1e-6;
const solution = jacobiMethod(A, b, initialGuess, maxIterations, tolerance);
console.log("Approximate solution:", solution);And code to check if diagonally dominant
diagonally dominant matrix in JavaScript, we’ll follow these steps:
Given a square matrix A of size n x n, we want to check if it’s diagonally dominant.
A matrix is diagonally dominant if, for every row, the magnitude of the diagonal entry is larger than or equal to the sum of the magnitudes of all other (non-diagonal) entries in that row.
Specifically, the matrix A is diagonally dominant if:
For each row i, the following condition holds
function isDiagonallyDominant(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
for (let i = 0; i < rows; i++) {
let sum = 0;
for (let j = 0; j < cols; j++) {
if (i !== j) {
sum += Math.abs(matrix[i][j]);
}
}
if (Math.abs(matrix[i][i]) < sum) {
return false;
}
}
return true;
}
Comments