분류 : 가져온 문서/오메가
LU decomposition, LU factorization
행렬을 하삼각행렬(lower triangular matrix)과 상삼각행렬(upper triangular matrix)의 곱으로 표현하는 방법이다. 순열 행렬을 포함하는 경우도 있다. LU 분해는 가우시안 소거법(Gaussian elimination)의 행렬 형태로 볼 수 있다. 컴퓨터를 이용한 계산에서 선형 연립방정식을 풀 때, 행렬을 역변환할 때, 행렬식(determinant)을 계산할 때 LU 분해를 이용한다. 이 방법은 앨런 튜링에 의해 도입되었다.
1. 정의 ✎ ⊖
A를 정방행렬(square matrix)이라고 두자. LU 분해는 A를, 적절한 행 혹은 열의 순서화(ordering)나 순열을 이용해 두 요소인 하삼각행렬 L과 상삼각행렬 U로 행렬분해한 것이다.
A=LU
하삼각행렬에서 대각선 위의 모든 성분은 0이고, 상삼각행렬에서 대각선 아래의 모든 성분은 0이다. 예를 들어, 3 X 3 행렬 A의 LU 분해는 아래와 같다.
\\begin{bmatrix} a_{11} & a_{12} & a_{13} \\\\ a_{21} & a_{22} &a_{23} \\\\ a_{31} & a_{32} & a_{33} \\end{bmatrix} = \\begin{bmatrix} l_{11} & 0 & 0\\\\ l_{21} & l_{22} &0 \\\\ l_{31} & l_{32} & l_{33} \\end{bmatrix} \\begin{bmatrix} u_{11} & u_{12} & u_{13}\\\\ 0 & u_{22} & u_{23}\\\\ 0 & 0 & u_{33} \\end{bmatrix}
행렬의 적절한 순서 또는 순열 없이는 행렬분해가 실현되지 않을 수 있다. 예를 들어, a_{11} = l_{11}u_{11} = 0은 행렬 곱셈을 확대하는 방법을 이용하면 확인이 쉽다. 따라서 최소한 l_{11}과 u_{11} 중 하나는 0이어야 하며, 이것은 L과 U 중 하나는 비가역(singular)이어야 함을 뜻한다. A가 가역이면 이것은 불가능하므로 절차상의 문제이다. 이 문제는 A의 행을 재정렬해 순열 행렬의 첫 번째 원소를 0이 아니도록 함으로써 해결할 수 있다. 이후의 분해 단계에서 발생하는 같은 문제 또한 같은 방법으로 해결할 수 있다.
행 또는 열에서의 적절한 순열이 LU 분해의 충분조건임이 드러난다. '부분 피봇팅에 의한 LU분해'(LU factorization with Partial Pivoting)는 종종 행 순열의 LU 분해를 아래의 식에 대해서만 지칭한다.
PA = LU
이 식에서 P는 순열 행렬이다. 모든 정방행렬이 이 형태로 분해될 수 있으며(1), 분해는 산술적으로 안정하다.(2) 이것은 LUP 분해를 유용한 기술로서 사용할 수 있도록 한다.
'완전 피봇팅에 의한 LU 분해'는 아래와 같은 형태를 띤다.
PAQ = LU
Q는 A의 열을 재정렬한다. LDU 분해는 아래와 같은 분해 형태이다.
A=LDU
D는 대각행렬(diagonal matrix)이고 L과 U는 단위 삼각행렬들이다.
A가 정방행렬이라는 전제를 두었지만, 이 분해법들은 직사각행렬로 일반화할 수 있다. 이 경우, L과 D는 A와 행의 개수가 일치해야 하며, U는 A와 같은 차원이어야 한다.
A=LU
하삼각행렬에서 대각선 위의 모든 성분은 0이고, 상삼각행렬에서 대각선 아래의 모든 성분은 0이다. 예를 들어, 3 X 3 행렬 A의 LU 분해는 아래와 같다.
\\begin{bmatrix} a_{11} & a_{12} & a_{13} \\\\ a_{21} & a_{22} &a_{23} \\\\ a_{31} & a_{32} & a_{33} \\end{bmatrix} = \\begin{bmatrix} l_{11} & 0 & 0\\\\ l_{21} & l_{22} &0 \\\\ l_{31} & l_{32} & l_{33} \\end{bmatrix} \\begin{bmatrix} u_{11} & u_{12} & u_{13}\\\\ 0 & u_{22} & u_{23}\\\\ 0 & 0 & u_{33} \\end{bmatrix}
행렬의 적절한 순서 또는 순열 없이는 행렬분해가 실현되지 않을 수 있다. 예를 들어, a_{11} = l_{11}u_{11} = 0은 행렬 곱셈을 확대하는 방법을 이용하면 확인이 쉽다. 따라서 최소한 l_{11}과 u_{11} 중 하나는 0이어야 하며, 이것은 L과 U 중 하나는 비가역(singular)이어야 함을 뜻한다. A가 가역이면 이것은 불가능하므로 절차상의 문제이다. 이 문제는 A의 행을 재정렬해 순열 행렬의 첫 번째 원소를 0이 아니도록 함으로써 해결할 수 있다. 이후의 분해 단계에서 발생하는 같은 문제 또한 같은 방법으로 해결할 수 있다.
행 또는 열에서의 적절한 순열이 LU 분해의 충분조건임이 드러난다. '부분 피봇팅에 의한 LU분해'(LU factorization with Partial Pivoting)는 종종 행 순열의 LU 분해를 아래의 식에 대해서만 지칭한다.
PA = LU
이 식에서 P는 순열 행렬이다. 모든 정방행렬이 이 형태로 분해될 수 있으며(1), 분해는 산술적으로 안정하다.(2) 이것은 LUP 분해를 유용한 기술로서 사용할 수 있도록 한다.
'완전 피봇팅에 의한 LU 분해'는 아래와 같은 형태를 띤다.
PAQ = LU
Q는 A의 열을 재정렬한다. LDU 분해는 아래와 같은 분해 형태이다.
A=LDU
D는 대각행렬(diagonal matrix)이고 L과 U는 단위 삼각행렬들이다.
A가 정방행렬이라는 전제를 두었지만, 이 분해법들은 직사각행렬로 일반화할 수 있다. 이 경우, L과 D는 A와 행의 개수가 일치해야 하며, U는 A와 같은 차원이어야 한다.
