연립방정식 를 풀 때 Gaussian Elimination을 적용하면 계수행렬을 Upper Triangular Matrix로 바꿀 수 있다. LU Decomposition은 이 소거 과정을 두 개의 삼각행렬에 저장하는 방법이다.
정사각행렬 를 다음과 같이 분해한다.
여기서 은 Lower Triangular Matrix이고, 는 Upper Triangular Matrix이다.
보통 의 대각성분을 모두 1로 둔다. 이러한 행렬을 Unit Lower Triangular Matrix라고 한다.
LU Decomposition이 필요한 이유
에 를 대입하면
이다. 여기서 새로운 벡터 를
로 두면 원래 문제는 다음 두 문제로 나뉜다.
첫 번째 식은 Lower Triangular Matrix이므로 위에서 아래로 값을 구하는 Forward Substitution을 사용한다. 두 번째 식은 Upper Triangular Matrix이므로 아래에서 위로 값을 구하는 Back Substitution을 사용한다.
행렬 는 같고 우변 만 여러 번 바뀌는 문제에서는 를 한 번만 분해하면 된다. 이후에는 두 번의 삼각행렬 계산만 수행하면 되므로 같은 Gaussian Elimination을 반복할 필요가 없다.
Gaussian Elimination과 L
다음 행렬을 분해한다.
첫 번째 열의 아래쪽 원소를 제거한다.
그 결과는 다음과 같다.
두 번째 열의 아래쪽 원소를 제거한다.
따라서
이다. 소거 과정에서 사용한 multiplier 를 대각선 아래에 저장하면
을 얻는다. 실제로
이다. Gaussian Elimination에서 제거된 정보가 사라진 것이 아니라 에 저장된 것이다.
LU Decomposition으로 연립방정식 풀기
다음 문제를 생각한다.
먼저
을 푼다. Forward Substitution을 적용하면
이므로
이다. 이제
를 Back Substitution으로 풀면
을 얻는다.
행 교환과 PA=LU
LU Decomposition을 진행하다 보면 pivot이 0이거나 수치적으로 너무 작은 경우가 있다. 이때는 행 교환이 필요하다.
행 교환은 Permutation Matrix 로 나타낸다.
Permutation Matrix는 Identity Matrix의 행을 재배열한 행렬이다. 각 행과 열에 1이 하나씩만 존재하며 다음 성질을 가진다.
따라서 실제 수치 계산에서는 단순한 보다 pivoting을 포함한 형태가 더 일반적이다.
계산량
일반적인 Gaussian Elimination 또는 LU factorization에는 대략 의 연산이 필요하다. 그러나 분해 이후 Forward·Back Substitution은 각각 이다.
따라서 하나의 에 대해 여러 우변을 풀 때 LU Decomposition의 장점이 커진다.
정리
- LU Decomposition은 Gaussian Elimination을 행렬의 곱으로 표현한 것이다.
- 에는 소거 과정의 multiplier가 저장되고 에는 소거 결과가 저장된다.
- 는 Forward Substitution으로, 는 Back Substitution으로 푼다.
- 행 교환이 필요하면 형태를 사용한다.
- 같은 계수행렬에 여러 우변이 주어질 때 계산을 크게 줄일 수 있다.
확인 문제
1
다음 행렬을 LU Decomposition한다.
2
앞에서 구한 를 이용해 다음 연립방정식을 푼다.
풀이
1번
첫 번째 행의 3배를 두 번째 행에서 뺀다.
따라서
이다. 실제로 가 성립한다.
2번
먼저
을 풀면 , 이므로 이다.
이제
에서 , 이므로 이다. 따라서
이다.