3.2. Метод Гаусса–Зейделя
Движение к оптимуму происходит поочередно по каждой из осей до нахождения частного экстремума (рис. 3.3). После нахождения частного экстремума по одной из осей начинается поиск экстремума по другой оси до частного минимума при условии, что значение первой переменной равно найденному минимуму (максимуму) на первой оси. И так поочередно. Процесс последовательно продолжается до тех пор, пока не будет достигнута заданная точность локализации экстремума, т. е. если шаг по каждой из осей приводит к возрастанию (уменьшению) функции, а величина шага меньше или равна заданной точности поиска, то расчет закончен.
Рис. 3.3. Путь поиска экстремума методом поочерёдного изменения переменных
Далее приведен текст программы, позволяющий реализовать описанный выше алгоритм.
Function[]=GaussZeidel2D_170809();
function z=fz_xy2(x,y);
nx=length(x);
ny=length(y);
for i=1:nx
for j=1:ny
z(i,j)=-sqrt(256-(x(i))^2-(y(j))^2);
end
end
end
disp('ДВУМЕРНЫЙ ПОИСК МИНИМУМА ФУНКЦИИ ');
disp('С ИСПОЛЬЗОВАНИЕМ МЕТОДА ГАУССА–ЗЕЙДЕЛЯ');
disp('применен для указанной функции: z(i,j)=-sqrt(256-(x(i))^2-(y(j))^2);
disp('ВВОД ИСХОДНЫХ ДАННЫХ точность по аргументу, края диапазона поиска');
function[x,z,masx,masz]=scanx1(xleft,xright,h,y);
%создание массива точек
n=ceil(abs((xright-xleft)/h)); % определяем число шагов
% функция ceil округляет число в сторону плюс бесконечности
masx(1)=xleft;
masz(1)=fz_xy2(xleft,y);
for i=2:n
masx(i)=masx(i-1)+h;
masz(i)=fz_xy2(masx(i),y);
end
% поиск минимума
min=masz(1); % стандартный алгоритм поиска минимума
num=1;
for i=2:n
if masz(i)<min
min=masz(i);
num=i;
end
end
%возвращаемые значения (минимум)
x=masx(num);
z=masz(num);
end
function[y,z,masy,masz]=scany1(yleft,yright,hy,x);
%создание массива точек
n=ceil(abs((yright-yleft)/hy));
masy(1)=yleft;
masz(1)=fz_xy2(x,yleft);
for i=2:n
masy(i)=masy(i-1)+hy;
masz(i)=fz_xy2(x,masy(i));
end
% поиск минимума
min=masz(1); % стандартный алгоритм поиска минимума
num=1;
for i=2:n
if masz(i)<min
min=masz(i);
num=i;
end
end
%возвращаемые значения (минимум)
y=masy(num);
z=masz(num);
end
%метод сканирования 2-мерный
function[x,y,z,xleft,xright,yleft,yright,xn]=scan2();
xleft=input('введите левую границу диапазона X поиска=');
xright=input('введите правую границу диапазона X поиска=');
hx=input('введите допустимую погрешность X=');
yleft=input('введите левую границу диапазона Y поиска=');
yright=input('введите правую границу диапазона Y поиска=');
hy=input('введите допустимую погрешность Y=');
eps=input('введите минимальное изменение функции (можно ноль):');
choiceTab=input('ВОПРОС выводить пошагово как таблицу? Да=1 нет=0 ');
%создание массива точек
xn=ceil(abs((xright-xleft)/hx)); % определяем число шагов
%объявляем переменные для возвращаемых значений
x=xleft;
y=yleft;
z=-1;
disp('ВЫВОД ПРОМЕЖУТОЧНЫХ РЕЗУЛЬТАТОВ ПОШАГОВО ');
for i=1:xn
%обращение к функции сканирования
[x,z]=scanx1(xleft,xright,hx,y); % по х
%вывод таблицы
if choiceTab==1
string=print(‘номер= %4i\tаргумент x= %7.3f\tаргумент y= %7.3f\tфункция= %7.3f\tпоиск по х’,i,x,y,z);
disp(string);
end
zx=z;
[y,z]=scany1(yleft,yright,hy,x); % по у
%вывод таблицы
if choiceTab==1
string=print(‘номер= %4i\tаргумент x= %7.3f\tаргумент y= %7.3f\tфункция= %7.3f\tпоиск по y’,i,x,y,z);
disp(string);
end
zy=z;
dz(i)=abs(zx-zy);
if dz(i)<eps
disp(‘dz<eps’);
break;
end
end
end
%обращение к функции сканирования
[x,y,z,xleft,xright,yleft,yright,xn]=scan2();
%выбор оформления вывода на экран
choiceGraf=input('ВОПРОС выводить трехмерный график? Да=1 нет=0 ');
% подготовка к выводу текста
% num2str преобразует число в строку символов
disp('НАЙДЕН МИНИМУМ');
sxy=strcat('оптимальные значения аргументов: х=',num2str(x),' у=',num2str(y));
sz=strcat('минимум функции=',num2str(z));
disp(sxy) % вывод на экран
disp(sz)
%подготовка данных для графика
if choiceGraf==1
hx=(xright-xleft)/xn;
hy=(yright-yleft)/xn;
% подготовка к построению графика
masx=xleft:hx:xright;
masy=yleft:hy:yright;
masz=fz_xy2(masx,masy);
surf(masx,masy,masz);
grid on;
title(‘z=-sqrt(256-x.^2-y.^2)’);
xlabel(‘X’);
ylabel(‘Y’);
zlabel(‘Z’);
smin=strcat(‘\leftarrow Minimum (‘,num2str(x),’,’,num2str(y),’,’,num2str(z),’)’);
text(x,y,z,smin);
zeroMas=masx*0;
hold on;
%surf(zeroMas,zeroMas,masz); % построены оси
%surf(zeroMas,masy,zeroMas); % построены оси
%surf(masx,zeroMas,zeroMas); % построены оси
legend(‘z(i,j)=-sqrt(256-x(i)*x(i)-y(j)*y(j))’,0);
end
end
После выполнения этой программы пользователь видит на экране соответствующий текст, вводит нужные значения и получает график:
ДВУМЕРНЫЙ ПОИСК МИНИМУМА ФУНКЦИИ
С ИСПОЛЬЗОВАНИЕМ МЕТОДА ГАУССА–ЗЕЙДЕЛЯ
Применен для указанной функции: z(i,j)=-sqrt(256-(x(i))^2-(y(j))^2)
ВВОД ИСХОДНЫХ ДАННЫХ точность по аргументу, края диапазона поиска
введите левую границу диапазона X поиска=-10
введите правую границу диапазона X поиска=10
введите допустимую погрешность X=.5
введите левую границу диапазона Y поиска=-10
введите правую границу диапазона Y поиска=10
введите допустимую погрешность Y=.5
введите минимальное изменение функции (можно ноль):.1
ВОПРОС выводить пошагово как таблицу? Да=1 нет=0 1
ВЫВОД ПРОМЕЖУТОЧНЫХ РЕЗУЛЬТАТОВ ПОШАГОВО
номер= 1 аргумент x= 0.000 аргумент y=-10.000 функция=-12.490 поиск по х
номер= 1 аргумент x= 0.000 аргумент y= 0.000 функция=-16.000 поиск по y
номер= 2 аргумент x= 0.000 аргумент y= 0.000 функция=-16.000 поиск по х
номер= 2 аргумент x= 0.000 аргумент y= 0.000 функция=-16.000 поиск по y
dz<eps
ВОПРОС выводить трехмерный график? Да=1 нет=0 1
НАЙДЕН МИНИМУМ
оптимальные значения аргументов: х=0 у=0
минимум функции=-16
Рис. 3.4. Пример применения метода Гаусса–Зейделя