mo-crib-03

Количественной характеристикой качества решаемой задачи является число

понятно что μ >=1 если μ примерно равно 1 то говорят что задача хорошо обусловлена, т.е ее линии уровня представляют собой концентрические окружности. Если μ >>1 то линии уровня сильно вытянулы в одних направлениях и слабо в других.

13. метод дихотомии метод свена

2) метод свена (медод грубого поиска или метод удвоения интервалов) предназначен для первоначального сужения исходного интервала перед применением более сложных методов поиска.

15. методы оценивания с помощью квадратичной аппроксимации.

1)метод однократного оценивания: f(x)- унимодальная непрерывная достаточно гладкая, тогда ее в ограниченном интервале можно аппроксимировать некоторой квадратичной функций а затем искать минимум этой квадратичной функции.

Есть 3 точки: x1, x2, x3 соответственно f1, f2, f3 потребуем чтобы в этих точках значение

ϕ(x) совпадало с f(x)

ϕ(x) = a0 + a1 (x − x1 )+ a2 (x − x1 )(x − x2 )

(x1 ) = ϕ(x1 ) = f 1 = a0 ; a0 = f1f

б) переназначаем х1 х2 х3 в естественном порядке и (если надо заного вычисляем f1 f2 f3). Далее выбираем min f = min{ f1 , f2 , f3} и соответствующий xmin = arg(min f ) затем по методу однократного оценивания проводим квадратичную аппроксимацию х1 х2 х3 и

далеко перд х1 и тогда ее невозможно окружить 2-мя точками, тогда надо применить

методы квадратичной аппроксимации обладают суперлинейной скоростью сходимости.

16) метод средней точки метод касательных метод секущих 1) метод деления интервала пополам ( метод средней точки):

по знаку f '(xk ) определяем неперспективную половину,

в оставшейся находим середину и вычисляем f '(xk +1 ) . Условие остановки: | f '(xk )|£ ε

2) метод касательных (метод Ньютона): Решение гарантировано если f(x) строго выпукла

3) метод секущих: более универсальны (не надо искать 2 производную) работает в том числе и на невыпуклых функциях, но для гарантии решения требует чтобы для

невыпуклых функций знаки производных были различны в очередных 2-х точках f '(x1 )× f '(x2 ) < 0

Запишем уравнение для секущей:

очередную секущую через точки 3 и 1 если f '(x2 ) > 0 то очередную хорду проводим через 3 и 4.

условие остановки: | f '(xk )|< ε

17) метод поиска по симплексу( S 2 метод ) 1962 год , Нелдер и Мид 1965.

Симплекс – это многогранник в n-мерном пространстве, образованный n+1 вершинами, стоящих на равном расстоянии друг от друга.

Процедура отражения любой вершины симплекса, т.е перенос некоторой вершины симплекса по прямой, проходящей через эту точку и через центр тяжести остальных вершин на некоторое расстояние(т.е используя свойство симплекса что на любой его гране можно построить новый симплекс. xn1-нормальное отражение, xn2-растяжение симплекса Применительно к k-ой итерации

1) если надо, переобозначаем вершины x(0 ) (k ), x(1) (k ),..., x(n ) (k )так чтобы оно

удовлетворяло

f (x(0) (k ))≤ f (x(1) (k ))≤ ... ≤ f (x(n ) (k )), при этом n-

ая точка является худшей точкой и отражению подвергается всегда худшая точка.

2) Найдем центр тяжести остальных вершин

1 n−1

x(c ) (k ) = ∑ x(i ) (k ) n i=0

3)Вычислим пробную точку для нормального отображения u (k ) = x (n ) (k )+ (1 + Q)(x (c ) (k ) − x (n ) (k )), Q = α = 1

Случай α : f (x (0 ) (k ))≤ f (u (k )) ≤ f (x (n−1) (k ))=> именно u (k ) вершиной заменяем x (n ) (k ) и уходим на (k+1) итерацию

Случай β : если f (u (k )) < f (x(0) (k )) то направление перемещения в u (k ) перспективно

итогда следует проверить случай растяжения симплекса в этом направлении

v(k ) = x (n ) (k ) + (1 + Q )(x (c ) (k ) − x (n ) (k )), Q = β = 2 если f (v (k )) < f (u (k )) то u (k )

единичную длину.

Если некоторая вершина не исключается к М-ой итерации то текущий симплекс заменяется новым с вершиной x (0) , соответсвующей наилучшей в текущем симплексе.

M =1.65n + 0.05n2

18) метод поиска Ху-ка Дживса.

Если из x (k ) выходить и двигаться в направлении d = (x (k ) сходиться быстрее к точке x *.

Первая процедура: исследующий поиск. x (t ) - текущая точка (базовая) выбираются

фиксируются значения остальных координат, если один из них привел к успеху т.е уменьшению функции, то фиксируемся в этой точке и уже из нее делаем шаги вдоль следующей координаты ± x2 в результате находиться точка x(t+1) . Эта процедура обеспечивает локальный поиск и движению к дну оырагов.

Вторая процедура: поизк по образцу x (k +1) = x(k ) + (x (k ) − x (k −1) ), x(k ) и x(k −1) - базовые точки, производиться движение вдоль оврагов.

Алгоритм:

Подготовительный этап: 1. x (0) , x j j = 1, n,α > 1 ε > 0

Шаг 2: в последней из найденных базовой точке x (k −1) производим исследующий поиск (в начале это точка x (0) ), если он приводит к успеху то последнюю из успешно найденных точек обозначаем x (k ) и переходим к 4.

Шаг 3: если || x ||≤ ε то остановка последняя из базовых точек является

Шаг 4: выполняем поиск по образцу x (k +1)врем1 = x (k ) + (x (k ) − x (k −1) ) затем проводим в найденной точке исследующий поиск и получаем xврем(k +1)2 и выбираем наилучшую

)], если f (x(k +1) )< f (x)(k ) , то шаг 4 считаем удачным и

уходим на его начало, при этом проводим переобозначение

точек x(k +1) − > x(k ); x(k ) − > x(k −1) , иначе остаемся в последней базовой точке x(k ) н

обозначаем ее как x(k −1) и уходим на шаг 3.

19. метод сопряженных направлений Пауэла.

Предназначен для минимизации функций: f (x) = a + bx + 0.5xT Cx- > min не боее чем за n итераций (работает в рациональных дробях)

На первых (n-1) итерациях находится совокупность направлений в пространстве

d (1) , d (2 ),..., d (n−1) и на n-ой итерации выполняется последующая минимизация в этих направлениях. Фактически переходим в новую систему координат, оси которой совпадают с осями квадратичной функции Cn×n является диагональной,

d (i ) и d ( j ) называются сопряженными или сопряженными по отношению к матрице С,

или С-ортогональными, если выполняется: d (i ) T · C · d ( j ) = 0 i, j = 1, n i ¹ j

Работает для любых направлений. Докажем что (y(2) - y(1) ) является сопряженным с d

Это свойство для квадратичной функции называется построением параллельног оподпространства.

x (1), d , f (x (1) + λd ), y(1)

(21) ( (2) + λ ) (2 )

x , d , f x d , y

df dx = (b T + x T C )d = 0 dx dλ

(bT + y(2 ) T C )d = 0 - (bT + y(1) T C )d = 0

= (y(2) - y(1) )Cd = 0

Обычно выходят из одной начальной точки Алгоритм:

1. задаем начальную точку x(0) и набор линейно независимых ортогональных направлений S (1) , S (2 ),..., S (n )

2. строим текущюю линейку направлений поиска(в начале S (1) , S (2 ),..., S (n ) ), затем из последней точки эксперимента делаем (n+1) последовательных шагов минимизации функции в направлениях S (n ), S (1), S (2 ),..., S (n ) и обозначаем точки

минимизации x(1), x(2),.., x(n+1) 3. определяем новое сопряженное

направление d (1) = x(n+1) - x(1)

4.формируем очередную линейку направления поиска S (1) , S (2 ),..., S (n ) и в конец дописываем очередное сопряженное направление и выбрасываем

первое S (2),..., S (n ) , d (1) и уходим на шаг 2

со 2-ой итерации выполняем (n+1) шагов последовательного поиска в направлениях d (1) , S (2),..., S (n ), d (1) в результате находим d (2) ,сопряженное с d (1) , после (n-1) итерации алгоритма получаем S (n ) , d (1) , d (2) ,..., d (n−1) , и теперь рассмотрим n задач последовательной минимизации, в результате получим решение задачи.

Сходимость – суперлинейная.