递推方程求解方法

Posted by 韩同学的笔记本 on March 14, 2020

递推方程

递推方程标准型

\[\begin{cases} H(n)-a_1H(n-1)-a_2H(n-2)-\dots -a_kH(n-k)=0 \\ H(0) = b_0,H(1)=b_1,\dots,H(k-1)=b_{k-1} \end{cases}\]

特征方程

$x^k-a_1 x^{k-1} - \dots - a_k = 0$

定理

  • 定理一:$q^n$ 是递推方程的解 $\Leftrightarrow$ $q$ 是特征方程的根
  • 定理二:$h_1(n)$ 和 $h_2(n)$ 是递推方程的解则 $c_1h_1(n)$ 和 $c_2h_2(n)$也是递推方程的解
    • 推论:若 $q_1,q_2,\dots ,q_k$ 是递推方程的特征根,则 $c_1q_1^n+c_2q_2^n+\dots+c_kq_k^n$ 是递推方程的解
  • 定理三:设 $q_1,q_2,\dots,q_k$ 是递推方程不等的特征根,则 $H(n)=c_1q_1^n+c_2q_2^n+ \dots +c_kq_k^n$ 为通解
    • 通解:对递推方程的每一个解 $h(n)$ 都存在一组常数 $c’_1,c’_2,\dots,c’_k$ 使得 $h(n) = c’_1q_1^n+\dots+c’_kq_k^n$ 成立,则称 $c_1q_1^n+\dots+c_kq_k^n$ 为通解
  • 定理四:若 $q$ 是递推方程的 $e$ 重特征根,则 $q,nq^n, \dots, n^{e-1}q^n$ 是递推方程的线性无关的解
  • 定理五:设 $q_1, q_2, \dots, q_t$ 是递推方程的不相等的特征根,且 $q_i$ 的重数为 $e_i$ ,令$H_i(n) = (c_{i,1} + c_{i,2}n + \dots + c_{i,e_i}n^{e_i-1}) q_i^n$ ,那么通解 $H(n) = \sum_{i=1}^t H_i(n)$.
  • 定理六:对于非齐次递推方程, $H(n)=\overline{H(n)}+H^*(n)$ , $\overline{H(n)}$ 是对应齐次方程的通解, $H^*(n)$ 是一个特解
    • $f(n)$ 为 $n$ 的 $t$ 次多项式时一般 $H^*(n)$ 也为 $n$ 的 $t$ 次多项式 $\sum_{i=0}^t P_i n^i$
      • 注意:当特征根是 $1$ 时,需要设一个 $t+1$ 次的多项式 $H^*(n)$
    • $f(n)$ 为指数函数 $\beta ^n$ ,若 $\beta$ 不是特征根,则特解为 $H^*(n)=P \beta^n$