LU 행렬분해
LU Decomposition
Keon M. Lee
행렬의 분해
LU 분해
LU 분해 알고리즘
행렬의 분해
행렬 A의 분해 (factorization, decomposition)
A를 2개 이상의 행렬의 곱으로 나타내는 것 A= BC, A = BCD
LU 분해
Eigen 분해
QR 분해
SVD 분해
LU 분해
LU 분해 (LU factorization, LU decomposition)
행렬을 하 삼각행렬(lower triangular matrix) L과 상 삼각행렬(upper triangular matrix) U의 곱으로 표현
A = LU
정방행렬(square matrix) 뿐만 아니라 일반 사각행렬에도 적용 가능
단위 하 삼각행렬 (unit lower triangular matrix)
LU 분해
LU 분해의 예
3x3 행렬의 LU 분해
7 . 0 0
0
56 . 1 8
. 4 0
1 5
25
1 5
. 3 76
. 5
0 1
56 . 2
0 0
1
1 12 144
1 8
64
1 5
25
33 23 22
13 12
11
32 31
21
0 0
0 1
0 1
0 0
1
u u u
u u
u LU
A
LU 분해 알고리즘
LU 분해
A = LU
A는 행교환(row exchange) 없이 행 사다리꼴(row-echelon form)로 변 환 가능해야 함
교체와 상수배 행 연산에 대응하는 기본 행렬은 하 삼각행렬이고, 이들 의 역행렬과 이들의 곱도 하 삼각행렬임
LU 분해 알고리즘
LU 분해
A = LU
A는 행교환(row exchange) 없이 행 사다리꼴(row-echelon form)로 변 환 가능해야 함
교체와 상수배 행 연산에 대응하는 기본 행렬은 하 삼각행렬이고, 이들 의 역행렬과 이들의 곱도 하 삼각행렬임
LU 분해 알고리즘
A = LU
LU 분해 알고리즘
A = LU
LU 분해 알고리즘
LU 분해 알고리즘 (Doolittle’s LU Decomposition)
A = (a
ij)
nxn 행렬 for i=1,⋯,nfor j=1,⋯,i−1 α = aij
for p=1,⋯,j−1 α = α−aipapj aij = αajj
for j=i,⋯,n α = aij
for p=1,⋯,i−1 α = α−aipapj aij=α
LU 분해의 활용
선형시스템 해법 – factor-solve 접근법
Ax = b, A = LU
Ax = (LU)x = b
L(Ux) = b Ly = b
Ux = y
Ux = y Ly = b
x b
y A
U L
LU 분해의 활용
LU 분해을 이용한 선형시스템의 해법
L(Ux) = b
Ux = y Ly = b
LU 분해의 활용
LU 분해를 이용한 역행렬 계산
AB = I
A= LU, B = [b1 b2 … bn]
B의 첫번째 열
B의 마지막 열
0 0 1
1 21 11
1
bn
b b A Ab
0 1 0
2 22 12
2
bn
b b A Ab
1 0 0
2 1
nn n n
n
b b b A Ab
B의 두번째 열
LU 분해의 활용
LU 분해를 이용한 역행렬 계산
1 12 144
1 8 64
1 5 25
A
7 0 0
0
56 1 8
4 0
1 5
25
1 5 3 76 5
0 1 56 2
0 0 1
. . .
. .
. LU
A
0 0 1
1 12 144
1 8 64
1 5 25
31 21 11
b b b
0 1 0
1 12 144
1 8 64
1 5 25
32 22 12
b b b
000 . 5
417 . 1
08333 .
0
32 22 12
b b b
1 0 0
1 12 144
1 8 64
1 5 25
33 23 13
b b b
429 . 1
4643 .
0
03571 .
0
33 23 13
b b b
571 . 4
9524 .
0
04762 .
0
31 21 11
b b b
429 . 1 000
. 5 571
. 4
4643 . 0 417
. 1 9524 . 0
03571 .
0 08333 .
0 04762 .
0 A 1
LU 분해의 활용
LU 분해를 이용한 행렬식(determinant)의 계산
정방행렬 A = LU에 대해서
det(A) = det(L)det(U)
삼각행렬에서 det는 대각선 원소의 곱
7 0 0
0
56 1 8
4 0
1 5
25
1 5 3 76 5
0 1 56 2
0 0 1
. . .
. .
. LU
A
1 12 144
1 8 64
1 5 25
A
det(A) = -84 det(LU) = det(A)det(B) = -84
LU 분해 적용 알고리즘의 효율성
선형시스템의 해법
Gauss 소거법
LU 분해활용 기법
역행렬 계산
Gauss 소거법
LU 분해활용 기법
3 12 4
3
8 3 2 n
n n T
3 12 4
3
8 3 2 n
n n T
3 12 4
3
8 4 3 n2 n n
T
3 12 20
3
32
3 2n
n n T
n
(크기)10 100 1000 10000
Gauss 소거법활용/ LU 분해 활용
3.28 25.83 250.8 2501
자료출처: http://numericalmethods.eng.usf.edu
LU 분해 불가 행렬
LU 분해 불가능한 행렬
모든 행렬이 LU 분해 가능한 것은 아님
LU 분해 불가 행렬
행 피봇팅(row pivoting)을 이용한 LU 분해
행 교환을 통한 행렬 재조정
미리 행교환을 한 다음, LU 분해 적용 A = PLU
행교환은 순열행렬(permutation matrix) P를 사용하여 가능
• 여러가지 분해 가능
LU 분해 알고리즘
LU 분해 A = LU에서 L이나 U 가 단위 삼각행렬인 경우에는 LU 분해 가 유일하게 결정됨
LU 분해에서 L 또는 U가 단위 행렬이라는 제약 조건이 없으면, 여러 가지 LU가 분해가 가능함
LU 분해는 nxn 행렬에 대해서 적용하는 것을 기본으로 하나,
사각(rectangular) 행렬과 특이(singular) 행렬에도 적용가능함
LU 분해 알고리즘
MatLab/Octave에서 LU 분해
A = rand(3)
[L, U, P] = lu(A) % L*U = P*A b = rand(3,1)
bp = P*b
y = L\bp % y = L-1b Ly = b x = U\y % x = U-1y Ux = y
