Модуль 2. Вычисление значений функции с заданной степенью точности. Методы одномерной оптимизации

Модуль 2. Вычисление значений функции с заданной степенью точности.

Методы одномерной оптимизации.

1. Вычисление значений функции с заданной степенью точности.

1.1. Понятие ряда Тейлора.

1.1.1. Разложение функции в ряд Тейлора.

1.1.2. Разложение основных элементарных функций в ряд Тейлора.

1.2. Применение разложения функции в ряд Тейлора.

1.2.1. Замечание о точности вычислений.

1.2.2. Вычисление числа .

1.2.3. Вычисление .

1.3. Практикум.

2. Методы одномерной оптимизации.

2.1. Понятие оптимизации.

2.2. Метод сканирования.

2.3. Метод локализации.

2.4. Метод золотого сечения.

2.5. Метод поиска с использованием чисел Фибоначчи.

2.6. Практикум.

1. Вычисление значений функции с заданной степенью точности.

1.1. Понятие ряда Тейлора.

1.1.1. Разложение функции в ряд Тейлора.

Рассмотрим произвольную функцию f(x). Предположим, что для нее в точке существуют производные всех порядков до n-го включительно.

Замечание: в школьном курсе математического анализа изучается понятие производной первого порядка. Например, если f(x) = sinx, тогда . Производная функции так же является функцией, значит, от нее можно найти производную. Таким образом, получим производную второго порядка. Итак, вторая производная функции (или производная второго порядка) – это производная от ее первой производной: . Для рассматриваемой функции f(x) = sinx имеем .

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

В общем случае справедлива формула: , т. е. n-ая производная функции находится как первая производная от ее (n-1)-ой производной.

Производной нулевого порядка считается сама функция f(x).

Тогда для функции f(x) можно записать ряд Тейлора:

(1)

Заметим, что здесь мы имеем бесконечную сумму.

Если ограничиться несколькими первыми слагаемыми, то получим приближенную формулу Тейлора:

, (2)

правая часть которой называется многочленом Тейлора функции f(x).

Эта приближенная формула позволяет заменять в различных математических расчетах (аналитических и численных) произвольную функцию ее многочленом Тейлора. Из формулы Тейлора видно, что чем точка x ближе к точке x0, тем выше точность такой замены и эта точность растет с ростом степени многочлена. Это означает, в свою очередь, что чем больше производных имеет функция в некоторой окрестности точки x0, тем выше точность, с которой многочлен Тейлора приближает (заменяет) функцию в этой окрестности.

1.1.2. Разложение основных элементарных функций в ряд Тейлора.

Пусть функция f(x) имеет производные всех порядков в нуле. Тогда, полагая в (1) x0 = 0, сопоставим этой функции ряд Тейлора:

. (3)

Рассмотрим функцию . Запишем для нее разложение в ряд Тейлора. Для этого вычислим производные до n-го порядка включительно.

Имеем, , при n = 0, 1, 2, ….

Для функции формула (3) примет вид .

Доказано, что для любого действительного числа x

.

Действуя аналогичным образом, получаем разложения в ряд Тейлора других элементарных функций (см. таблицу 1).

Таблица 1.

Разложение функции в ряд Тейлора	Ограничения на х

1.2. Применение разложения функции в ряд Тейлора.

1.2.1. Замечание о точности вычислений.

При некоторых ограничениях на x функция f(x) совпадает с бесконечной суммой – рядом Тейлора. На практике мы не можем производить суммирование до бесконечности. Да и чаще всего требуется найти приближенное значение функции с определенной степенью точности.

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

1.2.2. Вычисление числа .

Воспользуемся разложение функции в ряд Тейлора

и тем фактом, что . Тогда . Заметим, что x = 1 является допустимым значением для замены функции в этой точке на ряд Тейлора. Получаем

или

.

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

n		(точность)	(только верные значащие цифры)
2	2,6666…	--
10	3,0418…	--
20	3,0916…	0,1	3,1
200	3,1365…	0,01	3,14
2000	3,14109…	0,001	3,141

Аналогичным образом можно вычислить значение числа e, Значения тригонометрических функций.

1.2.3. Вычисление .

Задача: вычислить с точностью 0,001.

Решение.

Преобразуем . Теперь можно применить следующее разложение функции в ряд Тейлора:

,

при этом , .

Получаем,

>0.001 <0.001

Ответ: =3,107 с точностью 0,001.

1.3. Практикум.

Вычислить производные второго и третьего порядка для следующих функций:

·  ;

·  ;

·  .

Вычислить приближенное значение числа e при n = 2, 3, 10, 30. Вычислить , ln2 с точностью 0,001.

Ответы.

1.

	-

2.

n	2	3	10	30
e	2,5	2,6666…	2,71828…	2,718281828…

2. Методы одномерной оптимизации.

2.1. Понятие оптимизации.

Оптимизация – это целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях. В математике оптимизация связана с нахождением оптимума (т. е. максимума или минимума) некоторой функции.

Если рассматриваемая функция является функцией одной переменной, в этом случае говорят об одномерной оптимизации.

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

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

Для определенности будем считать, что решаем задачу отыскания минимума функции y = f(x) на интервале (a; b).

2.2. Метод сканирования.

Интервал поиска (a; b) разбивается на несколько равных участков, каждый из которых равен шагу поиска h (рис. 1).

Рис. 1. Метод локализации.

Далее последовательно определяются значения функции f(x) во всех точках разбиения аргумента и в точках a и b и запоминается наименьшее значение. Таким образом, минимум может быть найден с точностью до h.

Достоинства метода: простота, возможность нахождения глобального минимума.

Недостаток метода: большой объем вычислений.

Пример. Найти минимум функции с точностью ε = 0,3 на интервале (-2; 1)

Решение. Точность ε = 0,3 - шаг поиска. Количество частей разбиения интервала

, где […] обозначают целую часть выражения, записанного в скобках.

n = 10.

n	0	1	2	3	4	5	6	7	8	9	10
Xn	-2	-1,7	-1,4	-1,1	-0,8	-0,5	-0,2	0,1	0,4	0,7	1
f(xn)	0	-0,51	-0,84	-0,99	-0,96	-0,75	-0,36	0,21	0,96	1,89	3

Наименьшее значение функции: -0,99.

Точка минимума: -1,1.

2.3. Метод локализации.

Алгоритм метода:

1.  Интервал поиска минимума (a; b) разбивается на четыре равные части точками x1, x2, x3.

2.  Вычисляются значения функции y = f(x) во всех точках разбиения и в точках x = a, x = b.

3.  Полученные значения f(x) сравниваются между собой, и из них выбирается наименьшее.

4.  Локализуется минимум, причем новый интервал поиска равен двум старым подынтервалам с наименьшим значением f(x) на их общей границе (на рис. 2 это соответствует интервалу (a, x2)).

5.  Интервал, в котором локализован минимум, опять делится на четыре равных подынтервала ( на рис. 2 точками x4, x5) и снова вычисляются значения функции y = f(x) в точках деления. Они сравниваются между собой, находится наименьшее, локализуется минимум в меньшем интервале ( на рис. 2 в интервале (x4, x5)) и так далее до тех пор, пока минимум не будет локализован в интервале, размер которого соответствует заданной точности поиска.

Замечание. Интервал, поиска разбивается именно на четыре, подынтервала с целью уменьшения объема вычислений: при этом каждый последующий подынтервал делится пополам, и вычислять значение функции нужно только в двух новых точках, так как её значения на концах нового интервала и в его середине известны из предыдущих расчетов.

2.4. Метод золотого сечения.

При построении процесса оптимизации стараются сократить объем вычислений и время поиска. Этого достигают обычно путем сокращения количества вычислений значений функции y = f(x). Одним из наиболее эффективных методов, в которых при ограниченном количестве вычислений f(x) достигается наилучшая точность, является метод золотого сечения.

Если известно, что функция f(x) имеет только один минимум на отрезке [a; b], то положение точки минимума можно уточнить, вычислив f(x) в двух внутренних точках отрезка. При этом возможны две ситуации:

1. . Минимум реализуется на отрезке [a; x2].

2. . Минимум реализуется на отрезке [x1; b].

В методе золотого сечения каждая из точек x1 и x2 делит исходный интервал на две части так, что отношение целого к большей части равно отношению большей части к меньшей, т. е. равно так называемому «золотому отношению». Это соответствует следующему геометрическому представлению:

Здесь или . Обозначим , получим . Решив данное уравнение, получим . Итак, длины отрезков [a, x1] и [x2, b] одинаковы и составляют 0,382 от длины (a, b). По значениям f(x1) и f(x2) определяется новый интервал (a, x2) или (x2, b), в котором локализован минимум. Найденный интервал снова делится двумя точками в том же отношении, причем одна из новых точек деления совпадает с уже использованной на предыдущем шаге.

Таким образом, длина интервала неопределенности на каждом шаге сжимается с коэффициентом 0,618. На первом шаге необходимы два вычисления функции, на каждом последующем – одно.

Алгоритм метода золотого сечения для минимизации функции.

1.  Вычисляется значение функции f(x1), где x1 = a + 0,382(b - a).

2.  Вычисляется значение функции f(x2), где x2 = b - 0,382(b - a).

3.  Определяется новый интервал (a, x2) или (x2, b), в котором локализован минимум.

4.  Внутри полученного интервала находится новая точка (x1 в случае 1) или (x2 в случае 2), отстоящая от его конца на расстоянии, составляющем 0,382 от его длины. В этой точке рассчитывается значение f(x). Затем вычисления повторяются, начиная с пункта 3, до тех пор, пока величина интервала неопределенности станет меньше или равна ε, где ε - заданное сколь угодно малое положительное число.

2.5. Метод поиска с использованием чисел Фибоначчи.

Данный материал отводится на самостоятельное изучение.

2.6. Практикум.

1. Укажите метод, который не используется в одномерной оптимизации:

a)  метод сканирования;

b)  метод золотого сечения;

c)  метод сопряженных направлений;

d)  метод локализации;

2. Критерием выбора нового отрезка в задаче отыскания максимума в методе “золотого сечения” является:

a)  Если f(x1)< f(x2), то новый отрезок: [a; x2],
если f(x) f(x), то: [x; b].

b)  Если f(x)< f(x), то новый отрезок: [x; b],
если f(x) f(x), то: [а; x].

c)  Если f(x)< f(x), то новый отрезок: [x; b],
если f(x) f(x), то: [а; x]

d)  Если f(x)< f(x), то новый отрезок: [x; b],
если f(x) f(x), то: [а; x].

3. В методе “золотого сечения” x и x находятся по формуле:

a)  x= а + 0,382*(b-a),
x= b - 0,382*(b-a).

b)  x= b + 0,382*(b-a),
x= a - 0,382*(b-a).

c)  x= а + 0,382*(b-a),
x= b + 0,382*(b-a).

d)  x= а + 0,382 / (b-a),
x= b - 0,382 / (b-a).

4. В каком из методов одномерной оптимизации общее число вычислений необходимо выбирать заранее?

a)  В метод золотого сечения.

b)  В метод локализации.

c)  В метод сканирования.

d)  В методе Фибоначчи.

5. Используя метод “золотого сечения”, максимизировать функцию: f(x)=2*x +3*x на интервале (0;2). Длина конечного интервала неопределенности не должна превосходить 0,5.

a)  xmax= 1,236; f(xmax) = 6,7634;

b)  xmax = 1,875; f(xmax) = 12,6563;

c)  xmax = 1,764; f(xmax) = 11,5154;

d)  xmax = 1,657; f(xmax) = 10,4623.

6. В методе локализации найдены значения

a = 0	f(a) = 0
x1 = 0,5	f(x1) = -9,16
X2 = 1,0	f(x2) = -11,7
X3 = 1,5	f(x2) = 11,32
b = 2	f(b) = 90,0

Определить новый интервал для следующего шага.

a)  (0; 1)

b)  (-9,16; 11,32)

c)  (0,5; 1,5)

d)  (-9,16; -11,7)

7. В таблице приведены результаты первых двух шагов минимизации функции на интервале (-3; 5) методом золотого сечения.

№ шага	a	b	x1	x2	f(x1)	f(x2)
1	-3,000	5,000	a)	b)	0,115	7,667
2	c)	d)	-1,112	0,056	-0,987	0,115

Вставьте недостающую информацию.

Ответы.

1	2	3	4	5	6
c	b	a	d	b	b

7. a) 0,056

b) 1,944

c) -3,000

d) 1,944