12248

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

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

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

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

Русский

2013-04-24

1 MB

58 чел.

Лабораторная работа 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.

 

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

42964. Исчисления экономических показателей работы предприятия и его подразделений 72.38 KB
  Введение Во введении студент должен охарактеризовать значение электроустановок в трубных и других цехах. Таблица Сметная стоимость оборудования Наименование электрооборудования Мощность кВт Количество шт Сметная стоимость руб.5 Определяем транспортные расходы: Тр = 01 · Ссм где Тр транспортные расходы руб.6 Определяем заготовительноскладские...
42965. Разработка информационной системы по предметной области спортивный комплекс 505.53 KB
  Информационнопоисковая система это система обеспечивающая поиск и отбор необходимых данных в специальной базе с описаниями источников информации индексе на основе информационнопоискового языка и соответствующих правил поиска.0 располагающей широкими возможностями по созданию приложений баз данных необходимым набором драйверов для доступа к самым известным форматам баз данных удобными и развитыми средствами для доступа к информации расположенной как на локальном диске так и на удаленном сервере а также большим коллекцией...
42966. Цифровая радиолиния КИМ-ЧМнФМ 4.95 MB
  Рязань 2012 Содержание Общая характеристика системы управления Расчет и выбор основных технических характеристик системы 2.5 Расчет энергетического потенциала 3Контур управления и его анализ 4Разработка функциональной схемы радиолинии Спектр сигнала КИМЧМнФМ Описание функциональной схемы передатчика Описание функциональной схемы приемника Конструкция бортового приемника Заключение Литература 1. Общая характеристика системы управления сигнал дискретизация квантование кодирование приемник Командное радиоуправление...
42967. КОМПЬЮТЕРНОЕ ПРОЕКТИРОВАНИЕ МИКРОВОЛНОВОГО ФИЛЬТРА НИЖНИХ ЧАСТОТ НА ОСНОВЕ МИКРОПОЛОСКОВОЙ ЛИНИИ 107.64 KB
  Целью работы является проектирование фильтра нижних частот на основе микрополосковой линии определение продольных и поперечных величин всех его элементов. Основной задачей будет нахождение наиболее оптимальной модели фильтра...
42968. Расчет оборудования для вакуум-кристаллизации галургического хлорида калия на БКПРУ- 1.03 MB
  Для охлаждения осветленного насыщенного щелока от 90 до 18–°C используется принцип самоиспарения, при котором испарение части растворителя – воды и охлаждение щелока достигается в результате кипения щелока под вакуумом. При этом растворный пар образуется за счет тепла самого щелока, температура которого понижается.
42969. Доходы и расходы организации 605.54 KB
  Новосибирск Проверил: преподаватель кафедры ЭУЗ Ершова Татьяна Валентиновна Новосибирск 2010 План курсовой работы: План курсовой работы Доходы организации общие положения Доходы от обычных видов деятельности Операционные доходы...
42970. Расчет оборудования для вакуум-кристаллизации галургического хлорида калия на БКПРУ-4 1.03 MB
  Количество испаренной воды в каждой ступени рассчитываем по уравнению теплового баланса где Gn–количество щелока поступающего в nую ступень ВКУ кг ч; Сщел –теплоемкость щелока кДж кгС; tн –tк –перепад температур в nой ступени ВКУ С; rn –удельная теплота парообразования на nой ступени ВКУ кДж кг. Сводная таблица материального баланса Состав Приход кг ч Расход кг ч KCl раствор 8455216 3578556 KCl твердый 487666 NCl раствор 7241179 7241179 NCl твердый H2O раствор 27354605 24168545 H2O испаренная ...
42971. Принципиальная схема высокоэффективного импульсного регулятора напряжения постоянного тока 1.34 MB
  Регуляторыстабилизаторы напряжения или других параметров электроэнергии в цепях постоянного тока выполняются преимущественно на основе полупроводниковых приборов. На выходное напряжение преобразователя электроэнергии влияют различные факторы: изменение входного напряжения и тока нагрузки температура окружающей среды и др. Поскольку они вызывают изменения выходного напряжения их в этом смысле называют возмущающими. Точность поддержания напряжения при воздействии различных возмущающих факторов характеризуется соответствующими параметрами...
42972. Разработка ремонтной мастерской с ремонтно-технологической документацией на ремонт узлов металлоконструкции автомобильного крана 1.23 MB
  Определение годового объема работ по ТО и Р ремонтной мастерской и распределение трудоемкости по видам работ 15 1. Определение суммарного объема работ по ТО и Р 15 1. Годовой объем работ по отдельным зонам ремонтной мастерской 16 1. Распределение трудоемкости ТО по видам работ 17 1.