Programme JavaScript pour les matrices diagonalement dominantes
Les matrices sont un outil important en informatique et en mathématiques et peuvent être utilisées pour approximer rapidement des calculs difficiles. Une matrice est une collection de nombres organisés en lignes et en colonnes pouvant représenter des données ou un problème mathématique.
À travers cet article, nous découvrirons la matrice diagonale dominante. Nous étudierons les concepts, les algorithmes et les exemples de matrices diagonalement dominantes, ainsi que leur implémentation dans divers langages de programmation.
Matrice diagonalement dominante
Si pour chaque ligne de la matrice, la taille de l'entrée diagonale dans la ligne est supérieure ou égale à la somme des tailles de toutes les entrées non diagonales, nous pouvons appeler une matrice carrée diagonalement dominante. En termes simples, si la somme des éléments de la matrice, à l'exception des éléments diagonaux, est inférieure à la matrice diagonale.
Si nous avons une matrice carrée a contenant i lignes et j colonnes, nous pouvons utiliser des équations mathématiques pour la représenter comme une matrice diagonalement dominante -
$$mathrm{|:a_{ii}:|:geq:displaystylesumlimits_{jeq:i}:|:a_{ij} |}$$ m'appartenant où aij représente les entrées dans les colonnes i et j
Exemple
A = [ [6, -2, 0, 0], [2, 8, -3, 0], [1, 2, 9, -4], [0, 1, -2, 7] ]
Cette matrice est diagonalement dominante car elle satisfait aux conditions suivantes -
|a11| ≥ |a12| + |a13| + |a14| == |+6| ≥ |+2| + |+1| + |+0| |a22| ≥ |a21| + |a23| + |a24| == |+8| ≥ |+2| + |+3| + |+0| |a33| ≥ |a31| + |a32| + |a34| == |+9| ≥ |+1| + |+2| + |+4| |a44| ≥ |a41| + |a42| + |a43| == |+7| ≥ |+0| + |+1| + |+2|
Énoncé du problème
Étant donné une matrice carrée, écrivez un programme JavaScript pour vérifier si la matrice est diagonalement dominante.
Exemple
Considérons une matrice 3x3 -
| 4 -1 0 | | -1 4 -1| | 0 -1 4 |
Ici, les éléments diagonaux de chaque ligne sont respectivement 4, 4 et 4, et ils sont tous supérieurs à la somme des valeurs absolues des autres éléments de la ligne. Par conséquent, cette matrice est diagonalement dominante.
Voyons maintenant les solutions aux problèmes ci-dessus.
Méthode 1 : Fissuration par force brute
La méthode de la force brute consiste à parcourir chaque ligne de la matrice et à déterminer si l'élément diagonal est supérieur à la somme des valeurs absolues des autres éléments de la ligne.
Algorithme
Parcourez les lignes d'une matrice.
Calculez la somme des valeurs absolues des autres composants de chaque ligne.
Vérifiez si les éléments diagonaux de la rangée sont supérieurs ou égaux à la somme déterminée à l'étape 2.
Si l'élément diagonal est supérieur ou égal à la somme, continuez à itérer jusqu'à la ligne suivante.
Si les éléments diagonaux sont inférieurs à la somme, renvoie false, indiquant que la matrice n'est pas diagonalement dominante.
Exemple
<!DOCTYPE html>
<html>
<body>
<div id="matrix"></div>
<div id="output"></div>
<script>
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;
}
const matrix = [[4, -1, 0], [-1, 4, -1], [0, -1, 4]];
const output = isDiagonallyDominant(matrix) ? 'Matrix is diagonally dominant.' : 'Matrix is not diagonally dominant.';
document.getElementById('matrix').innerHTML = 'Matrix: ' + JSON.stringify(matrix);
document.getElementById('output').innerHTML = 'Output: ' + output;
</script>
</body>
</html>
Complexité temporelle : O(n2), où n est la taille de la matrice.
Méthode 2 : Tri
Dans cette méthode, nous trions la valeur absolue de chaque ligne par ordre décroissant. Nous déterminons ensuite si les éléments diagonaux de la ligne sont supérieurs ou égaux à la plus grande somme de n-1 valeurs absolues, où n est la taille de la matrice.
Algorithme
Parcourez les lignes d'une matrice.
Trier les éléments de campagne par valeur absolue par ordre décroissant.
Ajoutez les plus grandes valeurs absolues n-1, où n est la taille de la matrice.
Vérifiez si les éléments diagonaux de la rangée sont supérieurs ou égaux à la somme déterminée à l'étape 3.
Si l'élément diagonal est supérieur ou égal à la somme, continuez à itérer jusqu'à la ligne suivante.
Si les éléments diagonaux sont inférieurs à la somme, renvoie false, indiquant que la matrice n'est pas diagonalement dominante.
Exemple
<!DOCTYPE html>
<html>
<body>
<h2>Diagonally Dominant Matrix</h2>
<p id="matrix"></p>
<p id="output"></p>
<script>
function isDiagonallyDominant(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
for(let i = 0; i < rows; i++) {
const sortedRow = matrix[i].map(Math.abs).sort((a, b) => b - a);
const sum = sortedRow.slice(1, cols).reduce((acc, val) => acc + val, 0);
if(sortedRow[0] < sum) {
return false;
}
}
return true;
}
// Example matrix
const matrix = [[4, -1, 0], [-1, 4, -1], [0, -1, 4]];
// Display input matrix
const matrixElement = document.getElementById("matrix");
matrixElement.innerHTML = "Input Matrix: <br>" + JSON.stringify(matrix);
// Check if the matrix is diagonally dominant
const isDominant = isDiagonallyDominant(matrix);
// Display output
const outputElement = document.getElementById("output");
outputElement.innerHTML = "Is diagonally dominant: " + isDominant;
</script>
</body>
</html>
Complexité temporelle : O(n2 log n), où n est la taille de la matrice.
Méthode 3 : mise à l'échelle des lignes
Dans cette méthode, nous mettons d'abord à l'échelle chaque ligne de la matrice afin que ses éléments diagonaux soient égaux à 1. On voit alors si la valeur absolue des autres entrées de la ligne est inférieure à 1.
Algorithme
Parcourez les lignes d'une matrice.
Identifiez la ligne avec la valeur absolue la plus élevée.
Redimensionnez les lignes jusqu'à ce que les éléments diagonaux soient égaux à 1.
Vérifiez si la valeur absolue des entrées restantes dans la ligne est inférieure à 1.
Renvoie vrai si toutes les lignes répondent aux critères de l'étape 4, indiquant que la matrice est diagonalement dominante.
Si une ligne ne répond pas aux exigences de l'étape 4, renvoyez false, indiquant que la matrice n'est pas diagonalement dominante.
Exemple
<!DOCTYPE html> <html> <body> <h3>Diagonally Dominant Matrix</h3> <p>Matrix:</p> <pre id="matrix">
Is diagonally dominant:
<script> function isDiagonallyDominant(matrix) { const rows = matrix.length; const cols = matrix[0].length; for(let i = 0; i < rows; i++) { const maxAbsVal = Math.max(...matrix[i].map(Math.abs)); if(maxAbsVal === 0) { return false; } const scale = 1 / maxAbsVal; for(let j = 0; j < cols; j++) { matrix[i][j] *= scale; } const sum = matrix[i].slice(0, i).reduce((acc, val) => acc + Math.abs(val), 0) + matrix[i].slice(i+1, cols).reduce((acc, val) => acc + Math.abs(val), 0); if(sum >= 1) { return false; } } return true; } const matrix = [[4, -1, 0], [-1, 4, -1], [0, -1, 4]]; document.getElementById('matrix').innerHTML = matrix.map(row => row.join(' ')).join(''); document.getElementById('output').innerHTML = isDiagonallyDominant(matrix) ? 'true' : 'false'; </script>