- •Оглавление
- •Глава 1. Краткие основы работы в matlab
- •1.1. Интерфейс.
- •1.2. Редактирование м-файлов
- •1.3. Построение графиков
- •1.4. Построение поверхности
- •1.5. Операции с матрицами.
- •1.6. Нелинейные уравнения и системы
- •1.7. Интегрирование
- •1.8. Решение обыкновенных дифференциальных уравнений и систем.
- •1.9. Поиск экстремума функции одной переменной.
- •1.10. Поиск экстремума функции нескольких переменной.
- •Глава 2. Одномерная оптимизация с применением пакета matlab минимальный шаг по аргументу
- •Минимальное изменение функции
- •2.1. Метод сканирования
- •2.2. Метод чисел Фибоначчи
- •2.3. Метод локализации экстремума
- •2.4. Метод обратного половинного шага
- •2.5. Метод золотого сечения
- •Глава 3. Двухмерная оптимизация с применением пакета matlab
- •3.1. Метод сканирования
- •3.2. Метод Гаусса–Зейделя
- •3.3. Метод пробных движений
- •Соломатин Алексей Сергеевич Решение типовых задач одномерной и многомерной оптимизации с применением пакета matlab
- •125047, Москва, Миусская пл. 9.
2.5. Метод золотого сечения
В основе этого метода лежит правило геометрического отношения или золотого сечения:
или ,
где – длина всего отрезка;– длина его большей части;– длина его меньшей части.
Рис. 2.5. Графическая иллюстрация правила золотого сечения
В соответствии с этим правилом определяются точки исследуемого интервала, в которых необходимо производить вычисление функции .
Из рис. 2.5 следует, что:
.(1)
Тогда, подставляя в (1) соотношение (2) получим:
.(2)
Обозначив отношение и подставив его в (2), получим:
,(3)
откуда следует:
.(4)
Решение этого уравнения дает:
.(5)
Поскольку , то его значение принимается равным:
. (6)
Рис. 2.6. Графическая иллюстрация метода золотого сечения
На исследуемом интервале (рис. 2.6) определяются две точки X1 = Xmin + k²a и X2 = Xmin + ka, где а – длина интервала [Xmin, Xmax]. Находим значения функции в точках Xmin, X1, X2, Xmax. Если наименьшее значение R будет соответствовать точке X1, то новым интервалом поиска будет [Xmin, X2], и на этом интервале находится новая точка X3 = Xmin + k²a, где ka – длина интервала [Xmin, X2] Если наименьшее значение R будет в соответствовать точке X2, то новым интервалом поиска будет [X1, Xmax], и на этом интервале находится новая точка X4 = X1 + ka, где ka – длина интервала [X1, Xmax]. Затем процедура повторяется. Абсолютная ошибка в определении экстремума после s вычислений будет вычисляться по формуле:
.(7)
Далее приведен текст программы, позволяющий реализовать описанный выше алгоритм.
function[]=ZolotSechenie1D_170809();
function y=f(x)
y=(x+2).*(x-4);
end
disp('МЕТОД ПОИСКА МИНИМУМА ФУНКЦИИ МЕТОДОМ ЗОЛОТОГО СЕЧЕНИЯ');
disp('Применен для указанной функции: y=(x+2)*(x-4)');
disp('ВВОД ИСХОДНЫХ ДАННЫХ точность по аргументу, края диапазона поиска');
function [x,y,xleft1,xright1,nn]=ZolS1()
eps=input('точность=');
xleft=input('левый край поиска=');
xright=input('правый край поиска=');
xleft1=xleft; %возвращаемые значения
xright1=xright; %возвращаемые значения
k=(sqrt(5)-1)/2; %число К, показывающее отношения длин отрезков
x1=xleft+k*k*abs(xleft-xright);
x2=xleft+k*abs(xleft-xright);
z=0;
j=0;
nn=1;
disp('ВЫВОД ПРОМЕЖУТОЧНЫХ РЕЗУЛЬТАТОВ ПОШАГОВО ');
while abs(xleft-xright)>eps
R1=f(x1);
R2=f(x2);
if R1<R2 % если минимум в точке Х1
z=x1; % для возвращения значения минимума
j=R1; % для возвращения значения минимума
%для следующей итерации подготавливаем интервал с четырьмя точками по правилу золотого сечения вместо xleft,x1,x2
xright=x2;
x2=x1;
x1=xleft+k*k*abs(xleft-xright);
%возвращаемые значения
mas1x(nn)=x1;
mas1y(nn)=R1;
else %если минимум в точке Х2
z=x2;
j=R2;
%для следующей итерации подготавливаем интервал с четырьмя точками по правилу золотого сечения вместо x1,x2,xright
xleft=x1;
x1=x2;
x2=xleft+k*abs(xleft-xright);
%возвращаемые значения
mas1x(nn)=x2;
mas1y(nn)=R2;
end %конец if
%вывод на экран минимума функции и соответствующего аргумента соответствующего аргумента для выполнения итерации
string=strcat('шаг номер:',int2str(nn),' аргумент:',num2str(mas1x(nn)),' функция от него:',num2str(mas1y(nn)));
disp(string);
nn=nn+1;
end %конец while
%возвращаемые значения найденного минимума и возвращения значения
x=z;
y=j;
nn=nn-1;
end
%обращение к функции методом золотого сечения
[x,y,xleft1,xright1,nn]=ZolS1();
%выбор оформления вывода на экран
choiceTab=input('ВОПРОС выводить пошагово как таблицу? Да=1 нет=0 ');
choiceGraf=input('ВОПРОС выводить график? Да=1 нет=0 ');
%вывод таблицы
if choiceTab==1
disp('вывод результатов');
for i=1:nn
string=print(‘номер= %4i\tаргумент= %7.3f\tфункция= %7.3f’,i,mas1x(i),mas1y(i));
disp(string);
end
end
disp('НАЙДЕН МИНИМУМ')
sx=strcat('оптимальное значение аргумента=',num2str(x),' с точностью:',num2str(abs(mas1x(nn)-mas1x(nn-1))));
sy=strcat('минимум функции=',num2str(y),' с точностью:',num2str(abs(mas1y(nn)-mas1y(nn-1))));
sn=strcat('выполнено:',num2str(nn),' итераций');
disp(sx) % вывод на экран
disp(sy)
disp(sn)
% подготовка к построению графика
h=0.1;
x1=xleft1:h:xright1;
y1=f(x1);
plot(x1,y1,'k-');
grid on;
title('y=(x+2)(x-4)');
xlabel('X'); ylabel('Y');
text(x,y,’\leftarrow Minimum’);
zeroMas=x1*0;
hold on;
if choiceGraf==1
plot(mas1x,mas1y,’r.’);
legend(‘plot with minimal step’,’points by Gold method’,0);
else
legend(‘plot with minimal step’,0);
end
hold on;
plot(x1,zeroMas,’k-‘,zeroMas,y1,’k-‘);
end
После выполнения этой программы пользователь видит на экране соответствующий текст, вводит нужные значения и получает график:
МЕТОД ПОИСКА МИНИМУМА ФУНКЦИИ МЕТОДОМ ЗОЛОТОГО СЕЧЕНИЯ
Применен для указанной функции: y=(x+2)*(x-4)
ВВОД ИСХОДНЫХ ДАННЫХ точность по аргументу, края диапазона поиска
точность=0.1
левый край поиска=-10
правый край поиска=10
ВЫВОД ПРОМЕЖУТОЧНЫХ РЕЗУЛЬТАТОВ ПОШАГОВО
шаг номер:1 аргумент:5.2786 функция от него:-7.1486
шаг номер:2 аргумент:0.55728 функция от него:-7.1486
шаг номер:3 аргумент:-0.55728 функция от него:-8.804
шаг номер:4 аргумент:1.2461 функция от него:-8.804
часть вывода вырезана
шаг номер:9 аргумент:0.92089 функция от него:-8.9997
шаг номер:10 аргумент:1.0214 функция от него:-8.9997
шаг номер:11 аргумент:0.95928 функция от него:-8.9997
шаг номер:12 аргумент:0.99767 функция от него:-8.9997
ВОПРОС выводить пошагово как таблицу? Да=1 нет=0 1
ВОПРОС выводить график? Да=1 нет=0 1
вывод результатов
номер= 1 аргумент= 5.279 функция= -7.149
номер= 2 аргумент= 0.557 функция= -7.149
номер= 3 аргумент= -0.557 функция= -8.804
номер= 4 аргумент= 1.246 функция= -8.804
номер= 5 аргумент= 1.672 функция= -8.939
номер= 6 аргумент= 0.983 функция= -8.939
номер= 7 аргумент= 0.820 функция= -9.000
номер= 8 аргумент= 1.084 функция= -9.000
номер= 9 аргумент= 0.921 функция= -9.000
номер= 10 аргумент= 1.021 функция= -9.000
номер= 11 аргумент= 0.959 функция= -9.000
номер= 12 аргумент= 0.998 функция= -9.000
НАЙДЕН МИНИМУМ
оптимальное значение аргумента=0.98301 с точностью:0.038388
минимум функции=-8.9997 с точностью:0
выполнено:12 итераций
Рис. 2.7. Пример применения метода золотого сечения