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

Latest revision as of 09:55, 17 November 2017

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 $1/3$ 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 $1/3$ 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: ${\textstyle G=(N,\Sigma ,S,P)}$ donde N es una colección finita de no terminales, ${\textstyle \Sigma }$ es un alfabeto compuesto de terminales, S es un no terminal determinado que se llama símbolo inicial y

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 ${\textstyle 1/3}$ 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).

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.

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):

Figure 3: Figura 3

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

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.
${\textstyle x_{i}=a+ih}$
${\textstyle h={\frac {b-a}{n}}}$ donde a es el límite inferior de la integral y b es el límite superior de la integral.
${\textstyle {\frac {(b-a)^{3}}{12n^{3}}}\sum _{i=1}^{n}f''(\xi _{i})}$ donde ${\textstyle \xi _{i}}$ 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) :

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 ${\textstyle {\frac {1}{3}}}$ de Simpson es la siguiente: ${\textstyle 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 }$ ,

Donde:

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

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:

Función	Notación
$e^{x}$	exp(x)
Logaritmo de base a de x	log(x,a)
X elevado a la A potencia	pow(x,a)
Raíz a-ésima de x	root(x,a)
Factorial de x	fact(x)
Seno de x	sin(x)
Coseno de x	cos(x)
Tangente de x	tan(x)
Cotangente de x	cot(x)
Secante de x	sec(x)
Cosecante de x	csc(x)
Seno Hiperbólico de x	sinh(x)
Coseno Hiperbólico de x	cosh(x)
Tangente Hiperbólica de x	tanh(x)
Cotangente Hiperbólica de x	coth(x)
Secante Hiperbólica de x	sech(x)
Cosecante Hiperbólica de x	csch(x)
Arco seno de x	asin(x)
Arco coseno de x	acos(x)
Arco tangente de x	atan(x)
Arco cotangente de x	acot(x)
Arco secante de x	asec(x)

Tabla 1 Ejemplos:

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

$\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 ]$

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

$\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 ]$

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).

Figura 5

Figure 5: Figura 5

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):

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):

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).

Figure 9: Figura 9

Figure 10: Figura 10

Figure 11: Figura 11

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 ${\frac {1}{3}}$ 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 ${\frac {\pi }{32}}$ 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.

Figure 13: Figura 13

Figure 14: Figura 14

Figure 15: Figura 15

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)

Latest revision as of 09:55, 17 November 2017