对角占优矩阵的 JavaScript 程序

javascriptjavascript 2023-08-28 05:11:59 1186
摘要： 矩阵是计算机科学和数学中的重要工具，可用于快速逼近困难的计算。矩阵是按行和列组织的数字的集合，可以表示数据或数学问题。通过本文，我们将了解对角显性矩阵。我们将研究对角占优矩阵的概念、算法和示例，以及它们在各...

对角占优矩阵的 JavaScript 程序

矩阵是计算机科学和数学中的重要工具，可用于快速逼近困难的计算。矩阵是按行和列组织的数字的集合，可以表示数据或数学问题。

通过本文，我们将了解对角显性矩阵。我们将研究对角占优矩阵的概念、算法和示例，以及它们在各种编程语言中的实现。

对角占优矩阵

如果对于矩阵中的每一行，行中对角项的大小大于或等于所有非对角项的大小之和，我们可以称方矩阵为对角占优。简单来说，如果矩阵中除对角元素以外的元素之和小于对角矩阵。

如果我们有一个包含 i 行和 j 列的方阵 a，我们可以使用数学方程将其表示为对角占优矩阵 -

$$\mathrm{|\:a_{ii}\:|\:\geq\:\displaystyle\sum\limits_{j

eq\: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"></pre>
   <p>Is diagonally dominant: <span id="output"></span></p>
   <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>
</body>
</html>

时间复杂度：O(n3)，其中 n 是矩阵的大小。

结论

在这篇博客中，我们讨论了一个通过各种方法来查找矩阵是否对角占优的程序。其中一些使用循环、排序和行缩放方法。希望您发现此信息有用。

标签：