본문 바로가기

(비정기) Mr.K's Post/Weekly paper

Matrix Decomposition


안녕하십니까 Mr. K입니다

어쩌다보니 처음같지 않게 포스팅이 뜸해지는군요 -_-;

본 내용은 PKU 3685 : Matrix 와는 전혀 관계없는 내용이므로 해당 내용을 보시고자 하는 분들은 뒤로가기를 눌러주세요



오늘 소개할 내용은 행렬 분해법입니다

그 중에서도 LU-분해법(LU-Decomposition)에 대해서 소개하도록 하겠습니다



예전에 소개했던 Interpolation : part 1 에서

N차 다항식을 구하기 위해 N+1개의 점들을 행렬의 원소로 갖는 Vandermonde matrix를 사용했었습니다

그래서 아래와 같은 꼴의 문제로 바뀌게 되었지요


그러나 당시 포스트에도 언급했듯이,

구하고자 하는 다항식의 차수가 커지면 그만큼 오래걸린다는 단점이 존재했습니다



이번에 소개할 LU-분해법은 그 시간을 조금 줄여줄 수 있는 방법입니다

위의 문제를 아래와 같은 꼴로 바꾸어서 푸는 것이지요


이때, L과 U는 각각 다음과 같은 하-삼각행렬(Lower triangular matrix)과 상-삼각행렬(Upper triangular matrix)입니다

*는 임의의 수를 뜻합니다
0이 있어도 상관없습니다

이렇게 분해하면 무슨 장점이 있느냐,
-라고 생각하시는 분들도 있겠지만

A가 희소행렬(sparse matrix)이 아니라면
오히려 이 방법이 가우스-조르단의 소거법보다도 빠른 시간에 문제해결이 됩니다

얼마나 빠른가 하면,

사실 AN INTRODUCTION TO Programming and Numerical Methods in MATLAB에 나온 그래프는
이것보다 더 깔끔한 곡선을 그리고 있고, 두 방법간의 시간차도 더 크게 나와있지만
그대로 그려내기가 쉽지 않더군요 -_-; 이게 그나마 제일 비슷하게(모양만) 나온 그래프인듯 합니다


이정도의 차이를 나타내지요

위의 Full inversion이 가우스-조르단의 소거법이라 보시면 됩니다



이제 그 방법을 보기로 하지요

예시는 Interpolation : part 1 에서 사용했던 Vandermonde matrix를 사용하도록 하겠습니다

1. 먼저, L은 항등행렬로, U는 영행렬로 설정해둡니다



2. U의 1행에 A의 1행을 그대로 복사합니다



3. L의 1열에 A의 1행을 그대로 복사하되,
L의 1행 1열 원소가 1을 유지하도록 (A의 1행 ÷ U의 1행 1열 원소)의 값을 L의 1열에 복사합니다
(여기서는 U의 1행 1열 원소, 즉 A의 1행 1열 원소가 1이기 때문에 나누는 작업이 필요하지 않습니다)
(이 작업을 하기 위해 필요한 조건 : A의 1행 1열 원소는 0이 아니어야 합니다)



4. U의 2행의 원소들을 구합니다
U의 2행 1열은 0으로 놔두고, (∵ U는 상-삼각행렬이므로)
U의 2행 2열은,
위 그림에 나와있는 L의 2행과 U의 2열을 곱해서 나온 수 k를 A의 2행 2열에서 뺀 뒤, L의 2행 2열의 값으로 나누어줍니다
(여기서 k = 1×1 + 1×0 + 0×0 = 1이고, A의 2행 2열은 2, L의 2행 2열은 1이므로 (2-k)/1 = 1을 U의 2행 2열에 대입합니다)
U의 2행 3열도 마찬가지로 구해줍니다



5. L의 2열의 원소들을 구합니다
L의 1행 2열은 0으로 놔두고, (∵ L은 하-삼각행렬이므로)
L의 2행 2열은 1로 놔두고, (∵ L의 대각선은 전부 1로 고정되어있습니다)
L의 3행 2열은,
위 그림에 나와있는 L의 3행과 U의 2열을 곱해서 나온 수 m을 A의 3행 2열에서 뺀 뒤, U의 2행 2열의 값으로 나누어줍니다
(여기서 m = 1×1 + 0×1 + 1×0 = 1이고, A의 3행 2열은 3, U의 2행 2열은 1이므로 (3-m)/1 = 2를 L의 3행 2열에 대입합니다)
(주의사항 : U의 2행 2열의 값이 0일 경우, (3-m)/0을 계산하지 않고 (3-m)만을 계산해서 대입합니다)



6. U의 n행, L의 n열의 원소들을 채우는 작업이 끝날 때까지 4. 와 5. 를 반복합니다


이제 A가 L과 U로 분해되었으니, 조금 더 간단하게 연립방정식을 풀 수 있습니다



코드로 구현한 것은 다음과 같습니다






전에 연분수에 대해 보강한다 어쩐다 했는데

빈둥빈둥 놀다보니 그럴 시간이 안나는군요 -_-; 빨리 분석을 시작해야할텐데;

다음주에는 뭘 소개할지 모르겠지만,

소재를 못찾으면 수학1에 나오는 행렬의 기본 에 대해 끄적일지도.. -_-;


(포스팅 소요시간 : 약 75분)


+α (9:37부터 수정 시작)
포스팅을 끝내고 화장실에서 생각을 좀 해봤는데, A를 LU로 분해했을 때의 장점을 하나 빼먹었군요 -_-;


또 하나의 장점이라면 장점인데,

분해하기 전의 행렬보다 분해하고 난 후의 두 삼각행렬에서 행렬식(Determinant)을 구하는 것이 훨씬 쉽지요
(∵ 삼각행렬의 행렬식은 모든 대각원소의 곱이기 때문에)

그래서 두 삼각행렬의 행렬식을 구해서 곱하면, 그것이 기존 행렬의 행렬식이 되고,
그 값이 0이냐 아니냐에 따라 연립방정식의 해의 존재유무를 더 빨리 알아낼 수 있게 될겁니다


또 하나 빼먹은 것은,
A의 1행 1열의 원소가 0일 경우의 분해방법입니다

다음과 같은 행렬 A에 대해서는 위의 분해방법을 적용할 수 없습니다


그러나 이러한 경우,
행을 치환해주는 행렬 P나 열을 치환해주는 행렬 Q를 이용해서

P는 항등행렬에서 1행과 2행을 치환한 것이고,
Q는 항등행렬에서 1열과 2열을 치환한 것입니다

PA 또는 AQ를 생각하면 이 분해법을 적용할 수 있습니다


(포스트 수정시간 : 약 20분)


+2α (9일 pm 11:03부터 수정 시작)
"플러스 알파" 적을 때 같이 적을려고 했다가 깜빡하고 넘어간게 하나 있네요 -_-;

저 위에 적어놓은 분해방법은
제가 3×3 행렬 몇개를 분해해보고, 그 방법을 일반화한 것입니다


실제로 LU분해법이 소개된 책에, 만약 그 분해법까지 자세히 나와있다면
이 포스트에서 보는 방법과 전혀 다를 수 있으니 참고바랍니다 (_ _)

(포스트 수정시간 : 약 4분)

'(비정기) Mr.K's Post > Weekly paper' 카테고리의 다른 글

Matrix : Part 2  (2) 2009.01.24
Matrix : Part 1  (8) 2009.01.17
무리수 √2의 값을 구해보자! : Part 5  (3) 2008.12.27
Interpolation : Part 3  (12) 2008.12.05
Interpolation : Part 2  (0) 2008.11.28