5.5 Algoritmos de prueba y error
Un área de la programación particularmente intrigante es la referente a la resolución general de problemas. Esta tarea consiste en dar con algoritmos para encontrar soluciones a problemas específicos sin seguir una regla fija para la computación, sino mediante "prueba y error". La manera más común para ello es descomponer el proceso de "prueba y error" en subtareas. A menudo, estas subtareas se expresan de manera natural en forma recursiva probando un número finito de veces las propias subtareas hasta dar con la solución al problema. En este caso se estaría planteando un esquema recursivo de prueba y error.
Otras veces, la manera de establecer el esquema para encontrar la solución no se plantea de manera recursiva, sino que se establece una condición que, mientras ésta se cumpla, el programa sigue actuando hasta dar con la solución mediante la repetición sistemática de una serie de pasos. En este caso se estaría planteando un esquema iterativo de prueba y error.
5.5.1 Algoritmos iterativos de prueba y error
Ejemplo 13. Método de Newton Rapshon de manera iterativa
El método de Newton-Raphson o simplemente el método de Newton, es uno de los métodos numéricos más poderosos para resolver el problema de búsqueda de raíces de una función matemática expresada en la forma f(x)=0. La base del método reside en el concepto de derivada de una función.
Esta figura muestra como se obtienen las raíces de una función f(x) mediante tangentes sucesivas. Comenzando con una aproximación inicial x0, la aproximación x1 es la intersección con el eje x de la línea tangente a la gráfica de f(x) en (x0,f(x0)). La aproximación x2 es la intersección con el eje x de la línea tangente a la gráfica de f(x) en (x1,f(x1)) y así sucesivamente.
Observa que:
De manera que para un valor xi se determina un nuevo valor xi+1 más próximo a f(x)=0.
De lo que se trata ahora es de hacer una función que ejecute iterativamente la operación señalada en la ecuación (5.8). Con esto nunca llegaremos a la solución f(x)=0, pero nos iremos aproximando sucesivamente, de manera que, después de realizar un número suficiente de iteraciones, habremos conseguido un valor de x muy próximo a la raíz. Generalmente no se programa un número concreto de iteraciones, sino que se establece un criterio para decidir cuando debe detenerse el proceso iterativo.
Como el objetivo es buscar un valor de x en el que f(x)=0, lo que se establece es que el proceso iterativo continúe mientras que f(x) supere un valor próximo a cero.
Para el ejemplo concreto realizaremos un programa para determinar las raíces de la siguiente función:
Para ello realizaremos una función de Matlab cuyo encabezado sea:
function raiz=Newton_Raphson(xo,error)
Donde los argumentos de entrada son:
xo: punto de inicio del método.
error: se utilizará para determinar la condición de parada del algoritmo.
Es la diferencia entre el valor de f(xi) y 0 y cuando se cumpla que |f(xi)|<|error| se para el método iterativo.
Los argumentos de salida son:
raiz: es el valor que tiene xi en el momento en el que se decide parar el algoritmo.
La función Newton_Raphson deberá realizar la iteración:
Para calcular la derivada utilizaremos una constante de derivación de 1e-10.
Además le agregaremos al programa un contador que indique cuántas iteraciones ha efectuado antes de pararse. En concreto dibujará unos 20 puntos de la función a lo largo del intervalor [raiz-1,raiz+1], siendo raiz el valor de retorno de la función. Incluiremos la función grid para dibujar un mayado a la gráfica.
El diagrama de flujo y el programa son los siguientes:
Ejemplo 14. Cálculo de las dimensiones óptimas de un cilindro.
Supongamos el caso de un jeque árabe que pide que se realice un programa para determinar las dimensiones que debe tener un barril de petróleo para que, albergando un determinado volumen, presente el mínimo área. El problema es que el jeque en cuestión quiere exportar el petróleo en bidones de distinto volumen, por lo que necesita un programa que sea capaz de dimensionar el barril en función del volumen solicitado.
Para solucionar esto vamos a realizar un algoritmo de prueba y error en el que estableceremos un proceso iterativo con el que nos acercaremos sucesivamente a la solución óptima. El algoritmo seguirá los siguientes tres pasos:
1º Se determina la altura h que debe tener un barril inicial que tenga un radio muy pequeño (por ejemplo r=0.001) para albergar el volumen Vc solicitado. Esta altura se encontrará lejos de la altura que de unas proporciones óptimas y sabemos que habrá que reducirla para dar con la geometría del barril óptimo.
2º Calcularemos el área que presenta este barril inicial.
3º Esta área inicial será muy grande. De lo que se tratará ahora es de implementar un sistema iterativo en el que se vaya incrementando el radio con un paso pequeño (por ejemplo paso=0.01) hasta dar con las dimensiones del barril (r y h) que presentan el mínimo área. El criterio para detener las iteraciones es que se lleguemos a aquella iteración en la que demos con un área lateral superior al área lateral que se había obtenido en el paso anterior.
Esto es, después del 2º paso se dispondrá de un primer área (llamémosle Area).
Ya dentro del proceso iterativo, al incrementar el radio, se podrá calcular un nuevo área para ese radio (llamémosle Area_nueva) que podrá compararse con el anterior área. Si resulta que se ha reducido el área, el proceso iterativo debe continuar. Si, por el contrario, el área nueva es peor, debe detenerse el proceso.
Vamos a programarlo en una función de Matlab cuyo encabezado sea:
function [r,h]=Area_optima(Vc)
Donde Vc es el volumen que debe albergar el barril y r y h son el radio y la altura -calculados por la función- que minimizan el área del barril de volumen Vc.
Las fórmulas que hay que considerar son:
Área de la circunferencia: πr2
Área de un cilindro: 2πr2 +2πrh
Volumen de un cilindro: πr2h
El diagrama de flujo para el 3er paso es el siguiente:
Espero haber ayudado en algo. Hasta la próxima oportunidad!
Twittear
No hay comentarios:
Publicar un comentario