22. Diagonalization and Powers of A

 

 

고유값에 대한 두 번째 강의입니다. 첫 번째 강의에서 핵심은 $Ax = \lambda x$ 였습니다. 여기서 $x$는 고유벡터이고 람다는 고유값입니다. 고유벡터와 고유값을 구한 다음 무엇을 해야할까요?

 

이것들을 잘 사용하는 방법 중 하나가 행렬의 대각화 입니다. 고유값과 고유벡터를 알면 행렬의 중요한 특성을 알 수 있는데 그 중 하나가 행렬의 대각화입니다.

 

$S^{-1}AS = \Lambda$  ($\Lambda$는 대각행렬로 원소는 고유값으로 이루어져있습니다.) 

 

이 식은 대각화에 대한 식입니다. 행렬 S는 A의 고유벡터들을 열에 가지고 있는 고유벡터 행렬입니다. 이 고유벡터 행렬은 가역행렬이여야 합니다. 즉 A의 고유벡터들로 이루어진 행렬 S가 가역행렬이여야 하니 A의 고유벡터들이 전부 선형독립이여야 합니다.

 

 

A가 n개의 독립 고유벡터를 가지고 있다고 해보겠습니다. 그러면 $AS$는 고유벡터와 A를 곱하는 형태가 됩니다. 

 

$AS =  A\left[\begin{matrix} | & | & & | \\ x_1 & x_2 & ... & x_n \\ | & | & & | \end{matrix} \right] = $ $\left[\begin{matrix} | & | & & | \\ \lambda_1 x_1 & \lambda_2 x_2 & ... & \lambda_n x_n \\ | & | & & | \end{matrix} \right] $

$= \left[\begin{matrix} | & | & & | \\ x_1 & x_2 & ... & x_n \\ | & | & & | \end{matrix} \right] \left[\begin{matrix} \lambda_1 & 0 & ... & 0 \\ 0 & \lambda_2 & ... & 0 \\ : & : & : & : \\ 0&0& ... & \lambda_n \end{matrix} \right] = S \Lambda$

 

왜 갑자기 식에 고유값이 포함됬을까요?  

$AS_1$ (A곱하기 S의 1열)은 $Ax_1$으로 쓸 수 있습니다. 여기서 $Ax = \Lambda x$이므로 $Ax_1 = \Lambda_1 x_1$

 

그러면 다음과 같이 표현이 가능해집니다.

 

$AS = S \Lambda$

$S^{-1}AS = S^{-1}S \Lambda$

$S^{-1}AS = \Lambda$

 

A만 남겨둘 수도 있습니다.

    - $A = S \Lambda S^{-1}$

 

그리고 $Ax = \lambda x$면

    - $A^2x = \lambda Ax = \lambda^2 x$ ($A^2$이 $\lambda ^2$이 될 수 있다.)

 

마지막으로 $A$를 제곱하면

    - $A^2 = S \Lambda S^{-1} S \Lambda S^{-1} = S \Lambda^2S^{-1}$

 

$A$의 제곱이 고유값 행렬 $\Lambda$에 영향을 주는 것을 알 수 있습니다. 행렬 $A$를 고유값 행렬과 고유벡터 행렬로 분해하면 조금 더 쉽게 $A$의 거듭제곱을 계산할 수 있습니다.

 

 

대각화는 A가 독립적인 n개의 고유벡터를 가지고 반복되는 고유값이 없는 경우 성립하게 됩니다.

고유값이 다른 경우는 n개의 독립적인 고유벡터를 갖습니다. 고유값이 중복되는 경우는 n개의 독립적인 고유벡터를 가질 수도 있고 가지지 않을 수도 있습니다. 

 

 

ex) $2 \times 2$ 단위행렬이 존재한다고 해보겠습니다. 이 행렬의 고유값은 무엇일까요? (고유값은 1이고 2번 반복)

 

$A = \left[\begin{matrix} 1 & 0 \\ 0& 1  \end{matrix} \right]$

 

$det$ $(A - \lambda) =$ $\begin{vmatrix} 1-\lambda & 0 \\ 0 & 1 - \lambda  \notag \end{vmatrix} =$ $(1 -  \lambda)^2 = 0$ ,   $\lambda_1 = 1$,   $\lambda_2 = 1$

 

$(A - \lambda I)x = 0$

 

$\left[\begin{matrix} 0 & 0 \\ 0 & 0  \end{matrix} \right] \left[\begin{matrix} x_1 \\ x_2  \end{matrix} \right] = $ $\left[\begin{matrix} 0  \\ 0   \end{matrix} \right]$

 

이렇게 되면

 

$\lambda_1$일 때 고유벡터는 $\left[\begin{matrix} 1 \\ 0 \end{matrix} \right]$

 

$\lambda_2$일 때 고유벡터는 $\left[\begin{matrix} 0 \\ 1 \end{matrix} \right]$

 

고유값이 중복되더라도 독립적인 고유벡터가 나올 수 있다! (단위행렬이 대표적인 예시)

 

 

 

고유값이 반복됬을 때 n개의 독립 벡터가 없는 경우에 대해서 알아보자 

 

$A = \left[\begin{matrix} 2 & 1 \\ 0 & 2  \end{matrix} \right]$

 

$det$ $(A - \lambda) =$ $\begin{vmatrix} 2-\lambda & 1 \\ 0 & 2 - \lambda  \notag \end{vmatrix} =$ $(2 -  \lambda)^2 = 0$ ,   $\lambda_1 = 2$,   $\lambda_2 = 2$

 

$\lambda_1$일 때 고유벡터는 $\left[\begin{matrix} 1 \\ 0 \end{matrix} \right]$

 

$\lambda_2$일 때 고유벡터는 존재하지 않습니다. (대각화가 불가능!)

 

 

$|\lambda| < 1$ 일때 $A^k \rightarrow$ as $k \rightarrow \infty$

- 모든 고유값의 절대값이 1보다 작을 때 A를 거듭제곱하면 0으로 수렴하게 됩니다. (고유값들의 상태를 보고 거듭제곱의 결과를 어느정도 예측할 수 있다.)

 

 

대각화의 또 다른 장점은 방정식을 쉽게 풀 수 있는 것입니다. 시간이 지남에 따라 변화하는 문제인 계차방정식 (difference equation)이 그 대표적인 예시입니다.

 

 

---

계차방정식과 미분방정식의 차이는?

미분의 시간은 연속적인 개념이고 계차의 시간은 이산적입니다. (시간을 정수 단위로 끊어서 생각함) 

 

Difference equation: $a_{n+1}-a_n = a_{n-1}$,   Differential equation: $\frac {dy} {dx} = y$

 

여기서 n이 커질 때 미지수의 증가폭, 감소폭을 알아내는 것이 목표입니다. (이것을 대각화를 통해 알아낼 수 있습니다.)

---

 

$u_{k+1} = A u_k$, A를 $u_k$에 곱해서 $u_{k+1}$을 얻을 수 있는 계차방정식이 존재한다고 하겠습니다. A를 100번 곱하면 어떤 결과가 나올까요?

 

$u_1 = A u_0$,  $u_2 = A^2 u_0$

즉 $u_k = A^k u_0$ 라는 관계가 성립한다는 것을 통해서 쉽게 k번째 값을 구할 수 있습니다.

 

$u$는 A의 고유벡터들의 선형결합으로 표현할 수 있습니다. (또는 고유벡터 행렬 S에 상수 c를 곱해서 표현할 수 있다.)

즉 $u = cA = cS$가 될 수 있다는 것입니다. (A가 n차원에서 독립적인 고유벡터를 n개 가지고 있을 때)

 

 

 

$u_0 = c_1x_1 + c_2x_2 + ... c_nx_n$  (x는 A의 고유벡터) 

 

여기다가 $A$를 곱하면, $Ax = \Lambda x$가 되니까 고유값 행렬과의 연산으로 바꿀 수 있다.

 

$Au_0 = c_1Ax_1 + c_2Ax_2 + ... c_nAx_n +$

$= c_1 \lambda_1 x_1 + c_2 \lambda_2 x_2 + ... c_n \lambda_n x_n +$

 

초기 벡터에 A를 곱하면 원하는 순서의 벡터를 얻을 수 있지만 대각화를 이용하면 이 계차방정식의 k값에 따른 미지수 증가폭을 찾을 수 있습니다. (계차방정식을 풀 수 있다.)

 

 

ex) 피보나치 수열

 

0, 1, 1, 2, 3, 5 ... 이때 100번째 숫자는 무엇일까?

 

- 얼마나 빨리 성장하는지를 어떻게 알 수 있을까? (고유값에 정답이 있다.)

- 일정한 성장치가 아니라 성장의 폭이 존재하는 방정식에 대해서 풀 수 있다.

 

피보나치 수열은 다음과 같이 계산이 됩니다.

$F_{k+2} = F_{k+1} + F_k$

 

이것을 $u_{k+1} = Au_k$로 바꿔써보겠습니다. u벡터를 두 개의 원소를 가진 벡터로 바꿔보겠습니다.

 

$u_k = \left[\begin{matrix} F_{k+1}  \\ F_k  \end{matrix} \right]$

 

$u_{k+1} = \left[\begin{matrix} 1 & 1  \\ 1 & 0  \end{matrix} \right]^A u_k = Au_k$

 

이 연산을 통해서 $F_{k+1} + F_k = F_{k+2}$로 다음 번 벡터를 출력할 수 있습니다. 2차 스칼라 문제를 u벡터에 두 개의 원소를 주어서 1차 시스템으로 변경한 것입니다. 이제 고유값과 고유벡터로 A와 u를 바꿔주면 됩니다.

 

$A = \left[\begin{matrix} 1 & 1  \\ 1 & 0  \end{matrix} \right]$

 

$|A - \lambda I| = \begin{vmatrix} 1-\lambda & 1 \\ 1 &  - \lambda  \notag \end{vmatrix}$ $= \lambda^2 - \lambda - 1$,  근의 공식을 적용해보면

 

$\lambda = \frac {1 \pm \sqrt{1 + 4} } {2}$

 

$\lambda_1 = \frac 12 (1 + \sqrt{5} ) \approx 1.618...$

$\lambda_2 = \frac 12 (1 - \sqrt{5} ) \approx -0.618...$

 

음수의 경우 1보다 작아서 거듭제곱을 여러 번 할 경우 0에 가까워집니다. 두 고유값이 다르니 대각화가 가능합니다.

 

$u_{100} = A^{100}u_k$

$A^{100}u_0 = c_1 \frac 12 (1 + \sqrt{5} ) x_1 + c_2 \frac 12 (1 - \sqrt{5} ) x_2$

$= c_1 \lambda^{100}_1 x_1 + c_2 \lambda^{100}_2 x_2$ (각각 람다 1, 람다 2를 대입하면 됩니다.)

 

$det$ (A - \lambda I), 즉 행렬 A의 고유값에 대한 A의 특성방정식을 만드는게 핵심입니다. 특성방정식을 만들고 나면  행렬이 수행하는 작업에 대한 특성을 알 수 있게됩니다.

 

$F_{k+2} = F_{k+1} + F_k$

$\lambda^2 - \lambda - 1$

 

피보나치 수열에 대한 특성이 다음과 같이 들어난다는 사실을 알 수 있습니다.

 

이제 고유벡터에 대해서 알아보겠습니다.

 

$(A - \lambda I)x =0$ 

 

$\left[\begin{matrix} 1-\lambda & 1 \\ 1 &  - \lambda\end{matrix} \right] $$\left[\begin{matrix} \lambda \\ 1 \end{matrix} \right] = \left[\begin{matrix} 0 \\ 0 \end{matrix} \right]$

 

$\left[\begin{matrix} \lambda^2 - \lambda - 1 \\  \lambda - \lambda  \end{matrix} \right] $$ = \left[\begin{matrix} 0 \\ 0 \end{matrix} \right]$

 

$x_1 = \left[\begin{matrix} \lambda \\ 1 \end{matrix} \right] = $ $\left[\begin{matrix} \frac 12 (1 + \sqrt{5} )  \\ 1 \end{matrix} \right] $, $x_2 = \left[\begin{matrix} \lambda \\ 1 \end{matrix} \right] = $ $\left[\begin{matrix} \frac 12 (1 - \sqrt{5} )  \\ 1 \end{matrix} \right] $

 

고유값과 고유벡터를 찾았습니다. 마지막으로 찾을 파라미터는 계수 c입니다. 초기 벡터 $u_0$으로 찾아보겠습니다. 그러면 $A^0$이 되니 고유값이 0이 되어 고유벡터와 계수만 남게됩니다. 

 

$u_0 = A^0u_0$ 

 

$A^0u_0 = c_1 \lambda_1^0 x_1 + c_2 \lambda^0_2 x_2$

$= c_1 x_1 + c_2 x_2$

$= \left[\begin{matrix} \frac 12 (1 + \sqrt{5} ) & \frac 12 (1 - \sqrt{5} ) \\ 1 & 1   \end{matrix} \right] \left[\begin{matrix} c_1 \\ c_2   \end{matrix} \right] =$ $\left[\begin{matrix} 1 \\ 0   \end{matrix} \right]$

 

이제 가우스 소거법을 진행해보겠습니다.

 

$ \left[\begin{matrix} 1 & \frac 12 (-3 + \sqrt{5} ) \\ 0 &  \frac 12 (5 - \sqrt{5} )   \end{matrix} \right] \left[\begin{matrix} c_1 \\ c_2   \end{matrix} \right] =$ $\left[\begin{matrix}  \frac 12 (-1 + \sqrt{5} ) \\  \frac 12 (1 - \sqrt{5} )  \end{matrix} \right]$

 

$c_1 =  \frac { \sqrt{5}} {5}$, $c_2 =  \frac {- \sqrt{5}} {5}$