算法-求解递归方程的方法

《算法-求解递归方程的方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章常用的数学工具2.2用生成函数求解递归方程2.2.1生成函数及其性质一、生成函数的定义定义2.1令是一个实数序列，构造如下的函数：（2.2.1）则函数称为序列的生成函数。例：函数则函数便是序列的生成函数。二、生成函数的性质1.加法设是序列的生成函数，是序列的生成函数，则（2.2.2）20是序列的生成函数。2．移位设是序列的生成函数，则（2.2.3）是序列的生成函数。3．乘法设是序列的生成函数，是序列的生成函数，则（2.2.4）是序列的生成函数，其中，4.z变换设是序列的生成函数，则（2.2.5）是序列的生成函数。特别地，有：20（2.2.6）所以，是序列的生成函数。当时，有：（2.2.

2、7）则是序列1,1,1,…的生成函数。利用：（2.2.8）可以去掉级数中的奇数项；同样，利用（2.2.9）可以去掉级数中的偶数项。5．微分和积分设是序列的生成函数，对求导数（2.2.10）显然，是序列的生成函数。同样，对求积分（2.2.11）则积分是的生成函数。20如果对（2.2.7）式求导数，可得：（2.2.12）则是算术级数1,2,3…的生成函数。如果对（2.2.7）式求积分，可得：（2.2.13）则是调和数的生成函数。2.2.2用生成函数求解递归方程例2.1汉诺塔（Hanoi）问题。宝石针的编号为、、，针串着64片金盘。希望把它们移到针或针。有可是金盘的数量，是移动个金盘的移动次数1．

3、当时，=1。2．当时，。3．当时，。递归关系式：（2.2.14）用作为系数，构造一个生成函数：令20由（2.2.14）及（2.2.7）式得：所以，令：有：求得。所以：，它是式中第项的系数。当时，移动次数为。例2.2菲波那契序列问题。、、表示第个月小兔子、大兔子的数目，及第个月兔子的总数目。则：（2.2.15）（2.2.16）（2.2.17）20第一式：第个月大兔子的数量，为前一个月大兔子的数量加上前一个月小兔子的数量；第二式：第个月小兔子的数量，为前一个月大兔子的数量；第三式：表示第个月兔子的总量为该月大兔子的数量及小兔子的数量之和。递归方程：（2.2.18）用作为系数，构造生成函数：令：所

4、以，有：20有：解得：把、代入，得到：令，则有：所以，第项系数为：2.3用特征方程求解递归方程2.3.1k阶常系数线性齐次递归方程一、k阶常系数线性齐次递归方程201、递归方程的形式：（2.3.1）2、递归方程的特征方程取代：两边分别除以，可得：把上式写成：（2.3.2）则式（2.3.2）称为递归方程（2.3.1）的特征方程。二、k阶常系数线性齐次递归方程的求解1、是特征方程的个互不相同的根。则递归方程（2.3.1）的通解为：（2.3.3）2、特征方程的个根中有个重根，递归方程（2.3.1）的通解形式为：（2.3.4）在（2.3.3）及（2.3.4）中，为待定系数。3、求解过程：把递归方程的

5、初始条件代入（2.3.3）或（2.3.4）中，建立联立方程，确定系数，从而可求出通解。例2.3三阶常系数线性齐次递归方程如下：解特征方程为：20把方程改写成：对特征方程进行因式分解，得：则有特征根：所以，递归方程的通解为：由初始条件得：解此联立方程，得：则递归方程的解为：例2.4三阶常系数线性齐次递归方程如下：解特征方程为：把特征方程改写成：进行因式分解：20最后得：求得特征方程的根为：所以，递归方程的通解为：代入初始条件：解此联立方程，得：则递归方程的解为：2.3.2k阶常系数线性非齐次递归方程一、k阶常系数线性非齐次递归方程1、递归方程的形式：（2.3.5）2、通解形式：20其中，是对应

6、齐次递归方程的通解，是原非齐次递归方程的特解。3、特解的求取1）是的次多项式，即（2.3.6）其中，是常数。特解也是的次多项式：（2.3.7）其中，为待定系数。2）是如下形式的指数函数：（2.3.8）其中，、为常数。a)不是特征方程的重根，特解为：（2.3.9）其中，为待定系数。b)是特征方程的重特征根，特解的形式为：（2.3.10）其中，是待定系数。例2.5二阶常系数线性非齐次递归方程如下：解对应的齐次递归方程的特征方程为：把此方程转换为：得到特征根为：20所以，对应的齐次递归方程的通解为：令非齐次递归方程的特解为：代入原递归方程，得：化简后得到：由此，得到联立方程：解此联立方程，可得：所

7、以，非齐次递归方程的通解为：把初始条件代入，有：解此联立方程，得：最后，非齐次递归方程的通解为：20例2.6二阶常系数线性非齐次递归方程如下：解对应齐次递归方程的特征方程为：此方程可改写成：所以，方程的解为：齐次递归方程的通解为：令非齐次递归方程的特解为：把特解代入原非齐次递归方程，得：整理得：可得联立方程：解此联立方程得：所以，非齐次递归方程的通解为：20用初始条件代入：解此联立方程得：最后，非齐次递归方程