행렬의 거듭제곱법
정의
크기가 $n \times n$인 정방행렬 $A$의 거듭제곱을 계산함으로서 $A$의 우세 고유값을 구하는 방법을 거듭제곱법the power method이라 한다.
설명
주어진 행렬의 고유값을 계산하기 위해서는 특성 다항식을 풀어야한다. 하지만 $5 \ge n$일 때는 근의 공식이 존재하지 않으므로 특성 다항식의 근을 대수적으로 쉽게 계산하는 것이 불가능하다. 이는 손 계산일 때도 물론 힘들지만, 컴퓨터로 계산할 때도 마찬가지이다. 거듭제곱법은 이러한 문제를 해결하기 위한 방법으로, 행렬의 거듭제곱을 계산하는 과정을 통해 우세 고유값을 근사적으로 구할 수 있다.
$n \times n$ 행렬 $A$와 $n$차원 벡터 $\mathbf{x} \in \mathbb{R}^{n}$에 대해서, 아래와 같은 수열을 $A$에 의해 만들어지는 거듭제곱수열power sequence generated by $A$이라 한다.
$$ \left\{ \mathbf{x},\quad A\mathbf{x},\quad A^{2}\mathbf{x},\quad \dots \right\} $$
거듭제곱 계산을 반복하면, 벡터의 크기가 너무 커지거나 작아져서 계산이 어려워진다. 이를 해결하기 위해, 아래의 정리와 같이 각 단계에서 벡터의 크기를 정규화하는 방법을 사용하거나, 벡터의 최대성분 크기를 조정하는 등의 방법을 사용한다.
정리
정리에 의해서 임의의 초기 벡터 $\mathbf{x}_{0}$에 행렬 $A$ 반복해서 곱하는 것으로 우세 고유값를 구할 수 있다. $\mathbf{x}_{0}$가 우세 고유공간과 직교하지 않아야한다는 가정이 필요하지만, $\mathbf{x}_{0}$를 무작위로 추출했을 때 그렇게 될 확률은 매우 낮다.
정리에서 우세 고유값이 양수인 것을 가정하는데, 만약 음수라면 $(1)$의 수열은 방향이 서로 반대인 단위 우세고유벡터에 가까워지며 진동할 것이다. 비슷하게 $(2)$는 우세 고유값의 절댓값에 수렴할 것이다.
만약 $A$가 대각화 가능하면 $n$개의 독립인 고유벡터를 가지므로, 정리의 조건을 만족한다.
$A$가 대칭행렬이면 $n$개의 독립인 고유벡터를 가지므로, 정리의 조건을 만족한다.
$\ell^{2}$ 정규화에 의한 거듭제곱법
$n \times n$ 행렬 $A$가 $n$개의 선형독립인 고유벡터를 갖는다 고 하자. $A$의 우세 고유값 $\lambda_{1}$이 양수라고 하자. 그러면 $\lambda_{1}$에 대응하는 고유공간에 직교하지 않는 단위 벡터 $\mathbf{x}_{0} \in \mathbb{R}^{n}$에 대해서, 아래와 같은 정규화된 거듭제곱수열은 우세 단위고유벡터에 수렴한다.
$$ \mathbf{x}_{0},\quad \mathbf{x}_{1} = \dfrac{ A \mathbf{x}_{0} }{\| A \mathbf{x}_{0} \|},\quad \mathbf{x}_{2} = \dfrac{ A \mathbf{x}_{1} }{\| A \mathbf{x}_{1} \|},\quad \dots,\quad \mathbf{x}_{k} = \dfrac{ A \mathbf{x}_{k-1} }{\| A \mathbf{x}_{k-1} \|},\quad \dots \tag{1} $$
또한 아래의 수열은 우세 고유값에 수렴한다.
$$ A \mathbf{x}_{1} \cdot \mathbf{x}_{1}, \quad A \mathbf{x}_{2} \cdot \mathbf{x}_{2}, \quad \dots, \quad A \mathbf{x}_{k} \cdot \mathbf{x}_{k}, \quad \dots \tag{2} $$
한편 $(1)$은 아래의 수열과도 같다.
$$ \mathbf{x}_{0},\quad \mathbf{x}_{1} = \dfrac{ A \mathbf{x}_{0} }{\| A \mathbf{x}_{0} \|},\quad \mathbf{x}_{2} = \dfrac{ A^{k} \mathbf{x}_{0} }{\| A^{k} \mathbf{x}_{0} \|},\quad \dots,\quad \mathbf{x}_{k} = \dfrac{ A^{k} \mathbf{x}_{0} }{\| A^{k} \mathbf{x}_{0} \|},\quad \dots $$
최대성분 크기 조정에 의한 거듭제곱법
$n \times n$ 행렬 $A$가 $n$개의 선형독립인 고유벡터를 갖는다 고 하자. $A$의 우세 고유값 $\lambda_{1}$이 양수라고 하자. 그러면 $\lambda_{1}$에 대응하는 고유공간에 직교하지 않는 단위 벡터 $\mathbf{x}_{0} \in \mathbb{R}^{n}$에 대해서, 아래와 같은 정규화된 거듭제곱수열은 우세 단위고유벡터에 수렴한다.
$$ \mathbf{x}_{0},\quad \mathbf{x}_{1} = \dfrac{ A \mathbf{x}_{0} }{\max(A \mathbf{x}_{0})},\quad \mathbf{x}_{2} = \dfrac{ A \mathbf{x}_{1} }{\max(A \mathbf{x}_{1})},\quad \dots,\quad \mathbf{x}_{k} = \dfrac{ A \mathbf{x}_{k-1} }{\max(A \mathbf{x}_{k-1})},\quad \dots \tag{3} $$
이때 $\max (\mathbf{x})$는 벡터 $\mathbf{x}$의 성분의 절댓값 중 가장 큰 값을 의미한다. 또한 아래의 수열은 우세 고유값에 수렴한다.
$$ \dfrac{A \mathbf{x}_{1} \cdot \mathbf{x}_{1}}{\mathbf{x}_{1} \cdot \mathbf{x}_{1}}, \quad \dfrac{A \mathbf{x}_{2} \cdot \mathbf{x}_{2}}{\mathbf{x}_{2} \cdot \mathbf{x}_{2}}, \quad \dots, \quad \dfrac{A \mathbf{x}_{k} \cdot \mathbf{x}_{k}}{\mathbf{x}_{k} \cdot \mathbf{x}_{k}}, \quad \dots $$
한편 $(3)$은 아래의 수열과 같다.
$$ \mathbf{x}_{0},\quad \mathbf{x}_{1} = \dfrac{ A \mathbf{x}_{0} }{\max(A \mathbf{x}_{0})},\quad \mathbf{x}_{2} = \dfrac{ A^{2} \mathbf{x}_{0} }{\max(A^{2} \mathbf{x}_{0})},\quad \dots,\quad \mathbf{x}_{k} = \dfrac{ A^{k} \mathbf{x}_{0} }{\max(A^{k} \mathbf{x}_{0})},\quad \dots $$
증명
$\ell^{2}$ 정규화에 의한 거듭제곱법에 대해서 증명한다. $A$의 $n$개의 선형독립인 고유벡터를 $\mathbf{v}_{i}$라 표기하자. 이들은 $\mathbb{R}^{n}$의 기저이므로, $\mathbf{x}_{0}$를 다음과 같이 표현할 수 있다.
$$ \mathbf{x}_{0} = c_{1}\mathbf{v}_{1} + \cdots c_{2}\mathbf{v}_{2} + \cdots + c_{n} \mathbf{v}_{n} \quad (c_{1} \ne 0) $$
여기서 $\mathbf{x}_{0}$가 $\lambda_{1}$의 고유공간과 직교하지 않으므로 $c_{1}$는 $0$이 아니다. $A^{k}$를 양변에 곱하고 정리하면 다음을 얻는다.
$$ \begin{align*} A^{k}\mathbf{x}_{0} &= c_{1}A^{k}\mathbf{v}_{1} + \cdots c_{2}A^{k}\mathbf{v}_{2} + \cdots + c_{n}A^{k}\mathbf{v}_{n} \\ &= c_{1}\lambda_{1}^{k}\mathbf{v}_{1} + \cdots c_{2}\lambda_{2}^{k}\mathbf{v}_{2} + \cdots + c_{n}\lambda_{n}^{k}\mathbf{v}_{n} \\ &= \lambda_{1}^{k} \left[ c_{1}\mathbf{v}_{1} + \cdots c_{2}\left( \dfrac{\lambda_{2}}{\lambda_{1}} \right)^{k}\mathbf{v}_{2} + \cdots + c_{n}\left( \dfrac{\lambda_{n}}{\lambda_{1}} \right)^{k}\mathbf{v}_{n} \right] \\ \end{align*} $$
$\lambda_{1}$가 우세 고유값이므로, 각괄호 내의 값은 $k \to \infty$일 때 $c_{1}\mathbf{v}_{1}$로 수렴한다.
보조정리
$\mathbf{x}_{k}$를 초기 단위벡터 $\mathbf{x}_{0}$에 대해 $\mathbf{x}_{k} = A^{k} \mathbf{x}_{0} / \left\| A^{k} \mathbf{x}_{0} \right\|$와 같이 나타낼 수 있다. 즉 $(1)$의 수열은 아래와도 같다. $$ \mathbf{x}_{0},\quad \mathbf{x}_{1} = \dfrac{ A \mathbf{x}_{0} }{\| A \mathbf{x}_{0} \|},\quad \mathbf{x}_{2} = \dfrac{ A^{k} \mathbf{x}_{0} }{\| A^{k} \mathbf{x}_{0} \|},\quad \dots,\quad \mathbf{x}_{k} = \dfrac{ A^{k} \mathbf{x}_{0} }{\| A^{k} \mathbf{x}_{0} \|},\quad \dots $$
위의 보조정리에 의해 $\mathbf{x}_{k}$는 우세단위벡터에 수렴한다. 이 결과로부터 $A \mathbf{x}_{k} \cdot \mathbf{x}_{k}$ 또한 우세 고유값으로 수렴함을 알 수 있다.
■
보조정리 증명
수학적 귀납법으로 증명한다. $k=1$일 때는 성립함을 알고있다. 이제 $k=m$일 때 성립한다고 가정하자. 그러면 $k=m+1$일 때도 성립한다는 것을 아래와 같이 보일 수 있다.
$$ \mathbf{x}_{m+1} = \dfrac{ A \mathbf{x}_{m} }{ \left\| A \mathbf{x}_{m} \right\| } = \dfrac{1}{\left\| A^{m}\mathbf{x}_{0} \right\|}\dfrac{ A (A^{m}\mathbf{x}_{0}) }{ \left\| \dfrac{A (A^{m}\mathbf{x}_{0})}{ \left\| A^{m}\mathbf{x}_{0} \right\|} \right\| } = \dfrac{A^{m+1} \mathbf{x}_{0}}{\left\| A^{m+1} \mathbf{x}_{0} \right\|} $$
■