가우스 소거법 with C++

가우스 소거법이란, 연립일차방정식(System of linear equations)의 해를 구하는 알고리즘이다.

 

기본적인 아이디어는, 계수로 이루어진 행렬 M이 있다고 할 때, M을 행사다리꼴행렬로 변환하는 것이다. 즉, 가우스 소거법은 어떤 임의의 행렬을 행사다리꼴로 변환하는 방법이다.

 

자세한 것은 아래를 참고하라.

https://ko.m.wikipedia.org/wiki/%EA%B0%80%EC%9A%B0%EC%8A%A4_%EC%86%8C%EA%B1%B0%EB%B2%95

가우스 소거법 - 위키백과, 우리 모두의 백과사전

가우스 소거법에 대한 설명

 

---

C++ 코드

#include <iostream>
#include <vector>
using namespace std;
using matrix=vector<vector<double>>;
void print_matrix(matrix &a){
    for(int i=0;i<a.size();i++,puts(""))for(int q=0;q<a[i].size();q++)cout<<a[i][q]<<' ';
}
namespace GaussianElimination{
    int n; // n is the size of matrix M
    matrix M; // M is system of linear equations
    void run(){
        /**********Gaussian_Elimination***********/
        for(int i=0;i<n-1;i++){
            if(!M[i][i])for(int q=i+1;q<n;q++)if(M[q][i]){
                    for(int cur=-1;cur++<n;)swap(M[i][cur],M[q][cur]);
                    i--;break;
                }
            else{
                double v=M[i][i];
                for(int q=-1;q++<n;)M[i][q]/=v;
                for(int j=i;++j<n;){
                    double multiple=M[j][i];
                    for(int q=-1;q++<n;)M[j][q]-=multiple*M[i][q];
                }
            }
        }
        double multiple=M[n-1][n-1];
        for(int q=-1;q++<n;)M[n-1][q]/=multiple;
        /**************Guass_Jordan***************/
        for(int i=n;--i>0;)for(int j=i;j--;){
            double multiple=M[j][i];
            for(int q=i-1;q++<n;)M[j][q]-=multiple*M[i][q];
        }
    }
}

int main(){
    using namespace GaussianElimination;
    cout<<"Enter the number of various >> ";
    cin>>n;
    M=vector<vector<double>>(n,vector<double>(n+1));
    for(int i=0;i<n;i++){
        cout<<"Enter the coefficients of the "<<i<<"th equation\n>>";
        for(int q=0;q<=n;q++)cin>>M[i][q];
    }
    cout<<"Matrix before run Gaussian Elimination\n";
    print_matrix(M);
    run();
    cout<<"Matrix after run Gaussian Elimination\n";
    print_matrix(M);
}