Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


Поиск по правильному симплексу




Поиск минимума целевой функции f(x) по данному методу основан на выборе в качестве пробных точек вершин правильного симплекса. Напомним, что правильным симплексом в En называется множество из n+1 равноудаленных друг от друга точек - вершин симплекса. Так, в E2 правильным симплексом является равносторонний треугольник, в E3 – тетраэдр.

Из аналитической геометрии известно, что если X0– одна из вершин правильного симплекса в En, то координаты остальных вершин X1,…, Xn находятся по формулам

(2.4) где d1= , d2= , t - длина ребра.

По известному симплексу можно построить новый симплекс путем отражения какой-либо вершины симметрично относительно центра тяжести Xс остальных вершин симплекса. Новая и старая вершины k и Xk связаны соотношением

= , = . (2.5)

В результате получается новый правильный симплекс с тем же ребром и вершинами

k=2 Xс - Xk, Xj, j=0,…,n, j¹k.

На рис.1 представлена иллюстрация описанной операции отражения в пространстве E2.

Рис. 1. Построение нового симплекса в Е2 отражением точки X2:

а - начальный симплекс X0, X1, X2; б - новый симплекс X0, X1, ;

центр отражения - точка Xс=(X0+X1)/2.

 

На каждой итерации поиска сравниваются значения функции f(x) в вершинах симплекса и выполняется описанная процедура отражения для той вершины, в которой f(x) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. Иначе выполняют ещё одну попытку отражения для вершины со следующим по величине значением f(x). Если и она не приводит к уменьшению функции, то сокращают длину ребра и строят новый симплекс с этим ребром. При этом в качестве базовой выбирают ту вершину X0 старого симплекса, в которой функция принимает наименьшее значение. Поиск точки минимума X* заканчивают, когда либо ребро симплекса, либо разность между значениями функции в вершинах симплекса становятся достаточно малыми. Опишем один из вариантов алгоритма этого метода.

Шаг 0. Задать параметр точности e, выбрать базовую точку X0 и длину ребра t, построить по формулам (2.4) начальный симплекс и вычислить f(X0).

Шаг 1. Вычислить значения функции f(X) в вершинах симплекса X1,…, Xn.

Шаг 2. Упорядочить вершины симплекса X0,…,Хn так,чтобыf(X0)£…£f(Xn).

Шаг 3. Проверить условие достижения точности

Если оно выполняется, то перейти к шагу 7, иначе – к шагу 4.

Шаг 4. Найти по формуле (4) центр тяжести Xc вершин X0,X1,…,Xn-1и выполнить отражение вершины Xn: n=2Xc - Xn.Если f( n) < f(Xn), то положить Xn= n и перейти к шагу 2, иначе – к шагу 5.

Шаг 5. Найти центр тяжести Xc вершин X0,X1,…,Xn-1,Xn и выполнить отражение вершины Xn-1: n-1 =2Xc - Xn-1.Если f( n-1)<f(Xn-1), то положить Xn-1= n-1 и перейти к шагу 2, иначе – к шагу 6

Шаг 6. Построить новый правильный симплекс с вдвое меньшим ребром, считая базовой вершину X0, а остальные n вершин находя по формуле Xj=(Xj+ X0)/2, j=1,…,n и перейти к шагу 1.

Шаг 7. Завершить вычисления, положив X*= X0, f *= f(X0).

 

 





Поделиться с друзьями:


Дата добавления: 2016-11-18; Мы поможем в написании ваших работ!; просмотров: 1056 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Студенческая общага - это место, где меня научили готовить 20 блюд из макарон и 40 из доширака. А майонез - это вообще десерт. © Неизвестно
==> читать все изречения...

4419 - | 4313 -


© 2015-2026 lektsii.org - Контакты - Последнее добавление

Ген: 0.01 с.