J & J - 정성태의 닷넷 이야기

사용자

메뉴

최근 덧글

[tree soap] 아차! f는 기억이 나는데, m은 ㅜㅜ 감사합니다!!! ^...[정성태] 'm'은 decimal 타입의 숫자에 붙는 접미사입니다. ...[정성태] https://lxr.sourceforge.io/ http...[정성태] VT sequences to "CONOUT$" vs. STD_O...[정성태] NetCoreDbg is a managed code debugg...[정성태] Evaluating tail call elimination in...[정성태] What’s new in System.Text.Json in ....[정성태] What's new in .NET 9: Cryptography ...[정성태] 아... 제시해 주신 "https://akrzemi1.wordp...[정성태] 다시 질문을 정리할 필요가 있을 것 같습니다. 제가 본문에...

글쓰기

제목

이름

암호

전자우편

HTML

홈페이지

유형

내용

<div style='display: inline'>
<h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>행렬로 바라보는 피보나치 수열</h1>
<p>
다음의 책을 보니 재미있는 내용이 있습니다. ^^<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
프로그래머를 위한 선형대수
; <a target='tab' href='http://www.yes24.com/24/goods/39446808'>http://www.yes24.com/24/goods/39446808</a>

(평을 보시면 아시겠지만, 저 역시 추천하고 싶은 책입니다. ^^)
</pre>
<br />
249페이지에 보면 "자기회귀모델(AR: AutoRegressive)"의 이산시간에 대한 예로,<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
오늘의 ζ(t)는 어제의 ζ(t - 1), 이틀 전의 ζ(t - 2), 사흘 전의 ζ(t - 3)과 오늘의 u(t)에 따라 다음과 같이 정해진다.

ζ(t) = -0.5ζ(t - 1) + 0.34ζ(t - 2) + 0.08ζ(t - 3) + 2u(t)

초기 조건 ζ(0) = 0.78, ζ(-1) = 0.8, ζ(-2) = 1.5
</pre>
<br />
소개가 되면서 다음과 같이 행렬 표현을 합니다.<br />
<br />
<div style='border: 1px solid black; padding: 10px'>
<script type="math/tex">
    x(t) = \begin{pmatrix}-0.5 & 0.34 & 0.08 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} x(t - 1), \quad \quad  x(0) = \begin{pmatrix}0.78 \\ 0.8 \\ 1.5 \end{pmatrix}
</script><br />
</div><br />
<br />
저걸 보니, 피보나치 수열이 생각났습니다.<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
황금비율 증명 - 피보나치 수와 연분수의 관계
; <a target='tab' href='http://www.sysnet.pe.kr/2/0/1312'>http://www.sysnet.pe.kr/2/0/1312</a>
</pre>
<br />
역시 초깃값이 주어지고 x(t)는 x(t - 1)에 의해 결정되니까요. 따라서 위와 같은 기준으로 피보나치 수열을 바라보면 다음과 같이 정리가 됩니다.<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
ζ(t) = 1ζ(t - 1) + 1ζ(t - 2)

초기 조건 ζ(0) = 1, ζ(-1) = 0
</pre>
<br />
간단하게 t = 1 ~ 4까지 테스트하면 이렇게 되고,<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
t = 1일 때, ζ(1) = ζ(1 - 1) + ζ(1 - 2) = ζ(0) + ζ(-1) = 1 + 0 = 1
t = 2일 때, ζ(2) = ζ(2 - 1) + ζ(2 - 2) = ζ(1) + ζ(0) = 1 + 1 = 2
t = 3일 때, ζ(3) = ζ(3 - 1) + ζ(3 - 2) = ζ(2) + ζ(1) = 2 + 1 = 3
t = 4일 때, ζ(4) = ζ(4 - 1) + ζ(4 - 2) = ζ(3) + ζ(2) = 3 + 2 = 5
</pre>
<br />
이를 행렬로 표현하면 다음과 같습니다.<br />
<br />
<div style='border: 1px solid black; padding: 10px'>
<script type="math/tex">
    x(t) = \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix} x(t - 1), \quad \quad  x(0) = \begin{pmatrix}1 \\ 0 \end{pmatrix}
</script><br />
</div><br />
<br />
마찬가지로 t = 1 ~ 4까지에 대해 행렬로 계산하면 이렇게 됩니다.<br />
<br />
<div style='border: 1px solid black; padding: 10px'>
<script type="math/tex">
\textrm{t = 1, } \quad \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix}1 \\ 0 \end{pmatrix}
</script><br />
<br />
<script type="math/tex">
\textrm{t = 2, } \quad \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix}1 \\ 0 \end{pmatrix}
</script><br />
<br />
<script type="math/tex">
\textrm{t = 3, } \quad \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix}1 \\ 0 \end{pmatrix}
</script><br />
<br />
따라서 (초깃값 2개를 넘어) n 번째 피보나치 수열은,<br />
<br />
<script type="math/tex">
\textrm{t = n, } \quad \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix}^n  \begin{pmatrix}1 \\ 0 \end{pmatrix}
</script><br />
</div><br />
<br />
보는 바와 같이 행렬 [1 1; 1 0]에 대해 n 승을 하고 그 값을 [1 0] 행렬에 곱하면 n 번째 피보나치 수열이 구해지는 것입니다. 실제로 octave 같은 도구를 이용해 다음과 같이 행렬 계산을 바로 해볼 수 있습니다.<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
function fib_1()
  
a = [1 1; 1 0]
b = [1;0]
a ^ 1 * b
a ^ 2 * b
a ^ 3 * b
a ^ 4 * b
a ^ 5 * b

endfunction
</pre>
<br />
위의 함수를 실행하면 2*1 행렬이 5개가 출력되는 데 그것의 첫 번째 원소들을 보면 1, 2, 3, 5, 8로 피보나치 수열이 나옵니다.<br />
<br />
<hr style='width: 50%' /><br />
<br />
행렬로 표현된 피보나치 계산에서 고윳값/고유벡터를 이용해 풀어보면 재미있는 결과가 나옵니다. <br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
[선형대수학 #3] 고유값과 고유벡터 (eigenvalue &amp; eigenvector)
; <a target='tab' href='http://darkpgmr.tistory.com/105'>http://darkpgmr.tistory.com/105</a>
</pre>
<br />
행렬 [1 1; 1 0]에 대한 고윳값, 고유벡터를 계산해 보면,<br />
<br />
<div style='border: 1px solid black; padding: 10px'>
<script type="math/tex">
    det(A - \lambda E) = det(\begin{vmatrix}1 & 1 \\ 1 & 0 \end{vmatrix} - \lambda \begin{vmatrix}1 & 0 \\ 0 & 1 \end{vmatrix})
</script><br />
<script type="math/tex">
    = \begin{vmatrix}1 - \lambda & 1 \\ 1 & 0 - \lambda \end{vmatrix}
</script><br />
<br />
위의 행렬식을 구하면,<br />
<br />
    = (1 - &#955;)(0 - &#955;) - 1<br />
    = &#955;<sup>2</sup> - &#955; -1 <br />
</div><br />
<br />
위와 같이 구한 특성 다항식을 특성 방정식에 따라 0 값이 나오는 해를 구하면,<br />
<br />
<div style='border: 1px solid black; padding: 10px'>
    det(A - &#955; E) = 0<br />
    <br />
    &#955;<sup>2</sup> - &#955; -1 = 0<br />
<br />
근의 공식에 따라,<br />
<br />
<script type="math/tex">
    x=\frac{-b\pm\sqrt{b^2-4 a c}}{2 a}
</script><br />
<br />
<script type="math/tex">
    x=\frac{1\pm\sqrt{5}}{2} \approx -0.61803, +1.61803
</script><br />
</div><br />
<br />
와 같이 계산됩니다. 고윳값을 구했으니 고유벡터까지 구해볼까요? ^^<br />
<br />
<div style='border: 1px solid black; padding: 10px'>
<script type="math/tex">
\begin{pmatrix}1 - \lambda & 1 \\ 1 & 0 - \lambda \end{pmatrix}  \begin{pmatrix}v_x \\ v_y \end{pmatrix} = \begin{pmatrix}0 \\ 0 \end{pmatrix}
</script><br />
<br />
연립 방정식으로 풀으면,<br />
<br />
(1 - &#955;)v<sub>x</sub> + v<sub>y</sub> = 0<br />
v<sub>x</sub> - &#955;v<sub>y</sub> = 0<br />
v<sub>x</sub> = &#955;v<sub>y</sub> <br />
<br />
따라서, v<sub>x</sub>가 v<sub>y</sub>의 &#955;배로 이뤄진 무수히 많은 벡터 = [&#955;t, t]<br />
</div><br />
<br />
그럼 고유 벡터를 아무거나 다음과 같이 선정할 수 있습니다.<br />
<br />
<div style='border: 1px solid black; padding: 10px'>
<script type="math/tex">
    \begin{pmatrix}\lambda \\ 1 \end{pmatrix}
</script><br />
<br />
따라서 고윳값 &#955;의 2가지 값에 대해,<br />
<br />
<script type="math/tex">
    \begin{pmatrix}\frac{1+\sqrt{5}}{2} \\ 1 \end{pmatrix}
</script><br />
<br />
<script type="math/tex">
    \begin{pmatrix}\frac{1-\sqrt{5}}{2} \\ 1 \end{pmatrix}
</script><br />
</div><br />
<br />
이 중에서 고유 벡터를 [(1 + sqrt(5)) / 2, 1]인 쌍으로 골라 보겠습니다. 이를 다시  Gram-Schmidt 정규 직교로 바꾸면,<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
Matlab/Octave로 Gram-Schmidt 정규 직교 집합 구하는 방법
; <a target='tab' href='http://www.sysnet.pe.kr/2/0/11235'>http://www.sysnet.pe.kr/2/0/11235</a>
</pre>
<br />
(0.52573, -0.85065), (-0.85065, -0.52573)로 구할 수 있습니다. 즉, 이 2개의 벡터 각각에 대응하는 &#955;배의 모든 벡터들이 고유 벡터들이 됩니다.<br />
<br />
<hr style='width: 50%' /><br />
<br />
실제로 위의 과정들을 간단하게 octave로 구할 수 있습니다.<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
a = [1 1; 1 0]
[ev, ei] = eig(a)

ev = 
    0.52573 -0.85065
   -0.85065 -0.52573

ei =

Diagonal Matrix

-0.61803   0
   0          1.61803
</pre>
<br />
또한, Av = &#955;v인 것도 다음과 같이 쉽게 계산해볼 수 있습니다.<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
a * [0.52573, -0.85065]'
ans =

-0.32492
   0.52573
</pre>
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
-0.61803 * [0.52573 -0.85065]'
ans =

-0.32492
   0.52573
</pre>
<br />
<hr style='width: 50%' /><br />
<br />
피보나치 수열의 고윳값과 고유벡터를 구했으니 n 번째 값을 구하는 방법에 대해 행렬의 성질로 다시 살펴보겠습니다.<br />
<br />
"<a target='tab' href='http://darkpgmr.tistory.com/105'>[선형대수학 #3] 고유값과 고유벡터 (eigenvalue &amp; eigenvector)</a>" 글에 보면 다음과 같은 공식이 나옵니다.<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
A = 행렬
P = 행렬 A의 고유벡터들을 열벡터로 하는 행렬
&#923; = 교윳값들을 대각 원소로 하는 대각 행렬

AP = P&#923;
A = P&#923;P<sup>-1</sup>
</pre>
<br />
이를 기반으로 A의 n 승을 다음과 같이 쉽게 구할 수 있는 방법을 포함하고 있습니다.<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
A<sup>k</sup> = (P&#923;P<sup>-1</sup>)<sup>k</sup>
   = (P&#923;P<sup>-1</sup>)(P&#923;P<sup>-1</sup>)......(P&#923;P<sup>-1</sup>)
   = P&#923;<sup>k</sup>P<sup>-1</sup>
   = Pdiag(&#955;<sup>k</sup><sub>1</sub>,......,&#955;<sup>k</sup><sub>n</sub>)P<sup>-1</sup>
</pre>
<br />
따라서, 가령 5번째 피보나치 수를 구하고 싶다면 고유 벡터와 그것의 역행렬만 구한 후 고윳값 2개를 대각 행렬로 갖는 것만 5 승을 해주면 되는 것입니다. 이것을 octave로 다음과 같이 테스트할 수 있습니다.<br />
<br />
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
ev * ei ^ 5 * inverse(ev)
ans =

8.0000  5.0000
    5.0000  3.0000
</pre>
<br />
즉, 고윳값을 알기 전에는 다음과 같은 행렬 계산이었지만,<br />
<br />
<div style='border: 1px solid black; padding: 10px'>
<script type="math/tex">
\textrm{t = n, } \quad \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix}^n  \begin{pmatrix}1 \\ 0 \end{pmatrix}
</script><br />
</div><br />
<br />
고윳값을 알게 된 이상, 그것은 대각행렬의 n 승으로 바뀌었기 때문에 단순히 스칼라 값인 고윳값 2개만 n 승을 해주면 되는 문제로 바뀐 것입니다.<br />
</p><br />

<br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span>

</div>

첨부파일

스팸 방지용 인증 번호

3099 (왼쪽의 숫자를 입력해야 합니다.)