QR 분해를 이용한 고유값 분석 알고리듬.

그람-슈미트 방법을 행렬로 표현한 것이다. 예컨대 크기 $n \times n$인 실수 대칭행렬 $A$를 생각해보자: $$\left( \begin{array}{cccc} \vdots & \vdots & \vdots & \vdots\\ \vec{a}_0 & \vec{a}_1 & \vec{a}_2 & \vdots\\ \vdots & \vdots & \vdots & \vdots \end{array} \right)$$ $A$가 가지고 있는 열 벡터 $\vec{a}_0, \vec{a}_1, \vec{a}_2, \ldots$로부터 서로 직교하는 정규화된 벡터 $\vec{q}_0, \vec{q}_1, \vec{q}_2, \ldots$를 만들어내고자 한다. 즉 $\vec{q}_i \cdot \vec{q}_j = \delta_{ij}$이며 이 때에 $\delta_{ij}$는 크로네커 델타이다.

그람-슈미트 방법에 따르면 아래의 방식으로 그러한 $\left\{ \vec{q}_i \right\}$를 찾을 수 있다: $$\begin{array}{cc} \vec{u}_0 = \vec{a}_0 & \vec{q}_0 = \vec{u}_0/\left| \vec{u}_0 \right|\\ \vec{u}_1 = \vec{a}_1 - \left( \vec{q}_0 \cdot \vec{a}_1 \right)\vec{q}_0 & \vec{q}_1 = \vec{u}_1/\left| \vec{u}_1 \right|\\ \vec{u}_2 = \vec{a}_2 - \left( \vec{q}_0 \cdot \vec{a}_2 \right)\vec{q}_0 - \left( \vec{q}_1 \cdot \vec{a}_2 \right)\vec{q}_1 & \vec{q}_2 = \vec{u}_2/\left| \vec{u}_2 \right| \end{array}$$

식을 다시 정리하면 \begin{eqnarray*} \vec{a}_0 &=& \left| \vec{u}_0 \right| \vec{q}_0\\ \vec{a}_1 &=& \left| \vec{u}_1 \right| \vec{q}_1 + \left( \vec{q}_0 \cdot \vec{a}_1 \right)\vec{q}_0\\ \vec{a}_2 &=& \left| \vec{u}_0 \right| \vec{q}_0 + \left( \vec{q}_0 \cdot \vec{a}_2 \right)\vec{q}_0 + \left( \vec{q}_1 \cdot \vec{a}_2 \right)\vec{q}_1 \end{eqnarray*}

멱 방법

• David S. Watkins, Understanding the QR algorithm, SIAM Review 24, 427 (1982).
• Mark Newman, Computational Physics (2013).