$n \times n$ 행렬 $A$가 주어져 있을 때, 임의의 벡터 $\vec{v}$에 계속해서 $A$를 곱해나감으로써 절대값이 가장 큰 고유값과 그에 해당하는 고유 벡터를 구하는 방법.

행렬 $A$가 고유값 $\lambda_1, \lambda_2, \ldots, \lambda_n$을 가지고 이들이 절대값 크기 순으로 정렬되어 있다고 하자 ($\left| \lambda_1 \right| > \left| \lambda_2 \right| \ge \ldots \left| \lambda_n \right|$). 이에 해당하는 고유 벡터들은 $\vec{v}_1, \vec{v}_2, \ldots, \vec{v}_n$이다. 즉, $$A \vec{v}_i = \lambda_i \vec{v}_i$$ 이고 논의를 간편하게 하기 위해 이들은 선형독립이라고 가정할 것이다.

시작하는 벡터 $\vec{v}$는 위의 고유 벡터들의 선형결합을 통해 다음처럼 적을 수 있다: $$\vec{v} = c_1 \vec{v}_1 + c_2 \vec{v}_2 + \cdots + c_n \vec{v}_n.$$ 임의로 잡은 $\vec{v}$에서 거의 언제나 $c_1 \neq 0$이 성립할 것이다. 위 식에 $A$를 $m$번 곱하면, $$A^m \vec{v} = c_1 \lambda_1^m \vec{v}_1 + c_2 \lambda_2^m \vec{v}_2 + \cdots + c_n \lambda_n^m \vec{v}_n.$$

가정상 $\lambda_1$의 절대값이 가장 크므로, $m$이 커질수록 우변의 첫 번째 항이 나머지 모두를 압도할 것이다. 따라서 $A^m \vec{v}$의 방향이 점차 수렴하게 되고 이것이 $\vec{v}_1$이다. $\vec{v}_1$을 찾은 후 여기에 $A$를 곱해 몇 배가 되는지를 보면 이것이 $\lambda_1$이다.

위 식을 $\lambda_1^m$으로 나누어보자. $$\frac{A^m \vec{v}}{\lambda_1^m} = c_1 \vec{v}_1 + c_2 \left( \frac{\lambda_2}{\lambda_1} \right)^m \vec{v}_2 + \cdots + c_n \left( \frac{\lambda_n}{\lambda_1} \right)^m \vec{v}_n.$$

우변의 두 번째 항이 $\vec{v}_1$으로부터 벗어난 오차를 대부분 설명한다. 따라서 이 방법을 사용할 때에 $A^m \vec{v}$의 방향이 고유 벡터 $\vec{v}_1$와 벗어나는 정도는 $A$를 한번 곱할 때마다 $\left| \lambda_2 / \lambda_1 \right| < 1$ 배만큼 줄어든다.

일단 $\vec{v}_1$을 찾은 후에는 그 방향의 성분을 가지지 않는 벡터를 잡아서 (즉, $c_1 = 0$) 마찬가지로 $A$를 곱해가면 두 번째로 큰 고유값과 그에 해당하는 고유 벡터를 구할 수 있다.

QR 알고리듬

• David S. Watkins, Understanding the QR algorithm, SIAM Review 24, 427 (1982).