Классификация методов одномерной безусловной оптимизации.




 

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

 

1. Методы исключения интервалов (линейный поиск):

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

1.2. Метод «золотого сечения»;

1.3. Метод Фибоначчи;

 

2. Метод полиномиальной аппроксимации:

2.1. Метод Пауэлла;

 

3. Методы с использованием производных:

3.1. Метод секущих;

3.2. Метод качательных.

 

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

Методы исключения интервалов накладывают единственное требование на исследуемую функцию: она должна быть унимодальной. Следовательно, указанные методы можно использовать для анализа как непрерывных, так и разрывных функций, а также в случаях, когда переменные принимают значения из дискретного множества. Логическая структура поиска с помощью методов исключения интервалов основана на простом сравнении значений функции в двух пробных точках. Кроме того, при таком сравнении в расчет принимается только отношение порядка на множестве значений функции и не учитывается величина разности между значениями функции.Большим достоинством этих методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы методов нулевого порядка, это возможность определения значений f(x) в заданных точках, а также, что исследуемая целевая функция в допустимой облас-ти, по крайней мере, обладает свойством унимодальности.

Определение 3. Функция f(x) называется унимодальной, если существует такая точка x*, что из следует , а из следует .

 

Другими словами, слева от x* функция f(x) монотонно убывает, а справа - монотонно возрастает.

 

Отметим, что в данном определении не предполагается ни гладкость, ни непрерывность функции.

 

 

Это важное свойство унимодальных функций. Если мы знаем значения f в точках и отрезка [a,b], , то мы можем определенно сказать на каком из отрезков лежит минимум x* функции f.

Действительно, возможны три различных результата:


a) . В этом случае интервал может быть отброшен.

 

 

б) . В этом случае интервал может быть отброшен.

 

в) . В этом случае интервалы и могут быть отброшены.

 

 

Методы поиска на основе исключения интервалов указывают на отрезок, на котором гарантированно лежит точка x*. Этот отрезок называют отрезком неопределенности. Если в качестве приближенного значения x* взять центр этого отрезка, то погрешность метода есть половина длины отрезка неопределенности.

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

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

Итак, рассмотрим задачу нахождения единственного корня на отрезке [a,b] нелинейного уравнения f(x) = 0 в предположении непрерывности функции f(x).

Геометрически корень x* соответствует точке пересечения графика функции y= f(x) с осью Ох.

Определение 4.. Число x* - есть корень уравнения кратности k, если при x= x * вместе с функцией f(x) обращаются в нуль ее производные до (k-1) порядка включительно, т.е.:

Корень кратности k=1 называется простым.

 

 

Так на рисунке корни и – простые, - как минимум кратности 2, как минимум кратности 3.

Если уравнения f(x) = 0 имеет на [a,b] несколько корней, то выполняется операция отделения (локализации) корней, т.е. нахождения достаточно малых окрестностей рассматриваемой области, в которых содержится одно значение корня данного уравнения. Для выявления отрезка, содержащего корень уравнения, следует построить график этой функции.

Для нахождения корней уравнения f(x) = 0 используются различные итерационные методы.

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




Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-02 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: