Applicate_Matrix_in_Recursion

Posted on Edited on In Word count in article: 1.3k Reading time ≈ 1 mins.

矩阵变换求解线性递归关系

0x1.矩阵变换求解线性递归关系

问题：对于线性递归函数f(x)，计算f(N)，其中N是大数。

以斐波那契数列f(i)=f(i-1)+f(i-2)为例。

分4步求解：

  1. 确定K，对于任意M>K，都有f(i)与f(i-K)无关

f(i)=f(i-1)+f(i-2)，因此K=2

  1. 确定初始变量F1

f(1)=1,f(2)=1,初始变量为[1,1]

  1. 确定变换矩阵T,使对于任意i，有

假设有,则T为

T=[0,1],[1,1]

  1. 确定Fn

1
2
3
4
a=matrix([1,1]).transpose()
for i in range(10):
    a=matrix([[0,1],[1,1]])*a 
    print(a.transpose())

0x2. 欧几里得算法&扩展欧几里得

  1. 递推公式

  1. 初始变量：M=[x,y]
  2. 变换矩阵

  1. Fn

同时注意到，由于最后有 因此有，即扩展欧几里得算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ext = matrix([[1,0],[0,1]])
x_ = matrix([0,0]).transpose()

def uclid(mat):
    global ext,x_  
    x,y = mat[0],mat[1] 
    print('x,y=',x,y)
    q = floor(x/y)
    print('q=',q) 
    
    m = matrix([[0,1],[1,-q]])
    mat = m * mat 
    ext = m * ext 
    if mat[1] == x_[0]:

        print('mat=',mat)
        return mat[0]
               
    else:
        uclid(mat) 

a = matrix([1997,615]).transpose() 

mat=uclid(a)
print('mat=',mat)
print('ext=',ext)