對角佔優矩陣的 JavaScript 程式
- WBOY轉載
- 2023-08-27 13:53:13657瀏覽
矩陣是電腦科學和數學中的重要工具，可用於快速逼近困難的計算。矩陣是按行和列組織的數字的集合，可以表示數據或數學問題。
透過本文，我們將了解對角顯性矩陣。我們將研究對角佔優矩陣的概念、演算法和範例，以及它們在各種程式語言中的實作。
對角佔優矩陣
如果對於矩陣中的每一行，行中對角項的大小大於或等於所有非對角項的大小總和，我們可以稱方矩陣為對角佔優。簡單來說，如果矩陣中除對角元素以外的元素總和小於對角矩陣。
如果我們有一個包含 i 行和 j 列的方陣 a，我們可以使用數學方程式將其表示為對角佔優矩陣 -
$$\mathrm{|\:a_{ii}\:|\:\geq\:\displaystyle\sum\limits_{jeq\:i}\:|\:a_{ij} |} $$ 為我所有 其中 aij 表示第 i 列和第 j 列中的條目
範例
A = [ [6, -2, 0, 0], [2, 8, -3, 0], [1, 2, 9, -4], [0, 1, -2, 7] ]
此矩陣是對角佔優的，因為它滿足以下條件 -
|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|
問題陳述
給定一個方陣，寫一個 JavaScript 程式來檢查該矩陣是否對角佔優。
範例
讓我們考慮一個 3x3 矩陣 -
| 4 -1 0 | | -1 4 -1| | 0 -1 4 |
這裡，每一行的對角線元素分別為4、4和4，它們都大於該行其他元素的絕對值總和。因此，此矩陣是對角佔優的。
現在讓我們來看看解決上述問題的方法。
方法一：暴力破解
暴力法包括迭代矩陣的每一行並確定對角元素是否大於該行中其他元素的絕對值總和。
演算法
迭代矩陣的行。
計算每行中其他分量的絕對值總和。
檢查該行的對角線元素是否大於或等於步驟 2 中確定的總和。
如果對角線元素大於或等於總和，則繼續迭代到下一行。
如果對角線元素小於總和，則傳回 false，表示矩陣不是對角佔優的。
範例
<!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>
時間複雜度：O(n2)，其中 n 是矩陣的大小。
方法二：排序
在此方法中，我們按降序對每行的絕對值進行排序。然後我們確定該行的對角線元素是否大於或等於最大的 n-1 個絕對值總和，其中 n 是矩陣的大小。
演算法
迭代矩陣的行。
依降序對行項目的絕對值進行排序。
增加最大的 n-1 個絕對值，其中 n 是矩陣的大小。
檢查該行的對角線元素是否大於或等於步驟 3 中確定的總和。
如果對角線元素大於或等於總和，則繼續迭代到下一行。
如果對角線元素小於總和，則傳回 false，表示矩陣不是對角佔優的。
範例
<!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>
時間複雜度：O(n2 log n)，其中 n 是矩陣的大小。
方法3：行縮放
在此方法中，我們首先縮放矩陣的每一行，使其對角線元素等於 1。然後我們查看該行中其他條目的絕對值是否小於 1。
演算法
迭代矩陣的行。
識別具有最高絕對值的行。
縮放行直到對角線元素等於 1。
檢查該行中剩餘條目的絕對值是否小於 1。
如果所有行都符合步驟 4 中的標準，則傳回 true，表示矩陣對角佔優。
如果任意行不符合步驟4的要求，則傳回false，表示該矩陣不是對角佔優的。
範例
<!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>