import matplotlib.pyplot as plt

МЕТОДЫ ОПИТИМИЗАЦИИ

РАБОТА № 5

ИССЛЕДОВАНИЕ МЕТОДОВ ОДНОМЕРНОГО ПОИСКА

Подготовил:

Студент ИТ-41

Невежин Роман Александрович

Киев

Цель работы: Исследование на ЭВМ поисковых алгоритмов минимизации функции одной переменной на безе методов исключения интервалов.

Варианте задания: Вариант №6

F6 = x²/2 – sin x

F5 = x² + 6x

Краткие теоретические сведения

Поиск с помощью золотого сечения (Golden section search) — это улучшение наивной реализации троичного поиска, служащего для нахождения минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации). За счет этого достигается выигрыш в производительности.

Пусть задана функция . Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки и такие, что:

, где — пропорция золотого сечения.

Таким образом:

То есть точка делит отрезок в отношении золотого сечения. Аналогично делит отрезок в той же пропорции. Это свойство и используется для построения итеративного процесса.

Алгоритм

На первой итерации заданный отрезок делится двумя симметричными относительно его центра точками и рассчитываются значения в этих точках.

После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой максимально (для случая поиска минимума), отбрасывают.

На следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку.

Процедура продолжается до тех пор, пока не будет достигнута заданная точность.

Формализация

Шаг 1. Задаются начальные границы отрезка и точность .

Шаг 2. Рассчитывают начальные точки деления: и значения в них целевой функции: .

Если (для поиска max изменить неравенство на ), то

Иначе .

Шаг 3.

Если , то и останов.

Иначе возврат к шагу 2.

Графики функций в границах (-10; 10)

F6 = x²/2 – sin x

F5 = x² + 6x

Листинг программы на языке программирования Python

In [1]:

# This line configures matplotlib to show figures embedded in the notebook,

# instead of opening a new window for each figure. More about that later.

# If you are using an old version of IPython, try using '%pylab inline' instead.

% matplotlib inline

In [2]:

from pylab import *

In [3]:

import matplotlib.pyplot as plt

In [4]:

from pylab import *

In [5]:

x = linspace (-10, 10)

y = (0.5 * x ** 2) - sin (x)

In [6]:

figure()

plot(x, y, 'r')

xlabel('x')

ylabel('y')

title('title')

show()

In [8]:

y5 = x ** 2 + 6 * x

In [9]:

figure()

plot(x, y5, 'b')

xlabel('x')

ylabel('y5')

title('F 5')

show()

In [10]:

from math import sqrt

phi = (1 + sqrt(5))/2

resphi = 2 - phi

In [25]:

def goldenSectionSearch(f, a, c, b, absolutePrecision):

if abs(a - b) < absolutePrecision:

return (a + b)/2

# Create a new possible center, in the area between c and b, pushed against c

d = c + resphi*(b - c)

if f(d) < f(c):

return goldenSectionSearch(f, c, d, b, absolutePrecision)

else:

return goldenSectionSearch(f, d, c, a, absolutePrecision)

In [26]:

f = lambda x: (0.5 * x ** 2) - sin (x)

In [34]:

minimum = goldenSectionSearch(f, 0, (-1 + resphi*2), 2, 1e-3)

In [35]:

minimum

Out[35]:

-0.2354213751997885

In [36]:

f = lambda x: x ** 2 + 6 * x

In [37]:

minimum = goldenSectionSearch(f, -4, (-1 + resphi*2), -2, 1e-3)

In [38]:

minimum

Out[38]:

-1.9996003778013953

Резльтаты расчетов:

Минимум F6 = -0.2354213751997885

Минимум F5 = -1.9996003778013953

Выводы

В работе я научился определять минимуму функции при помощи метода золотго счения при помощи ПЭВМ с использованием Python.

Дата добавления: 2015-11-28