[선형대수학] 37. LU분해는 정말 효율적일까 (vs 가우스 조르단 소거법)

우리는 지난시간까지 LU분해에 대해 공부했습니다. LU분해를 아래와 같은 두 가지 상황에 사용했습니다.

 

1) 연립방정식 풀이

2) 역행렬 계산

 

LU분해를 이용하여 연립방정식을 풀 수 있고, 역행렬을 계산할 수 있다는건 알겠습니다. 그런데 이걸 굳이 왜 쓰는지에 대한 의문이 사라지지 않았습니다. LU분해의 원리를 사용하지 않고, 그냥 가우스 소거법으로 푸는 것에 비해 장점이 느껴지지 않았기 때문입니다. 

 

LU 분해를 어떤 상황에 사용하는 것인지 알아보니 아래와 같은 상황에 사용한다고 합니다. 

 

"$Ax=b$ 에서 $A$는 그대로 있고, 여러 $b$에 대한 $x$를 구해야 하는 경우"

 

 

---

LU분해서 위와 같은 상황에서 정말 효율적인지 알아볼 수 있는 방법이 있습니다. 알고리즘의 cost를 계산해서 비교하면 됩니다. $n \times n$ 행렬에서 각 알고리즘이 연산 횟수는 아래와 같습니다. 

 

알고리즘	연산횟수
가우스-조르단 소거법 (forward 계산)	$\approx \frac{2}{3}n^{3}$
가우스-조르단 소거법 (backword 계산)	$\approx n^{2}$
LU 분해	$\approx \frac{2}{3}n^{3}$
Ly=b 계산	$\approx n^{2}$
Ux=y 계산	$\approx n^{2}$
기본행렬 연산으로 역행렬 계산	$\approx 2n^{3}$
$A^{-1}b$ 계산	$\approx 2n^{3}$

 

가우스-조르단 forward 는 하삼각요소를 제거하고 대각 요소를 1로 만드는 과정이구요. 가우스-조르단 backword 는 상삼각을 제거하는 과정입니다. 

 

연립방정식을 1개 푼다고 할 때, 가우스-조르단 소거법과 LU 분해의 연산횟수는 아래와 같습니다. 

 

가우스-조르단 소거법 $\approx \frac{2}{3}n^{3}+n^{2}$

LU 분해 $\approx \frac{2}{3}n^{3}+n^{2}+n^{2}$

 

A는 그대로 있고 b가 서로 다른 k개의 연립방정식을 풀 때의 연산횟수는 아래와 같습니다. 

 

가우스-조르단 소거법 $\approx k[ \frac{2}{3}n^{3}+n^{2}]$

LU 분해 $\approx \frac{2}{3}n^{3}+k[n^{2}+n^{2}]$

 

A가 유지된다면 LU분해를 매번 다시 할 필요가 없으니 확실히 효율적이다.