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

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

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 г.

Методы одномерной оптимизации
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации