LU분해

 1. LU분해의 개념

 

 가우시안 소거밥이나 가우스-조르단 소거법은 행렬의 크기가 작을 때는 괜찮지만, 행렬의 크기가 커지면 메모리 문제, 반올림 문제, 속도 문제 등 여러 문제가 발생할 수 있다. 이러한 문제를 LU분해를 통해 해결할 수 있다.

 

 우리가 풀고자 하는 선형 방정식운 n개의 방정식으로 구성된 Ax=b 형태이다.

 

 정사각 행렬 A를 다음과 같이 행렬 L과 U의 곱으로 분해하겠다.

 위 식처럼 분해하는 방법을 LU분해(LU factorization)라고 한다.

 

 2. LU분해 방법

 

 LU 분해의 목표는 행렬 A를 하 삼각 행렬 L과 상 삼각 행렬 U로 분해하는 것이다. LU분해에서 상 삼각 행렬 U는 가우스 행렬이고 이는 행렬 A를 가우스 행렬 U로 변환하는 과정에서 행렬 L을 구할 수 있다는 것을 의미한다.

 

 행렬 A를 가우스 행렬 U로 변환하는 과정은 기본 행 연산을 수행하는 과정은 행렬 A에 기본 행렬을 곱한다고 생각할 수 있다.

 위 식과 같이 양변에 기본 행렬의 역행렬을 곱해 주면 좌변에 행렬 A만 남는 것을 볼 수 있다.

 

 <예제>

 1단계에서는 1행 1열의 원소를 1으로 만들어 보겠다.

 2단계에서는 2행 1열 값을 0으로 만든다.

 

 3단계에서는 3행 1열의 값을 0으로 만든다.

 

 4단계는 2행 2열 값을 1로 만드는 것이다.

 

 5단계는 3행 2열 값을 0으로 만든다.

 

 6단계는 3행 3열 값을 1로 만드는 것이다.

 행렬 A를 가우스 행렬로 변환시킨 결과가 행렬 U에 해당한다.