3.2 Метод парабол
Рассмотрим
алгоритм квадратичной интерполяции
или метод парабол, т.е. в качестве
аппроксимирующей функции используется
парабола. Для однозначного задания
параболы необходимы три точки. Пусть
имеются три точки, для которых выполняется
,
,
.
Так как
– отрезок неопределенности и
– унимодальная функция, то найти такую
точку
нетрудно.
Парабола, проходящая через три точки
,
имеет вид
.
Поскольку
– унимодальная функция, то хотя бы одно
из неравенств
,
строгое и, следовательно, коэффициент
при старшем члене
положителен. Тогда
достигает минимума в точке
,
причем
.
Эта точка и выбирается в качестве точки
очередного вычисления значения функции.
Рис.6 Иллюстрация для метода парабол
Если
оказалось, что
,
условимся в качестве точки очередного
вычисления выбирать точку
.
Итак, следующее вычисление проводится
в точке
Определим
новый отрезок неопределенности с лежащей
внутри него точкой, для которой выполняются
условия аналогичные условиям, которым
удовлетворяла точка
.
В силу
унимодальности функции
и в зависимости
от выполнения или невыполнения условий
это будут
отрезки с точкой внутри:
и
;
и
;
и
;
и
;
и
;
и
.
Смотри рисунок. Далее строится парабола,
определяется ее минимум, и т.д., до тех
пор, пока длина отрезка неопределенности
не удовлетворяет заданной точности.
Схема алгоритма
Шаг
1. Задаются
и
.
Вычислить
.
Шаг
2. Вычислить
,
,
где
Шаг 3.
А)
При
.
Если
,
то
.
Если
,
то
.
Если
,
то
.
Б)
При
.
Если
,
то
.
Если
,
то
.
Если
,
то
.
Шаг
4. Если
,
то закончить поиск, положив
,
иначе перейти к шагу 2.
4 Поиск экстремума функции одной переменной в среде Матлаб
При решении задач максимума и минимума функции одной переменной выделяют задачи локального (на каком-либо интервале) и глобального (на всей числовой оси) экстремума. В MATLAB поиск локального минимума осуществляет функция:
[х, у]= fminbnd(name, a, b [, options])
для которой:
name - имя М-функции, вычисляющей значение ;
а, b - границы интервала, на котором осуществляется поиск минимума;
options - параметры, управляющие ходом решения;
х, у - координаты точки, в которой достигается минимум функции на заданном интервале.
Функцию fminbnd можно использовать и для вычисления локального максимума. Для этого достаточно взять функцию name с противоположным знаком.
Пример:
найти экстремум функции
на интервале
.
В М-файле с именем mf.m пишем:
function y=mf(x)
y=x.^4-0.5*x.^3-28*x.^2+140;
end
Потом в командном окне пишем:
x=-5:0.1:6;
y=-(x.^4-0.5*x.^3-28*x.^2+140);
plot(x,y,'-k'), grid
%Максимум функции на интервале [-2 2]
y=-mf(x);
[x,y]=fminbnd(@mf,-2,2)
Результат:
x =
3.7224e-008
y =
-140.0000
Рис.7 Иллюстрация для метода касательных
5. Программа работы
5.1. Изучить предлагаемые методы одномерной безусловной оптимизации.
5.2. В соответствии с вариантом задания (см. таблицу 1), определенным преподавателем, составить блок-схемы алгоритмов, реализующие заданные методы поиска. Для заданного начального интервала реализовать три шага алгоритма поиска минимума. Результаты расчетов представить в виде таблицы.
Используя средства Матлаба найти экстремумы заданных функций и сравнить с ранее полученными результатами.