АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Метод Гауса-Зайделя (покоординатного поиска)

Читайте также:
  1. F. Метод, основанный на использовании свойства монотонности показательной функции .
  2. FAST (Методика быстрого анализа решения)
  3. I этап Подготовка к развитию грудобрюшного типа дыхания по традиционной методике
  4. I. 2.1. Графический метод решения задачи ЛП
  5. I. 3.2. Двойственный симплекс-метод.
  6. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  7. I. Метод рассмотрения остатков от деления.
  8. I. Методические основы
  9. I. Методические основы оценки эффективности инвестиционных проектов
  10. I. Организационно-методический раздел
  11. I. Предмет и метод теоретической экономики
  12. I. Что изучает экономика. Предмет и метод экономики.

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)| < , или 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 находится в точке М.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)