LU Decomposition, LU Factorization   LU 분해, LU 인수분해

(2021-04-05)

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 분해를 가능케하는 방식

   

선형대수 수치방법
   1. 행렬 분해   2. LU 분해  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"