算法-求解递归方程地方法.doc

文档介绍：word
word
文档
word
第二章 常用的数学工具
用生成函数求解递归方程
生成函数与其性质
一、生成函数的定义
令是一个实数序列，构造如下的函数：
〔〕
如此函
所以，递归方程的通解为：
代入初始条件：
解此联立方程，得：
如此递归方程的解为：
k阶常系数线性非齐次递归方程
一、k阶常系数线性非齐次递归方程
word
word
文档
word
1、递归方程的形式：
〔〕
2、通解形式：
其中，是对应齐次递归方程的通解，是原非齐次递归方程的特解。
3、特解的求取
1〕是的次多项式，即
〔〕
其中，是常数。特解也是的次多项式：
〔〕
其中，为待定系数。
2〕是如下形式的指数函数：
〔〕
其中，、为常数。
a) 不是特征方程的重根，特解为：
〔〕
其中，为待定系数。
b) 是特征方程的重特征根，特解的形式为：
〔〕
其中，是待定系数。
二阶常系数线性非齐次递归方程如下：
解 对应的齐次递归方程的特征方程为：
word
word
文档
word
把此方程转换为：
得到特征根为：
所以，对应的齐次递归方程的通解为：
令非齐次递归方程的特解为：
代入原递归方程，得：
化简后得到：
由此，得到联立方程：
解此联立方程，可得：
所以，非齐次递归方程的通解为：
把初始条件代入，有：
word
word
文档
word
解此联立方程，得：
最后，非齐次递归方程的通解为：
二阶常系数线性非齐次递归方程如下：
解 对应齐次递归方程的特征方程为：
此方程可改写成：
所以，方程的解为：
齐次递归方程的通解为：
令非齐次递归方程的特解为：
把特解代入原非齐次递归方程，得：
整理得：
可得联立方程：
word
word
文档
word
解此联立方程得：
所以，非齐次递归方程的通解为：
用初始条件代入：
解此联立方程得：
最后，非齐次递归方程的解为：
解方程步骤归纳
〔1〕求齐次方程的解 但系数项待定
〔2〕确定特解 将特解带入原方程，确定各系数
〔3〕确定通解，由给定的初值确定确定齐次方程的未定系数。
word
word
文档
word
用递推方法求解递归方程
递推
非齐次递归方程：
〔〕
其中，、是常数，是的某一个函数。直接把公式应用于式中的，得到：
〔〕
汉诺塔问题。
由〔〕，汉诺塔的递归方程为：
直接利用〔〕式于汉诺塔的递归方程。此时，
从递推到1，有：
word
word
文档
word
用递推法求解变系数递归方程
一、变系数齐次递归方程：
〔〕
利用递推方法，容易得到：
〔〕
解如下递归函数：
由〔〕式，容易得到：
二、变系数非齐次递归方程：
〔〕
其中，是常数，和是的函数。利用〔〕式对进展递推，有：
word
word
文档
word
〔〕
解如下的递归函数：
对方程进展递推，有：
如果直接使用公式〔〕，此时，，有：
得到同样结果。
解如下的递归方程
解 对方程进展递推，有：
word
word
文档
word
由公式〔〕，得
如果直接使用公式〔〕，此时，，同样有：
换名
解如下的递归方程：
其中， 。
解 把表示成的关系，原递归方程改写为：
再令：
于是，原递归方程可写为：
word
word
文档
word
对上面方程进展递推，有：
如果直接使用〔〕式，可得：
word
word
文档
word
结果一样。
解如下的递归方程：