12248

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

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

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

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

Русский

2013-04-24

1 MB

61 чел.

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

 

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

77739. Диски и контроллеры SAS 1.93 MB
  SS может использовать и большой набор разновидностей RID. Такие гиганты как dptec или LSI Logic в своих продуктах предлагают расширенный набор функций для расширения миграции создания гнёзд и других возможностей в том числе касающихся распределённых массивов RID по нескольким контроллерам и приводам. Но SS это больше нежели интерфейс следующего поколения для профессиональных жёстких дисков хотя он идеально подходит для построения простых и сложных RIDмассивов на базе одного или нескольких RIDконтроллеров. Вместе с мощными...
77740. Интерфейс eSATA и высокоскоростной внешний кейс для десктопных винчестеров любой емкости 1.15 MB
  Интерфейс eST externl Seril T Вместе с тем с некоторых пор проблема выбора интерфейса для внешнего накопителя или контейнера для жестких дисков обрела очень симпатичное и оптимальное решение: внедрение последовательного дискового интерфейса Seril T изначально ориентированного на горячее подключение накопителей и увеличенную по сравнению с IDE длину сигнального кабеля позволило почти даром создавать внешние накопители и контейнеры просто выводя внутренний порт Seril T наружу компьютера. Именно так и поступали некоторые производители...
77741. ИССЛЕДОВАТЕЛЬСКИЙ ПОТЕНЦИАЛ И ПРИНЦИПЫ ЭФФЕКТИВНОСТИ ИССЛЕДОВАТЕЛЬСКОГО ПРОЦЕССА 42 KB
  Методологическая готовность проявляется в наличии цели и миссии исследования. Миссия исследования рассматривается как доминанта его проведения обеспечивающая последовательное движение к цели. Большое значение имеют: опыт исследования информационная база его проведения методика моделирования и оценок процессов или явлений доступность методов исследования наличие соответствующих технических средств квалификация исследователей.
77742. ФАКТОЛОГИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ИССЛЕДОВАНИЯ 42.5 KB
  От наличия и достаточности фактов зависит качество управленческих решений а следовательно и эффективность управления. Исследование управления также невозможно без фактов на которых оно строится. Роль фактов в исследовании заключается в том что они: очерчивают явление позволяют распознавать проблему определяют саму необходимость исследования создают мотивационное поле исследования.
77743. ОЦЕНКИ В ИСУ 52 KB
  Средством оценки является показатель. Оценки могут быть: программно-тестовые с использованием компьютерной техники; экспертные на основе работы группы экспертов. коллективные и индивидуальные; точные и приблизительные; эпизодические и периодические; общие и локальные; простые и сложные последние построены на специальных расчетах агрегировании информации построении синтетических показателей; Для достижения успеха исследования нужно уметь правильно выбирать вид оценки.
77744. МЫШЛЕНИЕ ИССЛЕДОВАТЕЛЯ 55 KB
  мышление абсолютно индивидуально Именно в мышлении проявляются особенности личности Однако любое разнообразие можно классифицировать. Это качество может быть как положительным так и отрицательным в зависимости от того по каким факторам мышление проявляет это качество.1 Индивидуализированное мышление ярко проявляющее черты личности индивидуальность неординарность.
77745. КРЕАТИВНОЕ ОБРАЗОВАНИЕ СОВРЕМЕННОГО МЕНЕДЖЕРА 72.5 KB
  Образование: определяет уровень развития способностей корректирует и формирует индивидуальность специалиста. Креативное образование образование ориентированное на развитие творческих способностей человека на закрепление в его профессиональном сознании установки на инновации включающее анализ проблем и вариантов деятельности. Это образование мотивирующее самостоятельное осмысление действительности самопознание индивидуальности превращения знаний в потенциал мышления и саморазвития.
77746. ПРОГРАММА И ПЛAH ИССЛЕДОВАНИЯ 37 KB
  Она должна содержать: обоснование предмета исследования важность и актуальность проблемы общее содержание исследуемой проблемы роль ее относительно других проблем необходимые условия для успешного решения проблемы финансирование кадровое обеспечение организационные условия временные ограничения и пр. Программа как правило состоит из следующих разделов: Цель проведения исследований Содержание проблемы ее актуальность и важность Парадигма и рабочая гипотеза решения проблемы в процессе исследования Обеспечение исследования...
77747. ФОРМЫ И ФАКТОРЫ ОРГАНИЗАЦИИ ИССЛЕДОВАНИЯ 65.5 KB
  Организация исследования определяет дифференциацию и интеграцию деятельности исследователей или исследовательских групп. В ней находят свое отражение распределение и комбинация ресурсов по времени видам работ кадрам проблемам Формы организации исследования Увеличение нагрузки персонала дополнительными обязанностями исследовательской работы. Такие исследования возможны если: у персонала управления есть резервы времени; его исследовательский потенциал достаточно высок.