Минимизируемая функция F(x) на отрезке [a,b].

МЕТОД ЛОМАНЫХ.

Постановка задачи

Минимизируемая функция F(x) на отрезке [a,b].

Требуется найти минимум F*(x) на отрезке [a,b].

Математическое обоснование

Функция F(x) удовлетворяет условию Липшица на отрезке [a,b], если существует постоянная L>0 такая, что

|F(x1)-F(x2)|<=L|x1-x2|, где x1,x2 из [a,b]

Постоянную L называют постоянной Липшица функции F(x) на отрезке [a,b].

Для вычисления минимума функции вводится константа Липшица L=DF/Dx=tga.

1. Находим константу Липшица:

L=tga=max{DF/e}, где e-заданная точность.

2.Проверяем на точность:

Если |b-a|<e, то выход из цикла, иначе переходим к п.3

3.Строим касательные на концах отрезка [a, b]:

a) Для точки a строим касательную y1 = -L(x-a)+f(a)

b) Для точки b строим касательную y2 = L(x-b)+f(b).

4.Находим точку пересечения касательных:

Y1=y2,

-L(x-a)+f(a)= L(x-b)+f(b),

x0 = (a+b)/2 + (f(a)-f(b))/2L.

5.В точке с координатами (x0,F(x0)) составляем еще две касательных:

a) y3 = L(x-x0)+f(x0)

b) y4 = -L(x-x0)+f(x0).

6.Находим точки пересечения прямых y1 и y3:

y1=y3,

-L(x-a)+f(a)= L(x-x0)+f(x0),

x1 = (a+x0)/2 + (f(a) – f(x0))/2L;

7. Находим точки пересечения прямых y2 и y4:

Y2=y4,

L(x-b)+f(b)= -L(x-x0)+f(x0),

x2 = (x0+b)/2 + (f(x0) – f(b))/2L.

8.Находим значение функции в точках x1 и x2:

a) Если F(x1) < F(x2), то b = x2,

x0 = x1;

b) Если F(x1)>F(x2), то a = x1,

x0 = x2.

9.Переходим к пункту 2.

Графическая иллюстрация метода

1)Находим x0,x1,x2.

F(x)

F(x₁)

F(x₂)

0 x

a x₁ x₀ x₂ b

2) Сравниваем значения F(x1), F(x2).

F(x)

F(x₁)

F(x₂)

0 x

a x₁ x₀ x₂ b

3) Если |a-b|<e, то находим F*=F((a+b)/2), иначе находим x1,x2 и переходим к п.2.

Структурная схема

M=F(i)/e

T F

T

	x0 = (a+b)/2 + (f(a)–f(b))/2L

F

x2 = (x0+b)/2 + (f(x0) - f(b))/2L

T F

a=x1

T F

Анализ

Метод ломанных невозможно реализовать без знания постоянной L. Следует заметить, что использование завышенной оценки L ухудшает скорость сходимости метода ломанных, приводит к излишне большому количеству вычислений значений минимизируемой функции. Если же пользоваться заниженной оценкой для L, то метод может привести к неправильному определению приближения минимального значения.

МЕТОД ПАРАБОЛ.

Постановка задачи

Дано: унимодальная функция F(x) на отрезке [a,b].

Найти: F*(x)=min{F(x)} при x из [a,b].

Математическое обоснование

1.Находим h-шаг:

h>0

2h<=b-a, откуда h<=(b-a)/2

2.Находим значения точек:

x1=a,

x2=a+h,

x3=a+2h.

3.Проходим отрезок [a, b] до тех пор пока не найдем выпуклую комбинацию трех точек:

F(x1)>F(x2)<F(x3).

4.Строим параболу проходящую, через точки: (x1,F(x1)), (x2,F(x2)), (x3,F(x3)) и находим координаты вершины.

a*x1^2+b*x1+c=F(x1)

a*x2^2+b*x2+c=F(x2)

a*x3^2+b*x3+c=F(x3)

Т.к. w=-b/(2a) - вершина параболы, находим a и b.

(x1)^2 x1 1

∆ = (x2)^2 x2 1 = (x1)^2*(x2-x3)–(x2)^2*(x1-x3)–(x3)^2*(x1-x2)

(x3)^2 x3 1

x1 1 F(x1)

∆1= x2 1 F(x2) = x1*(F(x3)–F(x2))–x2*(F(x3)–F(x1))–x3*(F(x2)–F(x1))

x3 1 F(x3)

(x1)^2 1 F(x1)

∆2= (x2)^2 1 F(x2) = (x1)^2(F(x3)–F(x2))–(x2)^2(F(x3)–F(x1))– (x3)^2(F(x2)–F(x1))

(x3)^2 1 F(x3)

a=∆1/∆;

a= ;

b=∆2/∆;

b= ;

w=- ;

4.Если |w- x₂|>e, h=h/2 – уменьшаем шаг на 2, иначе выходим

Графическая иллюстрация метода

1)Шаг берем равным h=(b-a)/2 и находим выпуклую комбинацию x1,x2,x3.

F(x)

F(x1) F(x3)

F(w)

F(x2)

0 x

x₁=a w x₂ x₃=b

2) h=(b-a)/4

F(x3)

F(x)

F(x1)

F(w)

F(x2)

0 x

x₁ w x₂ x₃

3) h=(b-a)/8

F(x)

F(x3)

F(x1)

F(w)

F(x2)

0 x

x₁ w x₂ x₃

4) Если |w- x₂|>e, продолжаем уменьшать шаг, иначе выходим.

Структурная схема

		X2=a+h
		X3=a+2h

T

F

F

T

	w=- ;

Анализ

Метод наиболее эффективен для функций хорошо аппроксимирующихся параболой и унимодальных на отрезке [a, b].

Погрешность вычислений меньше половины выбранного шага. Максимальное количество итераций при хорошо подобранном шаге = (b-a)/h.

Дата добавления: 2015-09-29