下载文档原格式
二阶常系数递推关系求解方法一、递推关系的定义与性质在数学中，递推关系是指通过递推公式来描述数列中各项之间的关系。
常系数递推关系是指递推关系中各项的系数都是常数。
设有一个序列 {an}，其中 n 表示序列中的项数。
如果序列满足递推关系 an = c1an-1+ c2an-2 + ... + ck an-k ，其中ci (1 ≤ i ≤ k) 为常数，那么我们称该序列满足一个 k 阶常系数递推关系。
常系数递推关系的性质：1. 齐次性：如果一个递推关系的非齐次项为0，即对于所有的 i，ci = 0，则该递推关系称为齐次线性递推关系。
2. 非齐次性：如果一个递推关系的非齐次项不为0，即存在一些 i，ci ≠ 0，则该递推关系称为非齐次线性递推关系。
3.初值条件：对于一个k阶线性递推关系，需要给出前k项的初值条件才能确定整个序列。
二、求解齐次线性递推关系的通解对于线性递推关系 an = c1an-1+ c2an-2 + ... + ck an-k ，其中ci (1 ≤ i ≤ k) 为常数，我们可以采用特征根法求解其通解。
1. 假设通解为an = λn ，将其代入递推关系，得到λ^n = c1λ^(n-1)+ c2λ^(n-2) + ... + ck λ^(n-k)2.将等式左边的λ^n移至等式右边，得到λ^n - c1λ^(n-1) - c2λ^(n-2) - ... - ck λ^(n-k) = 03.将该齐次方程转化为特征方程，即λ^k - c1λ^(k-1) - c2λ^(k-2) - ... - ck = 04.解特征方程，得到k个实数或复数根λ1,λ2,...,λk。
5.得到齐次线性递推关系的通解为an = A1λ1^n + A2λ2^n + ... + Akλk^n其中A1,A2,...,Ak为待定系数。
通过给定的初值条件，可以使用线性方程组求解方法来确定待定系数A1,A2,...,Ak。
三、求解非齐次线性递推关系的通解对于非齐次线性递推关系 an = c1an-1+ c2an-2 + ... + ck an-k + f(n)，其中 f(n) 为一个关于 n 的函数，我们可以采用常数变易法求解其通解。
零化多项式特征多项式最⼩多项式常系数线性齐次递推零化多项式/特征多项式/最⼩多项式/常系数线性齐次递推约定:I n是n阶单位矩阵，即主对⾓线是1的n阶矩阵⼀个矩阵A的|A|是A的⾏列式默认A是⼀个n×n的矩阵定义零化多项式:对于⼀个矩阵A，它的⼀个零化多项式f(λ)是满⾜f(A)=0的多项式，定义域包含矩阵最⼩多项式:次数最低的零化多项式特征多项式对于⼀个n阶的矩阵A，它的特征多项式p(λ)=|λI n−A|λ定义域不⽌是R，还可以是矩阵p(λ)是关于λ的⼀个不超过n+1次的多项式即p(λ)=∑n0a i x iCayley-Hamilton定理:矩阵的特征多项式也是它的零化多项式求解特征多项式带⼊n个数，求出得|xI n−A|,得到n个矩阵，通过⾼斯消元可以O(n3)地求出⾏列式然后可O(n2)拉格朗⽇插值求出原来的多项式，总复杂度受限于⾼斯消元，为O(n4)求解最⼩多项式构造矩阵序列a i=A i求出它的⼀个线性递推r i，即m∑j=0r j a i−j=m∑j=0r j A i−j=(m∑j=0r m−j A j)⋅A i−m=0∴m∑j=0r m−j A j=0所以可以由r i翻转得到f(λ)求解a i前n项的复杂度受限于矩阵乘法为O(n4)，求解递推式的复杂度为O(n3)考虑到实际求解递推式时，随机⽣成了两个向量u,v实际是计算标量序列{uA i v}的递推式，所以实际每次求出uA i复杂度应为O(n2)求这个递推式需要⽤到a i前2n项，求解复杂度为O(n3)因此总复杂度为O(n3)(但是如果只是求出来并没有什么⽤，因为求解⽅法是随机的，甚⾄连检查⼀次保证正确都需要O(n2(n+e))的时间(e为矩阵⾮0位置个数))求解稀疏⽅程组设⽅程系数⽤矩阵A表⽰，右侧每个⽅程的常数⽤向量b表⽰，答案⽤向量x表⽰，则满⾜关系式Ax=b，即x=A−1b求出{A i b}线性递推式，反推出A−1b即可反推⽅法:带⼊线性递推的m项，则∑m i=0A m−i b⋅r i=0A m−i br i=0两边同乘A−1，得到A−1b⋅r m+∑m−1i=0求解矩阵k次幂我们要求解A k，常规做法是直接⽤快速幂设矩阵A的⼀个零化多项式是f(λ)显然，A k可以⽤⼀个多项式表⽰A k=∑k0w i A i{w i}构成了⼀个k+1次多项式F k(x)存在⼀种合法的表⽰是F k(x)=x k∵f(A)=0∴∀i,f(A)A i=0也就是相当于我们要求出x k对于f(x)这个n+1多项式取模显然可以通过类似快速幂的⽅式倍增求解这个多项式，每次对f(x)取模复杂度是O(n log n)就能在O(n log m log n)时间得求出F(x)最后得到的F(x)是⼀个n次多项式那么带⼊就可以快速求出A k可以认为这个复杂度是受限于求解A0,A1,⋯,A n−1的O(n4)对于元矩阵A为稀疏矩阵的情况，设其包含e个⾮零位置那么求解B⋅A的过程是O(n⋅e)的，求解A0,A1,⋯,A n−1的过程，是O(n2e)的求解零化多项式的复杂度也是O(n2(n+e))的，因此总复杂度为O(n2(n+e))⽽⼀般的矩阵快速幂是O(n3log k)的，这种⽅法适⽤情况⾮常特殊另外，对于并不需要知道整个矩阵的答案，并且A0,A1,⋯,A n−1特殊的具体问题，这个⽅法也⼗分有效求解常系数线性齐次递推问题是要求数列f i=∑n j=1a j⋅f i−j给出f0,f1,⋯,f n−1，求第k项的值线性递推显然可以⽤初始向量列与转移矩阵的幂次的乘积表⽰，即f i=(S⋅A i)n，其中A为转移矩阵，S为初始向量列，我们求的是第n项对于n=4的情况，我们的转移矩阵A是12341a 421a 331a 241a 1鉴于它的特殊性，我们可以直接求出它的特征多项式表达式由λI n −A =12341λ−a 42−1λ−a 33−1λ−a 24−1λ−a 1带⼊⾏列式最暴⼒的求法枚举⼀个排列p i ，设排列p 的逆序对为f (p )，|A |=∑(−1)f (p )ΠA i ,pi 实际上合法的排列只有n 个，就是枚举p i =n那么p j =jj <i n j =i j −1j >i当i =n 时，(−1)f (p )ΠA i ,p i=λn −a 1λn −1当i >1时，f (p )=n −iΠA i ,p i=(−1)n −i +1λi ⋅a n −i +1(−1)f (p )ΠA i ,p i=−λi a n −i +1综上,转移矩阵A 的特征多项式有简单的表达p (λ)=|λI n −A |=λn −a 1λn −1−a 2λn −2−⋯−a n假设有f 0这⼀项(不需要知道是多少)，那么认为初始向量列为S =(f −(n −1),f −(n −2),⋯,f 0)这个问题，我们要求的是S ⋅A k 的第n 项，不需要知道整个矩阵类似求出A k 的过程，求出F_k(x)\mod p(\lambda)我们要求解(S\cdot A^k)_n=\sum_1^{n}[x^i]{F(x)}(S\cdot A^i)_n⽽(S\cdot A^i)_n=f_i 已知，求出F(x)后直接带⼊即可需要⽤到多项式取模，求解这个表达式是O(n\log n\log k)的，求完直接带⼊即可{Loading [MathJax]/extensions/TeX/mathchoice.js。
2阶常系数线性齐次递推关系Linear Homogeneous Relation of Degree 2•如果an的递推关系满足a n+C1a n-1+C2a n-2+…+C k a n-k=0，且初值为a0=d0, a1=d1, …a k-1=d k-1，则称这个等式为k阶常系数线性齐次递推关系（linear homogeneous relation of degree k）•多项式x k +C1x k-1+r2x k-2+…+r k=0称为它的特征多项式或特征方程（characteristic equation），其根称为特征根（characteristic root）。
是否常系数线性齐次递推关系？a n = a n-1⋅n Xa n = a n-1+2n-1 Xa n = 3a n-1+1 Xa n = 4a n-1- 4a n-2 √f n = f n-1 + f n-2 √T n = 2T n-1+1 Xx n+1 = x n(1-x n) X•例1•f= 1, f2 = 1, f n = f n-1+f n-21•特征方程是x2-x-1=0•例2•a= 1, a2 = 3, a n = 4a n-1-4a n-21•特征方程是x2-4+4=0•下面我们给出2阶常系数线性齐次递推关系的解法：•假设α, β是a n=c1a n-1+c2a n-2 的特征方程x2-c1x-c2=0 的两个根•a=(α+β)a n-1-(α⋅β)a n-2n•容易验证有a-α⋅a n-1=β⋅(a n-1-α⋅a n-2)n•递推可以得到：a n-αa n-1=β(a n-1-αa n-2)=β2(a n-2-αa n-3)=... =βn-1(a1-αa0)•由此倒推得到：a n-αn a0=(βn-1+αβn-2+α2βn-3+...+αn-1)(a1-αa0)•下面我们给出2阶常系数线性齐次递推关系的解法：•假设α, β是a n=c1a n-1+c2a n-2 的特征方程x2-c1x-c2=0 的两个根•若α≠β，则a n=uαn+vβn，其中u, v由初值决定•若α =β，则a n=a0⋅αn+(a1-αa0)⋅n⋅αn-1•例1•f 1 = 1, f 2 = 1, f n = f n -1+f n -2•特征方程是 x 2-x -1=0•两个特征根分别是 和 •于是 f n = us 1n + vs 2n•由 f 1 = 1和 f 2 = 1 得到1=us 1+vs 2 及1 = us 12 + vs 22 •解出1152+=s 2152-=s 15=u 15=-v•于是，斐波那契数列的第 n 项是1151152255n ⎛⎫⎛⎫+-=- ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭n n f•例2•a= 1, a2 = 3, a n = 4a n-1-4a n-21•特征方程是x2-4+4=0•特征根是α= 2，重数为二•可以求出a= 1/4•于是a n = a0⋅αn+(a1-αa0)⋅n⋅αn-1= (1/4)⋅2n+(1-2⋅1/4)⋅n⋅2n-1= (1+n)⋅2n-2E nd。
递推关系递归公式是用它自身来定义的一个公式，我们习惯称之为递推关系或递推式。
如正奇数序列可以用递推式描述为：f(n)=f(n-1)+2, n>1 且f(1)=1当n为很大的值时，直接用递推来计算f(n)会很麻烦，所以希望能够用一种封闭的式子来描述这个序列，从它入手可以直接计算f(n)。
如果找到这样一种封闭的式子，则称递推式已经解出。
下面的内容给出了求解基本的递推式的一些方法。
递推关系如果具有如下这种形式，则称为常系数线性齐次递推式：f(n)=a1f(n-1)+a2f(n-2)+…+a k f(n-k)这里f(n)称为k次的。
当一个附加项包括常数或者n的函数出现在递推中，那么它就称为非齐次的。
一、线性齐次递推式的求解令f(n)=a1f(n-1)+a2f(n-2)+…+a k f(n-k)的一般解含有f(n)=x n形式的特解的和。
用x n来代替上式中的f(n)，得到：x n =a1x n-1+a2 x n-2 +…+a k x n-k两边同时除以x n-k得到：x k =a1x k-1+a2 x k-2 +…+a k或者写成x k -a1x k-1-a2 x k-2 -…-a k =0以上两等式都称为原递推关系的特征方程。
下面我们只限于一阶和二阶的线性递推关系。
一阶齐次递推方程的解可以直接得到，令f(n)=af(n-1)，假定递推序列从f(0)开始，由于f(n)=af(n-1)=a2f(n-2)=…=a n f(0)所以f(n)=a n f(0)是递推的解。
如果递推的次数是2，那么特征方程变为x2-a1x-a2=0,令这个二次方程的根是r1和r2，递推的解是：f(n)=c1r1n+c2r2n(r1≠r2)f(n)=c1r n+c2nr n(r1=r2)代入序列初始的值f(n0)和f(n0+1)解方程得到c1和c2的值。
例1序列1,4,64,256,…可以用递推关系表示为f(n)=3f(n-1)+4f(n-2)，且f(0)=1,f(1)=4，求此递推式的解。
