[선형대수학] 4. 두리틀 분해 (Doolittle decomposition)

2010. 12. 19

두리틀 분해가 무엇인가요 ?

임의의 정칙행렬 A 는  대각선 성분이 모두 1인 하부삼각행렬  과 상부삼각행렬 로 분해하는 것을 말합니다.
즉  A = LU 가 되는 것이죠
이를 두리틀 분해라 합니다.



그냥 A로 놓고 사용하면 되지 뭐할려고 분해하는 것이죠?

이거 역시 이전시간에 배웠던거와 같이
행렬의 크기가 작으면 상관없으나 행렬의 크기가 만약 100*100 이라면 계산하는데 엄청난 시간이 소비됩니다.
그래서 이를 분해해서 사용합니다.
보통 두리틀 분해는 선형균등화나 행렬의 행렬값을 계산하기위한 시스템을 풀기위하여 수치분석으로 사용되어진다




그럼 어떻게 분해하죠? 예를들어서 설명해주세요

역시 말로 표현만 하면 이해하기 어렵습니다.


하나의 예를 들어보겠습니다.

다음 행렬이 있습니다.

2	-1	-2
-4	6	3
-4	-2	8

두리틀 분해를 하기위해서는 정칙행렬이어야 한다.  (그렇다 역행렬이 존재해야한다는 것이다.)

역행렬이 존재하기 위한 조건 행렬식이 0이 아니어야 한다는 다 알것입니다. (만약 모른다면 지난번 페이지를 보라!)
간단히 Sarrus 법칙으로 구해보겠다
(2*6*8) + (-1 * 3 * -4) + (-2 * -4 * -2) - (-2 * 6 * -4) - (-1 * -4 * 8) - (2 * 3* -2)
96 + 12 - 16 - 48 -32 + 12 =  24 이다.
0이 아니기 때문에 이 행렬은 정칙행렬입니다.


두리틀분해를 하기위한 필요조건은 만족했으니
상부삼각행렬과 하부삼각행렬을 구해보겠습니다.

먼저 봐야할 것은 상부삼각행렬의 곱과 하부삼각행렬의 곱이다.
아직 각각의 값을 모르니 a~ i 까지 미지수로 놓겠습니다.

1
a	1
b	c	1

< 하부 삼각행렬>

d	e	f
	g	h
		i

상부 삼각행렬



이 두 행렬의 곱은 A와 같다 하였다
곱을 할때 A의 1행1열의 값을 구하는 식을 보아라

<A의 1행 1열>
1*d + 0*0 + 0*0 = 2
1*d = 2
d = 2

<A의 1행2열>
1*e + 0*g + 0*0 = -1
1*e = -1
e = -1

<A의 1행3열>
1*f + 0*h + 0*i = -2
1*f = -2
f = -2

.
.
.
.
<A의 3행3열>


이런식으로 연립방정식으로 구하면
상부삼각행렬과 하부삼각행렬을 각각 구 할 수 있다.

1
-2	1
-2	-1	1

<하부삼각행렬>

2	-1	-1
	4	-1
		3

<상부삼각행렬 >


이 둘의 곱을 해보면 A의 값이 나옴을 알수가 있다.
여기에서는 행렬의 크기가 3*3 행렬이지만 만약 n*n 이라면 이역시 하루종일 걸리겠는데요



그냥 A로 사용하지 왜 이거 분해한느 시간이 더걸릴거 같은데 왜 분해하나요?

이를 사용하는 이유는 쉽게 식에의해서 각각의 행렬의 값을 구할수 있기 때문입니다.
이미 사람들은 각각의 행렬에 맞는 값을 구할수 있는 식을 유도해놨습니다.
우리는 이식만 이용해서 구하기만 하면 쉽게 분해할수 있기 때문입니다.

이 식들의 유도과정은 블로깅하는데 너무 시간오래 걸릴것 같다.
궁금하시면 알아서 찾아보길 바란다. 



이제 내용과 의미를 아셨다면 실전에 사용할 수 있도록 코딩 들어가셔야죠 ^^



도움이 되셨다면 리플 부탁드립니다 !
리플 하나가 큰 힘이 된답니다 ^^