程序员社区

【组合数学】递推方程 ( 非齐次部分是指数的情况 | 非齐次部分是指数的情况示例 )

文章目录

  • 一、非齐次部分是指数的情况
  • 二、非齐次部分是指数的情况 示例

一、非齐次部分是指数的情况


常系数线性非齐次递推方程 :

H

(

n

)

a

1

H

(

n

1

)

a

k

H

(

n

k

)

=

f

(

n

)

H(n) - a_1H(n-1) - \cdots - a_kH(n-k) = f(n)

H(n)a1H(n1)akH(nk)=f(n) ,

n

k

,

a

k

0

,

f

(

n

)

0

n\geq k , a_k\not= 0, f(n) \not= 0

nk,ak=0,f(n)=0

上述方程左侧 与 “常系数线性齐次递推方程” 是一样的 , 但是右侧不是

0

0

0 , 而是一个基于

n

n

n函数

f

(

n

)

f(n)

f(n) , 这种类型的递推方程称为 “常系数线性非齐次递推方程” ;

非齐次部分是指数的情况 :

如果上述 “常系数线性非齐次递推方程” 的 非齐次部分

f

(

n

)

f(n)

f(n) 是指数函数 ,

β

n

\beta^n

βn ,

如果

β

\beta

β 不是特征根 ,

则非齐次部分的特解形式为 :

H

(

n

)

=

P

β

n

H^*(n) = P\beta^n

H(n)=Pβn ,

P

P

P 是常数 ;

将上述特解

H

(

n

)

=

P

β

n

H^*(n) = P\beta^n

H(n)=Pβn , 代入递推方程 , 求解出常数

P

P

P 的值 , 进而得到了完整的特解 ;

“常系数线性非齐次递推方程” 的通解是

H

(

n

)

=

H

(

n

)

+

H

(

n

)

H(n) = \overline{H(n)} + H^*(n)

H(n)=H(n)+H(n)

使用上述解出的 特解 , 与递推方程 齐次部分的通解 , 组成递推方程的完整通解 ;

二、非齐次部分是指数的情况 示例


递推方程 :

a

n

=

6

a

n

1

+

8

n

1

a_n = 6a_{n-1} + 8^{n-1}

an=6an1+8n1

初值 :

a

1

=

7

a_1=7

a1=7

第一步 , 先求出该递推方程 非齐次部分对应的特解 ,

递推方程的标准形式是 :

a

n

6

a

n

1

=

8

n

1

a_n - 6a_{n-1} = 8^{n-1}

an6an1=8n1

非齐次部分是

8

n

1

8^{n-1}

8n1 ,

因此其 特解 的形式是

a

n

=

P

8

n

1

a^*n = P 8^{n-1}

an=P8n1 , 其中

P

P

P 是常数 ;

将特解代入上述递推方程 :

P

8

n

1

6

P

8

n

2

=

8

n

1

P 8^{n-1} - 6P 8^{n-2} = 8^{n-1}

P8n16P8n2=8n1

6

P

8

n

2

6P 8^{n-2}

6P8n2 项乘以

8

8

8 变成

6

P

8

n

1

6P8^{n-1}

6P8n1 , 再除以

8

8

8 变成

6

P

8

n

1

8

=

3

P

8

n

1

4

\cfrac{6P8^{n-1}}{8}=\cfrac{3P8^{n-1}}{4}

86P8n1=43P8n1 , 代入等式中 ,

P

8

n

1

3

P

8

n

1

4

=

8

n

1

P 8^{n-1} - \cfrac{3P8^{n-1}}{4} = 8^{n-1}

P8n143P8n1=8n1

P

8

n

1

4

=

8

n

1

\cfrac{P8^{n-1}}{4} = 8^{n-1}

4P8n1=8n1

P

4

=

1

\cfrac{P}{4} = 1

4P=1

P

=

4

P = 4

P=4

特解中的常数项

P

=

4

P=4

P=4 , 最终特解为

a

n

=

4

×

8

n

1

a^*n = 4\times 8^{n-1}

an=4×8n1

第二步 , 求出齐次部分的通解

递推方程的标准形式是 :

a

n

6

a

n

1

=

8

n

1

a_n - 6a_{n-1} = 8^{n-1}

an6an1=8n1 ,

齐次部分是

a

n

6

a

n

1

=

0

a_n - 6a_{n-1} = 0

an6an1=0

写出特征方程 :

x

6

=

0

x - 6 = 0

x6=0 ,

特征根

q

=

6

q= 6

q=6

写出齐次部分通解形式 :

a

n

=

c

×

6

n

\overline{a_n} = c \times 6^n

an=c×6n

“常系数线性非齐次递推方程” 的通解是

a

n

=

a

n

+

a

n

a_n = \overline{a_n} + a^*n

an=an+an

递推方程通解是 :

a

n

=

c

×

6

n

+

4

×

8

n

1

a_n = c \times 6^n + 4\times 8^{n-1}

an=c×6n+4×8n1

第三步 , 代入初值, 求出最终通解

代入初值

a

1

=

7

a_1 = 7

a1=7 到上述通解中得到

c

×

6

1

+

4

×

8

1

1

=

7

c \times 6^1 + 4 \times 8^{1-1} = 7

c×61+4×811=7

6

c

+

4

=

7

6c + 4 = 7

6c+4=7

c

=

1

2

c=\cfrac{1}{2}

c=21

a

n

=

c

×

6

n

+

4

×

8

n

1

a_n = c \times 6^n + 4\times 8^{n-1}

an=c×6n+4×8n1 通解中的常数常数

c

=

1

2

c=\cfrac{1}{2}

c=21 , 将常数代入 ,

通解为

a

n

=

1

2

×

6

n

+

4

×

8

n

1

a_n = \cfrac{1}{2} \times 6^n + 4\times 8^{n-1}

an=21×6n+4×8n1

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 【组合数学】递推方程 ( 非齐次部分是指数的情况 | 非齐次部分是指数的情况示例 )

相关推荐

  • 暂无文章

一个分享Java & Python知识的社区