Archivo

Posts Tagged ‘método babilónico’

Análisis numérico :D

noviembre 21, 2010 3 comentarios

Hablemos de matemáticas, de números y de algoritmos. Hablemos, en específico, de lo que es el análisis numérico. Ya sea por placer o por responsabilidad, espero que al leer esta entrada logre explicar lo que es el análisis numérico, su importancia actual y dar una breve introducción, que les permita avanzar posteriormente más a fondo, a un tema que es verdaderamente emocionante.

¡Análisis numérico, genial!

Y entonces, comenzando con este maravilloso tema:

¿En qué consiste el análisis numérico? ¿Cuál es su finalidad? Para dar una definición sencilla y clara será útil analizar uno de los problemas más conocidos dentro de la computación: El problema del agente viajero. El problema es tan simple como su nombre lo hacer aparentar, pues consiste en encontrar la ruta más corta y de menor costo entre una serie de nodos, de tal manera de que cada nodo sea visitado exactamente una sola vez.

Agente Viajero

Para solucionar este problema por lo general se emplean grafos ponderados (con un peso por arista) no dirigidos(multidireccionales) que representan los nodos (o ciudades) y el costo de viaje entre cada uno.

Grafo

Con la imagen superior podremos notar que, a pesar de tomarse a consideración sólo siete nodos, la complejidad para conocer el camino más corto ya es alta. Este es un ejercicio que se puede obtener a mano después de unos minutos de labor, sentido común y muchas comparaciones, pero si se manejara un número mayor de nodos, como por ejemplo 25, ¡vaya que el número de cálculos  crecería! Olvidémonos de los casos reales, donde el número de nodos, o en su caso ciudades, excede las centenas. El problema del viajero supone un alto grado de complejidad computacional y hace necesaria la adquisición de sistemas muy potentes y especializados que permitan obtener estos cálculos. Y aún así, el tiempo de solución es muy alto. Ahora bien, si obtener el resultado más corto es costoso, ¿Por qué no obtener un resultado que se aproxime a la solución real y que sea, aunque costoso, confiable y más rápido? Aquí es donde entra el algoritmo de Dijkstra, el cual obtiene la ruta más optima por medio de un algoritmo de aproximación. Aunque se presentan diferentes situaciones donde el algoritmo por lo general no es útil u óptimo, situaciones a las que sin embargo se les puede dar solución, el algoritmo nos permite computar la distancia más corta con un margen de error mínimo. Es importante mencionar que, a pesar de que el algoritmo es capaz de obtener la ruta óptima, la obtención puede ser muy costosa y es entonces que se recurre a la aproximación; a la obtención de un resultado menos óptimo, pero de similar utilidad. Y entonces:

¿Qué es el análisis numérico?

El análisis numérico es la búsqueda y estudio de algoritmos que permitan la solución de problemas complejos, que no pueden ser solucionados por una secuencia discreta de pasos o cuyos resultados son muy costosos de obtener en cuanto a tiempo y esfuerzo se refiere. El análisis numérico propone la obtención de resultados aproximados, dado un margen de error, que cubran las necesidades de quien requiere los resultados a una velocidad mayor que la de la obtención del resultado más óptimo o preciso, pero que aún así cumpla le sea útil para su finalidad. La importancia del análisis numérico dentro de las ciencias computacionales es inconmensurable debido a las bases fundamentales de la computación y las innumerables necesidades de las demás ciencias de procesar y obtener información a altas velocidades. En muchas ocasiones es inadecuado emplear soluciones de fuerza bruta, que devuelven el valor óptimo a costa de altos costos de ejecución y tiempo, y entonces es necesario obtener métodos alternos de proceso que devuelvan resultados no óptimos pero igual de útiles.

En lo personal, el análisis numérico es apasionante por la manera en que funciona: su finalidad es simplificar y obtener resultados útiles, dentro de un margen óptimo y poco costosos. Le da un aspecto más natural a la obtención de los resultados requeridos debido al margen de error y al sentido de la precisión requerida. Por lo general los cursos de análisis numérico comienzan estudiando este importante elemento de las matemáticas, la precisión de los resultados, y permiten el empleo de los métodos obtenidos con un grado alto de confianza. Es apasionante ver como una operación compleja puede ser simplificada a una recursión continua de pasos simples que ofrecen resultados con un margen de error arbitrario. Daré un ejemplo sencillo de la utilización del análisis numérico para la obtención de resultados aproximados.

La Raíz Cuadrada (Y el Método Babilónico :D)

Todos conocemos la raíz cuadrada, aquella operación presente en un gran número de fórmulas y fundamental dentro de la ciencia. Si pensamos en la solución manual, recordamos el radical con el radicando en su interior:

raíz simple

pero, si se plantea una raíz como:

No la raíz de dos!

¿Como se obtiene el resultado? La raíz de dos es un número irracional, es decir, no puede ser representada por medio de una fracción. Entonces, ¿Cómo la obtenemos? La raíz se podría obtener por el método manual de solución, pero transformar esa metodología a líneas de código o traducirla a lenguaje máquina no sería algo sencillo. Pero dicha metodología manual no es necesaria si se estudia un poco mejor el caso. Comenzando por el nombre del a operación, la “raíz cuadrada”, nos damos cuenta de las primeras pistas:

cuadrado

La raíz cuadrada se pude visualizar como la longitud de una base de tal manera que multiplicada por sí misma (como en un cuadrado) te de el área deseada. Debido a que no conocemos esta longitud, podemos comenzar a aproximarnos a ella por medio de la formula del rectángulo, el cual es equivalente a un cuadrado dada una base y altura igual. Entonces, dadas la fórmula del rectángulo:

area rectangulo

se puede calcular una nueva base y a partir de ésta una nueva altura, de tal manera de que la base y la altura se aproximen en su valor:

fórmulas de recursión

Con estas dos fórmulas se puede obtener una única fórmula, sustituyendo fórmula de la altura en la fórmula de la base (debido a que el valor de la altura es una simple función entre la altura y la base, no es necesario calcularla aparte):

fórmula de recursión

así, si se introduce la base resultante dentro de la ecuación superior, con el área igual al valor del cual se busca su raíz, se obtendrá, con cada iteración, un valor más cercano al deseado. La ecuación superior se ha de anotar como una función recursiva de la siguiente manera:

función recursiva

donde n es el valor del cual obtener su raíz y x es un número que se aproxime al resultado. Aunque realmente no importa el valor de x dado inicialmente, se recomienda utilizar un valor cercano al valor final, pues de esta manera converge más rápidamente al resultado:

resultados!

¡Listo! ahí tenemos la raíz cuadrada de 2 con una precisión de 7 dígitos, más que suficiente para la ocasión. Si vemos, sólo fue necesario realizar 4 iteraciones de con una x igual a 1. Mientras más alejada esté la x del valor deseado, más iteraciones se tendrán que realizar. Así termina la obtención de la raíz cuadrada de dos y tu, posiblemente, primer método numérico. Un buen ejercicio es la obtención de la función recursiva para las raíces cúbicas.

Herramientas

Para continuar con el aprendizaje, o para volver a comenzar en caso de que algo no haya quedado claro, se puede utilizar el libro llamado “Numerical Analysis” de los autores Richard L. Burden and J. Douglas Faires, donde se plantea un curso de introducción al análisis numérico, sus fundamentos y sus distintas aplicaciones. Posteriormente dedica el resto de los capítulos a información de consulta, de tal manera de que después de ser introducido se puede continuar el estudio del análisis numérico. Normalmente se recomienda para realizar ejercicios en un programa llamado MatLab. Este posee muchísimas herramientas, además de que existe una amplia gama de tutoriales y demos en Internet. Con MatLab se pude obtener una licencia de prueba. Otra alternativa es  SciLab, el cual es similar a MatLab y además posee un traductor de este último a SciLab, y es gratuito. Así que si no posees dinero para una licencia de MatLab o no quieres versiones de prueba, SciLab es una gran opción. El ejemplo en la imagen anterior está realizado en SciLab. Un gran recurso matemático para conocer y explorar el mundo del análisis numérico es http://mathworld.wolfram.com/, una enciclopedia muy completa donde se pueden resolver todas las dudas que uno tenga. Otra herramienta de visualización muy interesante es http://www.wolfram.com/mathematica/, donde se pueden encontrar diferentes comprobaciones a diferentes teoremas, métodos y axiomas matemáticos. Una comunidad muy rica de discusión es Mathoverflow , donde se puedes resolver tus dudas por medio de una comunidad amigable y consultar las entradas de otros usuarios. Además de estos sitios, existe un blog llamado BetterExplained donde el autor procura dar una explicación clara e intuitiva a diferentes problemas que se presentan al momento de conocer el mundo de las matemáticas. Éste en lo personal me ha resultado muy útil al momento de querer conocer profundamente el comportamiento o razón de alguna constante o procedimiento, por lo que lo recomiendo enormemente C:.

Eso es todo para esta entrada, espero haber sido claro y que se despierte esa brillante chispa en su mente por explorar el mundo numérico que nos rodea. Buen día.

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.