WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
министерство высшего образования и среднего специального образования россии дальневосточный государственный университет Одномерная минимизация Методические указания к самостоятельной работе студентов по курсу “Методы оптимизации” Владивосток, 2003 2 УДК 519.8 Методические указания предназначены для самостоятельной работы студентов по курсу “Методы оптимизации”. Рассмотрена достаточно простая тема: “Методы одномерной минимизации”, детально разбираются наиболее известные методы, приведены вычислительные схемы, разобраны примеры.

Подготовлено кафедрой процессов управления ДВГУ Составитель: Горячев Л.В.

Печатается по решению учебно-методического Совета ДВГУ © Дальневосточный Государственный Университет, 2003 3 Методы поиска экстремумов функции одного переменного составляют содержание наиболее простого раздела курса “Методы оптимизации” Для его изучения необходимо лишь знание начальных основ математического анализа. В связи с уменьшением в учебных планах аудиторных занятий и повышением роли самостоятельной работы студентов имеет определенный смысл вынести эту тему в рамки самостоятельных занятий. Поэтому, на наш взгляд, целесообразно дать студенту, изучающему курс “Методы оптимизации”, сжатое изложение основных понятий и алгоритмов указанного раздела с соответствующими указаниями полезными при самостоятельной работе.

Пусть требуется найти min f(x) при условии a x b, г де a и b-заданные концы отрезка.

Из курса математического анализа известно, что дифференцируемая функция f(x) достигает своего минимума в точках x, где f (x) = 0 или в граничных точках. Точки, в которых f (x) = 0 называются стационарными, их локализация-первый этап решения задачи на экстремум. Из множества стационарных точек необходимо выделить те, в которых действительно необходимо сравнит значения функции в точках локального минимума и на концах отрезка и выбрать среди них минимальное. Соответствующая ему точка будет являться точкой глобального минимума. Решением нашей задачи будет точка глобального минимума и значение f(x) в этой точке.

Напомним, что для идентификации точки локального минимума исследуют знак второй производной функции. Достаточным условием локального минимума является положительностьf (x) Если f (x) не существует, то следует проследить за знаком первой производной. Перемена знака с “-” на “+” соответствует случаю убывания функции слева от точки x, и возрастанию справа, т. е.

минимуму функции. Если же f (x) меняет знак с “-” на “+” при переходе через x, то имеет место локальный максимум.

Такой способ поиска минимума можно применять в тех случаях, когда функции f(x) и ее производные вычисляются сравнительно просто. В практических задачах нахождение производных функций и нахождение корней уравнения f (x) =0 может представлять большие трудности. В связи с этим важно иметь в арсенале методов оптимизации и методы, основанные не на вычислении производных, а на вычислении только значений функции в ряде специально подбираемых точек. При этом естественно желать, чтобы число таких точек стало возможно меньшим, а точность определения точки оптимума была не ниже заданной.

Последовательность действий при реализации большинства этих методов такова:

1. Согласно некоторому правилу выбирается несколько точек на отрезке [a, b] и на основе анализа значений в этих точках производится локализация минимума (максимума), т. е. выделяется новый отрезок[a1, b1], a a1

2. На полученном отрезке [a1, b1] снова по указанному правилу берется ряд точек для последующей локализации точки минимума, т. е. получаем новый отрезок. Процесс продолжается до тех пор, пока длина очередного отрезка не станет меньше заданной величины, либо пока не будет вычислено априори заданное число значений функции.

3. Имеется правило, по которому на последнем отрезке для x.

Очень простые алгоритмы поиска точек минимума (максимума) могут быть получены, если предположить, что исследуемая функция f(x) удовлетворяет условию унимодальности (одноэкстремальности).

Определение: Функция f(x) называется унимодальной на отрезке [a, b], если ! точка на этом отрезке такая, что для любых точек x1, x2 этого отрезка из x x1 x2 = f(x) f(x1) f(x2);

из x x1 x2 = f(x) f(x1) f(x2). Другими словами унимодальная функция монотонна на обе стороны от точки минимума x. Аналогично определяется унимодальная функция и для задачи на максимум. Унимодальные функции могут быть непрерывными, разрывными, дискретными и другими...

Основное свойство унимодальной функции состоит в том, что при помощи любой пары точек отрезка можно уменьшить отрезок поиска точки минимума.

Рис. 1: Унимодальные функции 0 a x1 x* x2 b a x1 x* x2 b Теорема: Пусть функция f(x) унимодальна на отрезке [a, b], а ее минимум достигается в точке x. Для любых точек x1 и x2 этого отрезка и таких, что a f(x2), то точка минимума x [x1, b) (рис. 2) 2. если f(x1) f(x2). Допустим противное, т. е. x (a, x1]. Тогда, так как x-точка минимума, то по определению f(x) f(x) для x [a, b] Получаем двойное неравенство f(x) f(x1) >f(x2) при x



Метод деления отрезка пополам. Рассматриваем задачу отыскания точки минимума x унимодальa+b- a+b+ ной функции f(x), определенной на отрезке. Возьмем две точки. x1 = ; x2 =, где 2 достаточно малая положительная постоянная. При этом точки x1, x2 делят отрезок почти пополамотсюда название метода. Вычисляем и сравниваем значения f(x1) и f(x2) Если f(x1) > f(x2)nj согласно доказанной теореме новый отрезок поиска точки x будет [x1, b]. Границы нового отрезка обозначим через a1 и b1, т. е. a1 = x1, b1 = b. Если f(x1) log2( ) - 1, число точек вычисления значений функции равно N =2k.

В случаях, когда число вычислении значения функции априори задано, следует, что при N =2k b-a точность вычисления точки минимума функции определяется величиной +, Замечание: Если 2k+функция дифференцируема и её производные могут быть вычислены, то алгоритм несколько упроak+bk ak+bk щается: если f ( ) < 0, то, очевидно, что функция f(x) убывает в окрестности точки ) и 2 ak+bk ak+bk искомая точка x лежит правее этой точки, т. е. новый отрезок поиска [, bk], если f ( ), 2 ak+bk то x [, bk]. К недостатком этого метода относится тот факт, что информация о значении функции в точках x1и x2 используется только на одном шаге. Более подробно с этим методом можно ознакомиться в [1. 2].

Метод золотого сечения Золотым или гармоническим делением, называется такое деление отрезка [a, b] точкой x на две неравные части, при котором отношение длины всего отрезка к длине его большой части равно отношению длины большей части к длине меньшей части отрезка, длина большей части отрезка является средней пропорциональной между длиной всего отрезка и меньшой его части. Для определения искомых точек необходимо составить уравнения:

b-a x-a b-a b-x =, если [a, x]-большая часть отрезка, и =, если [x, b]-большая часть отрезка.

x-a b-x b-x x-a Отсюда, анализируя эти уравнения, мы получим две точки золотого сечения:

3 - x1 = a + (b - a) a +0.382(b - a) - левая точка () 5 - 1) x2 = a + (b - a) a +0.618(b - a) - правая точка () 1+. При этом само соотношение, золотая пропорция r = 1.618034 Пользуясь свойством унимо дальности функции, сравниваем значения ее в этих точках: если f(x1) >f(x2), то новый отрезок поиска есть [a1, b1], г де a1 = x1, b1 = b, если f(x1)

2. Точки x1, x2 расположены к середине отрезка, чем к своим концам; 3. Точка x1 является точкой золотого сечения отрезка [a, x2], а точка x2 является точкой золотого сечения отрезка [x1, b]. Из последнего утверждения следует, что на последующем шаге мы уже будем иметь одну точку золотого сечения. Таким образом, на каждой итерации, кроме первой, метод золотого сечения требует определения лишь одной точки отрезка и одного значения функции, что и определяет большую эффективность этого метода по сравнению с методом половинного деления при заданной точности.

Если зафиксировать число n вычислений значений функции f(x), то методом золотого сечения значение x может быть найдено в 1.144n раз точнее, чем методом деления отрезка пополам. Длина отрезка по методу золотого сечения убывает последующему правилу:

n 5 - n =(b - a) Приведем схему метода золотого сечения. Пусть -требуемая точность вычисления точки минимума.

0. Начальный шаг: находим точки x1 и x2 по формулам (*) (**) 1. Вычисляем f(x1), f(x2) если f(x1) >f(x2), то переходим к шаг у 4.

если f(x1)

если f(x1) =f(x2), то переходим к шаг у 2.

2. Получаем новый отрезок [a, b], a = x1; b = x2.

b-a a+b Находим h = ;, если h, то x, fmin f(x) end, в противном случае переход к 0.

2 3. Получаем новый отрезок [a, b], a = a; b = x2.

b-a a+b Находим h =, если h, то x, fmin f(x) end; в противном случае x2 = x1, находим 2 x1 по (*), переход к 1.

4. Получаем новый отрезок [a, b], a = x1; b = b.

b-a a+b Находим h =, если h, то x, fmin f(x) end; в противном случае x1 = x2, находим 2 x2 по (**), переход к 1.





Методы половинного и золотого сечения относятся к классу так называемых симметричных методов. Дело в том, что имеющиеся на каждом шаге две точки отрезка x1 и x2 симметрично расположены относительно центра этого отрезка. Благодаря этому свойству всякий симметричный метод полностью определяется заданием отрезка [a, b] и правилом выбора первой точки. Тогда другая точка x2(x1) находится по правилу общему для всех симметричных методов:

x2 = a + b - x1, если x1 известна, x1 = a + b - x2, если x2 известна.

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

Впервые интерес к золотой пропорции возник еще в античной науке (Пифагор, Платон, Евклид).

Античные скульптуры и архитекторы широко используют её в своих художественных произведениях. Об этом и других применениях золотой пропорции можно познакомится в книге А. П. Стахова (Коды золотой пропорции. -М, Радио и связь, 1984).

Для иллюстрации сказанного приведем простой пример: определить минимальное значение функции e-x - 2cosx на отрезке [0, 1]. Точку x найти с абсолютной погрешностью <0.05.

1. Имеем отрезок [a, b] = [0, 1]. Вычисляем на нем по правилам (*) и (**) точки x1 и x2 : x1 = 0.382, x2 =0.618.

2. Вычисляем f(x1)иf(x2) : f(x1) =-1.1733; f(x2) =-1.0910.

3. Так как f(x2) >f(x1), то имеем новый отрезок поиска: [a, b] =[0, 0.618]. Проверяем на остановку:

h = (0.618 - 0) = 0.309 > 0.05.

4. На новом отрезке нам уже известна одна точка золотого сечения x2 := x1 = 0.382. Находим x1 =0 +0.382 · 0.616 = 0.236.

5. Вычисляем f(x1), f(x2) - нам известно: f(x1) =-1.155, f(x2) =-1.1733.

6. Сравнивая значения f(x1)иf(x2), имеем, что f(x1) > f(x2), следовательно приходим к новому отрезку [a, b] = [0.236, 0.618]. На нем имеет точку золотого сечения x2, h = (0.618 - 0.236)/2 = 0.191 > 0.05.

7. Находим новые точки на отрезке [0.238, 0.618]:

x1 := x2 =0.382;

x2 =0.236 + 0.618 · (0.618 - 0.236) = 0.472.

8. Вычисляем f(x2) =-1.1575; f(x1) =-1.1733 - нам известно, так как f(x2) >f(x1), заключаем, что новый отрезок поиска [a, b] =[0.236, 0.472].

9. На новом отрезке x2 := x1 =0.382;

x1 =0.236 + 0.318 · (0.472 - 0.236) = 0.326.

10. Находим f(x1) =-1.1728; f(x2) =-1.1733. Сравниваем: f(x1) >f(x2). Заключаем, что новый отрезок [a, b] =[0.326, 0.472]; h =0.07 > 0.05.

11. На новом отрезке x1 := x2 =0.382;

x2 =0.326 + 0.618 · (0.472 - 0.326) = 0.416.

12. Находим f(x2) = -1.1696; f(x1) = -1.1733. Так как f(x1) < f(x2), новый отрезок поиска [a, b] = [0.326, 0.416], h = (0.416 - 0.326) = 0.045 < 0.05. Вычисления закончены x (0.416 + 0.326) = 0.372, fmin f(0.372) = -1.1739.

МЕТОД ФИБОНАЧЧИ В тех случаях, когда вычисление значений функции в точках отрезка затруднительно (например, в условиях промышленного эксперимента) естественно стремление ограничиться числом необходимых измерений, не теряя в точности определения точки минимума. Поэтому в таких ситуациях применять метод, который бы при заданном n и мел бы наибольшую точность. К числу методов оптимальных по точности относится и метод Фибоначчи.

Числа Фибоначчи определяются соотношением:

Fn+2 = Fn+1 + Fn; n =0, 1, 2,... ; F0 =0, F1 =1.

Можно показать (выполнить это в качестве упражнения), что a) 1 1+ 5 1 - Fn = [( )n - ( )n)], n =1, 2,... ;

2 b) Fn+1 5 - limn = ;

Fn+2 Fn 3 - limn = Fn+2 Метод Фибоначчи также является симметричным и поэтому имеет много общего с методом золотого сечения. В последнем выбираемые на каждом шаге точки x1, x2 являются выпуклыми комбинациями концов текущего отрезка поиска:

x1 =(1 - )a + b; x2 = a +(1- )b;

3- 5 5- = ; (1- ) = 2 Величина остается постоянной в ходе поиска.

В методе Фибоначчи x1 =(1 - n-1+k)a + n-k+1b;

x2 =(n-1+k)a +(1- n-k+1)b x1-a В этом методе n-k+1 = изменяется на каждом шагу.

b-a Fn На первом шаге x1 = a + (b - a);

Fn+Fn+Fn x2 = a + b - x1 = a +(1- )(b - a) =a + Fn+1 Fn+Как и в методе золотого сечения, точки x1, x2 находятся на одинаковом расстоянии от середины отрезка [a, b] и ближе к середине, чем к соответствующему концу.

Fn На первом шаге n = Fn+Число вычислений значений функции f(x) фиксировано, текущим параметром процесса будет параметр k Fn+1 Fn+Длина отрезка на втором шаге будет равна (1 = b-a); 2 = b-x1 = x2 -a = (b-a) = Fn+2 Fn+Если на втором шаге будем иметь отрезок поиска [x1, b], то точка x2, будет левее середины нового отFn-резка. Поэтому на новом отрезке [a, b] =[x1, b], тогда роль x1 играет точка x2, т. е. x1 = a+ (b-a), Fn+Fn а x2 = a + (b - a) и т. д.

Fn+На k-ом шаге Fn-k+1 Fn-k+x1 = a + (b - a); x2 = a + (b - a), k =1, 2,..., n Fn+k+3 Fn-k+Длина отрезка поиска Fn-k+2 Fn-k+n = k-1 = Fn-k+3 Fn-При k = n процесс заканчивается, в этом случае x1 = x2, длина отрезка поиска n = Fn+Поэтому за приближение к точке x берем точку x = x1 = xПеред началом процесса поиска определяется наименьшее натуральное n, удовлетворяющее неравенству Fn+2 b - a Критерием остановки процесса служит выполнение условия k = n Схема вычислений по методу Фибоначчи в остальном аналогична схеме метода золотого сечения.

В качестве примера рассмотрим задачу определения точки минимума функции.

f(x) = + x x на отрезке [1, 2], n =1.k =1, k =5, [a, b] =[1, 2];

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.