Gaussian Elimination in C++

การแก้ระบบสมการเชิงเส้น (Linear Equations) เป็นหนึ่งในปัญหาพื้นฐานที่สำคัญในด้านคณิตศาสตร์และวิศวกรรม หนึ่งในวิธีการที่มีชื่อเสียงและเป็นที่นิยมใช้ในการหาคำตอบของระบบสมการนี้คือ วิธีการของ Gaussian Elimination หรือที่รู้จักกันในชื่อว่าการกำจัดแบบกาวส์ (Gaussian Elimination) ในบทความนี้ เราจะพูดถึงว่า Gaussian Elimination คืออะไร, มันใช้ในการแก้ปัญหาอะไร, ตัวอย่างโค้ดในภาษา C++, usecase ในโลกจริง, วิเคราะห์ความซับซ้อน (Complexity) และข้อดีข้อเสียของมัน

# Gaussian Elimination คืออะไร?

Gaussian Elimination เป็นวิธีอัลกอริทึมที่ใช้สำหรับแก้ระบบสมการเชิงเส้นโดยการใช้การดำเนินการแถว (row operations) เพื่อเปลี่ยนระบบสมการให้อยู่ในรูปแบบที่ง่ายต่อการหาคำตอบ ซึ่งปกติจะเป็นไปในสามขั้นตอนหลักๆ ได้แก่:

1. การแทนที่แถว (Row replacement)

2. การสลับแถว (Row swapping)

3. การจัดสเกลแถว (Row scaling)

โดยปกติ Gaussian Elimination จะถูกใช้เพื่อแปลงเมทริกรูปตารางของระบบสมการให้เป็นรูปแบบ Row Echelon Form หรือแม้แต่ Reduced Row Echelon Form ทำให้สามารถหาค่าของตัวแปรได้ด้วยการแทนค่าย้อนกลับ (Back Substitution).

# ตัวอย่างโค้ดใน C++

เพื่อให้เข้าใจการทำงานของ Gaussian Elimination ในภาษา C++ ต่อไปนี้เป็นตัวอย่างของโค้ดที่เรียบเรียงชุดสมการเชิงเส้น:

#include 
#include 

using namespace std;

// Function to perform Gaussian Elimination
vector gaussianElimination(vector> matrix) {
    int n = matrix.size();

    for (int i = 0; i < n; i++) {
        // Search for maximum in this column
        float maxEl = abs(matrix[i][i]);
        int maxRow = i;
        for (int k = i+1; k < n; k++) {
            if (abs(matrix[k][i]) > maxEl) {
                maxEl = abs(matrix[k][i]);
                maxRow = k;
            }
        }

        // Swap maximum row with current row (column by column)
        for (int k = i; k < n+1; k++) {
            float tmp = matrix[maxRow][k];
            matrix[maxRow][k] = matrix[i][k];
            matrix[i][k] = tmp;
        }

        // Make all rows below this one 0 in current column
        for (int k = i+1; k < n; k++) {
            float c = -matrix[k][i]/matrix[i][i];
            for (int j = i; j < n+1; j++) {
                if (i == j) {
                    matrix[k][j] = 0;
                } else {
                    matrix[k][j] += c * matrix[i][j];
                }
            }
        }
    }

    // Solve equation Ax=b for an upper triangular matrix A
    vector x(n);
    for (int i = n-1; i >= 0; i--) {
        x[i] = matrix[i][n]/matrix[i][i];
        for (int k = i-1; k >= 0; k--) {
            matrix[k][n] -= matrix[k][i] * x[i];
        }
    }

    return x;
}

int main() {
    // Example of a system of linear equations
    // 3x + 2y + z = 1
    // 2x + 3y + z = 2
    // x + 2y + 3z = 3
    vector> system = {
        {3, 2, 1, 1},
        {2, 3, 1, 2},
        {1, 2, 3, 3}
    };

    vector solution = gaussianElimination(system);

    // Display the solution
    for (int i = 0; i < solution.size(); i++) {
        cout << "Variable x" << i << " = " << solution[i] << endl;
    }

    return 0;
}

โปรดทราบว่าในโค้ดนี้ สมการถูกนำเข้ามาในรูปของเมทริกซ์ที่มีขนาด n x (n+1) เพื่อให้สามารถจัดการได้ง่าย และใช้การหาค่าสูงสุดในคอลัมน์เพื่อทำการสลับแถว ซึ่งจะช่วยลดปัญหาข้อผิดพลาดทางตัวเลข (Numerical error) ในการคำนวณ.

# Usecase ในโลกจริง

Gaussian Elimination มีการใช้งานอย่างกว้างขวางในด้านต่างๆ เช่น วิศวกรรมไฟฟ้าในการวิเคราะห์วงจร, ในปัญหาการไหลของของไหล (Fluid dynamics), การวางแผนทรัพยากรในโครงการ (Project resource planning), และในการจัดสรรงบประมาณ. อัลกอริธึมนี้ยังมีความสำคัญในด้านการเงิน เช่น การแก้ปัญหาการปรับ Striking prices ในตัวเลือกหุ้น (Stock options).

# ความซับซ้อน (Complexity)

ความซับซ้อนของ Gaussian Elimination ในการเปลี่ยนแปลงเมทริกซ์ไปยัง Row Echelon Form นั้นเป็นที่ O(n³) เนื่องจากต้องทำการทำงานซ้ำๆ ทั้งในแถวและคอลัมน์และต้องประมวลผลชุดของการดำเนินการกับทุก ๆ แถวที่อยู่ด้านล่างของปัจจุบัน. อย่างไรก็ตามการแก้ปัญหาสมการเชิงเส้นแบบใหญ่ๆ อาจต้องอาศัยการปรับปรุงเทคนิคพิเศษเช่นการใช้การคำนวณแบบขนาน (Parallel computing).

# ข้อดีข้อเสีย

ข้อดี:

- เป็นอัลกอริธึมพื้นฐานที่อธิบายชัดเจนและเข้าใจง่าย

- สามารถปรับปรุงได้ด้วยการใช้ Pivot ที่ถูกต้องเพื่อลดความผิดพลาดทางตัวเลข

- มีการใช้งานอย่างแพร่หลายในซอฟต์แวร์ด้านคณิตศาสตร์และวิศวกรรม

ข้อเสีย:

- ไม่เหมาะสำหรับหมู่เมทริกซ์ขนาดใหญ่ เนื่องจากมีความซับซ้อนที่สูง

- อาจมีปัญหาเมื่อพบกับเมทริกซ์ที่เกือบจะเป็น Singular หรือ Degenerate ทำให้เกิดผิดพลาดทางตัวเลขได้

- อาจมีปัญหาในการเลือก Pivot ที่ไม่เหมาะสม ซึ่งอาจนำไปสู่ผลลัพธ์ที่ไม่แม่นยำ

การศึกษาวิธีการของ Gaussian Elimination เป็นสิ่งสำคัญในการเพิ่มความเข้าใจพื้นฐานของการแก้ปัญหาทางคณิตศาสตร์และการประยุกต์ใช้ในวิศวกรรมและวิทยาศาสตร์. นักเรียนที่สนใจในการโปรแกรมเพื่อการจัดการกับข้อมูลเชิงคณิตศาสตร์ย่อมต้องมารู้จักกับมัน และที่ Expert-Programming-Tutor (EPT) พวกเราพร้อมที่จะนำทางเพื่อการเรียนรู้และพัฒนาทักษะที่จำเป็นในการก้าวเข้าสู่โลกแห่งการวิเคราะห์ข้อมูลที่หลากหลายอีกด้วย.

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง