12249

Методы минимизации функции одной переменной, использующие информацию о производных целевой функции

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

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

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

Русский

2013-04-24

781.11 KB

30 чел.

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

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

использующие информацию о производных целевой функции.

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

В лабораторной работе № 1 были рассмотрены прямые методы решения задачи минимизации функции одной переменной. В данной работе рассматриваются методы минимизации, которые используют информацию о производной целевой функции.

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

Метод средней точки.

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

Сравнивая  с нулем, делим отрезок поиска точки минимума ровно вдвое, причем на каждой итерации нам надо вычислить только одно значение , не вычисляя при этом самой функции.

Алгоритм:

  1. Задать начальный интервал неопределенности L0 и точность ε.
  2. Положить . Вычислить .
  3. Проверка на окончание поиска: если , то положить ,  и завершить поиск, иначе – перейти к шагу 4.
  4. Сравнить  с нулем. Если , то продолжить поиск на отрезке , положив , иначе перейти к отрезку , положив . Перейти к шагу 2.

Метод хорд.

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

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

Координата этой точки равна:

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

Алгоритм:

  1. Выбрать начальный интервал неопределенности L0 и точность .
  2. Вычислить значения , .
  3. Положить , , , .
  4. Вычислить точку и значение .
  5. Если , то перейти к шагу 8.
  6. Если , то положить , , в противном случае положить , .
  7. Перейти к шагу 4.
  8. Выбрать приближенно , . Поиск завершен.

Метод Ньютона (метод касательных).

Стратегия поиска: Пусть функция является дважды непрерывно дифференцируемой на отрезке . Тогда для приближенного решения уравнения  можно применить метод Ньютона, или метод касательных.

Пусть  - нулевое, или начальное приближение к искомой точке . Построим в точке  касательную к графику функции :

Выберем в качестве следующего приближения к  точку  пересечения касательной с осью абсцисс:

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

Возвращаясь к обозначению , получим, что для решения уравнения  необходимо построить последовательность

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

Алгоритм:

  1. Выбрать начальное приближение x0, точность ε и предельное число итераций M.
  2. Положить k = 0 (k – номер итерации).
  3. Вычислить , .
  4. Вычислить точку и значения производных , .
  5. Если , то перейти к шагу 8.
  6. Положить k = k +1.
  7. Если k < M  перейти к шагу 4, в противном случае завершить поиск (последовательность расходится, необходимо повторить поиск с другим начальным приближением).
  8. Выбрать приближенно , . Поиск завершен.

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

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

 

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

12228. Кинетика разложения мурексида в кислой среде. 31.36 KB
  Лабораторная работа №2 Кинетика разложения мурексида в кислой среде Цель работы: определение порядка реакции по мурексиду и катализатору кислоте и составление дифференциального кинетического уравнения реакции по результатам оп
12229. Измерение ЭДС элемента Якоби-Даниэля. Определение потенциала отдельных электродов 29 KB
  Измерение ЭДС элемента ЯкобиДаниэля. Определение потенциала отдельных электродов Цель работы: приготовление гальванического элемента и измерение его ЭДС. Вычисление ЭДС элемента при заданных концентрациях солей. Сравнение полученных результатов с вычисленными знач
12230. Определение порядка реакции окисления иодид-ионов ионами трехвалентного железа 194 KB
  Определение порядка реакции окисления иодидионов ионами трехвалентного железа Цель работы: определение частных кинетических порядков и общего кинетического действительного порядка реакции Fe3I Fe2I 1 в водном растворе и сравнение их со стехиометрическими поря
12231. ИЗУЧЕНИЕ КИНЕТИКИ РЕАКЦИИ ОМЫЛЕНИЯ СЛОЖНОГО ЭФИРА 74 KB
  Изучение кинетики реакции омыления сложного эфира Цель: Определить средние значения K реакции омыления этилацетата в щелочной среде при двух температурах; вычислить энергию активации данной реакции. Ход работы: Измерение постоянной сосуда. Определялась
12232. Омыление сложного эфира в щелочной среде при двух температурах 242 KB
  Изучение кинетики реакции омыления сложного эфира Цель работы: определение средних значений констант скорости реакции омыления сложного эфира в щелочной среде при двух температурах вычисление энергии активации и предэкспоненциального множителя. Принцип метода: ко
12233. Определение средних значений констант скорости реакции омыления сложного эфира 22.27 KB
  Лабораторная работа № 1 Цель работы: определение средних значений констант скорости реакции омыления сложного эфира этилацетата в щелочной среде. Опыты показывают что реакция протекает как реакция второго порядка.
12234. Определение константы диссоциации слабого электролита 337 KB
  Определение константы диссоциации слабого электролита Цель работы: установить зависимость удельной и эквивалентной электропроводности слабого электролита от концентрации. Рассчитать значения степени и константы диссоциации слабого электролита. Принцип метода: ко
12235. Реакция гидролиза сахарозы с образованием глюкозы и фруктозы 25.7 KB
  Лабораторная работа №3 Определение константы скорости инверсии тростникового сахара сахарозы. Цель работы: определить порядок реакции по сахару и катализатору определить средние константы скорости реакции . Изучаемым процессом является реакция гидролиза...
12236. Определить растворимости и произведения растворимости труднорастворимых солей 33.51 KB
  Цель работы: определить растворимости и произведения растворимости труднорастворимых солей. Рабочая формула где: S растворимость. предельные эквивалентные электропроводности ионов удельная электропроводность раствора Таблица 1 Дан...