Получение оптимальных проектных решений и их анализ с использованием математических моделей. Литовка Ю.В. - 49 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

от нуля и для них выполняется условие (S
k
)A(S
k+1
)
T
= 0.
Векторы
S
0
, S
1
, …, S
k
называются взаимно сопряженными, если все они отличны от нуля и для любых i, j = 0, ...,
k и i ≠ j выполняется условие (S
i
)A(S
j
)
T
= 0.
Частным случаем сопряженности векторов
S
k
и S
k+1
является случай их ортогональности (перпендикуляр-
ности), когда матрица
А представляет собой единичную матрицу.
В методе сопряженных градиентов система взаимно сопряженных направлений строится по правилу
,...,2,1,)();(
1
10
0
0
0
=β+−∇=−∇=
−
−
kSXfSXfS
k
k
kk
где коэффициент
1−
β
k
определяется из условия сопряженности векторов S
k
и S
k–1
, т.е.
(S
k–1
)A(S
k
)
T
= 0; (S
k–1
)A( 0))(
1
10
=β+∇−
−
−
Tk
k
k
SXf .
Проведя несложные преобразования, получим выражение для вычисления
1−
β
k
при минимизации квадра-
тичных функций:
.
)()(
))(()(
11
0
1
1
Tkk
Tk
k
SS
XfS
k
−−
−
∇
=β
−
A
A
(2.6)
Для произвольной
k-й итерации следующее приближение Х
k+1
к точке минимума Х
*
определяется из усло-
вия того, что точка
Х
k+1
является точкой минимума функции f
0
(X) вдоль направления, определяемого вектором
S
k
, т.е.
X
k+1
= X
k
+ h
k
S
k
, )(minarg
0
kk
h
k
hSXfh += .
Локализация отрезка (
h′, h″) содержащего значение h
k
, и поиск значения h
k
выполняются с использованием
тех же процедур, что и в методе наискорейшего спуска.
Для вычисления
1−
β
k
удобнее пользоваться другим выражением, в котором отсутствует матрица вторых
производных
А:
Tkk
Tkk
k
XfXf
XfXf
))())(((
))())(((
1
0
1
0
00
1
−−
−
∇∇
∇∇
=β
. (2.7)
В таком виде оно может быть использовано как для минимизации квадратичных, так и неквадратичных
функций, у которых значения вторых производных в точках Х
k
, k = 0, 1, …, не являются неизменными.
Таким образом, для минимизации квадратичных функций метод сопряженных градиентов является конеч-
но-шаговым и позволяет найти решение не более, чем за n итераций. Для минимизации неквадратичных функ-
ций метод перестает быть конечно-шаговым, получаемые им направления S
0
, S
1
, ..., не являются, вообще гово-
ря, взаимно сопряженными относительно какой-либо матрицы. В этом случае в качестве критерия окончания
поиска используется условие (2.3). Геометрическая иллюстрация метода сопряженных градиентов приведена на
рис. 2.12.
Рис. 2.12. Метод сопряженных градиентов
ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1. Составить алгоритмы решения задачи минимизации функции n переменных методами наискорейшего
спуска и сопряженных градиентов. Для вычисления
...,,2,1,
1
=
β
−
k
k
использовать выражение (2.7).
2. Подготовить программы для ЭВМ, реализующие алгоритмы п. 1.
3. Найти решение задачи перечисленными методами, используя задание из лабораторной работы 2.2. Ре-
шение задачи произвести каждым методом из двух различных начальных точек. Для функции Розенброка од-
ной из таких точек должна быть точка Х
0
= (–1, 2, 1).
Результаты решения задачи должны содержать последовательность точек Х
0
, Х
1
, ..., Х
*
с соответствующи-
ми значениями целевой функции в них.
4. Построить на бумаге линии равного уровня обеих функций и геометрически проиллюстрировать про-
цесс нахождения решения задачи для каждых метода, функции и начального приближения.
СОДЕРЖАНИЕ ОТЧЕТА
х
1
х
2
Х
0
Х
1
Х
2
s
1
s
0 –∇f
0
(x
1
)

Страницы