Project10 Dominant Eigenvalue Computation

Project10 "Power Method" - 가장 큰 고유값의 계산

(Dominant Eigenvalue Computation) 2000. 9.

서 론

이 project의 목적은 행렬의 가장 큰 eigenvalue를 수치적으로 구하는 방법을 개발하는 것이다. 인구 모델 같은 많은 모델에 대응하는 행렬의 가장 큰 eigenvalue는 그 모델의 해의 안정성(stability)을 결정하기 위한 많은 정보를 준다. Maple에 있어 eigenvals 와 같은 명령어는 자주 그 모델의 eigenvalue들에 대한 정확한 답을 안 준다. 더구나 행렬이 조금만 커져도 eigenvalue들을 구하기 힘들게 되는 경우가 많다. 그래서 크기가 큰 행렬의 경우에 가장 큰 eigenvalue를 구하는데 많이 쓰이는 방법이 "Power Method"(거듭 제곱 방법)이다.

배 경

만약, 을 eigenvalue로 갖는 행렬이라고 가정하면, 일반성을 잃지 않고 다음처럼 크기 순으로 배열할 수 있다. 주로 감소하는 방법으로 순서를 정한다.

이때 크기(절대값)가 가장 큰 실수의 고유값인 을 dominant eigenvalue라고 한다. 또 각각의 eigenvalue들에 대응하는 eigenvector를 각각 이라고 표시하자. 그러면 eigenvalue들이 서로 다르므로 그에 대응하는 eigenvector들의 집합은 1차 독립 집합이다. 즉,

우리가 하고자 하는 문제는 주어진 행렬 에 대해 가장 큰 고유값 을 찾는 것이다.

알아야 할 간단한 선형적 성질

이 project를 수행하면서 이미 알고 있는 다음과 같은 성질을 기억하면 도움이 될 것이다.

) eigenvector의 scalar곱도 하나의 eigenvector 이다. (대응하는 eigenvalue는 같다.)

) eigenvalue와 eigenvector임을 확인하는 가장 정확한 방법은 가 되는 것을 확인하는 방법이다.

) 우리는 를 column vector 라고 표시하자. 즉, 는 번째 성분만 1이고,나머지 성분은 모두 0인 vector이다.

그러므로 는 의 번째 column이 될 것이다.

The Power Method

Power Method는 간단하다. 임의의 vector 에 대하여 으로 표현할 수 있다. 왜냐하면 은 의 basis를 form하기 때문이다.

양변에 를 곱하고, 행렬의 곱의 선형성을 고려하면,

이 되며 또한 ( eigenvector들의 정의에 의해서) 이 된다. 여기서 양변에 를 번 반복하여 곱하면,

을 얻을 수 있다. 큰 값에 대해서는, 의 크기가 다른 들의 크기보다 크기 때문에 은 ( for all )보다 매우 커질 것이다. 그러므로 우변의 첫 번째 항은 다른 것을 dominate 할 것이고, 우리는 충분히 큰 에 대해서 을 얻을 수 있다.

게다가 eigenvector의 스칼라 배도 역시 eigenvector이므로 우리는 eigenvalue 에 대응하는 eigenvector를 찾을 수 있으며, 다음의 두 vector 와 의 성분들을 비교할 수 있다. 의 각 성분은 의 각 성분의 배이다.

그러면 vector 는 무엇일까? 그것은 임의로 선택될 수 있다. 그러나 다른 eigenvector 중에 하나이거나 그들의 1차 결합 중 하나이기는 원하지 않으므로 "Power Method"에서는 보통 를 안전하게 column vector 로 선택한다.

예제1) 라고 하자. 예를 들어 위의 를 이용하여 Maple이나 MATLAB 또는 MATHEMATICA를 이용하여 행렬의 거듭제곱을 구한다.

이 값들만으로 보면 연관성이 적어 보인다. 그러나, 각각을 자신의 첫 번째 성분으로 나누면 다음을 얻는다.

이제 연관성이 보인다. 만약 이 단계에서 이런 연관성이 안 얻어지면 극한에 가까이 갈 정도로 충분히 큰 값을 이용하면 궁극적으로 위와 같은 연관성을 갖게 된다.

우리는 eigenvalue/vector 의 정의를 이용하여 다음의 결과를 확인할 수 있다. 즉, dominant eigenvalue, 이며 그것에 대응하는 eigenvector는 임을 알 수 있다.

따라서 우리는 dominant eigenvalue가 4.820임을 확인했고, 그것에 대응하는 eigenvector는 라는 것을 알 수 있었다.

위에서 보았듯이 dominant eigenvalue와 그에 대응하는 eigenvector를 구하기 위하여 행렬 의 거듭제곱을 이용하였던 것이다. 그러면 얼마큼까지의 거듭제곱이 필요할까? 위의 예에서는 임의로 를 소수 3자리까지 계산할 수 있었다. 그러나 더욱 정확한 eigenvalue를 원한다면 연속적인 더 높은 거듭제곱의 행렬을 이용하면 된다. 음이 아닌 행렬에 대해서는 Perron Frobeius 정리가 위의 방법의 이론적인 근거를 준다. (http://matrix.skku.ac.kr/sglee/perron_frobenius/perron_frobenius.html )

연 습 문 제

문제 1) 위의 방법을 이용하여서 각각의 경우에 dominant eigenvalue와 그에 대응하는 eigenvector를 구하시오.

a) 다른 project의 모델[ project4 (인구 유동, 도시 계획) ]의 초기 행렬에 쓰였던

을 생각하자. 우선 와 를 비교해 본 결과 상수배가 덜 정확하여 좀더 큰 거듭제곱으로 와 를 비교하였다.

풀이) ,

이제 첫 번째 성분으로 나누면 다음과 같아진다.

따라서 dominant eigenvalue 는 이고, 이에 대응하는eigenvector는 이다

b) regular Markov Chain 에서 행렬을 선택하시오. (행렬이나 그이상의 행렬에서 마음대로 선택하시오)

풀이)

따라서 dominant eigenvalue는 1이고, 이에 대응하는 eigenvector는 이다. <즉, Row Stachastic 행렬의 경우 가장 큰 (simple) 고유값은 언제나 1이다.>

c) 행렬 의 경우는?

풀이)

따라서 dominant eigenvalue는 5.5922이고, 이에 대응하는 eigenvector 이다.

문제 2) 문제1에서 각 사용된 행렬에 대하여, eigenvalue와 eigenvector를 컴퓨터를 이용해서 푼 결과와 Power Method 이용하여 얻은 결과를 비교하시오.

http://matrix.skku.ac.kr/sglee/algebra/atlastkp/matlab/chap6.htm ( 참고 MATRAB 이용법)

풀이)

a) eigenvalue와 eigenvector가 소수점 이하 4째 자리까지 일치한다. (eigenvector는 6번째 성분만이 소수점 이하 5번째 자리에서 0.00001만큼 차이 난다.)

b) eigenval 명령어를 이용하여 얻은 결과와 Power Method를 이용하여 얻은 eigenvector가 정확히 일치한다.

c) eigenvalue와 eigenvector가 소수점 이하 4째 자리까지 일치한다.

문제 3)

a) 이 방법이 언제나 work하는 것은 아니다. 만약 행렬이 두 개 이상의 dominant eigenvalues ( 8과-8처럼)를 가지려면 그러면 위에서 묘사된 것처럼 eigenvalue에 수렴하는 현상이 언제나 일어나지 않는다.

예로 다음 행렬을 간단히 살펴보자.

(다시 말해서 전에 했었던 것처럼 Power Method를 써 보고 일어난 상태와 무엇이 잘못되었는지에 대해서 말해 보아라.

따라서 이 경우는 eigenvector를 구할 수 없다. 즉, Power Method가 work하지 않는다. 그렇다면 왜 Power Method가 work하지 않을까? 실제로 고유값은 -1. 0, 1 이 된다. 그 이유는 행렬 의 성분이 -1임 을 생각해 볼 때 가 nonnegative 행렬이 아니기 때문에 가장 큰 고유 값이 하나가 아닐 수 잇고 이 행렬이 그런 경우이다. 그래서 Power Method 가 work하지 않은 것이다. 즉, Power Method는 Perron -Frobenius 정리에 의하여 nonnegative 행렬일 경우에는 dominant eigenvalue가 simple (단, 한 개인) eigenvalue가 되므로 위와 같은 경우가 생기지 않고 dominating 고유값으로 수렴하는 알고리즘이 성립하는 것이다.

b) 다음은 대수학적으로 증명을 해보자.

만약 가 의 eigenvalue e 에 대응하는 eigenvector라고 한다면 는 또한 eigenvalue e+c 에 대응하는 의 eigenvector 이다.

증명) Let

[Show ]

(증명)

는 행렬 의 eigenvector 에 대응하는 eigenvalue이다.

c) b의 결과를 이용하여서 대각성분에 2를 더하여서 a)안에 있는 행렬에 대한 dominant eigenvalues(vector)를 구하여라.

< 이 의미는 스칼라 행렬을 더하여 nonnegative 행렬로 바꾸어 Power Method를 써고 가장 큰 고유값을 구하고, 그것을 다시 축이동하여 원래 행렬의 가장큰 고유값을 찾는 방법이다.>

풀이)

이 행렬의 eigenvalue들은 1, 2, 3이다. b)번에 의해서 의 eigenvalue들은 위의 행렬의 고유 갓에 각각 2를 뺀 -1, 0, 1이다. 따라서 dominant eigenvalue들은 -1과 1이다.

(따라서, 이 예는 nonnegative 행렬이 아니어도 적당한 scalar를 더해서 nonnegative 행렬을 만들 수 있으면 수정된 Power Method를 이용하여 dominant eigenvalue를 구한 후, 원래 행렬의 dominant eigenvalue를 구할 수 있는 방법을 보여 주는 것이다.)

문제 4) 그래프에 의해서 의 특성 방정식을 관찰하므로 써 dominant eigenvalue를 구할 수도 있다. 특성 방정식과 축과 만나는 곳이 eigenvalue를 임으로 1번 문제 c)에서 행렬의 특성 방정식을 구하여, 그것의 그래프를 그리면 가장 큰 eigenvalue를 쉽게 볼 수 있다. 이 과정을 소프트웨어를 이용하여 확인해 보아라.

풀이) 의 특성 방정식은 이다 .

( 참고로 문제5를 이용하면 dominant eigenvalue 는 4와 8사이에 있다는 것을 안다.) 4= max { min row sum = 3, min col sum = 4 }

Newton Method에 의해서 8을 초기 값으로 잡아서 적용한다. 그러면 약 5.922정도가 나온다.

문제 5)

a) (이론) 만약 가 nonnegative 행렬이고 dominant eigenvalue 과 그에 대응하는 dominant eigenvector ( Perron -Frobenius 정리에 의하여, 를 모두 양의 성분을 갖는다고 가정할 수 있다.) 를 갖는다고 한다면 의 값은 가장 큰 의 row sum과 가장 작은 row sum사이에 있다.

(힌트: 의 성분들의 합이 1이 되도록 의 크기를 만들어라. 그리고 나서 eigenvalue/vector의 정의를 생각해 보아라.)

증명) Let

이다.

let

는 가장 큰 row sum이고 가장 작은 row sum이다.

이므로 양변을 로 나누면

----(1)

이므로 양변을 로 나누면

----(2)

(1), (2)에 의해서

그러므로 dominant eigenvalue는 가장 큰 row sum과 가장 작은 row sum 사이에 있다. 의 eigenvalue는 같으므로 의 column sum 에 대해서도 같은 얘기가 성립한다.

b) Markov Chain에 이용되는 row stochastic 행렬에 대해서 dominant eigenvalue가 항상 1임을 보이기 위해 위의 결과를 이용하여라.

풀이) Markov Chain의 에 이용되는 row stochastic 행렬의 row sum은 항상 1임으로 a)에 의해서 dominant eigenvalue는 1이다.

c) 행렬의 row sum이 모두 같다면 는 eigenvector이다. eigenvalue에 대해서는 무엇을 말할 수 있는가?

풀이) 행렬라고 하자. 행렬의 row sum이 모두 같으므로, 라고 하자.

그러면 이므로 이다.

그러므로 는 eigenvector이고 즉, row sum이 모두 같은 행렬의 row sum이 바로 그 행렬의 eigenvalue 이다.

문제 6) Power Method 가 work하기 위해서 eigenvector/ eigenvalue에 주어져야 하는 가정은 무엇일까?

풀이) dominant eigenvalue가 단 하나여야만 한다. 그러면 동시에 그에 대응하는 1차 독립인 eigenvector는 하나뿐이다. 그리고 이것은 주어진 행렬 가 nonnegative행렬 (모든 성분이 nonnegative) 이기만하면 Perron-Frobenius 정리에 의하여 따라오는 성질이다.

이상구교수의 읽고 보는 수학 자료실 (http://matrix.skku.ac.kr/sglee/)