Metodos De Busqueda

República Bolivariana de Venezuela

Ministerio del Poder Popular para la Defensa

Universidad Nacional Experimental de la Fuerza Armada Bolivariana

Núcleo: Miranda – Extensión, Ocumare del Tuy

Sección: INS601D

Métodos de Búsqueda

Profesor: Alumnos:

Materano Víctor

Ocumare del Tuy, Octubre de 2012

INDICE

Introducción……………………………………………………………………………...1

Función Unimodal…………………………………………………………………….....2

Búsqueda de Finobacci………………………………………………………………......3

Búsqueda Dorada………………………………………………………………………..4

Método de Interpolación Cuadrática…………………………………………………….5

Métodos de Búsqueda Multidimensional………………………………………………..6

Métodos de Búsqueda de Variaciones Cíclicas…………………………………….......11

Conclusión……………………………………………………………………………...15

Referencias Bibliográficas………………………………………………………….......16

INTRODUCCIÓN

Las funciones de una variable son las más simples dentro del análisis funcional, y mediante ellas se puede describir muchos problemas de Ingeniería.

Además su conocimiento es muy importante, ya que permiten solucionar problemas más simples como subproblemas de otros problemas más complejos. Lo diversos métodos que existen para resolver problemas de este tipo, se les puede categorizar de acuerdo a la naturaleza de la función f(x) y la variable (x) involucrada, así como también al tipo de información acerca de f(x) que se dispone.

Algunos de los métodos numéricos de búsqueda de óptimos de una función en varias variables se basan en métodos de búsqueda de óptimos en una variable. Por ejemplo, el método de ascenso más rápido elige un punto dado y determina la dirección de máximo crecimiento en tal punto. Esta dirección es la del gradiente de la función en dicho punto. As´ y partiendo del punto y siguiendo esta dirección avanza para localizar el óptimo en dicha dirección. Imagínese avanzando en línea recta y tomando en cuenta solo la evaluación de la función para determinar el punto en la línea con la mayor evaluación. Una vez alcanzado este punto, se determina la dirección de máximo crecimiento en tal punto y se repite el proceso de búsqueda. Por su valor práctico, los métodos de búsqueda en una dimensión son dignos de revisar.

Ahora bien, entre los métodos de búsqueda multidimensionales se encuentran diferentes herramientas matemáticas, como por ejemplo, el método de búsqueda de Fibonacci, que se basa en la idea de que el cociente entre dos números de Fibonacci tiende a la Proporción Áurea o método de búsqueda de la sección dorada y mejor conocido como el número de oro entre otros.

Estos métodos son aplicados también en el área de la programación e informática para la realización de arreglos, diseño de páginas web, gestores de búsqueda en la web, entre otros. Obviamente son aplicados también en todas las áreas de la ingeniería, debido a que nos permiten determinar máximos y mínimos y en consecuencia hallar resultados óptimos aplicables, resultando el estudio de la optimización no lineal indispensable para el desarrollo investigativo y de producción en las empresas.

FUNCIÓN UNIMODAL

Una función es unimodal si sólo tiene un óptimo (relativo o absoluto). En caso que tenga varios óptimos se dice multimodal.

En general, tener la certeza de que el óptimo buscado existe y es único, normalmente se asume que la función es unimodal y se revisan las respuestas del que entrega la aplicación del algoritmo a problemas específicos.

Unimodal Multimodal

Una función f (x) es una función unimodal si por algún valor m, es monótona creciente para x ≤ m y monótonamente decreciente para x ≥ m. En ese caso, el valor máximo de f (x) es f (m) y no hay otros máximos locales.

La función unimodal también puede referirse a una función que sólo tiene un mínimo local, en lugar de máxima. [10] Por ejemplo, el muestreo unimodal Local, un método para hacer de optimización numérica, a menudo se ha demostrado con esta función. Se puede decir que una función unimodal bajo esta extensión es una función con un extremo local única.

Una propiedad importante de las funciones unimodal es que en el extremo se puede encontrar el uso de algoritmos de búsqueda como la búsqueda de la sección de oro, de búsqueda ternaria o interpolación parabólica sucesiva.

BÚSQUEDA DE FINOBACCI

Este método determina el mínimo valor de una función f sobre un intervalo cerrado [c1, c2].

Esta función puede estar definida en un dominio más amplio, pero el método requiere que dicho intervalo de búsqueda sea definido.

Se asume que f es unimodal.

El mínimo es determinado (al menos aproximadamente) mediante la evaluación en un cierto número de puntos. Se pretende definir una estrategia de búsqueda que seleccione la observación siguiente basada en los valores funcionales de las observaciones anteriores.

Esto se define según el siguiente problema:

Encontrar como seleccionar sucesivamente N observaciones, sin contar con un conocimiento explícito de la función, de forma tal que podamos encontrar la más pequeña región de incertidumbre posible en donde se encuentre el mínimo.

Esta región de incertidumbre es determinada en cualquier caso por: las observaciones (sus valores funcionales) y la suposición de que f es unimodal.

Luego que encontremos los valores funcionales en N puntos dentro del intervalo cerrado [c1, c2] c1 ≤ x1 ≤ … ≤ xN-1 ≤ xN ≤ c2

La región de incertidumbre es el intervalo [xk-1, xk+1] donde xk es el mínimo de los N puntos evaluados. En ese intervalo de encuentra el mínimo.

La estrategia para seleccionar sucesivamente observaciones para obtener la región de incertidumbre más pequeña se describe a continuación:

d1 = c2 – c1; es la amplitud inicial de la incertidumbre.

dk à es la amplitud de la región de incertidumbre luego de k observaciones.

BÚSQUEDA DORADA

Pertenece a los métodos de búsqueda lineal basados en intervalos, además es una versión mejorada de la búsqueda de Finobacci.

En la búsqueda de la sección dorada se usan tres valores de la función para detectar el valor extremo, se toma un cuarto número, y se determina donde ocurre el mínimo, si en los primeros tres o los últimos tres valores. Se minimiza la evaluación de la función objetivo al reemplazar los valores anteriores con los nuevos, haciendo que se cumplan las siguientes condiciones:

• L0 = L1 + L2

La primera condición específica que la suma de las dos sublongitudes L1 y L2 debe ser igual a la longitud original del intervalo.

• L1 L2

L0 L1

La segunda indica que el cociente o razón de las longitudes debe ser igual.

MÉTODO DE INTERPOLACIÓN CUADRÁTICA

Interpolación

La interpolación consiste en hallar un dato dentro de un intervalo en el que conocemos los valores en los extremos.

Interpolación lineal

Como dijimos, cuando las variaciones de la función son proporcionales (o casi proporcionales) a los de la variable independiente se puede admitir que dicha función es lineal y usar para estimar los valores la interpolación lineal.

Sean dos puntos (xo, yo), (x1, y1), la interpolación lineal consiste en hallar una estimación del valor y, para un valor x tal que x0<x<x1. Teniendo en cuenta que la ecuación de la recta que pasa por esos dos puntos es:

Obtenemos la fórmula de la interpolación lineal.

Interpolación Cuadrática. Fórmula de Lagrange

Cuando el polinomio que conviene es de 2º grado la interpolación recibe el nombre de cuadrática. El polinomio interpolador es único, luego como se encuentre da igual., sin embargo, a veces los cálculos son muy laboriosos y es preferible utilizar un método que otro. A la vista de los datos se decide.

Se puede llevar a cabo el método de resolver el sistema para encontrar los valores que determinan a la función cuadrática (a, b y c).

También podemos utilizar la expresión del polinomio interpolador así:

y= a + b(x-x0) + c(x-x0)(x-x1), con lo que la búsqueda de los coeficientes es muy sencilla.

Lagrange (1736-1813) dio una manera simplificada de calcular los polinomios interpoladores de grado n Para

...