Résolution de récurrences via un polynôme caractéristique avec des racines imaginaires

9

Dans l'analyse d'algorithmes, vous devez souvent résoudre des récurrences. En plus du théorème maître, des méthodes de substitution et d'itération, il en existe un qui utilise des polynômes caractéristiques .

Disons que j'ai conclu qu'un polynôme caractéristique a des racines imaginaires , à savoir et . Alors je ne peux pas utiliserx22x+2x 2 = 1 - ix1=1+ix2=1i

c1x1n+c2x2n

pour obtenir la solution, non? Comment dois-je procéder dans ce cas?

Koray
la source
Bienvenue! Notez que vous pouvez utiliser LaTeX par $...$.
Raphael
1
Je suis confus. Je suis sûr que vous voulez dire la méthode utilisant des polynômes caractéristiques , pas des équations. Qu'est-ce que ? Les solutions de l'équation que vous donnez ne sont pas imaginaires, mais simplement irrationnelles. Que voulez-vous dire par «appliquer le [polynôme]»? j
Raphael
6
Il a adopté l'habitude du physicien de mal orthographier . i
JeffE
Bien sûr, vous pouvez réellement. Premièrement, la solution satisfait la réapparition. Deuxièmement, l'espace de la solution est de dimension 2.
Strin

Réponses:

12

Oui, la solution est en fait pour certaines constantes et déterminées par les cas de base. Si les cas de base sont réels, alors (par induction) tous les termes complexes de s'annuleront, pour tout entier . α β T ( n ) nT(n)=α(1+i)n+β(1i)nαβT(n)n

Par exemple, considérons la récurrence , avec des cas de base et . Le polynôme caractéristique de cette récurrence est , donc la solution est pour certaines constantes et . Le branchement dans les cas de base nous donne ce qui implique ce qui implique et . La solution est donc T ( 0 ) = 0 T ( 1 ) = 2 x 2 - 2 x + 2 T ( n ) = α ( 1 + i ) n + β ( 1 - i ) n α βT(n)=2T(n-1)-2T(n-2)T(0)=0T(1)=2X2-2X+2T(n)=α(1+i)n+β(1i)nαβα + β = 0

T(0)=α(1+i)0+β(1i)0=α+β=0T(1)=α(1+i)1+β(1i)1=(α+β)+(αβ)i=2
α = - i β = i T ( n ) = i ( ( 1 - i ) n - ( 1 + i ) n ) .
α+β=0αβ=2i
α=iβ=i
T(n)=i((1i)n(1+i)n).

Cette fonction oscille entre et avec une "période" de 4. En particulier, nous avons pour tout , car (et parce que j'ai choisi soigneusement le cas de base ).-2n2nT(4n)=0n(1i)4=(1+i)4=4T(0)

JeffE
la source
1
Il me semble que les racines imaginaires du polynôme caractéristique (qui sont, si je me souviens bien, les singularités dominantes de la fonction génératrice de la séquence) impliquent quelque part des éléments négatifs. Est-ce vrai? Si c'est le cas, il est sûr de dire que vous ne devriez jamais rencontrer ce cas dans l'analyse d'algorithme.
Raphael
6
Pas nécessairement. Si les racines de la fonction caractéristique sont , et , par exemple, la fonction oscillera autour de pour certains , mais (avec les cas de base appropriés) elle sera toujours positive. 21+je1-jeα2nα
JeffE