한 항과 그 다음 항들간의 관계를 식으로 나타낸 것을, 점화식이라고 알고 있다.
점화식으로부터 일련의 과정을 통해 그 일반항을 구하는 것이 가능한데, 여기서는 행렬의 관점에서 점화식을 푸는 방법을 포스팅할 예정이다.
방법
점화식을 행렬로 푸는 원리는, 아래의 식으로 설명될 수 있다.
$$u_{k} = A^{k}u_{0} = S\Lambda^{k}S^{-1}u_{0}$$
이때, S의 역행렬에 u의 첫항을 곱한 것을 c로 표현한다면, 식은 아래와 같은 형태로 변형된다.
$$= c_{1}\lambda_{1}^{k}\left[\begin{matrix}e_{1}\end{matrix}\right] + c_{2}\lambda_{2}^{k}\left[\begin{matrix}e_{2}\end{matrix}\right] + ...$$
즉, u의 k 번째 항을 eigen vector들의 선형결합으로 표현한 형태가 된다.
정리하면,
$$\sum_{i}c_{i}(\lambda_{i})^{k}\left[\begin{matrix}e_{i}\end{matrix}\right]$$
피보나치 수열
위의 방법을 활용해 피보나치수열의 일반항을 구해보자.
주어진 점화식은 다음과 같다.
$$F_{k+2} = F_{k+1}+F_{k} \ (k = 0, 1, 2, ...)$$
일반항 F_k를 구하는 것이 목표다. 순서대로 따라가보자
1) 점화식을 u_(k+1) = A u_(k)의 꼴로 만들기
$$u_{k+1} = \left[\begin{matrix}F_{k+2}\\F_{k+1}\end{matrix}\right] = \left[\begin{matrix}F_{k+1}+F_{k}\\F_{k+1}\end{matrix}\right] = \left[\begin{matrix}1&1\\1&0\end{matrix}\right]\left[\begin{matrix}F_{k+1}\\F_{k}\end{matrix}\right]$$
u의 k 번째 항이 다음과 같은 꼴로 만들어짐을 확인하자.
$$u_{k} = A^{k}u_{0}$$
$$\left[\begin{matrix}F_{k+1}\\F_{k}\end{matrix}\right] = \left[\begin{matrix}1&1\\1&0\end{matrix}\right]^{k} \left[\begin{matrix}1\\0\end{matrix}\right]$$
2) A의 eigen values, eigen vectors 구하기
위에서 설명한 방법에 따라, 대각화를 위해 A의 eigen 요소들을 구해야 한다.
$$A^{k}u_{0} = S\Lambda^{k}S^{-1}u_{0}$$
계산하면, 다음과 같은 형태가 나올 것이다.
$$\lambda_{1}, \lambda_{2}, e_{1} = \left[\begin{matrix}\lambda_{1}\\1\end{matrix}\right], e_{2} = \left[\begin{matrix}\lambda_{2}\\1\end{matrix}\right]$$
3) 선형결합의 형태로 일반항 구하기
구한 eigen vector들의 선형결합으로 u의 일반항을 구해보자.
$$u_{k} = c_{1}\lambda_{1}^{k}\left[\begin{matrix}|\\e_{1}\\|\end{matrix}\right] + c_{2}\lambda_{2}^{k}\left[\begin{matrix}|\\e_{2}\\|\end{matrix}\right]+...$$
4) F의 일반항 구하기
구한 u의 일반항으로부터 F_k를 구하면 끝이다.
Markov Matrix
선형결합을 활용해 점화식을 푸는 또다른 예시 중 하나는 Markove Matrix이다.
아래와 같은 두 식에서부터 y, z의 일반항을 구하자.
$$y_{1} = 0.9 y_{0} + 0.2 z_{0}$$
$$z_{1} = 0.1 y_{0} + 0.8 z_{0}$$
식을 행렬로 표현하면 다음과 같다.
$$u_{k+1} = \left[\begin{matrix}y_{k+1}\\z_{k+1}\end{matrix}\right] = \left[\begin{matrix}0.9&0.2\\ 0.1&0.8\end{matrix}\right] \left[\begin{matrix}y_{k}\\z_{k}\end{matrix}\right]$$
마찬가지로, 위 방법을 활용해 일반항을 구해볼 것이다.
1) 점화식을 u_(k+1) = A u_(k)의 꼴로 만들기
2) A의 eigen values, eigen vectors 구하기
위에서 설명한 방법에 따라, 대각화를 위해 A의 eigen 요소들을 구해야 한다.
$$A^{k}u_{0} = S\Lambda^{k}S^{-1}u_{0}$$
계산하면, 다음과 같은 형태가 나올 것이다.
$$\lambda_{1} = 1, \lambda_{2} =0.7$$
$$e_{1} = \left[\begin{matrix}2\\1\end{matrix}\right], e_{2} = \left[\begin{matrix}1\\-1\end{matrix}\right]$$
3) 선형결합의 형태로, 일반항 구하기
$$u_{k} = c_{1}\lambda_{1}^{k}\left[\begin{matrix}|\\e_{1}\\|\end{matrix}\right] + c_{2}\lambda_{2}^{k}\left[\begin{matrix}|\\e_{2}\\|\end{matrix}\right]+...$$
4) k가 무한대가 될 때, 일반항이 수렴하는지 확인하기
k가 늘어남에 따라, 일반항도 함께 늘어나는 것이 아니라 수렴할 수 있다.
Markov Matrix의 Properties
위 예시에서 사용했던 두 식과 비교하면서, 아래 마르코브 행렬의 특징을 익혀보자.
1. 열 방향의 요소를 더하면 1이다.
2. 각 계수는 0 이상, 1 미만이다.
3. eigen value 중 최소 하나는 1이며, 나머지는 1보다 작다.
'수학 > 선형대수' 카테고리의 다른 글
| Unity Matrix & Homogeneous Least Square (0) | 2022.02.02 |
|---|---|
| Complex Matrix와 Hermite Matrix (0) | 2022.01.28 |
| Eigen Value & Eigen Vectors (0) | 2022.01.23 |
| Determinant의 활용 (0) | 2022.01.20 |
| Determinant의 성질들 (0) | 2022.01.20 |