 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Метод Гауса-Зайделя (покоординатного поиска)
1). Для некоторого начального значения X (0) = (X 1(0), X 2(0)… Xn (0)) фиксируют все координаты вектора X кроме одной (для определённости X1) и производится поиск максимума функции одной переменной с помощью одного из методов, рассмотренных в разделе 2.
0 (X1) = ¦0 (X1, X2(0),…, Xn(0)) →max.
Очевидно, что в процессе такой оптимизации будет меняться только одна переменная X1 , в результате получаем точку
X01 = (X10(1), X2(0), Xn(0)), где X10(1) = arg max 0 (X1)
 |
Рис. 3.5
2). Фиксируя в точке X01 все координаты X кроме второй, повторяют поиск максимума функции по X2. И, так до последней составляющей Xn. Цикл алгоритма завершается после n кратной операции одномерной оптимизации вдоль каждой из координат, после чего его повторяют, получая точки Xi0(2), в каждой из которых значение ¦0 не меньше предыдущего.
На рис. 3.5. представлена геометрическая интерпретация метода Гауса-Зайделя для случая функции двух переменных f (X) = f (X1, X2).
Расчёт заканчивается, когда |DXi(N)| < 
, или D¦0 (N)< e, где 
– номер цикла поиска.
DXi(N)= Xi(N)- Xi(N-1);
Df0(N)= f0(N)- f0(N-1);
Пример: Выполнить первый цикл поиска максимума функции:
¦0(X1, X2) = - X12 - X1X2 – X22 - 3X2 ® max, X1(0) = X2(0) = -1,
т.е. X(0)= 
.
Фиксируем X2 = -1 и, подставляя это значение в целевую функцию, получаем
0(X1) = - X12 + X1 – 1 + 3 = -X12 + X1 + 2 ® 
Используем необходимые условия max функции одной переменной
Получаем точку 
=[0,5; -1].
Фиксируем 
=0,5 и, подставляя это значение в целевую функцию, получаем:
.
После первого цикла поиска получаем точку:
(1)=[0,5; -1,75],
Проверим, увеличилось ли в результате значение целевой функции
f0 [ 
(1)]=-0,25+0,5*1,75-(-1,75)2+3*1,75≈2,8 > f0 [X(0)] = 0,
значит первый цикл вычислений сделан правильно.
В случае так называемых овражных функций (рис. 3.6), возможна остановка алгоритма в точках, далеких от действительного максимума, т.к. направления поиска в данном методе жёстко фиксированы вдоль осей координат и совершенно не учитывают характер функции ¦0(
).
 |
Рис. 3. 6
Допустим, что после N -го цикла поиска мы попали в точку X(N) (см. рис. 3.6.). Любое из дальнейших возможных направлений поиска, указанных на рис. стрелками, очевидно приведет к уменьшению значения целевой функции. Таким образом, точка X(N) будет признана max исследуемой целевой функции, хотя на самом деле max находится в точке М.
Поиск по сайту: