Sistema de cómputo distribuido para aproximación de series e integrales

==Sistema de cómputo distribuido para aproximación de series e integrales==

'''Jesús Carmona, Mario Cuevas, Luis Pereyra 

Facultad de Ingeniería 

Universidad Autónoma de Chihuahua 

Circuito No. 1, Campus Universitario 2, Chihuahua, Chihuahua C.P. 31125 

e-mail: a291463@uach.mx, mcuevas@uach.mx, a261804@uach.mx  '''

==Resumen==

El trabajo realizado fue desarrollar una herramienta de software que permite resolver integrales y sumas definidas con la particularidad de dividir el problema de forma equitativa entre diferentes servidores, con esto, se pretende alcanzar una mejor precisión y rapidez con la que son realizados los cálculos.   Se diseño un sistema de cliente servidor desarrollado en java para establecer las conexiones entre los distintos servidores a través de la red. Adjunto a eso se desarrollo un interprete de ecuaciones por medio de una gramática independiente del contexto para analizar las cadenas de texto que se pretenden resolver. En el aspecto teórico se emplearon las reglas de integración numérica de el trapecio y de <math>1/3</math> de Simpson  para la realización de los cómputos matemáticos necesarios para la resolución del problema.

''Palabras Clave.'' Integración, Series, Distribución,

==Distributed computing system for series and integral approximation   ==

==Abstract==

The work was to develop a software tool that allows solving definite integrals and sums with the particularity of dividing the problem equitably between different servers, with this, it is sought to achieve a better precision and speed with which the calculations are made.    A server client system developed in Java was designed to establish the connections between the different servers through the network. Adjunct to that was developed an interpreter of equations by means of a Grammar Independent of the Context to analyze the strings of text that are intended to solve. In the theoretical aspect, the numerical integration rules of the trapezoid and <math>1/3</math> of Simpson were used to perform the mathematical computations necessary to solve the problem.    ''Keywords.'' Integration, Series, Distribution,

==Introducción==

El proyecto funciona mediante un cliente encargado de recibir una ecuación en forma de cadena de texto introducida por el usuario, este cliente verifica la existencia de servidores disponibles para hacer uso de ellos en la distribución del cálculo, cada servidor se encarga de consultar el número de núcleos que tiene disponibles de manera local, con el propósito de volver a repartir la carga y realizar de manera mas rápida el problema, después cada servidor genera un resultado parcial compuesto por la suma de todos los resultados de las operaciones realizadas por el número de núcleos, el cual es enviado como respuesta al cliente, quien suma todas las partes para obtener un resultado global, el cual es mostrado al usuario.

El programa reconoce las ecuaciones usando Gramáticas Independientes del Contexto , las cuales están definidas como una 4-tupla: <math display="inline"> G=(N,\Sigma ,S,P)</math> donde N es una colección finita de no terminales, <math display="inline">\Sigma </math> es un alfabeto compuesto de terminales, S es un no terminal determinado que se llama símbolo inicial y

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: left; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>P \subseteq N X (N \cup \Sigma )^{*} </math>
|}
|}

es un conjunto de producciones.[1]

Los métodos de integración numérica se pueden utilizar para integrar funciones dadas, ya sea mediante una tabla o en forma analítica, la integración numérica puede ahorrar tiempo y esfuerzo si solo se desea conocer el valor numérico de la integral.[2] Las ecuaciones son resueltas utilizando métodos numéricos haciendo uso de la regla de <math display="inline">1/3</math> de simpson de aplicación múltiple y la regla del trapecio compuesta.

===Regla del trapecio===

El principio básico de dicha método es calcular el área bajo la curva de una función como se muestra en la (figura 1).

<div id='img-1'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura1.png|121px|Figura 1]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 1:''' Figura 1
|}

La regla del trapecio se basa en un polinomio de primer grado, es decir, si la función a integrar es de grado uno, el resultado sera exacto y no tendrá ningún error. La (figura 2) muestra como se comporta la regla del trapecio en un polinomio de grado mayor a uno. <div id='img-2'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura2.png|117px|Figura 2]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 2:''' Figura 2
|}

Una de las maneras de mejorar la precisión de este algoritmo consiste en dividir el intervalo de integración [a, b] en varios segmentos para así minimizar el margen de error, como se muestra en la siguiente figura  (figura 3):

<div id='img-3'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura3.png|100px|Figura 3]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 3:''' Figura 3
|}

La regla del trapecio compuesta esta dada por la formula: <math display="inline">I= \frac{h}{2}[f(a)+f(b)+2\sum _{i=1}^{n-1} f(x_{i})]-\epsilon </math>, <math display="inline">i=1,2,3,...,n</math>

Donde:

* f(a) es la función evaluada en el limite inferior de la integral.
* f(b) es la función evaluada en el limite superior de la integral.
* <math display="inline">x_{i}=a+ih</math>
* <math display="inline">h=\frac{b-a}{n}</math> donde a es el límite inferior de la integral y b es el límite superior de la integral.
* <math display="inline">\frac{(b-a)^{3}}{12n^{3}}\sum _{i=1}^{n}f''(\xi _i)</math> donde <math display="inline">\xi _i</math> es algún punto de la función.

Nótese que n no tiene un valor especifico ni se da alguna formula para calcularlo, esto se debe a que la n se definirá de acuerdo a los decimales de  precisión que se espera obtener de la integral.

===Regla de 1/3 de Simpson===

La regla de 1/3 de Simpson es similar a la regla del trapecio, la diferencia primordial esta en que se toma un polinomio de segundo grado para realizar la aproximación del área bajo la curva, por tanto gráficamente se observa de la siguiente manera  (figura 4) :

<div id='img-4'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura4.png|101px|Figura 4]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 4:''' Figura 4
|}

Dado que la parábola consta de tres puntos se requiere integrar un polinomio de Lagrange de segundo grado para llegar a  la formula de un tercio de Simpson de aplicación múltiple.

La formula usada en  la regla de <math display="inline">\frac{1}{3}</math> de Simpson es la siguiente: <math display="inline">I= \frac{h}{3}[f(x_{0})+4\sum _{i=1,3,5,...}^{n-1} f(x_{i})+24\sum _{j=2,4,6,...}^{n-2} f(x_{j})+f(x_{n}]-\epsilon </math>,

Donde:

* <math display="inline">f(x_{0}</math> es la función evaluada en el limite inferior de la integral.
* <math display="inline">f(x_{n}</math> es la función evaluada en el limite superior de la integral.
* <math display="inline">x_{i}=a+ih</math>
* <math display="inline">x_{j}=a+jh</math>
* <math display="inline">h=\frac{x_{n}-x_{0}}{n}</math> donde <math display="inline">x_{0}</math> es el límite inferior de la integral y <math display="inline">x_{n}</math> es el límite superior de la integral.
* <math display="inline">\frac{(b-a)^{5}}{180n^{4}}f^{-(4)}</math> .

===Gramática===

Mediante técnicas de Teoría de la computación se diseño una Gramática Independiente del Contexto (GIC) encargada de reconocer las cadenas de texto que serán analizadas por el programa, las cuales al ser procesadas de manera correcta inician el algoritmo matemático encargado de resolver las ecuaciones. La gramática se creo basada en la sintaxis de wolfram alpha en la cual las ecuaciones deben iniciar con un “int” o un “sum” dependiendo de si se quiere realizar una suma o una integral, seguido de un corchete ([), después se ingresa una ecuación, la cual puede o no empezar con un paréntesis y derivar en uno o mas términos ya sean funciones o constantes dependientes de una variable, después de ingresar por completo la ecuación se agrega una coma seguida de una llave() dentro de la cual el usuario escribe la variable respecto a la que se integrara o sumara y después escribirá los limites inferior y superior, todo esto separado por comas, y se finaliza cerrando las llaves y los corchetes. Es importante destacar la función ''int'' solo soporta una variable de integración, por lo que múltiples integrales requieren que se invoque la función de manera múltiple. A continuación se muestra una tabla con las funciones y el como aparecen en el programa:   
{|  class="floating_tableSCP wikitable" style="text-align: center; margin: 1em auto;min-width:50%;"
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Función 
| style="border-left: 2px solid;border-right: 2px solid;" |  Notación 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" | <math>e^{x}</math> 
| style="border-left: 2px solid;border-right: 2px solid;" |  exp(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Logaritmo de base a de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  log(x,a) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   X elevado a la A potencia 
| style="border-left: 2px solid;border-right: 2px solid;" |  pow(x,a) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Raíz a-ésima de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  root(x,a) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Factorial de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  fact(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Seno de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  sin(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Coseno de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  cos(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Tangente de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  tan(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Cotangente de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  cot(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Secante de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  sec(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Cosecante de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  csc(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Seno Hiperbólico de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  sinh(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Coseno Hiperbólico de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  cosh(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Tangente Hiperbólica de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  tanh(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Cotangente Hiperbólica de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  coth(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Secante Hiperbólica de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  sech(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Cosecante Hiperbólica de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  csch(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Arco seno de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  asin(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Arco coseno de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  acos(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Arco tangente de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  atan(x) 
|- style="border-top: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Arco cotangente de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  acot(x) 
|- style="border-top: 2px solid;border-bottom: 2px solid;"
| style="border-left: 2px solid;border-right: 2px solid;" |   Arco secante de x 
| style="border-left: 2px solid;border-right: 2px solid;" |  asec(x) 

|}


Tabla 1  Ejemplos: 

<math>\int _{0}^{15} x^{2}e^{3x}dx=int[pow(x,2)*exp(x), \left\lbrace x,0,15\right\rbrace]</math>

<math>\int _{0}^{5}x^{2}cos(x)e^{x}dx=int[pow(x,2)*cos(x)*exp(x),\left\lbrace x,0,5\right\rbrace]</math>

<math>\sum _{i=1}^{20}\frac{(i+21)}{2i}=sum[(i+12)/(2*i),\left\lbrace i,1,20,1\right\rbrace]</math>

<math>\sum _{n=2,4,6,...}^{100}(n-1)cos(n\pi )=sum[(n-1)*cos(n*pi), \left\lbrace n,2,100,2\right\rbrace]</math>

Nótese que para las sumas se agrego otro elemento en las llaves, este elemento denota el incremento que sufrirá la variable entre cada suma.

==Cliente y servidores==

El cliente fue desarrollado en Java, y su diseño le permite crear una red a la que se conectaran los servidores, en dichos servidores se busca la cantidad de núcleos que tiene disponibles la computadora para realizar las operaciones necesarias para resolver la integral o la suma introducida por el usuario.  En los siguientes diagramas se muestra el proceso de repartición realizado por el cliente y los servidores (figura5) y se ejemplifica su funcionamiento con una integral (figura 6).

<div id='img-5'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura5.png|600px|Figura 5]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 5:''' Figura 5
|}
<div id='img-6'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura6.png|211px|Figura 6]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 6:''' Figura 6
|}
Para comenzar a trabajar se debe de guardar un archivo junto al programa del cliente en el que aparecerán escritas las direcciones IP de las maquinas que se conectaran a la red de trabajo, en el caso de la maquina local debe ingresarse su Ip como “localhost”, después de eso todas las maquinas ejecutan el programa en java denominado “servidorsumatorias” como se muestra en el siguiente ejemplo en Linux (figura7):

<div id='img-7'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura7.png|264px|Figura 7]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 7:''' Figura 7
|}
después de encender el servidor el usuario a cargo del cliente ejecutara el programa de “cliente sumatorias” e ingresara su ecuación como se muestra en el siguiente ejemplo (figura 8): <div id='img-8'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura8.png|264px|Figura 8]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 8:''' Figura 8
|}
La división del trabajo se realiza en base a la cantidad de núcleos disponibles que regresa cada servidor, de tal manera que la integral se dividirá desde un inicio entre el número de núcleos y no entre el número de servidores disponibles, esto es para realizar una división mas homogénea, ya que no es lo mismo dar el mismo intervalo a una computadora que cuenta con 4 núcleos disponibles a darle el mismo intervalo a una que cuenta con solo un núcleo a su disposición. Una vez que el trabajo es dividido y enviado a los servidores estos regresaran un resultado parcial (figuras 9, 10 y 11) , una vez que concluye el proceso los resultados parciales son mostrados en pantalla y sumados por el cliente principal, quien muestra el resultado total (figura 12).   <div id='img-9'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura9.png|184px|Figura 9]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 9:''' Figura 9
|}
<div id='img-10'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura10.png|180px|Figura 10]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 10:''' Figura 10
|}
<div id='img-11'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura11.png|165px|Figura 11]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 11:''' Figura 11
|}
<div id='img-12'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura12.png|165px|Figura 12]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 12:''' Figura 12
|}

==Sumas e integrales==

Las sumas son realizadas de manera iterativa dividiendo la carga en intervalos de manera homogénea. Las integrales son realizadas de manera distinta dependiendo del tipo de función y de integral, es decir una integral sencilla es realizada por la regla del trapecio compuesta y una integral múltiple es realizada utilizando el método de integración de <math>\frac{1}{3}</math> de Simpson.  El programa divide la integral primero en segmentos grandes dependiendo de la diferencia que exista entre los limites superior e inferior, dichos segmentos servirán para que la distribución de trabajo dentro de la maquina sea mas estable, ademas estos segmentos serán divididos de nuevo al realizar el proceso de  integración. El criterio usado para la división de intervalos para la integración numérica fue mediante la diferencia de pendientes, se calcula la pendiente utilizando derivación numérica en el límite inferior y después se calcula en el punto medio; luego se repite este proceso con el punto medio y el límite superior, si al comparar cada par de pendientes el resultado esta fuera del parámetro el programa divide ese intervalo a la mitad y vuelve a realizar el proceso de comparación. Este algoritmo se repetirá hasta que la diferencia entre las pendientes este en el rango requerido de <math>\frac{\pi }{32}</math> radianes. El número de divisiones que se hicieron en este proceso sera la ''n'' a utilizar en la formula de integración por regla del trapecio compuesta para el numero de intervalos.

==Resultados y conclusiones==

Los resultados importantes a analizar obtenidos al probar este interprete fueron los siguientes: El primer objetivo era mejorar el manejo de memoria en el proyecto original, mejorar la rapidez y a lo mas mantener la precisión que ya manejaba el sistema.[4]  El sistema se comporto de manera estable al ingresarle una integral múltiple y como se muestra en el siguiente ejemplo (figuras 13, 14,15 y 16), el interprete es capaz de entender y resolver ecuaciones donde se combinan tanto series como integrales. <div id='img-13'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura13.png|198px|Figura 13]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 13:''' Figura 13
|}
<div id='img-14'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura14.png|198px|Figura 14]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 14:''' Figura 14
|}
<div id='img-15'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura15.png|221px|Figura 15]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 15:''' Figura 15
|}
<div id='img-16'></div>
{| class="floating_imageSCP" style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: 100%;max-width: 100%;"
|-
|[[Image:draft_Carmona_463159236-figura16.png|180px|Figura 16]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" | '''Figure 16:''' Figura 16
|}
De manera objetiva se debe reconocer que el programa aun no esta en su última etapa de desarrollo, ya que existen aspectos del mismo que pueden mejorarse, tal como la precisión y el uso de memoria requerido para alcanzar esas precisiones. Durante el desarrollo de el sistema para este proyecto se logro corregir de manera parcial el desbordamiento de pila que ocurría cuando se trataba de integrar funciones que crecían de manera exponencial, sin embargo aun falta trabajar en la repartición de los intervalos menores a uno ya que en ocasiones el programa trata de dividirlo mas de lo necesario y desencadena una multiplicación por un número tan cercano al 0 que la computadora regresa un 0 como resultado.  Se recomienda cambiar el lenguaje de programación del código fuente para tener acceso a otros tipos de dato que soporten mas decimales y nos den de ese modo la precisión que esperamos obtener del producto final.

==Referencias==

[1] Kelley, Dean,"Teoría de autómatas y lenguajes formales",Prentice Hall,(2000) 

[2] Nakamura, Sc. , "Métodos numéricos aplicados con software". México: Prentice Hall hispanoamericana, S.A.(1992) 

[3]Steven, Ch, Raymond, Ca. , "Métodos numéricos para ingenieros". México: McGraw-Hill, Interamericana.(2007) 

[4] Pereyra, Luis, "Sistema de cómputo distribuido para aproximación de series e integrales", Tesis de licenciatura,(2016)