이 글은 학부 수업을 들으면서 개인적으로 정리한 글입니다. 잘못된 내용이 있다면 댓글로 말씀 부탁드립니다!
Ax = b
Ax = b 형태의 연립 선형 방정식을 풀기 위한 방법에는 다양한 방법이 있습니다.
가장 기본적인 방법으로는 역행렬을 이용하는 방법, Gauss Elimination 등이 있습니다.하지만 행렬의 크기가 커지면 커질수록 역행렬을 이용하는 방법은 쉽지 않고, Gauss Elimination을 사용하자니 b의 값도 계속해서 계산해줘야하기에 비효율적입니다.
LU Factorization
따라서 위에서 말한 방법들도 좋지만, 행렬을 분해해 Solution을 찾는 LU Factorization을 알아보겠습니다.
위와 같은 형태의 식을 Ax = b 로 두겠습니다.
이런 형태에서 A를 L과 U (L => Lower triangular system, U => Upper triangular system)로 분해해 풀어 보겠습니다.
예시를 위해 A를 3*3, x = 3*1 의 형태로 두고, Ax = b의 형태를 Ax - b = 0 로 바꿔봅시다.
먼저, Ux = d 라고 가정하겠습니다.
그리고 L은 아래와 같이 정의합니다.
이제, Ux - d = 0과 A = LU로 아래와 같은 결과를 얻을 수 있습니다.
L(Ux - d) = Ax - b
=> LUx - Ld = Ax - b
=> Ld = b
LU
이제 A를 분해하는 L 과 U을 구하는 방법을 알아봅시다.
1. Gauss Elimination에서 했듯이, forward-elimination을 통해 U를 구합니다.
2. L의 원소의 값은 forward-elimination 과정에서 해당 위치의 원소를 0으로 만들기 위해 Pivot에 곱해지는 factor들과 같습니다. (예시를 보시길 바랍니다.)
예시 문제와 함께 위 방법을 진행해보겠습니다.
1. U
2. L
L은 먼저 대각 원소를 1로 채우고 아래의 element들의 값을 찾아주면 됩니다.
첫번째 column에 대한 forward-elimination하는 과정에서 (2,1), (3,1)의 위치를 0 으로 만들기 위해 pivot 값에 곱하는 factor들은
$l_{2,1} = \frac{0.1}{3}$ , $l_{3,1} = \frac{0.3}{3}$ 입니다.
두번째 column에 대한 forward-elimination하는 과정에서 (3,2)를 0으로 만들기 위해 Pivot에 곱하는 factor는
$l_{3,2} = \frac{-0.19}{7.00333}$ 입니다.
Find Solution
이제 L, U를 구했으니 solution을 찾으면 됩니다. Ld = b 에서 이미 L과 b를 알기에 d를 구할 수 있고,
그럼 Ux = d 의 U와 d값이 있으니 x를 구할 수 있습니다.
1. Ld = b, 2. Ux = d
