JavaScript-Programm für diagonal dominante Matrizen
Matrizen sind ein wichtiges Hilfsmittel in der Informatik und Mathematik und können zur schnellen Approximation schwieriger Berechnungen eingesetzt werden. Eine Matrix ist eine in Zeilen und Spalten organisierte Sammlung von Zahlen, die Daten oder ein mathematisches Problem darstellen können.
In diesem Artikel erfahren wir etwas über die diagonal dominante Matrix. Wir werden die Konzepte, Algorithmen und Beispiele diagonal dominanter Matrizen sowie deren Implementierung in verschiedenen Programmiersprachen untersuchen.
Diagonal dominante Matrix
Wenn für jede Zeile in der Matrix die Größe des diagonalen Eintrags in der Zeile größer oder gleich der Summe der Größen aller nicht diagonalen Einträge ist, können wir eine quadratische Matrix als diagonal dominant bezeichnen. Einfach ausgedrückt, wenn die Summe der Elemente in der Matrix mit Ausnahme der Diagonalelemente kleiner als die Diagonalmatrix ist.
Wenn wir eine quadratische Matrix a haben, die i Zeilen und j Spalten enthält, können wir mathematische Gleichungen verwenden, um sie als diagonal dominante Matrix darzustellen -
$$mathrm{|:a_{ii}:|:geq:displaystylesumlimits_{jeq:i}:|:a_{ij} |}$$ im Besitz von mir wobei aij die Einträge in den Spalten i und j darstellt
Beispiel
A = [ [6, -2, 0, 0], [2, 8, -3, 0], [1, 2, 9, -4], [0, 1, -2, 7] ]
Diese Matrix ist diagonal dominant, weil sie die folgenden Bedingungen erfüllt -
|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|
Problemstellung
Schreiben Sie bei einer gegebenen quadratischen Matrix ein JavaScript-Programm, um zu prüfen, ob die Matrix diagonal dominant ist.
Beispiel
Betrachten wir eine 3x3-Matrix -
| 4 -1 0 | | -1 4 -1| | 0 -1 4 |
Hier sind die Diagonalelemente jeder Zeile 4, 4 bzw. 4 und sie sind alle größer als die Summe der Absolutwerte der anderen Elemente in der Zeile. Daher ist diese Matrix diagonal dominant.
Sehen wir uns nun die Lösungen für die oben genannten Probleme an.
Methode 1: Brute-Force-Cracking
Bei der Brute-Force-Methode wird jede Zeile der Matrix durchlaufen und ermittelt, ob das Diagonalelement größer als die Summe der Absolutwerte der anderen Elemente in der Zeile ist.
Algorithmus
Iterieren Sie über die Zeilen einer Matrix.
Berechnen Sie die Summe der Absolutwerte der anderen Komponenten in jeder Zeile.
Überprüfen Sie, ob die Diagonalelemente der Reihe größer oder gleich der in Schritt 2 ermittelten Summe sind.
Wenn das Diagonalelement größer oder gleich der Summe ist, fahren Sie mit der Iteration zur nächsten Zeile fort.
Wenn die Diagonalelemente kleiner als die Summe sind, wird false zurückgegeben, was darauf hinweist, dass die Matrix nicht diagonal dominant ist.
Beispiel
<!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>
Zeitliche Komplexität: O(n2), wobei n die Größe der Matrix ist.
Methode 2: Sortieren
Bei dieser Methode sortieren wir den absoluten Wert jeder Zeile in absteigender Reihenfolge. Anschließend bestimmen wir, ob die Diagonalelemente der Zeile größer oder gleich der größten Summe von n-1 Absolutwerten sind, wobei n die Größe der Matrix ist.
Algorithmus
Iterieren Sie über die Zeilen einer Matrix.
Sortieren Sie die Werbebuchungen nach absolutem Wert in absteigender Reihenfolge.
Fügen Sie die größten n-1 absoluten Werte hinzu, wobei n die Größe der Matrix ist.
Überprüfen Sie, ob die Diagonalelemente der Reihe größer oder gleich der in Schritt 3 ermittelten Summe sind.
Wenn das Diagonalelement größer oder gleich der Summe ist, fahren Sie mit der Iteration zur nächsten Zeile fort.
Wenn die Diagonalelemente kleiner als die Summe sind, wird false zurückgegeben, was darauf hinweist, dass die Matrix nicht diagonal dominant ist.
Beispiel
<!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>
Zeitkomplexität: O(n2 log n), wobei n die Größe der Matrix ist.
Methode 3: Zeilenskalierung
Bei dieser Methode skalieren wir zunächst jede Zeile der Matrix so, dass ihre Diagonalelemente gleich 1 sind. Wir prüfen dann, ob der Absolutwert der anderen Einträge in der Zeile kleiner als 1 ist.
Algorithmus
Iterieren Sie über die Zeilen einer Matrix.
Identifizieren Sie die Zeile mit dem höchsten absoluten Wert.
Zeilen skalieren, bis die Diagonalelemente gleich 1 sind.
Überprüfen Sie, ob der absolute Wert der verbleibenden Einträge in der Zeile kleiner als 1 ist.
Gibt „true“ zurück, wenn alle Zeilen die Kriterien in Schritt 4 erfüllen, was darauf hinweist, dass die Matrix diagonal dominant ist.
Wenn eine Zeile die Anforderungen von Schritt 4 nicht erfüllt, geben Sie false zurück, was darauf hinweist, dass die Matrix nicht diagonal dominant ist.
Beispiel
<!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>