1. LU 분해 (LU Decomposition, LU Factorization)
ㅇ 계수행렬을 하 삼각행렬 및 상 삼각행렬의 곱으로 인수분해하는 것
- A = L U
. L은 단위 하 삼각행렬 (또는, 하 삼각행렬)
. U는 상 삼각행렬 (또는, 단위 상 삼각행렬)
.. U는 A를 행교환없이 행축소한 행사다리꼴과 같음
.. 즉, (E1 E2 ... Ek) A = U
ㅇ LU 분해 가능
- 만일, 계수행렬 A가 행교환없이도 행사다리꼴로 행축소 가능한 정방행렬이면,
- A = L U 형태로 분해 가능
ㅇ LU 분해 알고리즘
- 일련의 행 교환 없이 행 교체 만으로 A를 행사다리꼴인 상 삼각행렬 U로 변환시킴
. 각 단계에서 사용된 배수들을 기록해 둠
- 이 과정에 대응되는 각각의 배수 및 그 역수를 원소로하는 하 삼각행렬 L을 만듬
2. LU 분해에 의한 풀이
ㅇ LU 분해에 의한 선형연립방정식 풀이
- ① A x = b → L U x = b (LU 분해)
- ② U x = y 로써 n x 1 행렬 y 를 정의함
- ③ L y = b 에 의해 y 를 구함 (전진 대입,forward substitution)
- ④ U x = y 에 의해 x 를 구함 (후진 대입,backward substitution)
ㅇ LU 분해에 의한 풀이 이유
- 선형연립방정식 풀이에서,
- 가우스 소거법,가우스 조르단 소거법을 사용하여 컴퓨터 계산을 수행하면 계산량이 많아서,
- 소규모인 경우에는, 무난하나,
- 대규모인 경우에는, 반올림오차,메모리과다사용,수행속도 면에서 불리함
3. LDU 분해
ㅇ LU 분해는, 여러 형태로 분해가능하여 유일하지 않으나, LDU 분해는 유일하게 분해됨
- A = L D U
. L,U : 주 대각선 성분 모두 `1`인 단위 하 또는 상 삼각행렬
. D : 대각행렬
ㅇ 例)
4. PLU 분해
ㅇ 피보팅을 이용한 LU 분해
- 행렬 A가 반올림오차를 줄이기 위해 행 교환이 필요한 경우에,
예비적 처리를 함으로써 LU 분해를 가능케하는 방식
