你好,欢迎来到经管之家 [登录] [注册]

设为首页 | 经管之家首页 | 收藏本站

递推关系的解法研究_数学与应用数学论文范文

发布时间:2014-05-09 来源:人大经济论坛
数学与应用数学论文范文 字数:3283 递推关系的解法研究 [摘 要] 递推关系是组合论中的重要内容,几乎在一切数学分支中都有应用,如何解递推关系,又是递推关系中的重要问题,事实上并没有一般法则能使我们解出所有的递推关系,我们只是对极少数的几类递推关系得到一般解法。递推关系可以用普通的迭加方法,公式法以及生成函数法研究。 [关键词] 递推关系、斐波那契递归、线性齐次递推关系、非齐次递推关系、生成函数 递推关系是组合论中的重要内容,几乎在一切数学分支中都有应用,如何解递推关系,又是递推关系中的重要问题,事实上并没有一般法则能使我们解出所有的递推关系,一、简单的递推关系: 算术序列,hn=hn-1+q. 几何序列,hn=h(n-1)q. 可以用普通的迭加方法 满足递推关系和初始条件 fn=fn-1+ fn-2 (n≥2) f0=0, f1=1 的数列 f0, f1,f2,f3,…叫做斐波那契序列,序列的项叫做斐波那契数,式中的递推关系叫做斐波那契递归。 现在的目标是得到斐波那契数的公式,并为此叙述求解递推关系的技巧, 考虑在形式 Fn-fn-1-fn-2=0 (n≥2) 下斐波那契递推关系,先忽略f0 和f1的初始值。解决这个递推关系的一种方法是寻找形式为 fn=qn 的一个解,其中q是一个非零数。因此,在第一项等于q0=1 的几何序列种寻找一个解。我们观察到,fn=qn满足斐波那契递推关系当且仅当 qn-qn-1-qn-2=0 或等价地 qn-2(q2-q-1)=0 (n=2,3,4,......) 由于假设q异于零,我们断言fn=qn是斐波那契递推关系的解当且仅当q2-q-1=0 和 两者都是斐波那契递推关系的解。由于斐波那契递推关系是线性的和齐次的。通过直接计算得到 对于任意选择的常数和,上式也是递推关系的解 二、线性齐次递推关系 令 h0,h1,h2,…,hn,… (1) 是一个数列。如果存在量A1,a2,…,ak, ak≠0和量bn(每一个量都可能依赖于n)的 hn=a1hn-1+a2hn-2+…+akhn-k+bn(n≥k) (2) 则称该数列满足k阶线性递推关系. 解常系数线性齐次递推关系,即如 hn=a1hn-1+a2hn-2+…+akhn-k (n≥k) (3) 其中A1,a2,…,ak是常数且ak≠0的递推关系的一种特殊方法。 递推关系可以重写为形式 hn-a1hn-1-a2hn-2-…-akhn-k=0 (n≥k)  (4) 一旦所谓的初始值即H0,h1,h2,…,hn,…能够给出,则满足递推关系(或更一般地,满足(2)的数列) h0,h1,h2,…,hn,…就被唯一的确定。递推关系(74)从n=k开始“解开”。忽略初始值并在没有给出初始值,通过考虑那些形成几何序列的解并通过适当的修改它们来找到“足够”的解 线性齐次递推关系的求解,可按照离散函数所采用的与指数函数的作用类似的方法进行,其中,只对非负整数n(有几何序列)有定义. 定理: 令q为一非零数。则Hn 是常系数线性齐次递推关系 Hn-a1hn-1-a2hn-2-…-akhn-k=0 (ak≠0,n≥k) (5) 的解,当且仅当qn是多项式方程 Xk-a1xk-1-a2xk-2―...―ak=0 (6) 的一个根。如果多项式方程有k个不同的根q1,q2,.....,qk, 则 Hn=c1qn1+c2q2n+ ....... +ckqnk (7) 是下述意义下式(5)的一般解:无论给定h0,h1,....,hk-1什么初始值,都存在常数c1,c2,.....ck,使得公式(7)是满足递推关系(5)和初始条件的唯一的序列。 多项式方程(6)叫做递推关系(5)的特征方程,而它的k个根叫做特征根。根据定理,如果特征根互异,那么式(7)就是式(5)的一般解。 例 求解满足初始值H0=1,h1=2和h2=0,和的递推关系 Hn= 2hn-1+hn-2-2hn-3 (n≥3)
经管之家“学道会”小程序
  • 扫码加入“考研学习笔记群”
推荐阅读
经济学相关文章
标签云
经管之家精彩文章推荐