Задача поиска экстремума функции одной переменной возникает при оптимизации целевой функции, зависящей от одной скалярной переменной. Такие задачи входят составной частью во многие итерационные методы решения задач многомерной оптимизации.
Например, численные методы поиска экстремума имеют особенность в том, что их применение не позволяет определить точное значение координат, при котором достигается экстремум функции. В этом случае определяют интервал неопределенности, в котором локализуется экстремум функции. Величина этого интервала – ∆, определяется исходя из требований точности результата решения при постановке задачи (быстродействие, точность и пр.). Таким образом, численное решение задачи поиска экстремума функции сводится к уменьшению интервала неопределенности от исходного до ∆.
Метод прямого сканирования
Задача заключается в локализации экстремума функции одной переменной, заданной на интервале [ a, b ] с точностью до ∆. При решении этой задачи весь интервал разбивается на участки величиной ∆. В узлах разбиения вычисляются значения функции Q и из них выбирается экстремальное. Этот метод требует больших затрат времени (зависящего от значения ∆), но главное его преимущество – это определение глобального экстремума. Блок-схема алгоритма поиска Q (x) представлена на рис. 3.
Рис.3. Блок схема алгоритма метода прямого сканирования
Метод половинного деления (дихотомии)
Требуется определить экстремум унимодальной функции Q (u) на отрезке [ a, b ] с точностью ∆. Отрезок [ a, b ] делится пополам и вычисляются значения функции Q (x 1) = F 1 и Q (x 2) = F 2 в точках 
На основе анализа значений F 1 и F 2 вдвое уменьшается интервал неопределенности и процесс повторяется пока b – a > ∆+ e, где малое положительное число. Блок-схема этого метода приведена на рис.4, б.
Рис.4. Алгоритм метода дихотомии
2.3 Метод "золотого сечения"
Интервал неопределенности делится не пополам, как в методе дихотомии, а в определенном иррациональном соотношении 
(рис.5, а). Это соотношение выполняется при 
Метод заключается в том, что по заданным a и b как можно точнее определяется значение внутренней точки x 1 (см. рис.5, б) по формуле
x 1 = b – (b – a) / 1,618033989…
Точка x 2 определяется как точка, симметричная точке x 1 на отрезке (a – b), т.е. (x 1– a)=(b – x 2).
На основе анализа значений F 1 = Q (x 1) и F 2 = Q (x 2) интервал неопределенности сокращается путем отбрасывания из рассмотрения отрезка в котором экстремум исключен, исходя из условий унимодальности Q (u). Далее мы определим симметричную точку внутри новых границ, вычисляем значение Q в этой точке, проводим анализ и т.д. до тех пор, пока разность между симметричными точками внутри интервала неопределенности больше ∆. Блок-схема алгоритма метода "золотого сечения" представлена на рис.6.
Рис.5 Метод "золотого сечения":
а – золотое сечение; б – геометрическое представление
Рис. 6. Блок-схема алгоритма метода «золотого сечения»
Метод Фибоначчи
Метод, использующий числа Фибоначчи, позволяет наиболее эффективно достичь заданной точности в поиске экстремума функции Q (u). Числа Фибоначчи определяются соотношением
F 0 = F 1 = 1; Fk = Fk –1 + Fk –2; k = 2, 3, …,
где, например F 2 = 2, F 3 = 3, F 4=5, …, F 10 =89, F 11 = 144, F 20 = 10946. Число Фибоначчи можно вычислить по формуле
При большом " k " отношение соседних чисел Фибоначчи близко к отношению "золотого сечения".
Этот метод делит интервал неопределенности не в постоянном соотношении, а в переменном и предполагает некоторое, вполне определенное, зависящее от ∆, число вычислений значений функции Q (u).
Рис.7. Блок-схема алгоритма метода Фибоначчи
По заданному ∆ определяется количество вычислений n и соответствующее ему число Фибоначчи Fn, исходя из соотношения
.
Методический пример
Требуется исследовать на минимум функцию y =(x -1)2+1 методом прямого сканирования.
1) Создаем свою рабочую папку на диске D или Е под именем:
Фамилия_Группа.
2) Запускаем Matlab и делаем свою директорию текущей (из выпадающего списка Current Directory).
3) Открываем окно редактора М-файлов (на панели инструментов кнопка <New M-File>) и создаем М-файл-функцию, реализующую y =(x -1)2+1:
%Исследуемая функция
function y=Q(x)
y=(x-1).^2+1;
return
Сохраняем М-файл под именем Q, Matlab автоматически присвоит ему расширение.m.
4) Открываем окно редактора М-файлов и создаем М-файл-функцию, реализующую метод прямого сканирования:
% Определние min функции одной переменной методом пря%мого сканирования
% Входные параметры: a, b - границы интервала [a,b], %del - точность
% Выходные параметры: xmin, Qmin - точка минимума; n - %количество вызовов Q(x)
%
function [xmin,Qmin,n]=pr_scan(a,b,del)
x=a; % присвоение начального значения аргументу х
n=0; % начальное значение счетчика вызовов Q(x)
while x<b % начало оператора цикла с предусловием
qq=Q(x); % вычисление значения функции в точке х
n=n+1; % счетчик вызовов функции Q(x)
if x==a % начало условного оператора if
Qmin=qq;
xmin=x;
elseif qq<Qmin
Qmin=qq;
xmin=x;
end; % конец оператора if
x=x+del; % переход к следующему шагу
end; % конец оператора while
% Строим график
x=-2:0.1:2; % диапазон изменения аргумента с шагом 0.1
plot(x,Q(x)),grid %рисование графика с коорд. сеткой
title('y=(x-1)^2+1') % оформление заголовка
xlabel('x') % подпись оси х
ylabel('Q(x)') % подпись оси y
%отметка точки min маркером в виде точки размером 20pcs
line(xmin, Qmin,'Marker','.','MarkerSize', 20);
Сохраняем данный М-файл под именем pr_scan.
5) В командном окне (Command Window) вводим входные параметры и запускаем на решение функцию pr_scan:
>> a=-2;
>> b=2;
>> del=0.001;
>> [xmin,Qmin,n]=pr_scan(a,b,del)
xmin =
1.0000
Qmin =
n =
В окне Figure 1 наблюдаем график построенной функции (рис. 8).
Рис. 8. График функции y =(x -1)2+1
Задание
Таблица 1
| № п/п | Функция | Границы интервала | Интервал неопределенности | |
| a | b | D | ||
| Y = x 4 - 2 x 2 + sin x + 3 | -2 | 0.001 | ||
| Y = x 4 - 2 x 2 + 3cos x – 3 x | -2 | 0.001 | ||
| Y = x 4 - 2 x 2 – 0.7sin x + 5 | -2 | 0.001 | ||
| Y = x 4 - 2 x 2 – 3arctg x + 3 | -2 | 0.001 | ||
| Y = x 4 - 2 x 2 – 3arcsin x + 3 | -2 | 0.001 | ||
| Y = - x 3 + 2 x 2 + 3e x - 3 | -2 | 0.001 | ||
| Y = - x 3 + 2 x 2 + 3e x +sin x - 3 | -2 | 0.001 | ||
| Y = x 4 - 2 x 2 - 3e x -sin x + 5 | -2 | 0.001 |
Таблица 2
| № функции | Вариант | ||||||||||||||
| + | + | + | + | + | |||||||||||
| + | + | + | + | + | |||||||||||
| + | + | + | + | + | |||||||||||
| + | + | + | |||||||||||||
| + | + | + | |||||||||||||
| + | + | + | |||||||||||||
| + | + | + | |||||||||||||
| + | + | + |
Выбрав в соответствии с заданным преподавателем вариантом (см. табл.1, 2) функции для исследования, выполните приводимые ниже задания.
1) Разработать программы реализации методов одномерной оптимизации в системе Matlab: прямого сканирования, дихотомии, «золотого сечения» и метода Фибоначчи.
2) С помощью разработанных программ исследовать на минимум заданные функции.
3) Оценить трудоемкость алгоритмов (по числу вызовов исследуемой функции для заданного интервала неопределенности).
Рекомендации.
1. Создать свою рабочую папку, в которую поместить разработанные программы.
2. Функции №1,2,3 исследовать методом прямого сканирования.
Содержание отчета
Отчет должен содержать программы, графики исследуемых функций, результаты расчетов, выводы.
Контрольные вопросы
1. Что такое интервал неопределенности?
2. Технология поиска экстремума изученными методами.
3. Область применения изученных методов.