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.

 

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

43515. Будова та основні характеристики мікропроцесора Intel Core i5-661 888.5 KB
  Опис процесора Intel Core i5661 рисунок. Intel Core i5661 Процесор Intel Core i5651 заснований на 32нм ядрі Clrkdle. І в цьому лежить його головна технологічна відмінність від процесорів Intel Core i57xx. Так Intel Core i5650 – це двоядерний процесор на відміну від чотирьохядерних Intel Core i57xx що мають вдвічі більший обєм кешпамяті 8 МБ проти 4 МБ.
43516. СОЦІАЛЬНА СТРАТИФІКАЦІЯ СУЧАСНОГО СУСПІЛЬСТВА 197 KB
  Поняття соціальної стратифікації суспільства. Типи стратифікованого суспільства . Соціальна стратифікація сучасного суспільства .
43517. Проектирование цифрового счетчика 454 KB
  Дополнительные требования: предусмотреть управление реверсом и индикацию направления счета Теоретическая часть Счетчиком называется последовательное устройство предназначенное для счета входных импульсов и фиксации их числа в двоичном коде. В цифровых схемах счетчики могут выполнять следующие микрооперации над кодовыми словами: 1 установка в исходное состояние запись нулевого кода; 2 запись входной информации в параллельной форме; 3 хранение информации; 4 выдача хранимой информации в параллельной форме; 5 инкремент ...
43518. Развитие коммуникативных способностей личности подростка в процессе обучения искусству 97.5 KB
  Влияние обучения искусству на развитие коммуникативных способностей личности подростка. Изучение театральных основ и развитие личности. Внутренние факторы – это состояние отношение качество личности круг умений и навыков которые необходимы в общении.
43519. Технологические процессы и оборудование 468 KB
  Котёл предназначен для получения горячей воды с температурой до 150° С и давлением 2,25 МПа в отдельно стоящих котельных для использования в системах отопления, вентиляции и горячего водоснабжения объектов промышленного и бытового назначений и на ТЭЦ в качестве пиково-резервных источников тепла.
43520. Технология производства хлористого калия методом растворения-кристаллизации 426 KB
  Осветление горячего насыщенного щелока от глинистых и солевых частиц. Охлаждение осветленного насыщенного щелока за счет самоиспарения под вакуумом и кристаллизация хлористого калия. Сгущение хлоркалиевой пульпы с целью отделения основной массы маточного щелока от кристаллов хлористого калия. Нагрев растворяющего щелока.
43521. НАПРЯМИ ТА ПРОПОЗИЦІЇ ЩОДО ВДОСКОНАЛЕННЯ ПРОФЕСІЙНОГО ПІДБОРУ ПЕРСОНАЛУ НА ПІДПРИЄМСТВІ 276.5 KB
  Якщо чисельність персоналу менша від нормативної, кадрового потенціалу стає недостатньо для розв’язання нагальних проблем розвитку організації. Планові перетворення виробничої та управлінської бази організації в цьому разі не забезпечуються достатньою професійною й інтелектуальною підтримкою наявних кадрів.
43522. Оценка эффективности затрат на предупреждение аварии и обучение нештатных АСФ 521 KB
  Основная причина и прогнозирование масштаба аварии. Технологический способ локализации аварии. Расчет сил и средств локализации аварии. Задание на учение и решение руководителя по ликвидации аварии.
43523. Облік операцій з фінансової оренди (лізингу) підприємства 816.5 KB
  Виходячи з вищесказаного була вибрана тема курсової роботи – Облік операцій з фінансової оренди лізингу підприємства. Тема оренди та лізингу є однією з найбільш актуальних як для великих підприємств так і для невеликих фірм. Оскільки подібні угоди не допускають можливості дострокового припинення оренди правильне визначення величини періодичної плати забезпечує власникові повне відшкодування...