Resolución de relaciones de recurrencia con apoyo de Wolfram Mathematica

Solving recurrence relations supported by Wolfram Mathematica

Enrique Vílchez-Quesada

enrique.vilchez.quesada@una.cr

Escuela de Informática

Universidad Nacional. Heredia, Costa Rica.

Fecha de recepción del artículo: 22 de abril de 2014.

Fecha de revisión del artículo: 5 de junio de 2014.

Fecha de aprobación del artículo: 5 de julio de 2014.

Resumen

El presente trabajo introduce algunos algoritmos para resolver relaciones de recurrencia lineales, homogéneas y no homogéneas, con coeficientes constantes y no constantes, utilizando software como recurso principal en los procesos de resolución. La aplicación comercial Wolfram Mathematica ha brindado el sustento técnico necesario para la implementación de los métodos empleados. Se presentan además, distintos ejemplos de relaciones de recurrencia, mostrando la efectividad y limitaciones de los algoritmos creados por el autor y programados en el ambiente que provee Mathematica.

Palabras claves: relaciones; recurrencia; solución; software; Mathematica.

Abstract

This paper introduces some algorithms for solving linear relationships, homogeneous and non-homogeneous recurrence with constant and non-constant coefficients, using software as the main resource in solving processes. The Mathematica commercial application has provided the technical support necessary for the implementation of the methods used. It also presents other examples of recurrence relations, showing the effectiveness and limitations of the algorithms created by the author and programmed in Mathematica environment that provides.

Keywords: relations; recurrence; solution; software; Mathematica.

La resolución de relaciones de recurrencia es un tema fundamental en distintas áreas de conocimiento al proporcionar métodos de solución ante problemas complejos que muchas veces no pueden ser abordados de forma directa. Sus aplicaciones abarcan contenidos vinculados con matemática básica, estructuras de datos, análisis de algoritmos, entre otras.

Los procedimientos clásicos de resolución expuestos en la mayor parte de la bibliografía (Johnsonbaugh, 2005, Kolman, Busby y Ross, 1997) se fundamentan en la construcción de ecuaciones y sistemas de ecuaciones que los vuelven poco eficientes cuando el término , de la relación de recurrencia, depende de una cantidad significativa de expresiones anteriores a “n”.

Con el presente artículo se muestran algunos algoritmos novedosos para resolver relaciones de recurrencia lineales, homogéneas y no homogéneas, con coeficientes constantes y no constantes, utilizando como apoyo el uso de software. En la actualidad el empleo de programas de computación para contribuir con la simplificación de procesos es una tarea muy común y necesaria, cuando los problemas abordados implican una cantidad de cálculos relativamente grandes. En este contexto, el software comercial Mathematica se ha convertido en el insumo esencial para resolver el álgebra relacionada con los métodos compartidos.

La notación que caracteriza este documento se sustenta en suponer una sucesión de números reales como una función , y donde a su elemento n-ésimo se le denota como . Además, la sucesión de números reales se representa a través de la expresión: .

Relaciones de recurrencia homogéneas lineales

En esta sección se muestra un método para encontrar más rápidamente los elementos de una sucesión definida por una relación de recurrencia homogénea lineal. Las ideas se basan en expresar la relación de recurrencia mediante un sistema de ecuaciones lineales, aspecto que ya había sido expuesto en Vílchez (2004). El aporte del presente trabajo reside en exhibir algunas funciones construidas mediante el uso del software Mathematica, para resolver relaciones de recurrencia de este tipo con coeficientes constantes o sin estos.

Aspectos generales

Una relación de recurrencia homogénea lineal es aquella de la forma:

junto con las k condiciones iniciales:

siendo los funciones y los números reales fijos .

El lector debe observar que si todos los son números reales, la relación de recurrencia formada es de coeficientes constantes. El método aquí propuesto se fundamenta en el siguiente sistema de ecuaciones:

El cual, matricialmente puede expresarse así:

(1)

siendo,

y,

En (1) por el método iterativo, puede ser dado en términos de:

como se detalla a continuación:

Lo anterior permite concluir que:

(2)

Como:

entonces en (2), corresponde a la última fila de la matriz resultante al calcular:

De hecho, la expresión (2) constituye un algoritmo que permite determinar los elementos de más rápidamente en comparación con la relación de recurrencia original y, es en este punto, donde el empleo de software se convierte en una herramienta esencial.

Encontrando elementos de la sucesión y comparando velocidades

En Mathematica una implementación de (2) que retorna la última fila de la matriz es:

Los argumentos Coeficient_List y ConditionInitial_List definen la relación de recurrencia mediante un vector de coeficientes y una lista de condiciones iniciales, respectivamente. En ElementoSucesiónH el parámetro m_ simboliza un número natural sobre el cual se desea obtener de la sucesión , el término . Pese a todos los cálculos que involucra ElementoSucesiónH, esta función resulta ser más rápida que la relación de recurrencia original. Lo anterior se puede comprobar experimentalmente a través del siguiente programa elaborado con Mathematica:

El comando Timing en PruebaH determina el tiempo de ejecución en el cálculo de elementos de , comparando dos formas de resolución por medio de las cuales se obtienen: ElementoSucesiónH y la relación de recurrencia inicial. PruebaH compara los tiempos y determina cuál método fue más eficiente en cada caso. Consideremos a continuación algunos ejemplos de recorrido.

Ejemplo 1. Sea la sucesión recursiva sujeta a las condiciones y . Compare la velocidad de convergencia de la relación de recurrencia dada y la función ElementoSucesiónH.

Solución 1. Con la finalidad de crear en el software Mathematica, se debe cambiar la notación empleada en el enunciado, sustituyendo n por n-2:

Luego:

ClearAll limpia de la memoria la variable , Table verifica que en las 31 comparaciones realizadas, y ElementoSucesiónH den el mismo resultado y PruebaH proporciona la salida mostrada. Del Out se concluye que en la mayor parte de los casos el algoritmo expuesto en (2) es más eficiente.

Ejemplo 2. Considere la sucesión definida por la relación de recurrencia sujeta a las condiciones , y . Compare la velocidad de respuesta de la relación de recurrencia y la función ElementoSucesiónH.

Solución 2. Por las limitaciones sintácticas del software, en la relación de recurrencia inicial se debe sustituir n por n-3, de donde:

Por otra parte, en Mathematica:

En la salida arrojada por el programa, el algoritmo matricial fue más eficiente 10 veces. Pese a ello, las 10 ejecuciones donde fue más efectivo ocurrieron en los 10 cálculos finales, por lo que podríamos interpretar que a partir del elemento 21 este método se mostró más rápido.

Los ejercicios anteriores evidencian de forma empírica la efectividad de (2) sobre la relación de recurrencia preliminar.

Resolviendo relaciones de recurrencia

Mediante el uso de ElementoSucesiónH y el comando del software Mathematica FindSequenceFunction es posible generar una función que intenta encontrar de manera explícita los elementos de una sucesión dada por una relación de recurrencia homogénea lineal. FindSequenceFunction recibe como parámetros una lista con algunos elementos de la sucesión y busca una fórmula explícita que la genere. No en todos los casos se desempeña exitosamente, pero en muchos sí lo hace, convirtiéndose este mecanismo de razonamiento, en la base del algoritmo empleado para buscar la solución de una relación de recurrencia homogénea lineal cualesquiera. El método ResolRRH realiza el proceso descrito en este apartado.

ResolRRH busca una lista mínima de elementos de la sucesión recursiva para la cual FindSequenceFunction retorna una respuesta. Esto puede provocar en algunos ejemplos que ResolRRH se sobrecargue, ocasionando un tiempo de ejecución poco satisfactorio. En dichos casos, lo ideal es aislar del código de ResolRRH, la función que permite encontrar elementos de , lo cual permitiría al usuario correr manualmente FindSequenceFunction sobre una cantidad de elementos mm_ que se escogería directamente. Esta función corresponde a:

Se abordan algunos ejemplos de uso.

Ejemplo 3. Resuelva la sucesión recursiva sujeta a las condiciones iniciales y . Compare la velocidad de convergencia de la solución explícita y la función ElementoSucesiónH.

Solución 3. En Mathematica:

Si se desea comparar la velocidad de respuesta de la solución de la relación de recurrencia con respecto a ElementoSucesiónH, un código de programación afín es el siguiente:

Al emplear PruebaHS, se obtiene:

Los resultados parecen mostrar pocas diferencias en tiempo de ejecución, entre la solución explícita y el algoritmo matricial.

Ejemplo 4. Sea dada la relación de recurrencia sujeta a las condiciones , y . Resuelva y compare la velocidad de respuesta con respecto a la función ElementoSucesiónH.

Solución 4. En Mathematica:

Es importante aclarar en este ejercicio, cómo el método ResolRRH toma un tiempo de ejecución significativo dada la complejidad que implica para el programa Mathematica, encontrar la solución explícita. El lector puede observar, inclusive, en la resolución de la relación de recurrencia, una ecuación diferencial que representa la función encontrada por el ordenador. La respuesta anterior, también se genera en el software de manera más rápida haciendo uso de SolveRRHM:

Desde luego, sin haber corrido el método ResolRRH es imposible poder adivinar que en el valor veintidós, SolveRRHM converge. Por otra parte, al emplear PruebaHS para comparar eficiencias, se obtiene:

De igual manera en este caso, tanto el algoritmo matricial como la función explícita presentan velocidades similares.

Un aspecto interesante de destacar en los ejemplos expuestos previamente, lo constituye la comparación del método matricial y la función explícita que resuelve cada relación de recurrencia. En los ejercicios se concluyó que su velocidad de respuesta es muy similar. Ciertamente, el desenlace es curioso dado que se esperaría un mejor rendimiento en la solución explícita. Pese a ello, los experimentos verifican que el algoritmo establecido en (2) es bastante competente para hallar los elementos de una sucesión, definida por una relación de recurrencia homogénea lineal.

También, para finalizar esta sección, es fundamental indicar que los métodos ResolRRH y SolveRRHM brindan buenos resultados en la mayor parte de relaciones de recurrencia homogéneas lineales, donde no aparecen funciones trascendentales. Esta advertencia es importante para el lector, pues si la relación de recurrencia contiene un logaritmo, o bien, una función trigonométrica, el comando FindSequenceFunction no suele proporcionar un resultado y como consecuencia de ello, tampoco ResolRRH y SolveRRHM.

La siguiente sección realiza un recorrido similar, para resolver relaciones de recurrencia lineales no homogéneas.

Relaciones de recurrencia lineales no homogéneas

Esta sección instaura un método para encontrar más rápidamente los elementos de una sucesión definida por una relación de recurrencia lineal no homogénea. Los fundamentos teóricos se sustentan en un conjunto de ideas demostradas formalmente en Vílchez (2009). El aporte principal de lo compartido reside en presentar ciertas funciones elaboradas con el software Mathematica, para resolver relaciones de recurrencia de este tipo con coeficientes constantes o sin estos.

Aspectos generales

Una relación de recurrencia lineal no homogénea es aquella de la forma:

junto con las k condiciones iniciales:

siendo los funciones y los números reales fijos . Si todos los son números, el lector preverá que la relación de recurrencia comprendida es de coeficientes constantes.

El método aquí propuesto se fundamenta en el siguiente sistema de ecuaciones lineales:

El cual, matricialmente puede expresarse así:

(3)

siendo,

y:

En (3) por el método iterativo, puede ser hallado en términos de:

como se detalla:

Lo anterior permite construir la ecuación:

(4)

Como:

entonces en (4), corresponde a la última fila de la matriz resultante. En la expresión (4), por lo tanto, es posible excluir a , pues contribuye con un cero en la suma que deriva la última fila de la matriz. Luego, (4) conforma un algoritmo que calcula los elementos de más rápidamente en comparación con la relación de recurrencia original. El software Mathematica se utilizará en este sentido, como una herramienta para el cómputo de (4).

Encontrando elementos de la sucesión y comparando velocidades

En Mathematica una función que retorna el resultado de la última fila de (4) es:

Los argumentos Coefi_List, ConditInitial_List y F_List definen la relación de recurrencia mediante un vector de coeficientes , una lista de condiciones iniciales y la función , respectivamente. En ElementoSucesiónNH el parámetro w_ simboliza un número natural sobre el cual se desea obtener de la sucesión , el término . A pesar de todos los cálculos que involucra ElementoSucesiónNH, esta función resulta ser más rápida que la relación de recurrencia original. Lo anterior, se puede comprobar experimentalmente a través del siguiente programa creado en Mathematica:

La instrucción Timing en PruebaNH encuentra el tiempo de ejecución en el cálculo de elementos de , comparando la eficiencia de ElementoSucesiónNH con respecto a la relación de recurrencia inicial. PruebaNH caso por caso, determina cuál algoritmo muestra un tiempo de ejecución menor.

Se puede verificar experimentalmente la efectividad de (4) sobre la ecuación recursiva de una sucesión dada.

Resolviendo relaciones de recurrencia

Por medio del uso de la función ElementoSucesiónNH y el comando del software Mathematica FindSequenceFunction, es posible construir un método que busca encontrar de manera explícita, los elementos de una sucesión dada por una relación de recurrencia lineal no homogénea. Esta forma de razonamiento es similar a lo propuesto en ResolRRH, con la excepción de recibir una relación de recurrencia lineal no homogénea. La función ResolRRNH realiza lo anteriormente descrito.

ResolRRNH determina una lista mínima de elementos de la sucesión recursiva para la cual FindSequenceFunction busca una función explícita. Esto puede provocar una sobrecarga, al igual que en la instrucción ResolRRH, suscitando un tiempo de ejecución poco satisfactorio. Lo ideal, algunas veces, para solucionar este conflicto, reside en aislar del código de ResolRRNH, la función que permite encontrar elementos de , facilitando correr manualmente FindSequenceFunction sobre una cantidad mm_ de elementos que el usuario elegiría. Esta función corresponde a:

Prosigue un ejemplo relacionado con el uso de estas funciones.

Ejemplo 5. Resuelva la sucesión recursiva sujeta a las condiciones y . Compare la velocidad de convergencia de la solución explícita y la función ElementoSucesiónNH.

Solución 5. En el software:

Si el objetivo ahora es comparar la velocidad de respuesta de la solución de la relación de recurrencia con respecto a ElementoSucesiónNH, un código de análisis es:

Al utilizar PruebaNHS se obtiene:

El Out muestra un tiempo de ejecución más adecuado en la solución explícita.

Un aspecto importante de destacar en el ejemplo anterior reside en la comparación del método matricial y la función explícita que resuelve cada relación de recurrencia. En el ejercicio se concluyó que la velocidad de convergencia es mejor en la función explícita. El experimento verifica que el algoritmo expuesto en (4) es menos competente para hallar los elementos de una sucesión, definida por una relación de recurrencia lineal no homogénea.

Finalizando esta sección, es fundamental indicar que los métodos ResolRRNH y SolveRRNHM brindan resultados muy aceptables en la mayor parte de relaciones de recurrencia lineales no homogéneas, donde no aparecen funciones trascendentales. Esta advertencia es esencial, pues si la relación de recurrencia contiene un logaritmo, o bien, una función trigonométrica, el comando FindSequenceFunction, como ya se había señalado, con frecuencia no proporciona un resultado y, por lo tanto, tampoco lo hacen ResolRRNH y SolveRRNHM.

Conclusiones

Los métodos de trabajo expuestos en el presente artículo representan un esfuerzo por buscar algoritmos novedosos que permitan resolver computacionalmente relaciones de recurrencia de cualquier tipo.

Lo anterior resulta una búsqueda muy ambiciosa, pero necesaria, ante los diversos problemas que demandan el planteamiento y la exigencia de resolución, de una relación de recurrencia.

A pesar de las limitaciones de los algoritmos empleados, estos ofrecen una buena alternativa específicamente en relaciones de recurrencia lineales homogéneas, no homogéneas, con coeficientes constantes o sin estos. Además, en casos particulares, las funciones compartidas pueden resultar caminos viables hacia la exploración de relaciones de recurrencia no lineales.

Referencias

Calderón, S. y Morales, M. (2000). Relaciones de recurrencia. Costa Rica: Taller de publicaciones del Instituto Tecnológico de Costa Rica.

Johnsonbaugh, R. (2005). Matemáticas discretas. México: Pearson Prentice Hall.

Kolman, B., Busby, R. y Ross, S. (1997). Estructuras de matemáticas discretas para computación. México: Prentice-Hall Hispanoamericana.

Monge, J. y Vílchez, E. (2001). Valores propios y las sucesiones definidas de forma recursiva. Revista Virtual Matemática, Educación e Internet, 2(2), 1-16. Descargado de http://www.tec-digital.itcr.ac.cr/revistamatematica/ContribucionesN22001/Monge/ final/index.html

Rosen, K. (2007). Discrete Mathematics and its applications [Matematica discrete y sus aplicaciones.]. USA: Mc. Graw-Hill.

Vílchez, E. (2004). Resolución de sucesiones definidas por una relación de recurrencia homogénea lineal con valores propios de multiplicidad algebraica mayor estricta que uno. Revista Virtual Matemática, Educación e Internet, 5(2). 1-16. Descargado de http://www.tec-digital.itcr.ac.cr/revistamatematica/contribuccionesV5n2dic004/ Vilchez-recurrencia/ARecurrencia2WEB/index.html

Vílchez, E. (2009). Resolución de relaciones de recurrencia lineales no homogéneas con coeficientes constantes a través de valores y vectores propios. Revista Virtual Matemática, Educación e Internet, 10(1). 1-29. Descargado de http://www.tec-digital.itcr.ac.cr/revistamatematica/ARTICULOS_V10_N1_2009/RESOLUCION_RELACIONES_RECURRENCIA/index.htm

Resolución de relaciones de recurrencia con apoyo de Wolfram Mathematica (Enrique Vílchez Quesada) por Revista Uniciencia se encuentra bajo una Licencia CreativeCommons Atribución-NoComercial-SinDerivadas 3.0 Unported.