LU 분해(영어: LU decomposition)는 수치 해석 분야에서 하삼각행렬상삼각행렬의 곱으로 표현하는 것이다. L과 U는 각각 Lower와 Upper를 의미한다. 때때로 치환행렬(permutation matrix)도 함께 곱으로 나타내기도 한다. LU 분해는 가우스 소거법에서 많이 이용된다. LU 분해는 앨런 튜링에 의해 소개됐다.

일반적인 행렬 를 예약한다면,

하삼각행렬(lower triangular matrix)
상삼각행렬(upper triangular matrix)

분해의 예편집

  •  
 
 

계산편집

  •  
 
 
 
 
 

하부 삼각행렬  주대각선 로 놓음으로써,

 
 

다음을 얻을수있다.

 
 
 
 

따라서,

 

분해편집

사다리꼴행렬을 이용한   분해

 
 
 
 
 
  이다.


 
 
 
 
 
 

항상   가 성립하는 것은 아니다.

역행렬과정의 불완전한 LU분해편집

가우스 소거법을 사용해서, 다음과 같은 행렬  단위행렬  첨가 행렬로 계산하면, 역행렬 를 얻을수있다.

 

기본행연산을 가하면, 다음과 같다.

 

따라서  은 다음과 같다.

 

사다리꼴행렬의 역행렬 중간 과정은 유사한 LU 분해를 보여주지만

그러나, 이것은 완전한 LU 분해가 아니다.

 

그러나 이러한 역행렬 과정을 통해 추가적인 조작으로  분해 를 유도할수있다.

응용편집

선형 연립방정식의 풀이편집

다음 선형 연립방정식이 주어져 있다.

 

계수 행렬  를 행 교환을 허용한 가우스 소거법을 통해 LU 분해하면 다음과 같은 꼴로 분해된다. 여기서  순열 행렬이다.

 

따라서 연립방정식은 다음과 같이 나타낼 수 있다.

 

연립방정식의 해는 2단계에 걸쳐서 풀이한다.

  1. 전진 대입:  를 y에 대해 풀고,
  2. 후진 대입:  를 x에 대해서 푼다.

LU 분해를 통한 풀이는 계수 행렬이 같고  만이 달라질 때, 매번 첨가행렬의 가우스 소거법을 통해 연립방정식의 해를 구하는 것보다 간편하다. 그러나 LU 분해를 하는 과정 자체는 가우스 소거법과 동일한 과정을 거치게 된다.

행렬식 계산편집

삼각행렬행렬식은 주대각 성분의 곱이 행렬식과 같다는 점을 이용하면 LU 분해를 통해 행렬식을 쉽게 계산할 수 있다. 순열 행렬은  를 만족하는 직교 행렬이므로  이라는 점을 이용할 수 있다.

 

여기서 S는 LU 분해를 할 때 행 교환을 시행한 횟수이다.

함께 보기편집

참고편집