Приложение 3. Метод Ньютона

Метод Ньютона минимизации функции является обобщением известного метода Ньютона отыскания корня уравнения f '(x) = 0, где f(x) - скалярная функция скалярного аргумента х. Минимизация f(x) основывается на использовании квадратичной аппроксимации функции f(x) в точке x_k:

F(x) = f(x_k) + f '(x_k)(x - x_k) + f ''(x_k)(x - x_k)²* 1/2

В качестве приближения х_k+1к минимуму х* берется точка, в которой производная F'(x) равна нулю, т.е.f'(x_k) + f ''(x_k)(x_k+1 -x_k) = 0.

Таким образом, x_k+1= x_k- f '(x_k)/f ''(x_k).

Итерационный процесс строит последовательность точек {x_k}, которая при определенных условиях квадратично сходится к некоторой стационарной точке х* функции f(x), т.е. к точке, в которой f ' (x*) = 0. Процесс останавливается, когдаx_k+1- x_k≤иf '(x_k)≤, где> 0 - заранее заданное малое число.

Существенными недостатками метода Ньютона являются: 1) сложность задания начального приближения х₁в малой окрестности искомого минимума х*; 2) необходимость вычисления вторых производных минимизируемой функции.

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

Метод секущих предлагает заменить вторую производную f ''(x_k) в ньютоновской формуле её линейной аппроксимацией (f '(x_k)-f '(x_k-))/(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. Задать- погрешность вычисления минимума и принять 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)≤, то остановиться.

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

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

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

Приложение 5. Метод кубической интерполяции для одномерной минимизации

Суть алгоритма заключается в том, что на каждой итерации функция f(x) аппроксимируется кубическим полиномом F(x), точка минимума x^(*)которого берётся в качестве текущего приближения к искомому минимуму х*. Алгоритм предполагает вычисления в каждой очередной точке значений функции f(x) и её производной f '(x).

Начальный этап. Задать, х₁, h₁- параметры метода, имеющие общепринятый смысл. Методом Свенна установить начальный интервал [a, b]:

(1) Изменить направление поиска h₁= -h₁, если f '(x₁) > 0.

(2) Вычислять f_kв точках x_k+1= x_k+ h_kпри h_k= 2h_k-1, k=2,3,...m-1 до тех пор, пока не продвинемся в точку x_m, такую, что f '(x_m)f '(x_m-1) < 0.

(3) Если x _m-1< x_m, то положить a = x_m-1, b = x_m, иначе - a = x_m, b = x_m-1.

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

Шаг 1. Найти аппроксимирующий минимум:

(1) Вычислить параметр = (z + w - f '(a))/(f '(b) - f '(a) + 2w),

где z = f '(a) + f '(b) + 3(f(a) - f(b)) / ( b - a), w = (z² - f '(a)f '(b))^1/2 .

a + (b - a), если 0≤  < 1,

(2) Принять аппроксимирующий минимум

x^(*)= a, если< 0, и

x^(*)= b, если> 1.

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

Если f '(x)<или x = a, или x = b, поиск окончить. Иначе вернуться на шаг 1, используя новый интервал [a, x], если f '(x) > 0, либо интервал [x, b], если f '(x) < 0.