Метод касательных

При решении задачи оптимизации применяются также методы, использующие производные различных порядков (непрямые методы). Во многих случаях эти методы обеспечивают большую скорость сходимости, чем прямые. Также применяют и смешанную стратегию: на начальном этапе минимизации применяют более трудоемкие методы, а на завершающем этапе – более точные и быстрые.

Пусть f(x) - дифференцируемая выпуклая функция на отрезке [a,b], причем . Геометрически метод касательных заключается в построении последовательности точек , являющимися абсциссами точек пересечения касательных к графику функции y=f(x), проводимых в граничных точках отрезков [a_i,b_i], сходящихся к минимуму. При этом очередная касательная проводится в точке графика, соответствующей точке пересечения касательных.

Алгоритм метода касательных состоит в следующем:

1. Положим a₀=a, b₀=b, i=0.

2. Вычислим абсциссу точки пересечения касательных:

3. Если , положим a_i+1=a_i, b_i+1=x_i и перейдем к п.5, в противном случае к п.4.

4. Положим a_i+1= x_i, b_i+1=b_i

5. Если , то xmin=x_i – точка минимума найдена, иначе i=i+1 и осуществляется переход к п.2 (следующая итерация).

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

· xmin=a если и ;

· xmin=b если и ;

· xmin=a если ;

· xmin=b если .

Таким образом, рекуррентная формула метода:

Условие окончания поиска минимума:

Пример 1.6.5-1. Пусть требуется найти минимум функции f(x) = x² – sin(x) на отрезке [0;π/2] с точностью ε=0.01.

функция выпуклая

минимум есть

n	an	bn	xn	f(xn)	f’(xn)
		1.50796	0.80374	-0.07395	0.91346
		0.80374	0.42235	-0.2315	-0.06744
	0.42235	0.60374	0.61688	-0.19795	0.41806
	0.42235	0.61688	0.52071	-0.22635	0.17395
	0.42235	0.52071	0.47182	-0.23189	0.05290
	0.42235	0.47182	0.47115	-0.23245	-0.00736

Точность достигнута. xmin=0.47115, f(xmin)= -0.23245.

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