Доклад - Методы одномерной оптимизации - файл n1.doc

приобрести
Доклад - Методы одномерной оптимизации
скачать (319.5 kb.)
Доступные файлы (1):

n1.doc

320kb.

16.09.2012 08:27

скачать

---

Смотрите также:
• Лабораторная работа №1 (Лабораторная работа)
• Лабораторная работа №1 (Лабораторная работа)
• Методы безусловной многомерной оптимизации. Рекомендации к выполнению лабораторных, практических и курсовых работ по дисциплине Методы оптимизации (Документ)
• Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации (Документ)
• Лекции по методам оптимизации (Лекция)
• Лабораторная работа №1 (Методы одномерной минимизации) (Лабораторная работа)
• Лабораторная работа №1 «Численные методы решения задач одномерной оптимизации средствами Excel» студент группы бпс-215 (Документ)
• Курсовая работа по методам оптимизации (Курсовая)
• Лабораторная работа - Методы одномерной оптимизации (вариант 5) (Лабораторная работа)
• Лекции - Методы оптимизации (Лекция)
• Некрасова М.Г. Методы оптимизации (Документ)
• Задача о рюкзаке ( о ранце ) (Документ)

n1.doc

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

- функция одной переменной

- целевая функция.
Решение: найти х, при котором принимает оптимальное значение.

2 варианта:

• 
  минимизировать – задача минимизации;
  
• 
  максимизировать – задача максимизации.
  

Рассмотрим случай минимизации

2 способа:

• 
  аналитический
  
• 
  численный
  

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

1. 
   точка называется глобальным минимумом, если для
   
2. 
   точка называется строгим глобальным минимумом, если для
   
3. 
   точка называется локальным минимумом, если для
   
4. 
   точка называется строгим локальным минимумом, если для
   

Следствие: любая точка глобального минимума является локальным минимумом, обратное не верно.

Аналитический способ нахождения локального минимума.
- дифференцируема

- необходимое условие точки локального минимума.



















Численные методы.
Пусть функция задана на интервале , при этом существует такая точка , что на – монотонно убывает, а на – монотонно возрастает, то функция унимодальная.









а b
Если из того что следует, что , то функция называется монотонно возрастающей. Если из того что следует, что , то функция называется монотонно убывающей.


Методы одномерного поиска.
Разобьем и вычислим значение функции в каждой точке.

















искомый минимум
В результате остается интервал меньшего размера, к которому применяется тот же метод, и находим еще один интервал, в конце находим интервал с заведомо нужной точкой.
Интервал неопределенности – интервал, в котором заведомо находится точка минимума. Наиболее эффективное разбиение – двумя точками на 3 равных отрезка.





1)

2)
- после выполнения n шагов сокращение исходного интервала



- точность с которой надо найти решение задачи.

N=2n, где n – число шагов, N – число вычислений (мера эффективности данного решения).

Метод золотого сечения.
Точки должны быть расположены на равном расстоянии.




а b






; ; ;

; - золотое сечение.
а










- величина сокращения на каждом шаге



число итераций растет как логарифм функции.


Одномерная оптимизация с использованием производных.
. Пусть целевая функция дифференцируема .

точка локального минимума	точка локального максимума	точка перегиба

Методы для нахождения корня уравнения функции 1-ой производной от исходной.
Нахождение локального минимума или максимума сводится к нахождению корней первой производной от данной

f’(x)=0
Если f’(x) представляет собой многочлен, то уравнение называется алгебраическим (полиномиальным), если f’(x) представлена тригонометрическими, логарифмическими, показательными и т.п. функциями, то уравнение называется трансцендентным.( вдальнйшем вместо f’(x) будем употреблять f(x) )

Решение уравнения вида разбивается на два этапа:

1. 
   отделение корней, т.е. отыскание достаточно малых областей, в каждой из которых заключен один и только один корень уравнения;
   
2. 
   вычисление выделенного корня с заданной точностью.
   

На первом этапе может помочь построение приближенного графика функции f(x) или, если функция достаточно сложная, то можно попытаться представить уравнение в виде и построить два графика и , тогда корнями уравнения будут абсциссы точек пересечения этих кривых.

Выбор интервалов, в которых имеется один и только один корень производится на основании известных свойств непрерывных функций:

• 
  Если на концах некоторого интервала функция непрерывна и принимает значения разных знаков, т.е. , то на этом интервале уравнение имеет хотя бы один корень (один или нечетное количество корней).
  
• 
  Если на концах интервала функция принимает значения одинаковых знаков, т.е. , то на этом интервале уравнение не имеет корней или имеет четное количество корней.
  
• 
  Если на интервале первая и вторая производные функции сохраняют определенный знак, т.е. и или и , и не обращаются в нуль на всем участке, то функция монотонна, и корень будет единственным.
  

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

• 
  половинного деления;
  
• 
  Ньютона.
  

Метод половинного деления

Суть метода половинного деления (дихотомии) заключается в следующем.

Отрезок делится пополам и за первое приближение корня принимается точка c, которая является серединой отрезка, т.е.. Если , это корень уравнения. Если нет, то далее выбирается тот из отрезков [a, c] или [c, b], на концах которого функция имеет разные знаки. Полученный отрезок снова делится пополам, и проводятся те же рассуждения. Деление продолжается до тех пор, пока длина отрезка не станет меньше заданного .

Графическая интерпретация метода представлена на рис. 1.1. Метод половинного деления реализуется в виде следующего алгоритма:

Найти точку c = (a + b)/2.

Если f(a)f(c) <0, то корень лежит на интервале [a, c], если нет, то корень лежит на интервале [c, b].

Если величина интервала не превышает некоторое достаточно малое число е, то найден корень с точностью е, иначе возврат к п.1.

Несмотря на простоту, этот метод требует слишком большого количества вычислений и не всегда позволяет найти решение с заданной точностью.






Блок-схема алгоритм решения уравнения методом деления пополам.

Метод Ньютона (метод касательной):
Идея метода касательных состоит в следующем. Возьмем некоторую точку , участка , например, и проведем касательную к графику функции в точке . Уравнение касательной в точке имеет вид:

.

В качестве начального приближения корня уравнения примем абсциссу точки пересечения этой касательной с осью Ох. Тогда, полагая в уравнении касательной , можно найти абсциссу точки пересечения:

.

Это значение можно принять за следующее приближение . Далее касательная проводится через точку , абсцисса пересечения которой с осью Ох даст второе приближение корня , и так далее, пока не будет достигнута точность .

Алгоритм, реализующий метод касательных, можно представить так:

Определяется начальное приближение: если , то начальное приближение , иначе .

Уточняется значение корня по формуле .

.

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

Алгоритм решения уравнения методом Ньютона

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРЗОВАНИЯ

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ

РЕФЕРАТ

По теме:

«Методы одномерной оптимизации »
Выполнил: ********************

Руководитель: *************

г. Уфа. 2008 г.

---

Методы одномерной оптимизации