如何在Python中解决递归关系 [英] How to solve recurrence relations in Python

问题描述

我正在尝试编写代码以为递归关系提供数值答案.该关系本身很简单，定义如下.变量x是整数

I am trying to write code to give numerical answers to a recurrence relation. The relation itself is simple and is defined as follows. The variable x is an integer

如果i＞ 0且i ＜p，则p(i)＝ p(i + 2)/2 + p(i-1)/2. x
• p(0)= p(2)/2
如果我> = x ，
• p(i)= 1

• p(i) = p(i+2)/2 + p(i-1)/2 if i > 0 and i < x
• p(0) = p(2)/2
• p(i) = 1 if i >= x

这也在此代码中.

from __future__ import division
def p(i):
    if (i == 0):
        return p(2)/2
    if (i >= x):
        return 1
    return p(i-1)/2+p(i+2)/2


x = 4
#We would like to print p(0)  for example.

当然，这实际上并不会让您计算p(0).您如何在python中做到这一点?

This of course doesn't actually let you compute p(0). How can you do this in python?

是否有可能建立一个numpy.linalg.solve然后可以求解的联立方程组?

Is it possible to set up a system of simultaneous equations which numpy.linalg.solve can then solve?

推荐答案

很正确，可以使用线性代数解决.我在下面所做的是一个简单的硬编码翻译.通过重新排列p(0)至p(3)的公式，将其编码为右手边为=0.对于以递归关系出现在基例中的p(4)和p(5)，在右侧有一个=1.

You're right this can be solved using linear algebra. What I've done below is a simple hard-coded translation. Your equations for p(0) to p(3) are coded up by rearranging them so that the right hand side is =0. For p(4) and p(5) which appear in the recurrence relations as base cases, there is an =1 on the right hand side.

• -p(0) + p(2)/2 = 0

p(i-1)/2 - p(i) + p(i+2)/2 = 0对于i> 0和i< x

p(i-1)/2 - p(i) + p(i+2)/2 = 0 for i > 0 and i < x

p(i) = 1如果i> = x

这是为n=4

import numpy
a=numpy.array([[-1,   0, 0.5,  0,   0,   0], # 0
               [0.5, -1,   0,0.5,   0,   0], # 1
               [0,  0.5,  -1,  0, 0.5,   0], # 2
               [0,    0, 0.5, -1,   0, 0.5], # 3
               [0,    0,   0,  0,   1,   0], # 4
               [0,    0,   0,  0,   0,   1], # 5
              ])
b=numpy.array([0,0,0,0,1,1])
# solve ax=b
x = numpy.linalg.solve(a, b)
print x

Edit ，这是以编程方式构造矩阵的代码，仅针对n=4进行了测试！

Edit, here is the code which constructs the matrix programmatically, only tested for n=4!

n = 4

# construct a
diag = [-1]*n + [1]*2
lowdiag = [0.5]*(n-1) + [0]*2
updiag = [0.5]*n
a=numpy.diag(diag) + numpy.diag(lowdiag, -1) + numpy.diag(updiag, 2)

# solve ax=b
b=numpy.array([0]*n + [1]*2)
x = numpy.linalg.solve(a, b)

print a
print x[:n]

这将输出

[[-1.   0.   0.5  0.   0.   0. ]
 [ 0.5 -1.   0.   0.5  0.   0. ]
 [ 0.   0.5 -1.   0.   0.5  0. ]
 [ 0.   0.   0.5 -1.   0.   0.5]
 [ 0.   0.   0.   0.   1.   0. ]
 [ 0.   0.   0.   0.   0.   1. ]]
[ 0.41666667  0.66666667  0.83333333  0.91666667]

与问题中您评论中的解决方案相符.

which matches the solution in your comment under your question.

这篇关于如何在Python中解决递归关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！