Diagonally Dominant Matrix (เมทริกซ์ครอบคลุมแนวทแยง) ใน C++

บทนำ

เมทริกซ์ครอบคลุมแนวทแยง (Diagonally Dominant Matrix) คือเมทริกซ์สี่เหลี่ยมจัตุรัสที่ในแต่ละแถว ค่าสัมบูรณ์ขององค์ประกอบแนวทแยง มีค่ามากกว่าหรือเท่ากับผลรวมค่าสัมบูรณ์ขององค์ประกอบอื่นๆ ในแถวเดียวกัน

เงื่อนไข

สำหรับทุกแถว i: |A[i][i]| ≥ Σ|A[i][j]| สำหรับ j ≠ i

ตัวอย่าง

4  2  1
3  5  2
2  4  7

แถว 1: |4| ≥ |2|+|1| = 3 ✓ แถว 2: |5| ≥ |3|+|2| = 5 ✓ แถว 3: |7| ≥ |2|+|4| = 6 ✓

ขั้นตอนการแก้ปัญหา

วนลูปทุกแถว i
คำนวณผลรวมค่าสัมบูรณ์ขององค์ประกอบที่ไม่ใช่แนวทแยง
เปรียบเทียบกับค่าสัมบูรณ์ขององค์ประกอบแนวทแยง
ถ้ามีแถวไหนไม่ผ่าน → ไม่ใช่ Diagonally Dominant

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

#define N 3

bool isDiagonallyDominantMatrix(int matrix[N][N], int n) {
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            if (i != j) {
                sum += abs(matrix[i][j]);
            }
        }
        if (abs(matrix[i][i]) < sum) {
            return false;
        }
    }
    return true;
}

int main() {
    int matrix[N][N] = {{4, 2, 1}, {3, 5, 2}, {2, 4, 7}};
    if (isDiagonallyDominantMatrix(matrix, 3)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

ผลลัพธ์

Yes

ประยุกต์ใช้

เมทริกซ์ประเภทนี้สำคัญในวิธีแก้ระบบสมการเชิงเส้นแบบ Iterative (Gauss-Seidel, Jacobi) ให้收敛 (Converge) ได้รับประกัน

สรุป

การตรวจสอบ Diagonally Dominant ง่ายและรวดเร็ว O(n²) เป็นขั้นตอนสำคัญก่อนใช้ iterative solvers