Differences

This shows you the differences between two versions of the page.

--- 전산물리학:qr_알고리듬 [2016/05/20 16:25] – admin
+++ 전산물리학:qr_알고리듬 [2023/09/05 15:46] (current) – external edit 127.0.0.1
@@ Line 5: / Line 5: @@
 [[:수학:그람-슈미트 방법]]을 행렬로 표현한 것이다.
 예컨대 크기 $n \times n$인 실수 대칭행렬 $A$를 생각해보자:
-$$\left(
+$$A = \left(
 \begin{array}{cccc}
 \vdots & \vdots & \vdots & \vdots\\
@@ Line 12: / Line 12: @@
 \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*}
+이다. 이를 행렬로 정리해보면
+$$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)
+=
+\left( \begin{array}{cccc}
+\vdots & \vdots & \vdots & \vdots\\
+\vec{q}_0 & \vec{q}_1 & \vec{q}_2 & \vdots\\
+\vdots & \vdots & \vdots & \vdots
+\end{array} \right)
+\left( \begin{array}{cccc}
+\left| \vec{u}_0 \right| & \vec{q}_0 \cdot \vec{a}_1 & \vec{q}_0 \cdot \vec{a}_2 & \cdots\\
+& \left| \vec{u}_1 \right| & \vec{q}_1 \cdot \vec{a}_2 & \cdots\\
+& 0 & \left| \vec{u}_2 \right| & \cdots
+\end{array} \right) = Q~R.
+$$
+이 때 $\vec{q}_i \cdot \vec{q}_j = \delta_{ij}$이므로 $Q$는 직교행렬이고 ($Q^T Q = I$), $R$은 대각선 아래 원소가 모두 $0$인 상삼각행렬임에 유의.
 ======작동법======
+주어진 행렬 $A$를 QR 분해한다: $A = Q_1 R_1$. 즉, $R_1 = Q_1^T A$.
+이제 순서를 뒤집어서 새로운 행렬 $A_1 = R_1 Q_1$을 만든다. 위에서 구한 $R_1$을 대입하면, $A_1 = Q_1^T A Q_1$이다.
+이를 다시 QR 분해한다: $A_1 = Q_2 R_2$. 즉, $R_2 = Q_2^T A_1$.
+다시 순서를 뒤집어서 새로운 행렬 $A_2 = R_2 Q_2$를 만든다. 풀어서 적으면
+$$A_2 = R_2 Q_2 = Q_2^T A_1 Q_2 = Q_2^T Q_1^T A Q_1 Q_2.$$
+이를 $k$번 반복하면,
+$$A_k = \left( Q_k^T \ldots Q_1^T \right) A \left( Q_1 \ldots Q_k \right).$$
+$\hat{Q} = (Q_1 \ldots Q_k)$가 직교행렬임은 쉽게 확인할 수 있다:
+$$\hat{Q}^T \hat{Q} = \left(Q_k^T \ldots Q_1^T \right) \left(Q_1 \ldots Q_k \right) = I.$$
+직교 행렬에 의한 변환은 고유치를 바꾸지 않아서 $A_k = \hat{Q}^T A \hat{Q}$의 고유치는 원래 행렬과 동일하고, 이 고유치들은 $k$가 무한대로 가는 극한에서 $A_k$의 대각선상에 위치한다. 수식으로 적어보면:
+$$A = \hat{Q} A_\infty \hat{Q}^T =
+\left( \begin{array}{ccc}
+\vdots & \vdots & \vdots\\
+\vec{v}_0 & \vec{v}_1 & \vdots\\
+\vdots & \vdots & \vdots
+\end{array} \right)
+\left( \begin{array}{ccc}
+\lambda_0 & & \\
+& \lambda_1 & \\
+& & \ddots
+\end{array} \right)
+\left( \begin{array}{ccc}
+\cdots & \vec{v}_0 & \cdots\\
+\cdots & \vec{v}_1 & \cdots\\
+\cdots & \cdots & \cdots
+\end{array} \right).
+$$
+위에서의 표기법처럼 $\lambda_i$는 $i$ 번째 고유값, $\vec{v}_i$는 그에 해당하는 고유 벡터이다.
+곱해진 세 개의 행렬 중 첫 번째는 $\vec{v}_i$들을 열 벡터로,
+마지막 행렬은 행 벡터로 가지고 있다.
 ======설명======
+$A$의 $i$ 번째 고유치가 $\lambda_i$, 그에 해당하는 고유 벡터가 $\vec{v}_i$라고 하자:
+$$A \vec{v}_i = \lambda_i \vec{v}_i.$$
+편의상 $\left| \lambda_0 \right| > \left| \lambda_1 \right| > \ldots$로 정렬되어 있다고 하자.
+$A=Q_1 R_1$일 때에 이로부터 유도되는 또다른 행렬이 $A_1 = R_1 Q_1 = Q_2 R_2$라고 했으므로
+$$A^2 = Q_1 R_1 Q_1 R_1 = Q_1 Q_2 R_2 R_1$$
+임을 알 수 있다. 일반적으로
+$$A^n = \left( Q_1 \ldots Q_n \right) \left( R_n \ldots R_1 \right) = \hat{Q} \hat{R}$$
+이 성립한다.
+[[:전산물리학:멱 방법]]에 의하면, 임의의 벡터 $\vec{u}$가 있을 때 $A^n \vec{u}$는 $A$의 가장 큰 고유치 $\lambda_0$에 해당하는 고유 벡터 $\vec{v}_0$ 방향으로 수렴한다.
+\begin{eqnarray*}
+\vec{u} &=& a_0 \vec{v}_0 + a_1 \vec{v}_1 + \ldots\\
+A^n \vec{u} &=& a_0 \lambda_0^n \vec{v}_0 + a_1 \lambda_1^n \vec{v}_1 + \ldots
+\end{eqnarray*}
+임의의 $\vec{u}$에 대해 이 성질이 성립한다는 것은 $A^n$의 열들이 이미 $\vec{v}_0$와 유사한 방향임을 의미한다.
+$A^n = \hat{Q} \hat{R}$로 분해했을 때, 그람-슈미트 방법에 따라 $\hat{Q}$의 첫 번째 벡터 $\vec{q}_0$는 $A^n$의 첫 번째 열 벡터와 같은 방향이다. 즉 $\vec{q}_0$는 $\vec{v}_0$에 해당한다.
+그람-슈미트 방법을 따라 $A^n$의 열들로부터 이미 찾은 벡터들과 직교하는 공간을 생각하면 $\vec{q}_1, \vec{q}_2, \ldots$를 얻는다. 이는
+$$A^n \vec{u} = a_0 \lambda_0^n \vec{v}_0 + a_1 \lambda_1^n \vec{v}_1 + a_2 \lambda_2^n \vec{v}_2 + \ldots$$
+에서 $0 = a_0 = a_1 = \ldots$에 해당하고 따라서 그 때마다 $\vec{v}_1, \vec{v}_2,\ldots$들을 근사적으로 얻게 된다.
 ======함께 보기======