Лекция: Гибридный квазиньютоновский алгоритм.

Заданы g: →R, x0:

for k=0, 1, 2, … do

Решить, необходим ли останов; если нет, то:

Построить локальную модель, описывающую поведение g вблизи xk и найти xN – приближенное решение модельной задачи.

а) решить, взять ли xk+1 = xN; если нет, то: б) выбрать xk+1, используя глобальную стратегию (здесь как можно реже прибегать к решению модельной задачи.

Критерии останова:

,

где typ x — типичное значение x; masheps — машинная точность определяемая с помощью алгоритма

masheps=1.0

while 1.0+masheps>1.0 do {masheps=masheps/2}.

Если производные не заданы, то можно использовать либо конечно-разностный метод, либо метод секущих (последний обычно медленнее)

,

или

,

если велико.

В методе секущих

,

Если hс=const — сходимость линейная, если hс=hck и {hck}→0, при k→∞, то сходимость сверхлинейная.

Собственно минимизация это решение уравнения f¢ (x) = 0 методом Ньютона с глобальной стратегией по условию while f(x+) ≥ f(xc).

Строим квадратичную модель

.

Экстремальная точка квадратичной модели совпадает с решением по методу Ньютона уравнения f¢ (x) = 0

.