9.3: Operadores de avance
- Page ID
- 118546
Gran parte de nuestra motivación para resolver ecuaciones de recurrencia proviene de un problema análogo en matemáticas continuas: ecuaciones diferenciales. No hace falta que antes hayas estudiado a estas bestias para entender qué haremos en lo que resta de este capítulo, pero si tienes, la motivación de cómo abordamos los problemas será más clara. Como su nombre indica, las ecuaciones diferenciales involucran derivadas, las cuales denotaremos usando notación “operador” por\(Df\) en lugar de la notación Leibniz\(df/dx\). En nuestra notación, la segunda derivada es\(D^2f\), la tercera es\(D^3f\), y así sucesivamente. Considera el siguiente ejemplo.
Resolver la ecuación
\(Df = 3f\)
si\(f(0) = 2\).
- Solución
-
Aunque no hayas estudiado ecuaciones diferenciales, deberías reconocer que esta pregunta en realidad solo nos está pidiendo que encontremos una función\(f\) tal que\(f(0)=2\) y su derivada sea tres veces en sí misma. Ignoremos\(f(0)=2\) por el momento la condición inicial y centrémonos en la carne del problema. ¿Qué función, cuando tomas su derivada, cambia sólo al ser multiplicada por 3? Se debe pensar rápidamente en la función\(e^{3x}\), ya que\(D(e^{3x})=3e^{3x}\), que tiene exactamente la propiedad que deseamos. Por supuesto, para cualquier constante\(c\), la función\(ce^{3x}\) también satisface esta propiedad, y esto nos da el gancho que necesitamos para satisfacer nuestra condición inicial. Tenemos\(f(x)=ce^{3x}\) y queremos encontrar\(c\) tal que\(f(0)=2\). Ahora bien\(f(0)=c \cdot 1\), también lo\(c=2\) hace el truco y la solución a esta ecuación diferencial muy simple es\(f(x)=2e^{3x}\).
Con ecuaciones diferenciales, aplicamos el operador diferencial\(D\) a funciones diferenciables (generalmente infinitamente diferenciables). Para las ecuaciones de recurrencia, consideramos el espacio vectorial\(V\) cuyos elementos son funciones desde el conjunto\(\mathbb{Z}\) de números enteros hasta el conjunto\(\mathbb{C}\) de números complejos. Luego consideramos una función\(A:V \rightarrow V\), llamada el operador de avance, y definida por\(Af(n)=f(n+1)\). (Por diversos trucos y juego de manos, podemos extender una secuencia {\(a_n:n \geq n_0\)} para que sea una función cuyo dominio es todo\(\mathbb{Z}\), por lo que esta técnica se aplicará a nuestros problemas.) De manera más general,\(A^pf(n)=f(n+p)\) cuando\(p\) es un entero positivo.
Dejar\(f \in V\) ser definido por\(f(n)=7n−9\). Luego aplicamos el polinomio operador de avance\(3A^2−5A+4\) a\(f\) con\(n=0\) lo siguiente:
\((3A^2 - 5A + 4)f(0) = 3f(2) - 5f(1) + 4f(0) = 3(5) - 5(-2) + 4(-9) = -11\).
Como análogo del Ejemplo 9.6, considere el siguiente ejemplo simple que involucra al operador de avance.
Supongamos que la secuencia {\(s_n:n \geq 0\)} satisface\(s_0=3\) y\(s_{n+1}=2s_n\) para\(n \geq 1\). Encuentra una fórmula explícita para\(s_n\).
- Solución
-
Primero, escribamos la pregunta en términos del operador de avance. Podemos definir una función\(f(n)=s_n\) para\(n \geq 0\), y luego la información dada se convierte en eso\(f(0)=3\) y
\(Af(n) = 2f(n)\),\(n \geq 0\).
¿Qué función tiene la propiedad que cuando la adelantamos, es decir, evaluarla en\(n+1\), da el doble del valor que toma en\(n\)? La primera función que te viene a la mente debe ser\(2^n\). Por supuesto, al igual que con nuestra ecuación diferencial, para cualquier constante\(c, c2^n\) también tiene esta propiedad. Esto sugiere que si tomamos\(f(n)=c2^n\), estamos en camino de resolver nuestro problema. Ya que sabemos eso\(f(0)=3\), tenemos\(f(0)=c2^0=c\), así\(c=3\). Por lo tanto,\(s_n=f(n)=3 \cdot 2^n\) para\(n \geq 0\). Esto satisface claramente nuestra condición inicial, y ahora podemos comprobar que también satisface nuestra ecuación de operador de avance:
\(Af(n) = 3 \cdot 2^{n+1} = 3 \cdot 2 \cdot 2^n = 2 \cdot (3 \cdot 2^n) = 2 \cdot f(n)\).
Antes de pasar a desarrollar métodos generales para resolver ecuaciones de operadores de avance, digamos una palabra sobre por qué seguimos hablando en términos de operadores y mencionamos que podemos ver cualquier secuencia como una función con dominio\(\mathbb{Z}\). Si has estudiado algún álgebra lineal, probablemente recuerdes haber aprendido que el conjunto de todas las funciones infinitamente diferenciables en la línea real forman un espacio vectorial y que la diferenciación es un operador lineal en esas funciones. Nuestra analogía con las ecuaciones diferenciales se mantiene bien aquí, y funciona desde\(\mathbb{Z}\) para\(\mathbb{C}\) formar un espacio vectorial y\(A\) es un operador lineal en ese espacio. No nos detendremos en los aspectos técnicos de esto, y no se requiere ningún conocimiento del álgebra lineal para entender nuestro desarrollo de técnicas para resolver ecuaciones de recurrencia. No obstante, si te interesa más colocar todo lo que hacemos en base rigurosa, lo discutimos más a fondo en la Sección 9.5.
9.3.1 Ecuaciones de Coeficientes Constantes
Es fácil ver que una ecuación de recurrencia lineal se puede reescribir convenientemente usando un polinomio\(p(A)\) del operador de avance:
\[p(A)f = (c_0A^k + c_1A^{k-1} + c_2A^{k-2} + \cdot \cdot \cdot + c_k)f = g \label{9.3.1} \]
En\(\ref{9.3.1}\), pretendemos que\(k \geq 1\) es un entero,\(g\) es un vector fijo (función) de\(V\), y\(c_0,c_1,…,c_k\) son constantes con\(c_0,c_k \neq 0\). Tenga en cuenta que ya que\(c_0 \neq 0\), podemos dividir ambas partes por\(c_0\), es decir, de hecho podemos asumir que\(c_0=1\) cuando sea conveniente hacerlo.
9.3.2 Raíces y Factores
El polinomio\(p(A)\) puede analizarse como cualquier otro polinomio. Tiene raíces y factores, y aunque estos pueden ser difíciles de determinar, sabemos que existen. De hecho, si el grado de\(p(A)\) es\(k\), sabemos que sobre el campo de los números complejos,\(p(A)\) tiene\(k\) raíces, contando multiplicidades. Tenga en cuenta que ya que suponemos que\(c_k \neq 0\), todas las raíces del polinomio\(p\) son distintas de cero.
9.3.3 ¿Qué tiene de especial Cero?
¿Por qué hemos limitado nuestra atención a las ecuaciones de recurrencia de la forma\(p(A)f=g\) donde el término constante\(p\) es distinto de cero? Consideremos la alternativa por un momento. Supongamos que el término constante de\(p\) es cero y que 0 es una raíz\(p\) de multiplicidad\(m\). Entonces\(p(A)=A^mq(A)\) donde el término constante de\(q\) es distinto de cero. Y la ecuación\(p(A)f=g\) puede entonces escribirse como\(A^mq(A)f=g\). Para resolver esta ecuación, consideramos en cambio el problema más simple\(q(A)f=g\). Entonces\(h\) es una solución del problema original si y sólo si la función\(h′\) definida por\(h′(n)=h(n+m)\) es una solución al problema más simple. En otras palabras, las soluciones al problema original son solo traducciones de soluciones a la más pequeña, por lo que en su mayor parte seguiremos enfocándonos en ecuaciones de operador de avance donde\(p(A)\) tiene término constante distinto de cero, ya que poder resolver este tipo de problemas es todo lo que necesitamos para resolver el clase más grande de problemas.
Como caso especial, considere la ecuación\(A^mf=g\). Esto requiere\(f(n+m)=g(n)\), es decir,\(f\) es solo una traducción de\(g\).