Cálculo simbólico

En matemáticas y ciencias de la computación, el cálculo simbólico, también conocido como cálculo algebraico o álgebra computacional, es un área científica que se refiere al estudio y desarrollo de algoritmos y software para la manipulación de expresiones matemáticas y otros objetos matemáticos. Aunque, hablando con propiedad, el álgebra computacional debe ser un subcampo de la computación científica, ellos son considerados generalmente campos distintos, porque la computación científica se basa generalmente en el análisis numérico con números aproximados en punto flotante; mientras que, el álgebra computacional enfatiza el cálculo exacto con expresiones que contengan variables que no tienen cualquier valor dado y por lo tanto son manipulados como símbolos (de ahí se debe el nombre de cálculo simbólico).

Las aplicaciones de software que realizan cálculos simbólicos son conocidos como sistemas de álgebra computacional, con el término sistema aludiendo a la complejidad de las principales aplicaciones que incluyen, al menos, un método para representar los datos matemáticos en una computadora, un lenguaje de programación de usuario (por lo general diferente del lenguaje usado para la ejecución), un administrador de memoria, una interfaz de usuario para la entrada/salida de expresiones matemáticas, un gran conjunto de subrutinas para realizar operaciones usuales, como la simplificación de expresiones, la regla de la cadena utilizando diferenciación, factorización de polinomios, integración indefinida, etc.

En los comienzos del álgebra computacional, alrededor de 1970, cuando los algoritmos clásicos fueron puestos por primera vez en los ordenadores, resultaron ser altamente ineficientes.^[1] Por lo tanto, una gran parte de la labor de los investigadores en el campo consistió en revisar el álgebra clásica con el fin de hacerla más computable y descubrir algoritmos eficientes que implementen esta eficacia. Un ejemplo típico de este tipo de trabajo es el cálculo del máximo común divisor de polinomios, que se requiere para simplificar fracciones. Casi todo en este artículo, que está detrás del algoritmo clásico de Euclides, ha sido introducido por la necesidad del álgebra computacional.

El álgebra computacional es ampliamente utilizada para experimentar en matemática y diseñar las fórmulas que se utilizan en los programas numéricos. También se usa para cálculos científicos completos, cuando los métodos puramente numéricos fallan, como en la criptografía asimétrica o para algunos problemas no lineales.

Terminología

Algunos autores distinguen álgebra computacional de cálculo simbólico usando el último nombre para hacer referencia a las clases de computación simbólica que no sean el cálculo con fórmulas matemáticas. Algunos autores utilizan la computación simbólica para la materia en el aspecto de ciencias de la computación y "álgebra computacional" para el aspecto matemático.^[2] En algunos idiomas el nombre del campo no es una traducción directa de su nombre en inglés. Por lo general, se le llama calcul formel en francés, que significa "cálculo formal".

El cálculo simbólico también ha sido referido, en el pasado, como manipulación simbólica, manipulación algebraica, procesamiento simbólico, matemática simbólica, o álgebra simbólica; pero estos términos, que también se refieren a la manipulación no computacional, no están más en uso para referirse al álgebra computacional.

Comunidad científica

No existe una sociedad científica que sea específica del álgebra computacional, pero esta función es asumida por el grupo de interés especial de la ACM llamada SIGSAM (Special Interest Group on Symbolic and Algebraic Manipulation).^[3]

Hay varias conferencias anuales sobre álgebra computacional, siendo el premier ISSAC (International Symposium on Symbolic and Algebraic Computation), el cual es patrocinado regularmente por SIGSAM.^[4]

Hay varias revistas especializadas en el álgebra computacional, siendo Journal of Symbolic Computation fundada en 1985 por Bruno Buchberger, una de las principales.^[5] Hay también otras varias revistas que publican regularmente artículos de álgebra computacional.^[6]

Representación de datos

Como software numérico son altamente eficientes para el análisis numérico aproximado; es común, en álgebra computacional, para enfatizar en el cálculo exacto de los datos exactamente representados. Tal como una representación exacta, implica que, incluso cuando el tamaño de la salida es pequeño, entonces los datos intermedios que son generados durante un cálculo pueden crecer de un modo impredecible. Este comportamiento se denomina desbordamiento de la expresión. Para obviar este problema, se utilizan diversos métodos en la representación de los datos, así como en los algoritmos que los manipulan.

Números

Los sistemas de números habituales utilizados en el análisis numérico son o bien los números de punto flotante o los números enteros de un tamaño acotado fijo, que están inadecuadamente llamados enteros por la mayoría de los lenguajes de programación. Ninguno es conveniente para el álgebra computacional, debido al desbordamiento de la expresión.

Por lo tanto, los números básicos en álgebra computacional son los números enteros de los matemáticos, comúnmente representados por una señalizada secuencia ilimitada de dígitos en alguna base de numeración, por lo general la base más grande permitida por la palabra de la máquina. Estos números enteros permiten definir los números racionales, que son fracciones irreducibles de dos números enteros.

La programación de una aplicación eficaz de las operaciones aritméticas es una tarea difícil. Por lo tanto, la mayoría de los sistemas de álgebra computacional libres y algunos comerciales, como Maple (software), utilizan la biblioteca GMP; el cual es por lo tanto un estándar de facto.

Expresiones

Excepto para los números y variables, cada expresión matemática puede ser vista como el símbolo de un operador seguido por una secuencia de operandos. En el software del álgebra computacional, las expresiones se suelen representar de esta manera. Esta representación es muy flexible, y muchas cosas, que no parecen ser expresiones matemáticas a primera vista, pueden ser representadas y manipuladas como tal. Por ejemplo, una ecuación es una expresión con "=" como un operador, una matriz puede ser representada como una expresión con "matriz" como un operador y sus filas como operandos.

Incluso los programas pueden ser considerados y representados como expresiones con el operador "procedimiento" y, al menos, dos operandos; la lista de parámetros y el cuerpo, que son en sí mismos una expresión con "cuerpo" como un operador y una secuencia de instrucciones como operandos. A la inversa, cualquier expresión matemática puede ser vista como un programa. Por ejemplo, la expresión a + b puede ser vista como un programa para la adición, con a y b como parámetros. La ejecución de este programa consiste en la evaluación de la expresión para valores dados de a y b, y si no tienen ningún valor - o sea, que son indeterminados -, el resultado de la evaluación es simplemente su entrada.

Este proceso de evaluación diferida es fundamental en el álgebra computacional. Por ejemplo, el operador "=" de las ecuaciones es también, en la mayoría de los sistemas del álgebra computacional, el nombre del programa de la prueba de igualdad: normalmente, la evaluación de una ecuación representa una ecuación, pero, cuando se necesita una prueba de igualdad, - ya sea preguntado explícitamente por el usuario a través de una "evaluación de un booleano" de comandos, o automáticamente iniciado por el sistema en el caso de una prueba dentro de un programa -, entonces la evaluación de un booleano 0 o 1 se ejecuta.

A medida que el tamaño de los operandos de una expresión es impredecible y puede cambiar durante una sesión de trabajo, la secuencia de los operandos se suele representar como una secuencia de punteros (como en Macsyma) o como ingresos de una tabla hash (como en Maple).

Simplificación

La aplicación cruda de las reglas básicas de derivación con respecto a x en la expresión ${\displaystyle a^{x}}$ da el resultado ${\displaystyle x\cdot a^{x-1}\cdot 0+a^{x}\cdot (1\cdot \log a+x\cdot {\frac {0}{a}})}$. Tal horrible expresión no es aceptable claramente, y es necesario un procedimiento de simplificación tan pronto como se trabaja con expresiones generales.

Esta simplificación se realiza normalmente a través de reglas de reescritura. Hay varias clases de reglas de reescritura que deben ser consideradas. La más simple consiste en las reglas de reescritura que siempre reducen el tamaño de la expresión, como E → 0 o sin(0) → 0. Se aplican de forma sistemática en los sistemas del álgebra computacional.

La primera dificultad se presenta con operaciones asociativas como la suma y la multiplicación. La forma estándar de tratar con la asociatividad es considerar que la adición y multiplicación tienen un número arbitrario de operandos, o sea, a + b + c se representa como "+"(a, b, c). ¿Qué pasa con a - b + c? Para hacer frente a este problema, la forma más sencilla es volver a escribir de manera sistemática -E, E-F, E/F como (-1)⋅E, E + (-1)⋅F, E⋅F⁻¹ respectivamente. En otras palabras, en la representación interna de la expresión, no hay ninguna resta ni división ni menos unario, fuera de la representación de los números.

Una segunda dificultad se produce con la conmutatividad de la suma y la multiplicación. El problema es reconocer rápidamente los términos con el fin de combinarlos o cancelarlos. De hecho, el método para la búsqueda de términos semejantes, que consiste en la prueba de cada par de términos, es demasiado costoso para ser factible con sumas y productos muy largos. Para resolver este problema, Macsyma ordena los operandos de sumas y productos con una función de comparación que se ha diseñado con el fin de que los términos semejantes se encuentren en lugares consecutivos, y por lo tanto fáciles de detectar. En Maple, la función hash está diseñada para generar colisiones cuando se introducen términos semejantes, permitiendo unirlos entre ellos tan pronto como se introducen. Este diseño de la función hash permite también reconocer inmediatamente las expresiones de subexpresiones que aparecen varias veces en un cálculo y almacenarlas sólo una vez. Esto permite no sólo ahorrar algo de espacio en la memoria, sino también acelerar los cálculos, evitando repetir el mismo cálculo en varias expresiones idénticas.

Algunas reglas de reescritura a veces aumentan el tamaño de las expresiones a las que se aplican y algunas veces las disminuyen. Este es el caso de la distributividad o identidades trigonométricas. Por ejemplo la ley distributiva permite reescribir ${\displaystyle (x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1}$ y ${\displaystyle (x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1}$. Como no hay manera de hacer una buena elección general de aplicar o no una norma como la reescritura, tales reescrituras se realiza sólo cuando se les pregunta explícitamente por el usuario. Para la propiedad distributiva, la función computacional que aplica esta regla de reescritura es generalmente llamada "ampliar". La regla de reescritura inversa, denominada "factor", requiere de un algoritmo no trivial, que es por lo tanto una función clave en sistemas de álgebra computacional (ver factorización polinómica).

Aspectos matemáticos

En esta sección se consideran algunas cuestiones matemáticas fundamentales que plantean en cuánto uno quiere manipular expresiones matemáticas en un ordenador. Consideramos principalmente el caso de las fracciones racionales multivariantes. Esto no es una restricción real, porque, tan pronto como las funciones irracionales que aparecen en una expresión se simplifican, son generalmente considerados nuevos indeterminados. Por ejemplo ${\displaystyle (\sin(x+y)^{2}+\log(z^{2}-5))^{3}}$ es visto como un polinomio en ${\displaystyle \sin(x+y)}$ y ${\displaystyle \log(z^{2}-5)}$.

Igualdad

Hay dos nociones de igualdad de expresiones matemáticas. La igualdad sintáctica es la igualdad de las expresiones que significa que se escriben (o representan en una computadora) de la misma manera. Como es trivial, es raramente considerado por los matemáticos, pero es la única igualdad que es fácil de probar con un programa. La igualdad semántica es cuando dos expresiones representan el mismo objeto matemático , como en ${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}}$.

Se sabe que no puede existir un algoritmo que decide si dos expresiones que representan números son semánticamente iguales, si el exponente y los logaritmos se permiten en las expresiones. Por lo tanto (semánticamente) la igualdad puede ser probada sólo en algunas clases de expresiones tales como los polinomios y las fracciones racionales.

Para probar la igualdad de dos expresiones, en lugar de diseñar un algoritmo específico, es habitual ponerlos en alguna forma canónica o poner su diferencia en una forma normal y probar la igualdad sintáctica del resultado.

A diferencia de la matemática habitual, "forma canónica" y "forma normal" no son sinónimos en el álgebra computacional. Una forma canónica es aquella en la que dos expresiones en forma canónica son semánticamente iguales si y sólo si son sintácticamente iguales, mientras que una forma normal es aquella en la que una expresión en forma normal es semánticamente cero sólo si es sintácticamente cero. En otras palabras, cero tiene una única representación de expresiones en forma normal.

Las formas normales son generalmente preferidas en álgebra computacional por varias razones. En primer lugar, las formas canónicas pueden ser más costosa de calcular que las formas normales. Por ejemplo, para poner un polinomio en forma canónica, se tiene que ampliar por distributividad cada producto, si bien no es necesario, con una forma normal (véase más adelante). En segundo lugar, puede ser el caso, como por expresiones con radicales, que una forma canónica, si existe, depende de algunas decisiones arbitrarias y que estas opciones pueden ser diferentes para dos expresiones que han sido calculadas de forma independiente. Esto puede hacer impracticable el uso de una forma canónica.

Forma normal de las fracciones racionales

En esta sección, se describe una forma normal de uso frecuente para las fracciones racionales multivariantes.

Véase también

• Demostración automática de teoremas
• Prueba asistida por un ordenador
• Verificación de pruebas
• Verificación de modelos
• Cálculo simbólico-numérico
• Simulación simbólica

Referencias

1. Kaltofen, Erich (1982), «Factorization of polynomials», en B. Buchberger; R. Loos; G. Collins, eds., Computer Algebra, Springer Verlag, consultado el 20 de septiembre de 2012.
2. Making Computer Algebra More Symbolic (Invited), Stephen M. Watt, pp. 43-49, Proc. Transgressive Computing 2006: A conference in honor or Jean Della Dora, (TC 2006), April 24–26, 2006, Granada Spain
3. SIGSAM official site
4. SIGSAM list of conferences Archivado el 8 de agosto de 2013 en Wayback Machine.
5. Cohen, Joel S. (2003). Computer Algebra and Symbolic Computation: Mathematical Methods. AK Peters, Ltd. p. 14. ISBN 978-1-56881-159-8. Consultado el 30 de diciembre de 2009. (requiere registro).
6. SIGSAM list of journals

Otras lecturas

Para una definición detallada de la materia:

• Symbolic Computation (An Editorial), Bruno Buchberger, Journal of Symbolic Computation (1985) 1, pp. 1–6.

Para los libros de texto dedicados al tema:

• Davenport, James H.; Siret, Yvon; Tournier, Èvelyne (1988). Computer algebra: systems and algorithms for algebraic computation. Translated from the French by A. Davenport and J.H. Davenport. Academic Press. ISBN 978-0-12-204230-0.
• von zur Gathen, Joachim; Gerhard, Jürgen (2003). Modern computer algebra (second edición). Cambridge University Press. ISBN 0-521-82646-2.

• Datos: Q175515