Метод квадратичной интерполяции – экстраполяции

Алгоритм ЗС-1

Начальный этап

(1) Выбрать погрешность расчёта e=10-3¸10-7. Получить начальный интервал методом Свенна.

(2) Вычислить стартовые точки l1=a1+0,382L1, m1=a1+0,618L1 (следует отметить, что золотые числа следует вычислять точно)

(3) Принять k=1 – счётчик числа итераций

Основной этап

Шаг 1.Сократить ТИЛ рассмотрением 2-х ситуаций:

(1) Если f(l)<f(m),то

ak+1=ak

bk+1=mk

mk+1=lk

lk=ak+1+0,382Lk+1

иначе

ak+1=lk

bk+1=bk

lk+1=mk

mk=ak+1+0,618Lk+1

(2) Положить k=k+1, Lk+1=|bk+1-ak+1|

Шаг 2. Проверить критерий окончания поиска: если |ak+1-bk+1|£e - остановиться – минимум найден. Точнее фиксируем аппроксимирующий минимум как Метод квадратичной интерполяции – экстраполяции - student2.ru . Иначе вернуться на шаг 1.

Алгоритм ЗС-2

Начальный этап

(4) Выбрать погрешность расчёта e=10-3¸10-7. Получить начальный интервал методом Свенна.

(5) Вычислить стартовые точки l1=a1+0,382L1, m1=a1+0,618L1 (следует отметить, что золотые числа следует вычислять точно)

(6) Принять k=1 – счётчик числа итераций

Основной этап

Шаг 1. Взять очередную пробную точку x2=ak+bk-x1, симметричную исходной и сократить ТИЛ рассмотрением 4-х возможных ситуаций:

(1) Если (x1<x2) и (f(x1)<f(x2)) то b=x2;

(2) Если (x1<x2) и (f(x1)>=f(x2)) то a=x1;

(3) Если (x1>x2) и (f(x1)<f(x2)) a=x2;

(4) Если (x1>x2) и (f(x1)>=f(x2)) b=x1;

Увеличить счётчик числа итераций k=k+1

Шаг 2. Проверить критерий окончания поиска: если |ak+1-bk+1|£e - остановиться – минимум найден. Точнее фиксируем аппроксимирующий минимум как Метод квадратичной интерполяции – экстраполяции - student2.ru . Иначе вернуться на шаг 1.

Метод Фибоначчи

Метод Фибоначчи является процедурой линейного поиска минимума унимодальной функции f(x) на замкнутом интервале [a, b], отличающейся от процедуры золотого сечения тем, что очередная пробная точка делит интервал локализации в отношении двух последовательных чисел Фибоначчи. Последовательность чисел Фибоначчи задаётся условиями F0 = F1 = 1, Fk+1 = Fk + Fk-1, k = 1,2,... Начальными членами последовательности будут 1, 1, 2, 3, 5, 8, 13,... Стратегия поиска Фибоначчи требует заранее указать n - число вычислений минимизируемой функции и e - константу различимости двух значений f(x). Рассмотрим один из возможных вариантов метода.

Алгоритм Фибоначчи-1

Начальный этап

(1) Задать константу e, начальный интервал [a1, b1], длину конечного интервала Ln и определить число n так, чтобы выполнялось условие Fn > (b1 - a1)/Ln.

(2) Взять две пробные точки l1 = a1 + (Fn-2/Fn)(b1 - a1) и m1 = a1 + (Fn-1/Fn)(b1-a1). Положить k = 1.

Основной этап

Шаг 1. Сократить текущий интервал локализации:

(1) Если f(lk) < f(mk), то положить ak+1 = ak, bk+1 = mk,mk+1 =lk и вычислить новую точку lk+1 = ak+1 + (Fn-k-2/Fn-k)Lk+1, где Lk+1 = bk+1 - ak+1; перейти на шаг 2.

(2) Если f(lk)>> f(mk),то положить ak+1 =lk, bk+1 = bk, lk+1 = mk и вычислить mk+1 = ak+1 + (Fn-k-1/Fn-k) Lk+1.

Шаг 2. Проверить критерий окончания поиска:

(1) Заменить k на k+1. (2) Если k = n - 1, перейти на шаг 3, иначе - на шаг 1.

Шаг 3. Найти аппроксимирующий минимум х(*):

(1) Положить mk = lk + e.

(2) Если f(lk) > f(mk), то x(*) = (lk + bk)/2. В противном случае - x(*) = (ak + mk)/2.

Алгоритм Фибоначчи-2

Начальный этап

(1) Задать константу e, начальный интервал [a1, b1], длину конечного интервала Ln и определить число n так, чтобы выполнялось условие Fn > (b1 - a1)/Ln.

(2) Выбрать одну пробную точку Метод квадратичной интерполяции – экстраполяции - student2.ru . Положить

k = 1.

Основной этап

Шаг 1. Проверить критерий окончания поиска: если k=n, то остановиться и положить x*=x2.

Шаг 2. Сократить текущий интервал локализации рассмотрением 4-х ситуаций, аналогично методу золотого сечения-2.

Метод линейной интерполяции (метод секущих)

Метод секущих предлагает заменить вторую производную f ''(xk) в ньютоновской формуле её линейной аппроксимацией (f '(xk)-f '(xk-1))/(xk-xk-1).

Тем самым очередное приближение хk+1 к стационарной точке х* задаётся формулой вида

xk+1 = xk - f '(xk) * (xk - xk-1) / ( f '(xk) - f '(xk-1)).

Легко видеть, что хk+1 - точка пересечения с осью абсцисс секущей прямой, проходящей через точки хk и хk-1.

В отличие от метода Ньютона метод секущих гарантирует сходимость точек {xk} к стационарной точке х*, однако, сходимость метода достигается ценой потери быстродейсвия. Как правило, метод дихотомии оказывается эффективнее метода секущих, хотя последний и получен из более быстродействующей схемы.

Начальный этап. Пусть методом Свенна получен интервал неопределённости [a1,b1], границы которого удовлетворяют неравенству f'(a1)f '(b1) < 0. Задать e - погрешность вычисления минимума и принять k=1.

Основной этап

Шаг 1. Найти очередное приближение хk+1 к минимуму х* и проверить условие окончания поиска:

(1) xk+1 = bk - f '(bk)*(bk - ak)/(f '(bk) - f '(ak));

(2) если ½f '(xk+1)½ << e, то остановиться.

Шаг 2. Уменьшить интервал поиска минимума:

(1) если f '(xk+1) > 0, то ak+1 = ak, bk+1 = xk+1, в противном случае принять ak+1 = xk+1, bk+1 = bk;

(2) положить k = k + 1 и перейти на шаг 1.

Метод средней точки (метод Больцано)

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

Начальный этап. Для запуска метода необходимо:

(1) задать [a1,b1]- начальный интервал локализации минимума, на границах которого знаки производных различны, т.е. f'¢(a1)f'¢(b1)<0; e - малое положительное число;

(2) положить к=1 и перейти к основному этапу.

Основной этап

Шаг 1. Взять пробную точку хk в центре текущего интервала и проверить критерий окончания поиска: (1) xk = (ak + bk)/2; (2) если ½f'¢(xk)½ ≤ e и Lk= ½bk - ak½≤ e, то остановиться (хk = х* -аппроксимирующий минимум).

Шаг 2. Сократить текущий интервал:

(1) Если f ¢(xk) > 0, то положить ak+1 = ak и bk+1 =xk, в противном случае - ak+1 =xk, bk+1 =bk;

(2) заменить k на k+1 и вернуться на шаг 1.

Метод квадратичной интерполяции – экстраполяции

Данный метод относится к классу прямых методов, опирающихся на идею построения аппроксимирующего полинома второго порядка на основании информации о значениях функции в n+1 точке – узлах интерполяции.

Начальный этап

1. Выбрать произвольную точку x1ÎRn

2. Задаться величиной шага h=0.001

3. Определить погрешность

4. Положить счётчик числа итераций равным 1, а также b=x1

Основной этап

Шаг 1. Вычислить fi в 3-х точках: a, b и с – центральной (b) и двух соседних: a=b-h, c=b+h. Затем, по формуле

Метод квадратичной интерполяции – экстраполяции - student2.ru (1)

или

Метод квадратичной интерполяции – экстраполяции - student2.ru (2)

найти аппроксимирующий минимум d

Шаг 2. Проверить критерий близости 2-х точек b и d

Метод квадратичной интерполяции – экстраполяции - student2.ru и Метод квадратичной интерполяции – экстраполяции - student2.ru

Если оба условия выполняются – фиксируем аппроксимирующий минимум

Метод квадратичной интерполяции – экстраполяции - student2.ru

и останавливаемся. Если оба критерия не выполняются, полагаем b=d и возвращаемся на шаг 1.

Метод Пауэлла

Метод Пауэлла является одним из самых популярных методов. Эффективен как и рассмотренный ранее алгоритм квадратичной интерполяции – экстраполяции, если начальная точка x1Îd(x*).

Начальный этап

1. Выбрать ε1, ε2, h.

2. Взять 3 точки a, b, c на равных на равных интервалах. Предполагается, что сработал метод Свенна и получен интервал [a, b].

a=a;

c=b;

b=(a+c)/2;

Основной этап

1. Найти аппроксимирующий минимум на 1-й итерации по формуле:

Метод квадратичной интерполяции – экстраполяции - student2.ru

на последующих итерациях по формуле:

Метод квадратичной интерполяции – экстраполяции - student2.ru

2. Проверить критерии близости двух точек:

Метод квадратичной интерполяции – экстраполяции - student2.ru ; Метод квадратичной интерполяции – экстраполяции - student2.ru

Если он выполняется, принять Метод квадратичной интерполяции – экстраполяции - student2.ru и остановиться.

Если не выполняется, то из 2-х точек b и d выбрать «лучшую» - в которой наименьшее значение функции, обозначить её как b, а 2 соседние с ней – a и c. Далее рассмотреть 4 ситуации аналогично ЗС-2.

3. Положить k=k+1 и вернуться на шаг 1.

Метод Давидона

Начальный этап

1. Выбрать ε, x0, p, α1

2. Предполагается, что сработал метод Свенна и получен интервал [a, b].

Основной этап

1. Найти аппроксимирующий минимум, т.е. точку d по формулам:

Метод квадратичной интерполяции – экстраполяции - student2.ru

2. Проверить КОП: если y`r≤ ε, то остановиться, х=a+αrp. Иначе: сократить ТИЛ: если y`r <0, то [r,b], если y`r >0, то [a,r].

Положить k=k+1 и вернуться на шаг 1.

Методы многомерной минимизации

Здесь имеет смысл упомянуть о поиске минимума функции многих переменных по направлению, так как этом используется во многих методах описываемых далее. Поиск минимума по направлению производится с использованием одномерных методов, т.е. сначала многомерная функция сводится к одномерной функции зависящей от смещения по заданному направлению из заданной точки, а потом для неё вызывается один из методов одномерной минимизации:

Метод квадратичной интерполяции – экстраполяции - student2.ru

x – вектор от которого зависит функция

x0 – стартовая точка

p – направление

L – смещение по направлению

Метод Коши

Метод Коши относится к группе методов градиентного спуска. Градиентные методы – это методы, где на каждом шаге выбирается антиградиентное направление спуска.

Начальный этап

Выбрать x1, e, k.

Основной этап

Шаг 1

Метод квадратичной интерполяции – экстраполяции - student2.ru

Шаг 2

(1) Найти L как результат минимизации функции по направлению p.

(2) Метод квадратичной интерполяции – экстраполяции - student2.ru

Шаг 3

(1) Вычислить новое значение градиента

(2) Проверить КОП: если Метод квадратичной интерполяции – экстраполяции - student2.ru , то Метод квадратичной интерполяции – экстраполяции - student2.ru , иначе на Шаг 1.

Наши рекомендации