Метод ломаных Методические указания

Метод ломаных является последовательным методом, рассчитан­ным на минимизацию произвольных (не обязательно унимодаль­ных) функций, удовлетворяющих условию Липшица. Говорят, что функция f(х) удовлетворяет на отрезке [а; b] условию Липшица, если существует такое число L > 0 (константа Липшица), что

\f(x')-f(x")\<L\x'-x"\ (4.1)

для всех х', х"  [а; b].

Для проверки условия Липшица на практике используют сле­дующий факт: если функция f(х) имеет на отрезке [а; b] ограниченную производную, то она удовлетворяет условию (4.1), где .

Пусть функция f(х) удовлетворяет на [а; b] условию Липшица с константой L. Опишем метод ломаных для минимизации f(х).

Положим

и реализуем следующую схему вычислений:

Шаг 1. Вместо пары чисел образуем две новые пары и следующим образом:

где .

Шаг 2. Из полученных двух пар и выберем ту, у которой вторая компонента минимальна. Обозначим ее и исключим из рассматриваемого множества (очевидно, на данном шаге в качестве можно взять любую из пар , ). Вместо пары добавляем две новые пары и , компоненты которых находятся по формулам

где .

В результате получим множество, состоящее из трех пар чи­сел (х, р).

Шаг п. Из п полученных на предыдущих шагах пар (х, р) выбираем ту, у которой вторая компонента р минимальна. Обо­значим ее . Исключаем эту пару из рассматриваемого мно­жества и добавляем вместо нее две новые пары чисел и по формулам

где . (4.2)

Полагая х* ≈ , f* ≈ f( ), получим приближенное решение задачи минимизации. Точность определения f* характеризуется неравенствами .

Геометрически метод ломаных состоит в построении последовательности ломаных, приближающихся к графику функции f(х) снизу и имеющих угловые коэффициенты всех звеньев, равные ±L , как показано на рисунке 4.1.

Рисунок 4.1 – Метод ломаных

Контрольные вопросы:

1. Для каких функций применим метод деления ломаных?

2. Каким способом можно определить число корней функции на заданном отрезке?

3. Какие могут быть условия выхода при нахождении корней уравнения при помощи метода деления отрезка пополам?

4. В каких случаях метод деления отрезка пополам является более точным?

Какие преимущества и недостатки можно выделить при решении уравнения методом деления отрезка пополам, используя Microsoft Excel?

Применение метода

М етодом ломаных найти минимум функции f(x), e = 0,01.

Необходимо локализовать минимум функции, для этого воспользуемся рисунком 4.2:

Рисунок 4.2 – График заданной функции

На графике минимум нашей функции находится на отрезке [1,5;2,75]. Применим метод ломанных к функции на отрезке [1,5; 2,75].

Таблица 4.1 – Расчеты метода ломанных

n	Исключаемая пара		f(xn*)	Δn	2LΔn	Включенные пары
	xn*	pn*				xn'	xn''	pn
1	2,12825	-0,09272	-0,01212	0,49629	0,16120	1,63196	2,62455	-0,05242
2	1,63196	-0,05242	-0,00528	0,29024	0,09427	1,34172	1,92220	-0,02885
3	2,62455	-0,05242	-0,00698	0,27977	0,09087	2,34478	2,90431	-0,02970
4	2,34478	-0,02970	-0,00986	0,12214	0,03967	2,22264	2,46692	-0,01978
5	2,90431	-0,02970	-0,0047	0,15390	0,04999	2,75041	3,05822	-0,01720
6	1,34172	-0,02885	0,052222	0,49918	0,16214	0,84254	1,84090	0,01169
7	1,92220	-0,02885	-0,01312	0,09687	0,03146	1,82533	2,01906	-0,02098
8	1,82533	-0,02098	-0,01243	0,05269	0,01711	1,77264	1,87802	-0,01670
9	2,01906	-0,02098	-0,01292	0,04967	0,01613	1,96939	2,06873	-0,01695
10	2,22264	-0,01978	-0,01118	0,05293	0,01719	2,16970	2,27557	-0,01548
11	2,46692	-0,01978	-0,00855	0,06917	0,02247	2,39775	2,53609	-0,01416
12	2,75041	-0,01720	-0,00587	0,06975	0,02266	2,68066	2,82016	-0,01154
13	3,05822	-0,01720	-0,00373	0,08298	0,02695	2,97524	3,14119	-0,01046
14	1,96939	-0,01695	-0,01695	0,00000	0,00000	1,96939	1,96939	-0,01695
x*	1,96939	f(x*)	-0,01695

Из таблицы 4.1 видно, что на 7-ом шаге метода ломаных для данной функции достигается заданная точность.

Задание. Методом ломаных найти минимум функции f(x),  = 0.01

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Вариант 11

Вариант 12

Вариант 13

Вариант 14

Вариант 15

Вариант 16

Вариант 17

Вариант 18

Вариант 19

Вариант 20

Вариант 21

Вариант 22

Вариант 23

Вариант 24

Вариант 25

Вариант 26

Вариант 27

Вариант 28

Вариант 29

Вариант 30

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

Если вычисление или измерение производных функции f(х) не представляет больших затруднений, то при решении задачи минимизации можно применять непрямые методы, основан­ные на использовании производных f(х). Во многих случаях эти методы обеспечивают более быструю сходимость, чем прямые методы минимизации.

Метод касательных применяется для минимизации выпуклых дифференцируемых функций. Функция f (х) называется выпуклой на отрезке [а; b], если

(5.1)

для произвольных х', х" [а; b] и .

Проверка условия (5.1) почти всегда вызывает затруднения, поэтому на практике используют следующий критерий выпуклости:

Для того, чтобы дважды дифференцируемая на отрезке [а; b] функция f(х) была выпуклой на отрезке [а; b], необходимо и доста­точно, чтобы f"[x)≥0 при всех х[а; b].

Опишем метод касательных. Пусть f(х) - выпуклая дифферен­цируемая на отрезке [а; b] функция, причем . Построим последовательности , в соответствии с рекуррентными соотношениями

, (5.2)

при , (5.3)

при .

После п шагов полагаем . Требуемая точ­ность минимизации f(x) считается достигнутой, если производная f'(c) достаточно близка к нулю, т. е. | f'(c_п)|  , где >0 - заданное число, характеризующее точность.

Метод касательных имеет простой геометрический смысл: вели­чина с_n-1 из (5.2) - это абсцисса точки пересечения касательных к графику f(x), проведенных в граничных точках отрезка , как показано на рисунке 5.1а). Рисунки 5.1 б) и 5.1 в) поясняют формулы (5.3) для случаев и соответственно. Отрезок выби­рается так, чтобы x* .

а) б) в)

Рисунок 5.1 – Метод касательных

Если условие не выполняется, то

а) х*= а при f’ (а) > 0, f’ (b) > 0;

б) х*=b при f’ (а) < 0, f’ (b) < 0;

в) х*= а, если f'(a)=0, и х*=b, если f’(b)=0.

Метод Ньютона.

Метод Ньютона, использующий не только первую, но и вто­рую производные функции f(x), при определенных условиях обеспе­чивает значительно более высокую, чем рассмотренные выше методы минимизации, скорость сходимости к точке минимума х*.

Пусть f(x) - выпуклая дважды дифференцируемая на R функ­ция. Выбрав начальное приближение х₀, построим последователь­ность

(5.4)

Считая неравенство | f'(х_п)|   ( - достаточно малое число) усло­вием достижения требуемой точности вычислений, положим х* ≈ , f* ≈ f( ).

При неудачном выборе Хц последовательность (5.4) может рас­ходиться. Если же точка х₀ достаточно близка к х*, то эта последо­вательность сходится к х* достаточно быстро.

Оценка скорости сходимости может быть сформулирована сле­дующим образом. Пусть f(x) - дважды дифференцируемая на R функция, причем при всех x R. и f"'(х) удовлетво­ряет условию Липшица на R с константой L. Тогда, если началь­ное приближение х₀ удовлетворяет условию , то последовательность (5.4) сходится к единственной точке мини­мума х* функции f(х) на R, причем

Метод Ньютона часто используется на завершающем этапе минимизации, когда точка минимума х* грубо найдена другим, менее трудоемким методом и требуется найти х* с большой точ­ностью.

Применение методов

М етодом касательных найти минимум функции f(x), e = 0,01. Уточнить полученный результат методом Ньютона с точностью e = 10^-5.

Необходимо локализовать минимум функции, воспользуемся рисунком 5.2:

Рисунок 5.2 – График заданной функции

На графике минимум нашей функции находится на отрезке [-0,5;1]. Применим метод касательных к функции на отрезке [-0,5;1].

Таблица 5.1 – Расчеты метода касательных

n	an	bn	f(an)	f(bn)	f'(an)	f'(bn)	cn	f'(cn)	| f'(cn) |
1	-0,5	1	-0,6276	0,4597	-1,4794	2,8415	0,2348	0,7022	0,7022
2	-0,5000	0,2348	-0,6276	-0,9174	-1,4794	0,7022	-0,1306	-0,3915	0,3915
3	-0,1306	0,2348	-0,9744	-0,9174	-0,3915	0,7022	0,0519	0,1556	0,1556
4	-0,1306	0,0519	-0,9744	-0,9960	-0,3915	0,1556	-0,0393	-0,1180	0,1180
5	-0,0393	0,0519	-0,9977	-0,9960	-0,1180	0,1556	0,0063	0,0188	0,0188
6	-0,0393	0,0063	-0,9977	-0,9999	-0,1180	0,0188	-0,0165	-0,0496	0,0496
7	-0,0165	0,0063	-0,9996	-0,9999	-0,0496	0,0188	-0,0051	-0,0154	0,0154
8	-0,0051	0,0063	-1,0000	-0,9999	-0,0154	0,0188	0,0006	0,0017	0,0017
						x*	0,0006	f(x*)	0,0017

Из таблицы 5.1 видно, что на 8-ом шаге метода касательных для данной функции достигается заданная точность.

Ответы выписаны в последнюю строку таблицы.

Затем уточним полученный ответ методом Ньютона:

Таблица 5.2 – Расчеты метода Ньютона

n	xn	f(xn)	f'(xn)	f''(xn)	|f'(xn)|
1	0,000571	-1	0,001712	3	0,001712
2	-2,1E-11	-1	-6,2E-11	3	6,2E-11
x*	-2,1E-11	f(x*)	-1

Из приведенной таблицы 5.2 видно, что на 2-ом шаге метода Ньютона мы уточнили ответ, полученный методом касательных, с заданной точностью.

Задание. Методом касательных найти минимум функции f(x),  = 0.01. Уточнить полученный результат методом Ньютона с точностью  = 10^-5

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Вариант 11

Вариант 12

Вариант 13

Вариант 14

Вариант 15

Вариант 16

Вариант 17

Вариант 18

Вариант 19

Вариант 20

Вариант 21

Вариант 22

Вариант 23

Вариант 24

Вариант 25

Вариант 26

Вариант 27

Вариант 28

Вариант 29

Вариант 30

Метод градиентного спуска с дроблением шага.

Как известно из курсов анализа, градиент скалярной функции f(x) в некоторой точке x_k направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня (поверх­ности постоянного значения функции f(x), проходящей через точку x_k). Вектор, противоположный градиенту f’(x_k,), антиградиент, направлен в сторону наискорейшего убывания функции f(x). Выбирая в качестве направления спуска p_k антиградиент функции f(x) в точке x_k, мы приходим к итерационному процессу вида

(6.1)

В координатной форме этот процесс записывается следу­ющим образом:

(6.2)

Все итерационные процессы, в которых направление дви­жения на каждом шаге совпадает с антиградиентом (гра­диентом) функции, называются градиентными методами и отличаются друг от друга способами выбора шага _k.

Пусть f(х) - выпуклая дифферен­цируемая во всем пространстве Е^п функция и требуется найти ее точку минимума х*. Выбрав произвольное начальное приближение построим последовательность

(6.3)

где величины (параметрические шаги) выбираются достаточно малыми для того, чтобы выполнялось условие:

(6.4)

В качестве условия окончания вычислений обычно используется близость к нулю градиента т. е. выполнение неравенств

или

, (6.5)

где  - заданное достаточно малое число, после чего полагают .

Если при некоторомk условие (2.12) нарушается, то шаг в (6.3) уменьшают (дробят) в заданное число раз до выполнения неравен­ства (6.4) и продолжают вычисления.

Применение метода

М инимизировать функцию методом градиентного спуска с дроблением шага.

Таблица 6.1 – Вспомогательные расчеты метода градиентного спуска с дроблением шага

k	x(k)	y(k)	f(x,y)	f'(x)	f'(y)	a	|f'(x)|	| f'(y) |	(f'(x)^2+f'(y)^2)^0,5
0	0	0	1,00	15	0	1	15	0	15
	-15	0	3,34E+191		0		0
	0	0	1,00	15	0	0,5	15	0	15
	-7,5	0	7,60E+47		0		0
	0	0	1,00	15	0	0,25	15	0	15
	-3,75	0	9,34E+11		0		0
	0	0	1,00	15	0	0,125	15	0	15
	-1,875	0	954,89		0		0
	0	0	1,00	15	0	0,0625	15	0	15
1	-0,9375	0	-8,46	-5,5777	0	0,0625	5,5777	0	5,577729169
	-0,5889	0	-6,86		0		0
	-0,9375	0	-8,46	-5,5777	0	0,03125	5,5777	0	5,577729169
	-0,7632	0	-8,32		0		0
	-0,9375	0	-8,46	-5,5777	0	0,01563	5,5777	0	5,577729169
2	-0,8503	0	-8,63	1,2472	0	0,01563	1,2472	0	1,247209578
3	-0,8698	0	-8,6416	-0,0233	0	0,01563	0,0233	0	0,023327045
x*	-1	y*	0	f(x*,y*)	-8,6416

Из таблицы 6.1 видно, что на 3-ом шаге для данной функции достигается заданная точность.

Задание. Минимизировать функцию методом градиентного спуска с дроблением шага,  = 0.05

№ варианта	a	b	c	d
1	1.0	-1.4	0.01	0.11
2	2.0	-1.3	0.04	0.12
3	3.0	-1.2	0.02	0.13
4	4.0	-1.1	0.16	0.14
5	5.0	-1.0	0.25	0.15
6	6.0	-0.9	0.36	0.16
7	7.0	-0.8	0.49	0.17
8	8.0	-0.7	0.64	0.18
9	9.0	-0.6	0.81	0.19
10	10.0	-0.5	0.94	0.20
11	11.0	-0.4	1.00	0.21
12	12.0	-0.3	1.21	0.22
13	13.0	-0.2	1.44	0.23
14	14.0	-0.1	1.69	0.24
15	15.0	-0.0	1.85	0.25
16	16.0	0.0	1.99	0.26
17	17.0	0.1	2.56	0.27
18	18.0	0.2	2.89	0.28
19	19.0	0.3	3.24	0.29
20	20.0	0.4	3.81	0.30
21	21.0	0.5	4.00	0.31
22	22.0	0.6	5.02	0.32
23	23.0	0.7	4.84	0.33
24	24.0	0.8	5.29	0.34
25	25.0	0.9	5.76	0.35
26	26.0	1.0	6.25	0.36
27	27.0	1.1	6.76	0.37
28	28.0	1.2	6.98	0.38
29	29.0	1.3	7.29	0.39
30	30.0	1.4	8.41	0.40

Литература

1. Прокушева А.П. «Экономика информатики». – М: Изд. дом Дашков и К, 2000. – 84 стр.

2. Карасева А.И., Аксютина З.М., Савельева Т.И. Курс высшей математики для экономических вузов. – М.: Высшая школа, 1982. – 382 с.

3. Мастяева И.Н., Горобцов Г.Я., Турундаевский В.Б. Методические указания и задания по курсу «Прикладная математика и математическое моделирование в бизнесе». – М.: Московский государственный университет экономики, статистики и информатики, 1997. – 115с.

4. Айвазян С.А., Бирюков И.С., Мешалкин Л.Д. «Прикладная статистика: основы моделирование и первичная обработка данных». Справочное издание. – М.: Финансы и статистика, 1983. – 471с.

5. Сигорский В.П. «Математический аппарат инженера». Издание 2-е. – К.: Техника, 1977. – 768с.

6. Басакер Р., Саати Т. «Конечные графы и сети». – М.: Наука, 1973. – 386с.