Resolución de recurrencias mediante polinomios característicos con raíces imaginarias

En el análisis de algoritmos, a menudo tienes que resolver las recurrencias. Además del teorema maestro, los métodos de sustitución e iteración, hay uno que usa polinomios característicos .

Digamos que he concluido que un polinomio característico tiene raíces imaginarias , a saber, y . Entonces no puedo 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 obtener la solución, ¿verdad? ¿Cómo debo proceder en este caso?

algorithms algorithm-analysis recurrence-relation Koray
fuente

¡Bienvenidos! Tenga en cuenta que puede usar LaTeX por $...$ .

Raphael

Estoy confundido. Estoy seguro de que te refieres al método que usa polinomios característicos , no ecuaciones. ¿Qué es

? Las soluciones de la ecuación que das no son imaginarias, sino meramente irracionales. ¿Qué quiere decir con "aplicar el [polinomio]"?

j

$j$

Raphael

Ha adoptado el hábito del físico de escribir mal

i

$i$

JeffE

Por supuesto que puedes en realidad. Primero, la solución satisface la recurrencia. En segundo lugar, el espacio de solución es de dimensión 2.

Strin

Respuestas:

Sí, la solución es de hecho para algunas constantes y determinadas por los casos base. Si los casos base son reales, entonces (por inducción) todos los términos complejos en se cancelarán, para todos los enteros . $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ $\alpha$ $\beta$ $T(n)$ $n$

Por ejemplo, considere la recurrencia , con los casos base y . El polinomio característico de esta recurrencia es , por lo que la solución es $T(n) = 2T(n-1) - 2T(n-2)$ $T(0)=0$ $T(1)=2$ $x^2-2x+2$ para algunas constantes y . Conectar casos base nos da $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ $\alpha$ $\beta$ que implica

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$

que implica

. Entonces la solución es

α + β = 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 función oscila entre y $\sqrt{2}^n$ $-\sqrt{2}^n$ $T(4n) = 0$ $n$ $(1-i)^4 = (1+i)^4 = -4$ $T(0)$

JeffE
fuente

Me parece recordar que las raíces imaginarias del polinomio característico (que son, si mal no recuerdo, las singularidades dominantes de la función generadora de secuencias) implican elementos negativos en alguna parte. ¿Es eso cierto? Si es así, es seguro decir que nunca debería encontrarse con este caso en el análisis de algoritmos.

Raphael

2

$2$

1 + i

$1+i$

1 - i

$1-i$

α 2^{n}

$\alpha 2^n$

α

$\alpha$