12248

Прямые методы минимизации функции одной переменной

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа 1. Прямые методы минимизации функции одной переменной. В данной работе рассматриваются методы решения поставленной задачи не использующие вычисления производных прямые методы минимизации. Постановка задачи: Требуется найти безусловный ми...

Русский

2013-04-24

1 MB

66 чел.

Лабораторная работа 1.

Прямые методы минимизации функции одной переменной.

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

Постановка задачи: Требуется найти безусловный минимум функции одной переменной f(x), т.е. такую точку , что . Значение точки минимума вычислить приближенно с заданной точностью ε.

Предполагается, что для функции f(x) предварительно определен начальный интервал неопределенности L0 = [a0, b0] (имеется априорная информация о положении точки минимума, а именно то, что точка минимума , но более точное положение ее неизвестно), причем на заданном интервале функция является унимодальной (для любых функция монотонно убывает, для любых функция монотонно возрастает).

Метод равномерного поиска (метод перебора).

Стратегия поиска: Метод относится к пассивным стратегиям.

Задается количество интервалов N, на которое разбивается исходный интервал
L0 = [a0, b0]. Вычисления производятся в N +1 равноотстоящих друг от друга точках. Путем сравнения величин f(xi), i = 0,1,…,N находится точка xk, в которой значение функции наименьшее. Искомая точка минимума считается заключенной в интервале [xk-1, xk+1].

Алгоритм:

  1. Задать начальный интервал неопределенности L0 и точность ε.
  2. Задать количество интервалов разбиения .
  3. Вычислить точки ,  .
  4. Вычислить значения функции в найденных точках: f(xi) , .
  5. Среди точек найти такую, в которой функция принимает наименьшее значение: .
  6. Выбрать приближенно , . Поиск завершен.

Метод поразрядного поиска.

Стратегия поиска: Метод является усовершенствованным вариантом метода перебора. В этом методе перебор точек интервала неопределенности L0 происходит сначала с шагом , i = 0, 1, … (при этом точка x0 совпадает с концом отрезка a0) до тех пор, пока не выполнится условие , или пока очередная из точек xi не совпадет с концом отрезка b0. После этого шаг уменьшается в несколько (2, 4, 10) раз, и производится перебор точек в противоположном направлении (с новым шагом) до тех пор, пока значения f(x) не перестанут уменьшаться, или очередная точка не совпадет с концом отрезка a0. Процедура уменьшения шага и смены направления перебора на противоположное повторяется несколько раз. Поиск прекращается, если текущий шаг дискретизации при последнем проходе алгоритма  не превосходит заданной точности .

Следует отметить, что в данном методе интервал неопределенности может быть полубесконечным: L0 = [a0, +∞) или L0 = (-, b0] (во втором случае начальное направление перебора выбирается в сторону уменьшения значений x).

Алгоритм:

  1. Задать начальный интервал неопределенности L0 и точность ε.
  2. Задать начальный шаг дискретизации .
  3. Положить i = 1, x0 = a0. Вычислить значение функции  f(x0).
  4. Определить точку xi = xi-1+Δ и значение функции  f(xi).
  5. Если и , то положить i = i +1 и вернуться к шагу 4.
  6. Задать новый шаг дискретизации .
  7. Если , то перейти к шагу 12.
  8. Вычислить точку xi = xi-1-Δ и значение функции  f(xi).
  9. Если и , то положить i = i +1 и вернуться к шагу 8.
  10. Задать новый шаг дискретизации и перейти к шагу 4.
  11. Если , то перейти к шагу 12.
  12. Выбрать приближенно , . Поиск завершен.

Метод дихотомии.

Стратегия поиска: Метод относится к последовательным стратегиям и является одним из вариантов метода исключения отрезков.

Алгоритм опирается на анализ значений функции в двух точках. Для их нахождения текущий интервал неопределенности делится пополам и в обе стороны от середины откладывается по по δ/2, где δ < 2ε – малое положительное число. По результатам сравнения значений функции в этих точках из дальнейшего рассмотрения исключается часть текущего интервала неопределенности: из трех отрезков, полученных в результате разбиения интервала, выбирается тот отрезок, который не содержит точку с меньшим значением функции, и исключается из дальнейшего рассмотрения. Условия окончания итераций для всех вариантов метода исключения отрезков стандартные: поиск заканчивается, когда длина текущего интервала неопределенности оказывается меньше установленной величины точности ε.

Алгоритм:

  1. Задать начальный интервал неопределенности L0 и точность ε.
  2. Выбрать δ < .
  3. Положить k = 0 (k – номер итерации).
  4. Вычислить длину текущего интервала L0 = b0 - a0.
  5. Вычислить точки , и значения функции f(x1), f(x2).
  6. Сравнить f(x1) и f(x2).
  7. Если , то положить ak+1 = ak, bk+1 = x2.

  В противном случае () положить ak+1 = x1, bk+1 = bk.

  1. Вычислить длину нового интервала неопределенности Lk+1 = bk+1- ak+1.
  2. Если Lk+1 > ε, то перейти к шагу 5.
  3. Выбрать приближенно , . Поиск завершен.

Метод золотого сечения.

Стратегия поиска: Метод относится к последовательным стратегиям и является одним из вариантов метода исключения отрезков.

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

Алгоритм:

  1. Задать начальный интервал неопределенности L0 и точность ε.
  2. Положить k = 0 (k – номер итерации).
  3. Вычислить длину текущего интервала L0 = b0 - a0.
  4. Вычислить значение и точки , .
  5. Вычислить значения функции , .
  6. Сравнить значения , .
  7. Если , то положить , , , .
    В противном случае () положить , , , .
  8. Вычислить длину нового интервала неопределенности Lk+1 = bk+1- ak+1.
  9. Если Lk+1 > ε, то перейти к шагу 5.
  10. Выбрать приближенно , . Поиск завершен.

Вопросы и задания

  1. Реализовать функции для трех методов из приведенных выше: метода перебора, метода поразрядного поиска, метода дихотомии (либо метода золотого сечения вместо метода дихотомии).
  2. Выбрать для выполнения лабораторной работы тестовую функцию, номер которой соответствует последней цифре номера Вашего компьютера
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13. Для выбранной функции и для каждого реализованного метода изучить зависимость скорости работы (числа вычислений функции N) от заданного значения точности ε. Для этого необходимо определить число вычислений функции N при нескольких (от трех до пяти) значениях точности, например, при  и построить график зависимости .
  14.  Провести сравнение методов между собой: сравнить сложность реализации, скорость работы (точность). Какой из рассмотренных методов более оптимален для низкой точности () и для высокой точности ()?
  15.  Сохранить результаты для использования в лабораторной работе 2.

 

А также другие работы, которые могут Вас заинтересовать

29563. Экономическая и бухгалтерская прибыль. В общем виде прибыль (profit) определяется как разность между совокупной выручкой (total revenue) 130 KB
  1 где TR totl revenue совокупная выручка доход; ТС totl cost совокупные издержки; Pr profit прибыль. Однако сами издержки бывают внешними явными и внутренними неявными. Вычтя из совокупной выручки дохода внешние издержки мы получаем бухгалтерскую прибыль. Бухгалтерская прибыль однако не учитывает внутренние или скрытые издержки.
29564. Правило наименьших издержек 138.5 KB
  Правило наименьших издержек.5 Правило наименьших издержек это условие согласно которому издержки минимизируются в том случае когда последний доллар марка рубль и так далее затраченный на каждый ресурс дает одинаковую отдачу одинаковый предельный продукт. Правило наименьших издержек обеспечивает равновесие положения производителя. В этом положении достигается оптимальная комбинация факторов производства обеспечивающая максимизацию издержек.
29565. Трансакционные издержки 73 KB
  Трансакционные издержки По материалам курсовой Определений понятия трансакционные издержки множество каждый из ученых пытается выделить какуюлибо специфичную сторону данных видов затрат однако в целом обобщая можно сказать что трансакционные издержки представляют собой определенные затраты затраты ресурсов времени на взаимоотношения с внешним окружением. Можно сказать что трансакционные издержки это цена оплачиваемая экономической системой за несовершенства и провалы рынка и провалы государства. То есть...
29566. Конкурентные и неконкурентные рынки 69.5 KB
  Принимая решение он рассматривает два его следствия: Эффект объема производства. Эффект цены. Если эффект объема производства больше чем эффект цены владелец колодца увеличит предложение воды. Если эффект цены превышает эффект объема производитель откажется от планов увеличения предложения.
29567. Понятия «неопределенность» и «риск». Предпосылки поведения потребителя в условиях неопределенности 365.5 KB
  Понятия неопределенность и риск. Неопределенность как условие риска Неопределенность одно из центральных понятий в современной теории и практике управления. Неопределенность выступает необходимым и достаточным условием риска в принятии решений. Как отмечается в этимологическом словаре Фасмера термины риск рисковать происходят от греческого rysicon утес скала; отсюда рисковать значит взбираться на скалу или лавировать между скалами.
29568. Теория игр в выборе потребителя. Динамические игры. Координационные игры 487.5 KB
  Динамические игры. Координационные игры. думаю главное самое основное рассказать у теории игр большой математический аппарат который нет смысла сейчас изучать главное передать суть теории применительно к выбору потребителя и к решениям принимаемым на предприятиях в условиях олигополии стратегии равновесия выигрыши. Из лекции Бодрова у него только про статические игры: Теория игр анализирует принятие решений экономическими субъектами называемыми в соответствии с установившейся традицией игроками в ситуациях когда на результат...
29569. Эластичность спроса. Эластичность спроса относительно дохода 73 KB
  Эластичность спроса. Эластичность спроса относительно цены показывает относительное изменение объема спроса под влиянием изменения цены на один процент. Оно вызывает значительное изменение величины спроса. Рост цен автомобиля Вольво на 10 рублей практически не ощутим для покупателей этой автомашины поэтому изменение цены и величины спроса дается в формуле эластичности не абсолютно а относительно: EPD =  Q Q : P P  = Q в P в  3.
29570. Потребительское поведение и выбор потребителя 117.5 KB
  Полезность блага utility of good это способность экономического блага удовлетворять одну или несколько человеческих потребностей. была выявлена закономерность: потребляемые последовательно части какоголибо блага обладают убывающей полезностью для потребителя. Это означает что любому бесконечно малому увеличению количества блага Q соответствует прирост общей полезности totl utility TU см. Хотя общая полезность с увеличением количества благ постепенно возрастает предельная полезность mrginl utility MU каждой дополнительной...
29571. Кривая цена-потребеление 55 KB
  Однако при этом не учитываются два важных обстоятельства: цены товаров и доход потребителей. Если I доход потребителя Px цена блага X Py цена блага Y а X и Y составляют соответственно купленные количества благ то уравнение бюджетного ограничения можно записать следующим образом: I = Px X PY Y или в более привычном виде: Y = I Py Px Py  X где Px Py угловой коэффициент бюджетной линии который измеряет наклон этой линии к оси абсцисс. При X = 0 Y = I Py то есть весь доход потребителя расходуется на благо Y....