ChM1

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

Метод градиентного спуска

Распространенным методом минимизации функций большего числа переменных является метод градиентного спуска. Рассмотрим функцию f, допустим, что она зависит от двух переменных x, y .

Вычислим ее частные производные fx , fy и образуем с их помощью

вектор, который называют градиентом функции

gradf (x, y) f (x, y) i f (x, y) j .

x y

Здесь i,j – единичные векторы, параллельные координатным осям.

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

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

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

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

91

– шаг.

новую точку, в которой процедуру повторяем заново. Процесс

продолжаем до получения наименьшего значения целевой функции.

Вописанном методе нужно вычислять на каждом шаге

оптимизации

gradf f , f

x1 x2

	градиент		целевой	функции	f (x1 , x2 , x3 ,..., xn ) :
,...,	f	.
	xn

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

Таким образом, в методе градиентного спуска последующее приближение получается из предыдущего смещением в направлении,

противоположном градиенту функции f(x). Каждое следующее приближение ищется в виде xn 1 xn n gradf (xn ) , где n

Приведенное описание не определяет алгоритм однозначно,

поскольку ничего не сказано о выборе параметра δn. Например, его можно определять из условий минимума величины f (xn n gradf (xn )) . В

этом случае метод называют методом наискорейшего градиентного спуска.

Вопросы для самоконтроля:

1. Основные понятия (понятие оптимизации, проектный параметр,

целевая функция, типы задач оптимизации).

2.Опишите метод «золотое сечение». Какие еще методы поиска существуют.

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

92

Лабораторная работа № 7

Задания:

1.Для заданной функции определить интервал, на котором она унимодальная.

2.Методом «золотое сечение» найти минимум функции и сравнить его с точным значением.

Таблица 7.1

		Данные к заданию
	№	Задание
	варианта
	1	y 24			2				x			1				x2
		3										30
	2	y x					1 x2
	3	y (x 5)ex
	4	y x4 6x2 10
	5	y	1				x2								1
			3x3
												3
	6	y (x 1)2 (x 1)3
	7	y x3					3x 3
	8	y x								1	10
										x
	9	y 3x4								3x3
		y		1			4
	10											x
				x
	11	y 0.1x4 8x
	12	y x4 6x2 10

93

Приложения

Приложение 1

Примерный итоговый тест по курсу

Вариант I

Часть A

Инструкция: при выполнении заданий A1-A10 необходимо выбрать один правильный ответ.

№1. Абсолютная погрешность это:

a)качественная оценка;

b)количественная оценка;

c)качественная и количественная оценка;

d)все варианты неверны.

№2. Сходимость метода простой итерации решения СЛАУ зависит от:

a)выбора начального приближения;

b)от диагонального преобладания матрицы;

c)от собственных чисел матрицы;

d)от правой части системы.

№3. Метод золотого сечения делит отрезок в пропорциях:

a)0.618 и 0.382;

b)0.682 и 0.318;

c)0.5 и 0.5;

d)0.219 и 0.781.

№4. Оценка остаточного члена полинома Лагранжа:

					(x x0 )(x x1 )...(x xn )
a)		R(x)				M n 1 , где M n 1	max	f (n 1) (x)	и
					(n 1)!
							x0 x xn

f (n 1) (x) – производная n+1-го порядка f(x);

94

(x x0 )(x x1 )...(x xn )

и f (n) (x) –

b)

R(x)

M n , где M n max

f (n) (x)

(n)!

x0 x xn

производная n-го порядка f(x);

c)

R(x)

(x x0 )(x x1 )...(x xi 1 )(x xi 1 )...(x xn )

M

n 1

, где

(n 1)!

и f (n 1) (x) – производная n+1-го порядка

M n 1 max

f (n 1) (x)

x0 x xn

f(x);

d)

R(x)

(x x0 )(x x1 )...(x xi 1 )(x xi 1 )...(x xn )

M n , где

(n)!

и

f (n) (x) – производная n-го порядка f(x).

M n max

f (n) (x)

x0 x xn

№5. Квадратурная формула, дающая более высокую точность:

a)формула левых прямоугольников;

b)формула правых прямоугольников;

c)формула средних прямоугольников;

d)формула трапеций.

№6. Метод Эйлера это:

a)неявный одношаговый метод;

b)явный многошаговый метод;

c)неявный многошаговый метод;

d)явный одношаговый метод.

№7. Что понимается под обратным ходом метода Гаусса:

a)приведение матрицы к треугольному виду;

b)нахождение определителя;

c)нахождение невязки;

d)получение корней.

№8. В методе хорд, каждое следующее приближение вычисляется по формуле:

a) x a b ;

2

95

b) xn 1 g(xn ) ;

c) x a

b a

F (a) ;

F (b) F (a)

d) x

x

f (xn )

.

n 1

n

f

'

(x

)

n

№9. При квадратичной интерполяции интерполяция для любой точки общего промежутка [a,b] проводится:

a)по двум ближайшим к ней узлам;

b)по трем ближайшим к ней узлам;

c)по узлам, находящимся слева от нее;

d)по четырем ближайшим к ней узлам

№10. Остаточный член формулы Симпсона:

a)h3 f IV ( ) ;

12

b)h5 f IV ( ) ;

90

c)h3 f II ( ) ;

12

d)h5 f IV ( ) 180

Инструкция: при выполнении заданий B11-B13 необходимо написать правильный ответ.

Часть B

№11. Вычислить и определить погрешности результата: x ab , если

3 c

a 3.85 0.01,b 2.0435 0.0004,c 962.6 0.1.

№12. Отделить графически корни уравнения: x cos(x) 0

№13. Какой метод реализует данный алгоритм:

96

Ввод a, b,

c:=(a+b)/2

f(a)f(c)<0

a:=c		b:=c

f(с)<

Вывод c, |f(c)|

Рис. 1

97

Вариант II

Часть A

Инструкция: при выполнении заданий A1-A10 необходимо выбрать один правильный ответ.

№1. Точность приближенного числа зависит от:

a)количества значащих цифр;

b)количества верных цифр;

c)правильности округления;

d)количества точных цифр.

№2. Какой из методов имеет лучшую сходимость:

a)метод простой итерации;

b)метод Зейделя;

c)метод Гаусса;

d)метод релаксации.

№3. От чего зависит размерность задачи оптимизации:

a)количества проектных параметров;

b)от вида целевой функции;

c)от количества целевых функций;

d)другое.

№4. Для линейной интерполяции в качестве интерполяционной формулы берется:

a)уравнение квадратного трёхчлена;

b)уравнение прямой;

c)уравнение многочлена нулевой степени;

d)уравнение многочлена степени больше двух.

№5. Точность формулы Ньютона-Котеса: a) остается постоянной;

98

b)уменьшается с увеличением степени интерполяционного многочлена;

c)увеличивается с увеличением степени интерполяционного многочлена;

d)все варианты неверны.

№6. Задача, в которой требуется найти частное решение дифференциального уравнения, удовлетворяющее начальному условию y(x0)=y0, называется:

a)краевой задачей;

b)особым решением;

c)задачей Коши;

d)задачей дифференцирования.

№7. Когда метод простой итерации будет сходящимся:

a)если значение a[i,j] – малое число;

b)если значение a[i,j] – большое число;

c)если значение a[i,j] – равно нулю;

d)если значение a[i,j] – произвольное число.

№8. Из каких двух этапов состоит итерационный процесс:

a)отделение корней и нахождение точного корня;

b)отделение корней и уточнения точного корня;

c)нахождение корня и уточнение корня;

d)нахождение приближенного корня и уточнение его.

№9. Узлами интерполяции называют:

a)частичные отрезки на каждом из которых, строится многочлен;

b)отклонение аппроксимирующей функции от заданных значений;

c)степени аппроксимирующих функций на заданных отрезках;

d)точки совпадения аппроксимирующей и аппроксимируемой функций.

99

№10. Метод, не являющийся методом численного интегрирования:

a)метод Рунге-Кутта;

b)метод Симпсона;

c)метод трапеций;

d)метод прямоугольников.

Инструкция: при выполнении заданий B11-B13 необходимо написать правильный ответ.

Часть B

№11. Вычислить и определить погрешности результата: x m a b

c d

a9.542 0.001

b3.128 0.002

m2.8 0.03

c0.172 0.001

d5.4 0.02

№12. Отделить корни уравнения: x 2 x 1

№13. Какой метод реализует данный алгоритм:

100