You are currently browsing the monthly archive for enero 2011.

Ya escribí sobre los conceptos básicos de una simulación numérica en el artículo Cómo hacer una simulación numérica. En este artículo quiero hablar de un caso más específico que muchas veces se da en la física: la simulación de una ecuación diferencial.

La “solución” de una ecuación diferencial sería una expresión analítica como x(t) = algo que ya no depende ni de la función x(t) ni de una de sus derivadas. Hallar estas soluciones es un arte difícil; a veces demasiado difícil. Esto puede llegar a tanta desperación que se ha llegado a ofrecer una recompensa de un millón de dólares para dar la solución de la ecuación diferencial de Navier-Stokes – una cantidad decente para adquirir el equipo informático necesario para simularla.

Como ejemplo en este artículo usamos el movimiento de cuerpos celestes bajo el efecto de la gravedad. Este movimiento se puede describir en una ecuación diferencial. Es posible resolver esta ecuación diferencial para dos cuerpos y, debido a esto, se puede predicir con gran exactitud la posición de un planeta que gira alrededor del sol. Sin embargo, todavía no se ha hallado una solución exacta del problema de tres cuerpos.

Mientras no se puede hallar una ecuación analíticamente, no queda más remedio que simularla. Una simulación se suele hacer sobre el tiempo, es decir, se conoce un estado para un momento determinado y se calcula el estado para un instante después.

Para ello se hace uso de una característica fundamental de las ecuaciones diferenciales: que sean diferenciables – es decir que describen curvas sin salto ni esquinas. Cuando más de cerca veo una curva diferenciable, más se parece a una recta. Por ejemplo, si miro un círculo con una lupa, entonces sólo veo una parte del círculo. Cuando más pequeña es esta parte, más recta parece. Bajo un microscopio ya será difícil decidir si veo una parte de una recta o de un círculo. Esto sginifica, en matemático, que una aproximación de una curva por secciones rectas cortas es lo suficientemente buena cuando las secciones son lo suficientemente cortas. Esto resulta en eligir pasos lo suficientemente pequeños para una simulación numérica. Por simular sobre el tiempo, estos pasos son pasos de tiempo.

Cuando estos pasos son lo suficientemente pequeños, entonces puedo aproximar el problema por ecuaciones líneales. Por ejemplo, durante un instante corto T, el vuelo de la Tierra alrededor del sól sigue una recta. Durante este tiempo corto, la acceleración hacia el sol es constante. El algoritmo para calcular el movimiento de la Tierra o cualquier otro cuerpo celeste sería el siguiente.

  1. Para el momento n conozco la masa, la posición y las velocidades de todos los puntos de masa. Calculo la aceleración an que un cuerpo experimienta con la ley de Newtown, que es la suma vectorial de todas las acceleraciones gravitatorias que sufre este cuerpo por todos las demás masas.
  2. Considero la aceleración an constante durante un paso de tiempo T. Con este paso de tiempo calculo la velocidad: un+1 = an · T
  3. Considero también la velocidad un+1 constante durante un paso de tiempo T. Así hallo la nueva posición: xn+1 = un · T
  4. Con estos calculos conozco todos los datos para el instante n+1 y puedo comenzar una nueva iteración del algoritmo para el instante n+2 desde el punto 1.

Una simulación numérica es una aproximación. Debido a esto y la resolución numérica limitada de los ordenadores se acumulan errores significativos durante la simulación. Por ejemplo, los cuerpos podrían alcanzar velocidades cada vez mayores con el paso de tiempo – algo que no sucedería en la realidad. Por eso es habitual añadir factores de corrección. En el ejemplo podríamos forzar que la energía de movimiento total sea constante reduciendo o aumentando conjuntamiente las velocidades de todos los puntos de masa.

Suele requerir experiencia encontrar la mejor manera de “estabilizar” la simulación numérica, es decir, conseguir que se ajuste a la realidad física durante un tiempo idealmente infinito. A veces se hace un análisis matemático exhaustivo para entender los errores sistemáticos, por ejemplo, por qué la energía total tiene tendencia de aumentar. Al final no se hacen las simulaciones numéricas porque son fáciles, sino porque hallar la solución de la ecuación diferencial fue imposible.

Otra manera de mejorar la calidad de una simulación es variar la longitud de paso de tiempo. Cuando más corto es, más se aproxima el resultado a la realidad, pero menos tiempo total simulo con el mismo esfuerzo. Idealmente puedo ajustar la longitud del paso del tiempo según la situacición. Por ejemplo, la aceleración entre dos puntos de masa alejados entre sí no varia mucho y, por lo tanto, no cometo mucho error a tomar la aceleración constante. En cambio, en un momento drámatico de acercamiento veloz, la dirección y magnitud de la aceleración cambian rápidamente. En esta situación debo acortar el paso de tiempo si quiero mantener la misma magnitud de error en el cálculo.

A veces conviene transformar una ecuación diferencial en otra forma más ventajosa para la simulación numérica. Conseguir que encima el algoritmo de una simulación sea estable requiere a menudo un gran conocmiento matemático. Sin embargo, las versiones más simples y menos exactos son a menudo la base para video-juegos o animaciones bastante impresionantes. Por eso son también un reto acequible para aprendices en programacion.

Como no existe un “completamente correcto” en una simulación numérica, son una herramienta de enseñanza ideal, cuando el camino es la meta y no el resultado final. La programación de ecuaciones diferenciales es un camino en que se puede aprender mucha programación.

Referencias

Por qué una simulación numérica

Cuando se hacen predicciones, se interesa por el valor de una variable x en un determinado tiemp t partiendo de una situación inicial. Estas predicciones pueden ser el número de coches que pasan por una calle a una determinada hora o cuando se forma un atasco. Muchas veces no es posible hallar estos valores analíticamente, es decir, no es posible escribir una ecuación x(t) = algo relativamente fácil a calcular.

En esta situación no hay más remedio que utilizar una simulación numérica. La idea fundamental de una simulación en el tiempo es la fácilidad de predicir lo que va a pasar en el próximo instante y que una larga secuencia de instantes me puede llevar a lo que va a succeder en un futuro lejano.

El algoritmo fundamental

Por ejemplo, si delante un semáforo esperan 5 coches y uno se acerca, es previsible que algunos segundos después habrá 6 coches esperando. En cambio, sería muy difícil predicir cuántos coches esperarán dentro de una hora. Sin embargo, podré aprovechar una predicción a corto plazo como estado inicial de una nueva predicción.

  1. Partiendo de una situación inicial, predigo (con fácilidad) lo que ocurrirá en el próximo instante.
  2. Utilizo esta predicción como la situación inicial para la próxima iteración.

Si sólo uso este algoritmo un número de veces suficiente grande, entonces llegaré a predecir a cuántos coches esperarán en una hora.

El modelo de la simulación

Un modelo en la ciencia es una representación simplificada de la realidad, pero que contiene las magnitudes más significativas. Un modelo de una simulación de tráfico de coches podría consistir en un grafo, donde los nodos representan intersecciones y los enlaces las calles. A cada calla se podría asociar una capacidad de coches. Cada coche tendría asociado un camino que no es otra cosa que una secuencia de nodos en el grafo. Si el coche es el primero en su calle, entonces entrará en la próxima si está todavía no está llena. De otro modo espera – y con ello todos los demás coches detrás.

Como vemos, este modelo representa el comportamiento más fundamental durante la hora punta en una ciudad, cuando todo está atascado. Este modelo no tiene en cuenta el tiempo que tarda el coche en trascurrir una calle. Pero este tiempo es despreciable cuando un coche pasa la mayor parte del tiempo esperando detrás otro. Sin embargo, este tiempo, sí, sería significativo cuando hay poco tráfico y el coche pasa la mayor parte a la velocidad máxima permitida.

Simplicidad contra precisión del modelo

Desde luego, la vida real es infinitamente más compleja: algún coche da la vuelta, peatones cruzan la calle, otros obstaculos ralentizan el tráfico. Omitir esto hace nuestra simulación menos precisa, pero más rápida a calcular. Muchas veces la imprecisión no nos afecta. Pedimos a una simulación numérica que nos diga si podemos esperar un atasco en una calle determinada, mientras no nos importa el número del primer coche en el atasco.

Otras veces la imprecisión puede ser significativa: también con nuestro pequeño algoritmo mencionado arriba, será bastante difícil predicir el número de coches exacto que esperan delante de un semáforo dentro de una hora. En un caso favorable, el número será más o menos el real. En el caso de que un sistema entra en lo que se llama caós determinista, la situación puede ser totalmente diferente. Dependiendo de que mi simulación numérica sirve para un proyecto de ingeniería o para uno de física de sistemas complejos, me interesa el primer o el segundo caso.

El significado del resultado

En todo caso es importante cuestionar si los resultados de la simulación se ajustan lo suficientemente bien a la realidad. Un modelo demasiado simple puede acabar en resultados inútiles. Un modelo más completo se ajusta más a la realidad, pero requiere un mayor tiempo de cálculo – a veces demasiado tiempo: un algoritmo que tarda 3 días en calcular la predicción del tiempo para mañana es poco útil.

A veces es incluso imposible encontrar un modelo adecuado. La razón por qué no podemos predicir el tiempo a largo plazo es el efecto mariposa: un minúsculo cambio puede causar un resultado completamente distinto. Una simulación puede dar una pista sobre el comportamiento esperado, pero no suele ser una predicción a ciencia cierta.

En general es preferible utilizar el modelo más simple que dé resultados útiles, ya que cualquier ingrediente adicional al modelo sube el esfuerzo de cálculo más que la precisión de los resultados. Además, un modelo simple es más versátil. Nuestro modelo de predicción de tráfico en una ciudad podría valer perfectamente para el tráfico de maletas en un aeropuerto o el datos en una red de ordenadores.

Introducción

Con funcioncitas me refiero a funciones de una o dos líneas, muchas veces con un cálculo muy simple, pero con un valor semántico muy potente.

Escribir una función adicional fracasa a menudo en una cierta pereza, porque hay que buscar un hueco en el fichero fuente, escribirla, en C y C++ hay que añadirlo en la cabecera, eventualmente serás capaz de escribir algún comentario de qué esta función debe hacer y todo esto para una línea de código bastante trivial. Pero esto se puede ver también de otra forma: escribes el código una vez, lo modificas diez veces y lo lees cien veces. Si tardas 99 segundos (1 minuto y 39 segundos) para escribir una función que te ahorra un segundo en la lectura, todavía ahorras tiempo.

El valor de las funciones pequeñas está en su claridad semántica, que mejora mucho la legibilidad del código – sobre todo cuando se trata de una combinación de varias funciones pequeñas. Para ilustrar esto, presento algunos ejemplos.

Copiar con punteros

Si p y q son dos punteros, entonces ¿qué hace el código de C siguiente?

while (*p++ = *q++) {}

Lo que hace es copiar el valor a que q apunta a la memoria referenciada por p. A continuación pasa ambos punteros al próximo y elemento y sigue copiando hasta que haya copiado un cero. (El valor de una asignación es el valor asignado, el cero se interpreta como un false y el bucle while termina.)

Tenemos una expresión booleana basada en cualquier tipo arbitrario que el compilador sepa amablemente interpretar como false o true y que, además, modifica las variables dentro de la expresión. A parte de tener un buen ejemplo de un uso sofisticado pero poco intuitivo del lenguaje de programación C, ¿para qué se podría utilizar un bucle así?

Pues, para copiar un string. En la biblioteca estándar de C hay una definición de strcpy similar a esta (la versión estándar devuelve un char*):

void strcpy(char *p, const char *q)
{
    while (*p++ = *q++) {}
}

Ahora la pregunta: ¿qué te parece más comprensible? ¿Una línea strcpy(p, q) o un bucle while (*p++ = *q++) {}? Técnicamente no trae ninguna ventaja llamar a la función strcpy, pero semánticamente, es decir, el significado del código es mucho más claro para el programador.

Funciones pequeñas son a menudo parte del estándar. La clase String en C# tiene un método IsNullOrEmpty. La expresión

if (!String.IsNullOrEmpty(miString))

reemplaza a

if (miString != null && miString.Length > 0)

Es lo mismo, pero el método IsNullOrEmpty deja la intención más obvia.

Acotar rangos

Un ejemplo simple. Mira el reloj cuánto tardas en contestar a la pregunta. ¿Qué representa c?

c = a < b ? a : b;

Y ahora los mismo otra vez. ¿Qué representa c?

c = min(a, b);

Esto era fácil, pero ¿qué tal con algunos niveles de anidamiento?

c = c < a ? a : (c > b ? b : c);

Esto limita c al rango [a, b]. Si no estás tan firme en el uso del operador ? : podrías escribir la línea anterior con if.

if (c < a)
{
    c = a;
}
else
{
    if (c > b)
    {
	    c = b;
	}
}

Un poco más amigable sería usar las funciones pequeñas min y max:

c = max(a, min(b, c));

Mi opción preferida sería una función

c = limitToRange(a, c, b);

donde el parámetro en medio será acotado al intervalo [a, b].

Puedes optar por hacer una pequeña función que ocupa una línea o la construción con el if anidado arriba que ocupa once líneas por cada variable que quieres acotar. Y puede haber muchas: si c es un índice de un array, entonces podrías tener la necesidad de acotarlo cada vez que accedes al array.

Algo parecido vale si quieres generar un error al recibir un índice fuera de rango. La manera directa sería escribir algo así

if (index < start || index >= end)
{
    std:ostringstream mensaje;
	mensaje << "Error de índice index = "
	        << index
			<< ". Fuera del rango ("
			<< start
			<< ", "
			<< end
			<< ").";
    throw std::exception(mensaje.str());
}

Pero igual vale la pena hasta escribir una clase de excepción propia.

if (indexOutOfRange(start, index, end))
{
    throw IndexException(start, index, end);
}

Conclusión

Funciones pequeñas aumentan considerablemente la legibilidad del código. Ayudan a reducir el número de líneas dedicadas a comprobar la calidad de los datos y dejan a consecuencia más espacio a la parte principal de una función. Para no perder velocidad en la ejecución, C++ ofrece definir estas pequeñas funciones inline.

Muchas veces las funciones pequeñas son tan generales que se pueden usar en todos los proyectos de programación. Una buena gestión debería procurar que se mantiene una biblioteca que todo el mundo en la empresa pueda usar. Como son funciones muy básicas, conviene también pensarse bien sus nombres y el espacio de nombres en que se encuentran.

Si no eres gerente sino un simple programador, entonces te recomiendo que guardes estas funciones en un fichero personal. Así puedes copiar y pegarlas en cualquier proyecto en que participas. De hecho, mantener una biblioteca personal puede facilitar tu trabajo.

Referencias

Escribe tu dirección de correo electrónico para suscribirte a este blog, y recibir notificaciones de nuevos mensajes por correo.

Únete a otros 56 seguidores

Archivos

enero 2011
L M X J V S D
« Dic   Mar »
 12
3456789
10111213141516
17181920212223
24252627282930
31