Resolvendo recorrências por meio de polinômio característico com raízes imaginárias

Na análise de algoritmos, você geralmente precisa resolver recorrências. Além do Teorema Mestre, métodos de substituição e iteração, existe um usando polinômios característicos .

Digamos que eu tenha concluído que uma polinomial característica tem imaginárias raízes, ou seja e . Então não posso usar $x^2 - 2x + 2$ $x_1 = 1+i$ $x_2 =1-i$

$\qquad c_1\cdot x_1^n + c_2\cdot x_2^n$

para obter a solução, certo? Como devo proceder neste caso?

algorithms algorithm-analysis recurrence-relation Koray
fonte

Bem-vinda! Observe que você pode usar o LaTeX por $...$ .

Raphael

Estou confuso. Tenho certeza de que você quer dizer o método usando polinômios characteristc , não equações. O que é ? As soluções da equação que você dá não são imaginárias, mas apenas irracionais. O que você quer dizer com "aplicar o [polinômio]"?

j

$j$

Raphael

Ele adotou o hábito do físico de escrever errado .

i

$i$

31412 JeffE

Claro, você pode realmente. Primeiro, a solução satisfaz a recorrência. Em segundo lugar, o espaço de solução é de dimensão 2.

Strin

Respostas:

Sim, a solução é de fato para algumas constantes e determinadas pelos casos base. Se os casos de base forem reais, todos os termos complexos em serão cancelados (por indução) , para todo o número inteiro . $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ $\alpha$ $\beta$ $T(n)$ $n$

Por exemplo, considere a recorrência , com casos base e . O polinômio característico dessa recorrência é ; portanto, a solução é para algumas constantes e . A conexão de casos base nos dá que implica o que implica e . Então a solução é $T(n) = 2T(n-1) - 2T(n-2)$ $T(0)=0$ $T(1)=2$ $x^2-2x+2$ $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ $\alpha$ $\beta$

T (0) = α (1 + i)^{0} + β (1 - i)^{0} = α + β = 0 T (1) = α (1 + i)^{1} + β (1 - i)^{1} = (α + β) + (α - β) i = 2

$T(0) = \alpha(1+i)^0 + \beta(1-i)^0 = \alpha+\beta = 0\\ T(1) = \alpha(1+i)^1 + \beta(1-i)^1 = (\alpha+\beta) + (\alpha-\beta)i = 2$

α + β = 0 α - β = - 2 i

$\alpha + \beta = 0 \\ \alpha - \beta = -2i$

α = - i

$\alpha = -i$

β = i

$\beta = i$

T (n) = i \cdot ((1 - i)^{n} - (1 + i)^{n}) .

$T(n) = i\cdot ((1-i)^n - (1+i)^n).$

Esta função oscila entre e com um "período" de 4. Em particular, temos para todos os , porque (e porque escolhi o caso base cuidado). $\sqrt{2}^n$ $-\sqrt{2}^n$ $T(4n) = 0$ $n$ $(1-i)^4 = (1+i)^4 = -4$ $T(0)$

JeffE
fonte

Parece que me lembro que as raízes imaginárias do polinômio característico (que são, se bem me lembro, as singularidades dominantes da função geradora da sequência) implicam elementos negativos em algum lugar. Isso é verdade? Nesse caso, é seguro dizer que você nunca deve encontrar esse caso na análise de algoritmos.

Raphael

Não necessariamente. Se as raízes da função característica são , , e , por exemplo, a função vai oscilar em torno de por algum , mas (com casos de bases apropriadas) será sempre positivo.

2

$2$

1 + i

$1+i$

1 - i

$1-i$

α 2^{n}

$\alpha 2^n$

α

$\alpha$

Jeffe