Поиск минимума функции многих переменных методом Нелдера - Мида
Курсовая работа, 16 Октября 2013, автор: пользователь скрыл имя
Описание работы
Впервые метод деформируемого многогранника был предложен Нелдером и Мидом. Они предложили метод поиска, оказавшийся весьма эффективным и легко осуществляемым на ЭВМ.
Чтобы можно было оценить стратегию Нелдера и Мида, кратко опишем симплексный поиск Спендли, Хекста и Химсворта, разработанный в связи со статистическим планированием эксперимента.
Содержание работы
Введение 3
1. Постановка задачи 5
2. Методика решения задачи 7
3. Алгоритм метода Нелдера–Мида. 8
4. Блок-схема 10
4.1 Блок-схема основной программы 10
4.2 Блок-схема процедуры calcMinimum 11
4.3 Блок-схема функции 12
5. Программа на языке Pascal 13
5.1 Основная программа 13
5.2 Unit 14
6. Результаты тестирования 18
Выводы 20
Литература 21
Файлы: 1 файл
курсовик.doc
— 169.00 Кб (Скачать файл)end;
{ вычисляем координаты цента тяжести}
for q:=1 to n do Point_H[q] := 0;
for i:=1 to n+1 do
begin
if i<>num_H then
for q:=1 to n do
Point_H[q] := Point_H[q]+(N_kub[i][q])/n;
end;
{ проверяем критерий останова }
len_max:=0;
for q:=1 to n do len_max := len_max+sqr(N_kub[1][q]-Point_
for j:=2 to n+1 do
begin
len:=0;
for q:=1 to n do len:=len+sqr(N_kub[j][q]-
if len>len_max then len_max := len;
end;
len:=0; for q:=1 to n do len:=len+sqr(e[q]);
if len_max < len then break;
{ выполняем отражение с a>0 }
for q:=1 to n do
Point_new[q] := Point_H[q] + a*(Point_H[q]-N_kub[num_H][q])
F_new := Formula(Point_new);
if F_new <= Fmin then
begin
{ выполняем растяжение}
for q:=1 to n do
Point_new2[q] := Point_H[q] + gamma*(Point_new[q]-N_kub[num_
F_new2 := Formula(Point_new2);
if F_new2 <= F_new then
begin
for q:=1 to n do N_kub[num_H][q] := Point_new2[q];
continue;
end
else
begin
for q:=1 to n do N_kub[num_H][q] := Point_new[q];
continue;
end;
end;
pr := 0;
for j:=1 to n+1 do
begin
if j<>num_L then
if (F_new<=Fmin) or (F_new>=Formula(N_kub[j])) then pr :=1;
end;
if pr = 0 then
begin
for q:=1 to n do N_kub[num_H][q] := Point_new[q];
continue;
end;
if F_new<Fmax then
begin
{ сжатие к основанию }
for q:=1 to n do
N_kub[num_H][q] := Point_H[q]+beta*(N_kub[num_H][
continue;
end
else
begin
for j:=1 to n+1 do
begin
if j<>num_L then { сжатие к лучшей вершине }
for q:=1 to n do
N_kub[j][q] := N_kub[num_L][q] + 0.5*(N_kub[j][q]-N_kub[num_L][
end;
continue;
end;
end;
end;
begin
end.
6. Результаты тестирования
Функция , точность 0.001
==Shag 1
x[1]=[3.00000, 4.00000], f(x[1])=4.000000
x[2]=[2.00000, 5.00000], f(x[2])=10.000000
x[3]=[3.00000, 6.00000], f(x[3])=16.000000
==Shag 2
x[1]=[3.00000, 4.00000], f(x[1])=4.000000
x[2]=[2.00000, 5.00000], f(x[2])=10.000000
x[3]=[2.00000, 3.00000], f(x[3])=2.000000
==Shag 3
x[1]=[3.00000, 4.00000], f(x[1])=4.000000
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[2.00000, 3.00000], f(x[3])=2.000000
==Shag 4
x[1]=[2.75000, 3.25000], f(x[1])=1.625000
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[2.00000, 3.00000], f(x[3])=2.000000
==Shag 5
x[1]=[2.75000, 3.25000], f(x[1])=1.625000
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[3.75000, 2.25000], f(x[3])=0.625000
==Shag 6
x[1]=[2.87500, 2.62500], f(x[1])=0.406250
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[3.37500, 2.12500], f(x[3])=0.156250
==Shag 7
x[1]=[2.93750, 2.31250], f(x[1])=0.101563
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[3.18750, 2.06250], f(x[3])=0.039063
==Shag 8
x[1]=[2.96875, 2.15625], f(x[1])=0.025391
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[3.09375, 2.03125], f(x[3])=0.009766
==Shag 9
x[1]=[2.98438, 2.07813], f(x[1])=0.006348
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[3.04688, 2.01563], f(x[3])=0.002441
==Shag 10
x[1]=[2.99219, 2.03906], f(x[1])=0.001587
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[3.02344, 2.00781], f(x[3])=0.000610
==Shag 11
x[1]=[2.99609, 2.01953], f(x[1])=0.000397
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[3.01172, 2.00391], f(x[3])=0.000153
==Shag 12
x[1]=[2.99805, 2.00977], f(x[1])=0.000099
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[3.00586, 2.00195], f(x[3])=0.000038
==Shag 13
x[1]=[2.99902, 2.00488], f(x[1])=0.000025
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[3.00293, 2.00098], f(x[3])=0.000010
==Shag 14
x[1]=[2.99951, 2.00244], f(x[1])=0.000006
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[3.00146, 2.00049], f(x[3])=0.000002
==Shag 15
x[1]=[2.99976, 2.00122], f(x[1])=0.000002
x[2]=[3.00000, 2.00000], f(x[2])=0.000000
x[3]=[3.00073, 2.00024], f(x[3])=0.000001
==============================
Результат:
Точка 1: Значение функции: 0.000002
[2.99976, 2.00122]
Точка 2: Значение функции: 0.000000
[3.00000, 2.00000]
Точка 3: Значение функции: 0.000001
[3.00073, 2.00024]
Выводы
Результаты тестирования показали, что метод Нелдера-Мида эффективно находит минимум функции с заданой точностью. При удачном выборе начальных приближений, минимум функции определяется за значительно меньшее количество итераций. Метод Нелдера–Мида имеет тот недостаток, что для сильно овражных функций может происходить вырождение симплекса, особенно при числе переменных N > 2.
Литература
- Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988
- Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука, 1987
- Васильков Ю.В., Василькова Н.Н. Компьютерные технологии вычислений в математическом моделировании. М.: Финансы и статистика, 1999.