선형대수(HYU)_19-20 차분방정식과 고유값

5.3 Difference Equations and Powers $A^k$

Differnece equation

수열의 일반항 사이의 관계식

$$\begin{gathered} u_{k+1}=A{u}_k \\ {u}_k=A^k{u}_k \end{gathered}$$

• finite 한 수의 finite 한 step으로 진행되는 equation.
• 무한한 수의 극소 단계로 진행되는 'differential equation'과 다르다.

Exmaples

1. 등차
   $$\begin{gathered} a_{n+2}-2a_{n+1}+a_n=0 \\ {a}_n=a_1+(n-1)d \end{gathered}$$
2. 계차
   $$\begin{array}{rl}p{a}_{n+2}+q{a}_{n+1}+r{a}_n& =0,(p+q+r=0)\\ p{a}_{n+2}-(p+r)a_{n+1}+r{a}_n& =0\\ p(a_{n+2}-a_{n+1})& =r(a_{n-1}+a_n)\\ b_{n_1}=\frac{r}{p}{b}_n& \to a_n=a_1+\sum _{k=1}^{n-1}{b}_k\end{array}$$
3. general case
   $$\begin{gathered} p{a}_{n+2}+q{a}_{n+1}+r{a}_n=0,(p+q+r\ne 0) \\ {a}_n=c_1({\alpha }_1{)}^2+c_2({\alpha }_2{)}^2 \end{gathered}$$

Fibonacci Numbers

---

$$\text{Fibonacci numbers}0,1,1,2,3,5,8,13$$

$$\text{Fibonacci equations}{F}_{k+2}=F_{k+1}+F_k$$

'1000'번째 Fibonacci number을 0과 1부터 시작해서 일일히 더해나가지 않고 구하기 위해서는 위의 difference equation의 해를 구해야 한다.

우선 위의 Fibonacci equation을

• one-step equation인 $u_{k+1}=A{u}_k$로 나타낼 수 있다.
• 각 step은 $u_k=(F_{k+1},F_k)$ 로 나타낼 수 있다.

$$\begin{array}{rl}{F}_{k+2}& =F_{k+1}+F_k\\ F_{k+1}& =F_{k+1}\end{array}becomes{u}_{k+1}=\left[\begin{array}{c}{F}_{k+2}\\ F_{k+1}\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_{k+1}\\ F_k\end{array}\right]=A{u}_k$$

one-step system $u_{k+1}=A{u}_k$ 는 $u_0$ 에서 시작해서 각 step마다 $A$를 곱한 것과 같다.

$$\begin{array}{rl}{u}_1& =A{u}_0\\ u_2& =A{u}_1=A^2{u}_0\\ ⋮& \\ u_{k+1}& =A{u}_k=A^{k+1}{u}_0\end{array}$$

difference equation의 $u_{k+1}=A{u}_k$의 solution은 $u_k=A^k{u}_0$ 이다.

실제로 문제가 되는 것은 $A^k$를 계산하는 것이다.

$A$가 $A=S\mathrm{\Lambda }{S}^{-1}$로 diagonalized 될 수 있다면

$$u_k=A^k{u}_0=(S\mathrm{\Lambda }{S}^{-1})(S\mathrm{\Lambda }{S}^{-1})\cdots (S\mathrm{\Lambda }{S}^{-1})u_0=S{\mathrm{\Lambda }}^k{S}^{-1}{u}_0$$

이므로 $S^{-1}{u}_0=c$ 로 나타내면 solution은 다음과 같다.

$$u_k=S{\mathrm{\Lambda }}^{k}c=\left[\begin{array}{c}\\ x_1& \cdots & x_n\\ \end{array}\right]\left[\begin{array}{ccc}{\lambda }_1^k& & \\ & \ddots & \\ & & {\lambda }_n^k\end{array}\right]\left[\begin{array}{c}{c}_1\\ ⋮\\ c_n\end{array}\right]=c_1{\lambda }_1^k{x}_1+\cdots +c_n{\lambda }_n^k{x}_n$$

First step을 이용해서 eigenvalue를 구할 수 있다.

$$
A-\lambda I =
$$\left[\begin{array}{cc}1-\lambda & 1\\ 1& -\lambda \end{array}\right]$$
\quad has \quad
det(A-\lambda I)=\lambda^2 - \lambda - 1 \

\text{Two eigenvalues} \quad \lambda_1 = {1+\sqrt{5}\over 2} \quad and \quad \lambda_2 = {1-\sqrt{5}\over 2}
$$

$A-\lambda I$의 second row가 $(1,-\lambda )$ 이므로, eigenvector는 $x=(\lambda ,1)$ 이다. $u_0$는 첫 두 Fibonacci number $F_0=0$, $F_1=1$ 이므로

$$S^{-1}{u}_0={\left[\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right]}^{-1}\left[\begin{array}{c}1\\ 0\end{array}\right]givesc=\left[\begin{array}{c}1/({\lambda }_1-{\lambda }_2)\\ -1/({\lambda }_1-{\lambda }_2)\end{array}\right]=\frac{1}{\sqrt{5}}\left[\begin{array}{c}1\\ -1\end{array}\right]$$

위의 $c$가 $u_k=c_1{\lambda }_1^k{x}_1+c_2{\lambda }_2^k{x}_2$의 constant이다. 두 eigenvector $x_1$, $x_2$ 모두 second component는 1이므로,

$$F_k=\frac{1}{\sqrt{5}}[{\left(\frac{1+\sqrt{5}}{2}\right)}^k-{\left(\frac{1-\sqrt{5}}{2}\right)}^k]$$

결과적으로 1000번째 Fibonacci number는
$$F_{1000}=\text{nearest integer to }\frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^{1000}$$

Characteristic Equation (강의 추가내용)

$$\text{Fibonacci equations}{F}_{k+2}=F_{k+1}+F_k$$

Fibonacci equation에서 $F_k{\lambda }^k$ 라고 가정하면,

$$\begin{gathered} F_{k+2}-F_{k+1}-F_k=0 \\ {\lambda }^{k+2}-{\lambda }^{k+1}-{\lambda }^k=0 \end{gathered}$$

$${\lambda }^2-\lambda -1=0$$

으로 정리할 수 있는데 이를 characteristic equation 이라고 하고 식으로부터 구한 근이 eigenvalue와 같다.

$${\lambda }_1=\frac{1+\sqrt{5}}{2}and{\lambda }_2=\frac{1-\sqrt{5}}{2}$$

대입하면 $F_k$는 다음과 같이 나타낼 수 있고,

$$\begin{array}{rl}{F}_k& =c_1{\lambda }_1^k+c_2{\lambda }_2^k\\ & =c_1{\left(\frac{1+\sqrt{5}}{2}\right)}^k-c_2{\left(\frac{1-\sqrt{5}}{2}\right)}^k\end{array}$$

$F_0=0$, $F_1=1$ 을 이용해서 $c_1$, $c_2$를 구하면 $F_k$를 완성할 수 있다.

만약 characteristic equation의 eigenvalue가 multiple root이면 solution은 다음과 같은 형태가 된다.

• Double root: $F_k=c_1(\lambda {)}^n+c_{2}n(\lambda {)}^n$
• Triple root: $F_k=c_1(\lambda {)}^n+c_{2}n(\lambda {)}^n+c_3{n}^2(\lambda {)}^n$

Least square Problem (강의 추가내용)

앞서 배운 least square problem에서,

$$Ax=b\left[\begin{array}{ccc}& & \\ & & \\ & A& \\ & & \\ & & \end{array}\right]\left[\begin{array}{c}\\ x\\ \end{array}\right]=\left[\begin{array}{c}\\ \\ b\\ \\ \end{array}\right]$$

least square solution을 구하면 다음과 같다.

$$\begin{array}{rl}{A}^{T}Ax& =A^{T}b\\ x& =(A^{T}A{)}^{-1}{A}^{T}b\\ J(x)& =min\Vert Ax-b{\Vert }^2\end{array}$$

다만 위 식은 $b=0$일 때 (i.e., $Ax=0$) 이용할 수 없다.

• 이처럼 $b=0$인 경우를 homogeneous equation,
• 아닌 경우 (i.e., $b\ne 0$) non-homogeneous equation 이라고 한다.

Homogeneous equation의 least square solution을 구하기 위해서 $\Vert Ax{\Vert }^2$ 계산해보면,

$$\Vert Ax{\Vert }^2=(Ax{)}^T(Ax)=x^T{A}^{T}Ax$$

$(A^{T}A)x=\lambda x$ 를 만족하는 $x$가 존재하면

$$x^T{A}^{T}Ax=x^T\lambda x=\lambda \Vert x{\Vert }^2$$

보다 편한 계산을 위해 $\Vert x{\Vert }^2=1$ 이라고 가정하면 (constraint)

$$\Vert Ax{\Vert }^2=\lambda$$

로 $\lambda$ 가 minimum이 되는 (A^TA)의 eigenvector $x$가 least square solution이 된다.

• eigenvalue of $A^{T}A$: error
• eigenvector of $A^{T}A$: least square solution
• $A^{T}A$의 eigenvalue는 error 값이므로 항상 0보다 크거나 같다. (i.e., $\lambda \ge 0$)

위에서 임의로 지정한 constraint를 고려해서 minimum을 계산할 수도 있다.

$$J(x,\lambda )=\Vert Ax{\Vert }^2+\lambda (1-\Vert x{\Vert }^2)$$

위 식에서 ($\partial J/\partial x)\to 0$, ($\partial J/\partial \lambda )\to 0$ 가 되는 값을 구하면 된다.

Particular solution (강의 추가내용)

$p{a}_{n+2}+q{a}_{n+1}+r{a}_n\ne 0$ 인 경우도 solution을 구할 수 있다.

예를 들어, 다음 식의 경우

$$p{a}_{n+2}+q{a}_{n+1}+r{a}_n=2{\left(\frac{1}{2}\right)}^n$$

solution은 다음과 같이 나타낸다.

$$c\{p{\left(\frac{1}{2}\right)}^{n+2}+q{\left(\frac{1}{2}\right)}^{n+1}+r{\left(\frac{1}{2}\right)}^n\}=2{\left(\frac{1}{2}\right)}^n$$

정리해서 주어진 $p,q,r$에 대해 $c$를 구하면 particular solution을 구할 수 있다.
$$c(\frac{p}{4}+\frac{q}{2}+r)=2$$

Homogeneous solution과 particular solution을 더하면 General solution을 구할 수 있다.

Markov Matrices

---

Markov Matrix는 상태가 변하는 확률 (state transition probability)에 대한 matrix이다.

예를 들어 다음과 같은 상황일 때,

매년마다 California 밖의 사람중 $\frac{1}{10}$이 California로 들어오고 California 안의 사람중 $\frac{2}{10}$이 California 밖으로 나간다. California 밖의 사람은 $y_0$, 안의 사람들은 $z_0$명에서 시작한다.

첫 해가 끝날 때 California 밖과 안의 사람은 다음과 같이 나타낼 수 있다.
$$\begin{array}{rl}& \text{Difference}\\ & \text{equation}\end{array}\begin{array}{r}{y}_1=.9y_0+.2z_0\\ z_1=.1y_0+.8z_0\end{array}or\left[\begin{array}{c}{y}_1\\ z_1\end{array}\right]=\left[\begin{array}{cc}.9& .2\\ .1& .8\end{array}\right]\left[\begin{array}{c}{y}_0\\ z_0\end{array}\right]$$

위의 예시와 예시의 matrix는 Markov process의 두 가지 중요한 성질을 보여준다.

1. 사람의 수 전체는 유지된다: Markov matri의 각 column의 entry를 더하면 1이 된다.
2. 안과 밖의 사람 수는 negative가 될 수 없다: Matrix는 negative entry를 갖지 않는다.

$u_k=S{\mathrm{\Lambda }}^k{S}^{-1}{u}_0$를 이용해서 Markov difference equation을 풀 수 있다.

$$u_k=\left[\begin{array}{cc}{e}_1& e_2\end{array}\right]\left[\begin{array}{cc}{\lambda }_1^k& \\ & {\lambda }_2^k\end{array}\right]\left[\begin{array}{c}{c}_1\\ c_2\end{array}\right],\left[\begin{array}{c}{y}_k\\ z_k\end{array}\right]=c_1{\lambda }_1^k{e}_1+c_2{\lambda }_2^k{e}_2$$

또한 state transition이 장기화 될 때, population이 'steady state'에 도달하는 것을 보일 수 있다.

우선 $A$를 diagonalize 하면

$$\begin{array}{r}A-\lambda I=\left[\begin{array}{cc}.9-\lambda & .2\\ .1& .8-\lambda \end{array}\right]hasdet(A-\lambda I)={\lambda }^2-1.7\lambda +.7\\ {\lambda }_1=1and{\lambda }_2=.7:A=S\mathrm{\Lambda }{S}^{-1}=\left[\begin{array}{cc}\frac{2}{3}& \frac{1}{3}\\ \frac{1}{3}& -\frac{1}{3}\end{array}\right]\left[\begin{array}{cc}1& \\ & .7\end{array}\right]\left[\begin{array}{cc}1& 1\\ 1& -2\end{array}\right]\end{array}$$

$k$년 후의 distribution은
$$\begin{array}{rl}\left[\begin{array}{c}{y}_k\\ z_k\end{array}\right]& =A^k\left[\begin{array}{c}{y}_0\\ z_0\end{array}\right]=\left[\begin{array}{cc}\frac{2}{3}& \frac{1}{3}\\ \frac{1}{3}& -\frac{1}{3}\end{array}\right]\left[\begin{array}{cc}{1}^k& \\ & {.7}^k\end{array}\right]\left[\begin{array}{cc}1& 1\\ 1& -2\end{array}\right]\left[\begin{array}{c}{y}_0\\ z_0\end{array}\right]\\ & =(y_0+z_0)\left[\begin{array}{c}\frac{2}{3}\\ \frac{1}{3}\end{array}\right]+(y_0-2z_0)\left[\begin{array}{c}\frac{1}{3}\\ -\frac{1}{3}\end{array}\right]\end{array}$$

오랜 시간이 지날수록 ($k$가 커질수록) $(.7{)}^k$가 매우 작아진다.

오랜 시간이 지나 limiting state에 도달한 solution $u_{\mathrm{\infty }}=(y_{\mathrm{\infty }},z_{\mathrm{\infty }})$는
$$\text{Steady state}\left[\begin{array}{c}{y}_{\mathrm{\infty }}\\ z_{\mathrm{\infty }}\end{array}\right]=(y_0+z_0)\left[\begin{array}{c}\frac{2}{3}\\ \frac{1}{3}\end{array}\right]$$

마지막에는 (in the limit) 전체 인구의 $\frac{2}{3}$은 California 밖에, $\frac{1}{3}$은 안에 있게된다. 첫 해가 시작할 때, 인구수의 $\frac{2}{3}$이 밖에 $\frac{1}{3}$이 안에 있다면 매번 같은 인구수를 유지하게 된다.

$$\left[\begin{array}{cc}.9& .2\\ .1& .8\end{array}\right]\left[\begin{array}{c}\frac{2}{3}\\ \frac{1}{3}\end{array}\right]=\left[\begin{array}{c}\frac{2}{3}\\ \frac{1}{3}\end{array}\right]orA{u}_{\mathrm{\infty }}=u_{\mathrm{\infty }}$$

이 때, Steady state는 $\lambda =1$에 상응하는 $A$의 eigenvector이다. $A$를 곱해 다음 step으로 넘어가도 $u_{\mathrm{\infty }}$는 바뀌지 않는다.

위의 예시에서 볼 수 있는 Markov process의 theory는:

모든 $a_{ij}\ge 0$를 갖고 각 column의 entry를 더하면 1이되는 Markov matrix $A$에 대해

1. ${\lambda }_1=1$은 $A$의 eigenvalue이다.
2. 그것의 eigenvector $x_1$는 nonnegative이고, 이 eigenvector는 $A{x}_1=x_1$인 steady state이다.
3. 다른 eigenvalue들은 $\Vert {\lambda }_i\Vert \le 1$을 만족한다.
4. $A$나 $A$의 $k$제곱이 모두 positive entry를 가지면 다른 $|{\lambda }_i|$는 1보다 작다.
5. $A^k{u}_0$는 $x_1$의 상수 배로 접근하며 이는 steady state $u_{\mathrm{\infty }}$이다.

Stability of $u_{k+1}=A{u}_k$

---

Fibonacci number과 Markov process의 차이점

• Fibonacci number $F_k$는 점점 커지므로 Fibonacci equation은 unstable하다.
• Markov equation의 각 stage를 더하면 1이 되므로 Markov process는 neutrally stable 하다.

$k\to \mathrm{\infty }$일 때, $u_{k+1}=A{u}_k$의 behavior를 살펴보면

• $A$는 diagonalizable
• $u_k$는 combination of pure solution이라 가정

$$\text{Solution at time k}{u}_k=S{\mathrm{\Lambda }}^k{S}^{-1}{u}_0=c_1{\lambda }_1^k{x}_1+\cdots +c_n{\lambda }_n^k{x}_n$$

위 식에서 $u_k$의 grouwth는 ${\lambda }_i^k$에 의해 결정된다.

즉, Stability는 eigenvalue에 의해 결정된다:

Difference equation $u_{k+1}=A{u}_k$는

• 모든 eigenvalue가 $|{\lambda }_i|<1$을 만족하면 stable
• 몇몇 eigenvalue는 $|{\lambda }_i|=1$이고 나머지는 $|{\lambda }_i|<1$이면 neutrally stable
• 최소 하나의 eigenvalue라도 $|{\lambda }_i|>1$ 이면 unstable

Positive Matrices and Applications in Economics

---

강의에서 다루지 않음