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

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

(1) Задать константу e, начальный интервал [a₁, b₁], длину конечного интервала L_n и определить число n так, чтобы выполнялось условие F_n > (b₁ - a₁)/L_n.

(2) Выбрать одну пробную точку . Положить

k = 1.

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

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

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

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

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

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

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

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

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

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

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

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

(1) x_k+1 = b_k - f '(b_k)*(b_k - a_k)/(f '(b_k) - f '(a_k));

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2015-07-15