文档介绍: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
结果一样。
解如下的递归方程: