선형대수 note 4: Factorization into A = LU

선형대수 note 2: Elimination with Matrices 의 마지막 부분과 이어진다.

    \[\begin{aligned} U &= E A \\ E^{-1} U &= A \end{aligned}\]

여기서 E^{-1} 은 elimination 과정에서 행 교환이 없었다면 하삼각 행렬의 형태로 나타난다. 식을 다시 쓰면,

    \[E^{-1} U = A = L U\]

의 형태로 LU 분해가 된다.

이번에는 행 교환이 필요하다고 가정해보자.

    \[\begin{aligned} PA &= LU \\ A &= P^{T} LU \end{aligned}\]

의 형태로 LU 분해를 할 수 있다.

LU 분해를 하면 어떤 장점이 있는 걸까?
A\mathbf{x} = \mathbf{b} 의 선형계에서 행렬 A 는 고정이고 벡터 \mathbf{b} 가 계속 바뀌는 상황을 가정해보자. ALU 분해를 미리 해놓으면 좀 더 효율적으로 해를 구할 수 있다.

    \[\begin{aligned} A\mathbf{x} &= \mathbf{b} \\ P^{T}LU\mathbf{x} &= \mathbf{b} \\ LU\mathbf{x} &= P\mathbf{b} \end{aligned}\]

U\mathbf{x} = \mathbf{y} 로 놓으면,

    \[L\mathbf{y} = P\mathbf{b}\]

1. \mathbf{y} 에 대한 선형계 L\mathbf{y} = P\mathbf{b} 를 푼다.
2. \mathbf{x} 에 대한 선형계 U\mathbf{x} = \mathbf{y} 를 푼다.

LU 는 triangular 행렬이기 때문에 elimination 과정없이 두번의 substitution 만으로 풀 수 있다.

다음은 C++ 로 만든 LU, P^TLU 분해 함수다 (공개 수학 라이브러리 Eigen 을 사용)


선형대수 note 목록

Leave a Reply

Your email address will not be published. Required fields are marked *