Linear Algebra with Sage

<Recurrence Relations>


Made by SKKU Linear Algebra Lab (2011)



The sequence @@x_n@@ of Fibonacci numbers is defined by the recurrence relation.

@@x_{n+2}=x_{n+1}+x_{n}, x_{0}=0, x_{1}=1@@ 

And a system of linear equations that describes the Fibonacci sequence is

@@\begin{pmatrix} x_{n+1} \\ x_{n} \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} x_{n} \\ x_{n-1} \end{pmatrix}@@.  

(이런 경우 Fibonacci sequence에 대응하는 행렬의 고유값과 고유벡터를 이용하여 @@x_n@@ 에 대한 일반식을 구할 수 있다.)

We can compute @@x_{10}@@ and @@x_{11}@@ easily using the matrix @@A@@.

Consider @@\begin{pmatrix} x_{11} \\ x_{10} \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} x_{10} \\ x_{9} \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{10}\begin{pmatrix} x_{1} \\ x_{0} \end{pmatrix}@@

(@@D=P^{-1}AP@@ 이면 @@D^{10}=P^{-1}A^{10}P@@이므로 @@PD^{10}P^{-1}=A^{10}@@를 이용하여 @@A^{10}@@을 구한다.)


Define a matrix @@A@@and a vector @@x_{0}@@. (행렬 @@A@@와 벡터 @@x_{0}@@를 생성한다.)

A=matrix(QQ,2,2,[1,1,1,0]);

x0=vector(QQ,[1,0]);


Find eigenvectors of @@A@@.(@@A@@의 고유벡터를 구한다.)

ev=A.eigenvectors_right(); ev

[(-0.618033988749895?, [(1, -1.618033988749895?)], 1),

(1.618033988749895?, [(1, 0.618033988749895?)], 1)]


Find a matrix @@P@@ and its inverse. (행렬 @@A@@를 대각화하는 행렬 @@P@@를 구하고 그 역행렬을 구한다.)

P=matrix([ev[0][1][0],ev[1][1][0]]).transpose();

PI=P.inverse();

P, PI

( [                  1                   1]

  [-1.618033988749895?  0.618033988749895?],

[ 0.2763932022500211? -0.4472135954999580?]

[ 0.7236067977499790?  0.4472135954999580?] )


Diagonalize the matrix @@A@@. (행렬 @@A@@를 대각화한다.)

D=PI*A*P; D

[-0.618033988749895?             0.?e-18]

[            0.?e-18  1.618033988749895?]


We can compute @@x_{10}@@and @@x_{11}@@easily using the matrix @@D@@. (행렬 @@D@@를 이용하여 @@x_{10}@@과 @@x_{11}@@를 구할 수 있다.)

P*(D^10)*PI*x0

(89.0000000000000?, 55.00000000000000?)



Conclusion : 같은 방법으로 어떤 Recurrence relation 도   @@x_{n}=Ax_{n-1}=A^{n}x_{0}@@로 표현하면  위와 같이 행렬의 대각화를 아용하여 같은 방법으로 일반항을 쉽게 구할 수 있다.