12249

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

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

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

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

Русский

2013-04-24

781.11 KB

31 чел.

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

 

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

29922. Отличие аудита от других форм эк.контроля 34 KB
  По мнению абсолютного большинства специалистов первое место принадлежит ревизии. Цель ревизии определение законности полноты и своевременности взаимных платежей и расчетов проверяемого объекта и федерального бюджета бюджетов государственных внебюджетных фондов а также эффективности и целевого использования государственных средств. Объекты ревизии все государственные органы в том числе их аппараты и учреждения в Российской Федерации государственные внебюджетные фонды а также органы местного самоуправления...
29923. Оформление результатов аудиторской проверки 35.5 KB
  Аудиторское заключение официальный документ дающий оценку достоверности бухгалтерского учета и отчетности аудируемого предприятия подтвержденный подписью имеющего лицензию руководителя проверяющей группы аудиторской фирмы и печатью этой фирмы. Возможны четыре вида аудиторских заключений: заключение без замечаний безоговорочное заключение; заключение с замечаниями заключение с оговорками; отрицательное заключение; заключение не дается совсем либо дается отказное заключение. Заключение с замечаниями делается при выявлении...
29924. Оценка финансового состояния, платеже- и кредитоспособности организации 31.5 KB
  Оценка платежеспособности осуществляется на основе характеристики ликвидности текущих активов т. Понятия платежеспособности и ликвидности очень близки но второе более емкое. От степени ликвидности баланса зависит платежеспособность. Анализ ликвидности баланса заключается в сравнении средств по активу сгруппированных по степени убывающей ликвидности с обязательствами по пассиву которые сгруппированы по степени срочности их погашения.