11.2 递推方程的公式解法

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【定义11.2.1】k阶常系数线性递推方程的标准形式为

其中k≥1, 为常数,;初值为 。若g恒为0,称为齐次方程;否则为非齐次方程。非齐次不要求g(n)在每一个n都非零,只要求不恒为零。汉诺塔递推为非齐次,斐波那契递推为齐次。

【定义11.2.2】对应齐次方程的特征方程为

它的根称特征根。因 ,所有根都不为0。

【定理11.2.1】对非零复数q,序列 满足齐次递推式,当且仅当q是特征根。将其代入,左边为 ,因前一因子非零,结论成立。此处“满足递推式”不自动表示满足指定初值。

【定理11.2.2与推论11.2.1】齐次递推式的解可作任意常系数线性组合:若h₁、h₂是解,则 也是解;推广到有限个解同样成立。因此任取特征根 , 都满足递推式。不过根若重复,这个表达式未必包含全部解。

【定义11.2.3】含任意常数的解族,若能通过选择常数覆盖各种初值确定的所有解,就称为通解;代入指定初值后得到特解于该初值问题的唯一序列。不要将“非齐次方程的一个特解”与“已满足给定初值的唯一解”混为一谈。

【定理11.2.3】若k个特征根互异,则齐次通解为 。代入初值得线性方程组

系数矩阵行下标j从0到k−1,列下标i从1到k;其范德蒙德行列式为 ,故常数唯一。构造出的序列与原序列初值相同,递推唯一性又保证以后每项相同,这一步说明它确为通解。

【例11.2.1】求 ,。特征方程 的根为 、。设 ,由 、 得 、,所以

它给出整数序列;数值计算大n时若直接用浮点数,应注意舍入误差。(例完)

【定理11.2.4】若互异特征根为 ,各自重数为 ,,则通解为

也就是说,m重根应贡献 这m个独立解,不能简单将同一个 重复m次。用移位算子E理解:,每作用一次,多项式次数降低一次,故m次可消去次数小于m的P。不同根对应的这些解共同构成k维解空间的一组基。

【例11.2.2】求 ,。特征多项式为 ,通解是 。代入初值得

解得 ,故

初值回代依次为1、0、0。(例完)

【定理11.2.5】非齐次通解=对应齐次通解+一个非齐次特解,即 。证明:线性算子L满足 ;任意另一解h与H*相减,,所以所有解均包含在这个解族中。

【待定系数与共振】若 ,,Pₜ为t次多项式,设β作为特征根的重数为m(非根时m=0),可试

其中Qₜ是待定的至多t次多项式。纯多项式对应β=1;纯指数对应t=0。乘 是为了避免与齐次解重合。若g是几个此类项之和,可分别求特解后相加。该方法不表示任意形式的g都具有这样的有限试探形式。

【例11.2.3】顺序插入排序。对j=2到n,先保存x=A[j]、置i=j−1;当i>0且A[i]>x时,把A[i]右移到A[i+1]并令i减1;循环结束后才将x放入A[i+1]。这样保持前j项已有序。把最终插入语句放在while之外,能正确处理x本来就应留在原位的情况。

只计关键字比较,在逆序且互异的输入上第j轮恰有j−1次,故 。根1为一重根,不能用一次多项式作特解;设 ,代入得 ,于是A=1/2,B=−1/2。通解 ,由初值得c=0,所以最坏比较次数为 ,时间量级为 。(例完)

【例11.2.4】汉诺塔:,。常数特解P满足P−2P=1,故P=−1;齐次通解为 ,所以 。代入初值得c=1,得到 。(例完)

【例11.2.5】求 ,。根2是二重根,试 ;代入后左边为 ,故P=1/2。通解 ,由初值得c₁=c₂=1,最终

写成后一形式可直接代入n=0,避免读者误以为出现负指数就不能计算。(例完)