IDEA激活码
文章目录
- 一、特解示例 1 ( 汉诺塔 )
- 二、特解示例 2 ( 特征根为 1 的情况 )
一、特解示例 1 ( 汉诺塔 )
Hanoi 问题 :
- 递推方程为 :
T
(
n
)
=
2
T
(
n
−
1
)
+
1
T(n) =2 T(n-1) + 1
T(n)=2T(n−1)+1 - 初值 :
T
(
1
)
=
1
T(1) = 1
T(1)=1
求该递推方程的解 ?
先解出其特解
1 . 特解形式 :
上述递推方程左侧是 “常系数线性齐次递推方程” 形式 , 不用管 ,
右侧的
1
1
1 与特解相关 ,
1
1
1 为
n
n
n 的
0
0
0 次多项式 ,
因此特解
H
∗
(
n
)
H^*(n)
H∗(n) 也是
n
n
n 的
0
0
0 次多项式 ;
2 . 写出特解形式 :
特解项数 : 则 特解项数 是
0
+
1
=
1
0 + 1 = 1
0+1=1 项 ;
特解每项组成 : 特解每一项由 常数 乘以
n
n
n 的次幂 组成 ,
-
1
1
1 个常数 设为
P
1
P_1
P1 ,
-
1
1
1 个
n
n
n 的次幂 , 幂取值
0
0
0 ,
因此特解的形式为
T
∗
(
n
)
=
P
1
n
0
T^*(n) = P_1n^0
T∗(n)=P1n0 ,
化简后为 :
T
∗
(
n
)
=
P
1
T^*(n) = P_1
T∗(n)=P1
3 . 将特解代入递推方程 :
将特解
T
∗
(
n
)
=
P
1
T^*(n) = P_1
T∗(n)=P1 ,
代入到递推方程
T
(
n
)
=
2
T
(
n
−
1
)
+
1
T(n) =2 T(n-1) + 1
T(n)=2T(n−1)+1 中 ,
得到 :
P
1
=
2
P
1
+
1
P_1 = 2P_1 + 1
P1=2P1+1
解方程结果 :
P
1
=
−
1
P_1 = -1
P1=−1
特解为 :
T
∗
(
n
)
=
−
1
T^*(n) = -1
T∗(n)=−1
递推方程求解完整过程 : 求解上述汉诺塔 常系数线性齐次递推方程 部分的通解 ,
T
(
n
)
−
2
T
(
n
−
1
)
=
0
T(n) - 2 T(n-1) = 0
T(n)−2T(n−1)=0 ;
1 . 特征方程 :
( 1 ) 递推方程标准形式 : 写出递推方程 标准形式 , 所有项都在等号左边 , 右边是
0
0
0 ;
T
(
n
)
−
2
T
(
n
−
1
)
=
0
T(n) - 2 T(n-1) = 0
T(n)−2T(n−1)=0
( 2 ) 特征方程项数 : 确定 特征方程项数 , 与 递推方程项数相同 ;
2
2
2 项 ;
( 3 ) 特征方程次幂数 : 最高次幂是 特征方程项数
−
1
-1
−1 , 最低次幂
0
0
0 ;
最低次幂
0
0
0 , 最高次幂
1
1
1 ;
( 4 ) 写出 没有系数 的特征方程 ;
x
+
1
=
0
x + 1 = 0
x+1=0
( 5 ) 逐位将递推方程的系数 抄写 到特征方程中 ;
x
−
2
=
0
x - 2 = 0
x−2=0
2 . 解特征根 : 将 特征方程的 特征根 解出来 ,
x
=
−
b
±
b
2
−
4
a
c
2
a
x = \cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}
x=2a−b±b2−4ac
特征根
q
1
=
2
q_1=2
q1=2 ;
3 . 构造递推方程的通解 :
( 1 ) 无重根 : 构造
c
1
q
1
n
+
c
2
q
2
n
+
⋯
+
c
k
q
k
n
c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n
c1q1n+c2q2n+⋯+ckqkn 形式的线性组合 , 该线性组合就是递推方程的 通解 ;
递推方程的齐次部分通解是 :
T
(
n
)
‾
=
c
2
n
\overline{T(n)} = c2^n
T(n)=c2n
“常系数线性非齐次递推方程” 的通解是
T
(
n
)
=
T
(
n
)
‾
+
T
∗
(
n
)
T(n) = \overline{T(n)} + T^*(n)
T(n)=T(n)+T∗(n)
非齐次部分的特解是 :
T
∗
(
n
)
=
−
1
T^*(n) = -1
T∗(n)=−1
因此汉诺塔递推方程的通解是 :
T
(
n
)
=
c
2
n
−
1
T(n) = c2^n - 1
T(n)=c2n−1
( 2 ) 有重根 : 参考下面的 “有重根下的通解形式列出” 内容 ;
4 . 求通解中的常数 :
( 1 ) 代入初值获得方程组 : 将递推方程初值代入通解 , 得到
k
k
k 个
k
k
k 元方程组 , 通过 解该方程组 , 得到 通解中的常数 ;
将初值
T
(
1
)
=
1
T(1) = 1
T(1)=1 代入上述通解
T
(
n
)
=
c
2
n
−
1
T(n) = c2^n - 1
T(n)=c2n−1 , 得到
2
c
−
1
=
1
2c - 1 = 1
2c−1=1
常数
c
=
1
c = 1
c=1 ;
( 2 ) 代入常数获得通解 : 将常数代入通解 , 就可以得到最终的递推方程的解 ;
将常数
c
=
1
c=1
c=1 代入通解 , 最终得到的就是递推方程的解 :
T
(
n
)
=
2
n
−
1
T(n) = 2^n - 1
T(n)=2n−1
二、特解示例 2 ( 特征根为 1 的情况 )
递推方程为 :
H
(
n
)
−
H
(
n
−
1
)
=
7
n
H(n) - H(n-1) = 7n
H(n)−H(n−1)=7n , 求该递推方程通解 ?
先求其齐次部分
H
(
n
)
−
H
(
n
−
1
)
=
0
H(n) - H(n-1) = 0
H(n)−H(n−1)=0 的通解 ;
写出特征方程 :
x
−
1
=
0
x - 1 = 0
x−1=0 , 特征根是
q
=
1
q= 1
q=1 ;
齐次部分通解形式 :
H
(
n
)
‾
=
c
1
1
n
=
c
1
\overline{H(n)} =c_11^n = c_1
H(n)=c11n=c1
求其特解 ( 失败尝试 ) :
上述是常系数 线性 非齐次方程 , 那么先求其 非齐次 部分对应的 特解 ,
右侧是
n
n
n 的
1
1
1 次方程 , 则对应的特解是
H
∗
(
n
)
=
P
1
n
+
P
2
H^*(n) = P_1n + P_2
H∗(n)=P1n+P2 , 将上述特解 , 代入到递推方程中 ,
P
1
n
+
P
2
−
(
P
1
(
n
−
1
)
+
P
2
)
=
7
n
\ \ \ \ P_1n + P_2 - (P_1(n - 1) + P_2) =7n
P1n+P2−(P1(n−1)+P2)=7n , 化简后变成 :
P
1
n
+
P
2
−
P
1
n
+
P
1
−
P
2
=
7
n
\ \ \ \ P_1n + P_2 - P_1n + P_1 - P_2 = 7n
P1n+P2−P1n+P1−P2=7n
P
1
=
7
n
\ \ \ \ P_1 = 7n
P1=7n
此时无法解出特解中的常数
P
1
,
P
2
P_1, P_2
P1,P2 , 因此不能设置特解为
n
n
n 的
1
1
1 次方程 ,
出现这种问题的原因是 , 齐次部分 , 特征方程是
x
−
1
=
0
x-1 = 0
x−1=0 , 对应的的特征根是
1
1
1 ,
特征根为
1
1
1 时 , 多项式的最高项会抵消掉 , 常数项也会被抵消掉 ;
求特解 , 将
n
n
n 的次幂提高
1
1
1 :
提高的次幂是 特征根
1
1
1 的重复度 , 如果重复度为
2
2
2 , 则需要提高
2
2
2 次幂 ;
为了解决上述问题 , 这里需要将
n
n
n 的次幂提高
1
1
1 , 将特解形式中的一次方项 , 设置成平方项 , 其中常数项不设置 , 即使设置了也会抵消掉 , 无法求出常数项值 ;
将特解设置成
n
n
n 的
2
2
2 次方程 ,
特解形式为
H
∗
(
n
)
=
P
1
n
2
+
P
2
n
H^*(n) = P_1n^2 + P_2n
H∗(n)=P1n2+P2n ;
将特解代入递推方程中 :
P
1
n
2
+
P
2
n
−
(
P
1
(
n
−
1
)
2
+
P
2
(
n
−
1
)
)
=
7
n
P_1n^2 + P_2n - ( P_1(n-1)^2 + P_2(n-1) )=7n
P1n2+P2n−(P1(n−1)2+P2(n−1))=7n
P
1
n
2
+
P
2
n
−
(
P
1
(
n
2
−
2
n
+
1
)
+
P
2
(
n
−
1
)
)
=
7
n
P_1n^2 + P_2n - ( P_1(n^2 -2n + 1) + P_2(n-1) )=7n
P1n2+P2n−(P1(n2−2n+1)+P2(n−1))=7n
P
1
n
2
+
P
2
n
−
P
1
n
2
+
2
P
1
n
−
P
1
−
P
2
n
+
P
2
=
7
n
P_1n^2 + P_2n - P_1n^2 + 2P_1n - P_1 - P_2n + P_2=7n
P1n2+P2n−P1n2+2P1n−P1−P2n+P2=7n
2
P
1
n
−
P
1
+
P
2
=
7
n
2P_1n - P_1 + P_2=7n
2P1n−P1+P2=7n
分析
n
n
n 的幂写出方程组 :
左右两侧是相等的 , 这里 根据
n
n
n 的次幂前的系数 , 写出方程组 ;
分析
n
n
n 的次幂的系数 :
-
n
2
n^2
n2 系数分析 : 右侧没有
n
2
n^2
n2 , 因此左侧的
n
2
n^2
n2 项之前的系数为
0
0
0 ; 左侧也没有
n
2
n^2
n2 项 , 无法抽取方程 ;
-
n
1
n^1
n1 系数分析 : 右侧是
7
n
7n
7n , 因此
n
n
n 前的系数是
7
7
7 ; 将左侧展开 ,
n
n
n 前的系数是
2
P
1
2P_1
2P1 ;
2
P
1
n
=
7
n
2P_1n = 7n
2P1n=7n
-
n
0
n^0
n0 系数分析 : 右侧是
0
0
0 ; 将左侧展开 ,
n
0
n^0
n0 前的系数是
P
2
−
P
1
P_2-P_1
P2−P1 ;
P
2
−
P
1
=
0
P_2-P_1 = 0
P2−P1=0
最终得到方程组 :
{
2
P
1
=
7
−
P
1
+
P
2
=
0
\begin{cases} 2P_1 = 7 \\\\ -P_1 + P_2 = 0 \end{cases}
⎩⎪⎨⎪⎧2P1=7−P1+P2=0
解上述方程组 , 得到结果 :
{
P
1
=
7
2
P
2
=
7
2
\begin{cases} P_1 = \cfrac{7}{2} \\\\ P_2 = \cfrac{7}{2} \end{cases}
⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧P1=27P2=27
特解是 :
H
∗
(
n
)
=
7
2
n
2
+
7
2
n
H^*(n) = \cfrac{7}{2} n^2 + \cfrac{7}{2}n
H∗(n)=27n2+27n
齐次部分通解形式 :
H
(
n
)
‾
=
c
1
\overline{H(n)} = c_1
H(n)=c1
最终通解是 :
H
(
n
)
=
H
(
n
)
‾
+
H
∗
(
n
)
=
c
1
+
7
2
n
2
+
7
2
n
H(n) = \overline{H(n)} + H^*(n) = c_1 +\cfrac{7}{2} n^2 + \cfrac{7}{2}n
H(n)=H(n)+H∗(n)=c1+27n2+27n
