C++로 구현하는 행렬의 LU 분해 프로그램

행렬의 LU 분해(LU Decomposition)는 하나의 행렬을 하삼각행렬(Lower Triangular Matrix)과 상삼각행렬(Upper Triangular Matrix)의 곱 형태로 나타내는 기법입니다. 이름 그대로 LU에서 L은 Lower(하삼각), U는 Upper(상삼각)를 의미합니다.

다음은 행렬의 LU 분해에 대한 간단한 예시입니다.

주어진 행렬:
1 1 0
2 1 3
3 1 1

L 행렬:
1 0 0
2 -1 0
3 -2 -5

U 행렬:
1 1 0
0 1 -3
0 0 1

이어서 행렬의 LU 분해를 수행하는 C++ 프로그램을 살펴보겠습니다.

예제 코드

#include<iostream>
using namespace std;
void LUdecomposition(float a[10][10], float l[10][10], float u[10][10], int n) {
    int i = 0, j = 0, k = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (j < i)
            l[j][i] = 0;
            else {
                l[j][i] = a[j][i];
                for (k = 0; k < i; k++) {
                    l[j][i] = l[j][i] - l[j][k] * u[k][i];
                }
            }
        }
        for (j = 0; j < n; j++) {
            if (j < i)
            u[i][j] = 0;
            else if (j == i)
            u[i][j] = 1;
            else {
                u[i][j] = a[i][j] / l[i][i];
                for (k = 0; k < i; k++) {
                    u[i][j] = u[i][j] - ((l[i][k] * u[k][j]) / l[i][i]);
                }
            }
        }
    }
}
int main() {
    float a[10][10], l[10][10], u[10][10];
    int n = 0, i = 0, j = 0;

    cout << "Enter size of square matrix : "<<endl;
    cin >> n;

    cout<<"Enter matrix values: "<<endl;
    for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
    cin >> a[i][j];
    LUdecomposition(a, l, u, n);
    cout << "L Decomposition is as follows..."<<endl;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            cout<<l[i][j]<<" ";
        }
        cout << endl;
    }
    cout << "U Decomposition is as follows..."<<endl;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            cout<<u[i][j]<<" ";
        }
        cout << endl;
    }
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

Enter size of square matrix : 3
Enter matrix values:
1 1 0
2 1 3
3 1 1
L Decomposition is as follows...
1 0 0
2 -1 0
3 -2 -5
U Decomposition is as follows...
1 1 0
0 1 -3
0 0 1

코드 설명

위 프로그램에서 LUdecomposition 함수는 입력받은 행렬 a[][]로부터 L 분해와 U 분해를 계산하여 각각 l[][] 배열과 u[][] 배열에 저장합니다. 이 과정은 중첩된 for 루프를 사용하여 구현됩니다.

핵심 로직을 보여주는 코드 조각은 다음과 같습니다.

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        if (j < i)
        l[j][i] = 0;
        else {
            l[j][i] = a[j][i];
            for (k = 0; k < i; k++) {
                l[j][i] = l[j][i] - l[j][k] * u[k][i];
            }
        }
    }
    for (j = 0; j < n; j++) {
        if (j < i)
        u[i][j] = 0;
        else if (j == i)
        u[i][j] = 1;
        else {
            u[i][j] = a[i][j] / l[i][i];
            for (k = 0; k < i; k++) {
                u[i][j] = u[i][j] - ((l[i][k] * u[k][j]) / l[i][i]);
            }  
        }
    }
}

main() 함수에서는 사용자로부터 정방행렬의 크기와 각 원소 값을 차례대로 입력받습니다.

cout << "Enter size of square matrix : "<<endl;
cin >> n;
cout<<"Enter matrix values: "<<endl;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cin >> a[i][j];

그런 다음 LU 분해 함수를 호출하고, 계산된 L 행렬과 U 행렬을 화면에 출력합니다.

LUdecomposition(a, l, u, n);
cout << "L Decomposition is as follows..."<<endl;
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        cout<<l[i][j]<<" ";
    }
    cout << endl;
}
cout << "U Decomposition is as follows..."<<endl;
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        cout<<u[i][j]<<" ";
    }
    cout << endl;
}

참고로 이 알고리즘은 피벗팅(pivoting) 없이 동작하는 기본적인 두들(Doolittle) 방식의 LU 분해입니다. 즉, U 행렬의 대각 성분이 모두 1이 되도록 분해됩니다. 따라서 분해 과정에서 대각 성분이 0이 되는 경우에는 행 교환(row swapping) 등의 피벗 처리가 추가로 필요할 수 있습니다.