Составители:
Рубрика:
26
Первую строку можно считать законченной, если в ячейке Q6
мы получим значение квадратичной функции в первом прибли-
жении, для чего в эту ячейку введем соответствующую формулу
(рис. 7.10).
Рис. 7.10
Во второй строке в ячейке A7 введем формулу «=A6 + 1», а в
диапазон B7:C7 – ссылку на приближение x, полученное в первой
строке (рис. 7.11).
Рис. 7.11
Далее выделим E6:Q6, в правом нижнем конце диапазона по-
явится черный «крестик» (рис. 7.12), потянув за который вниз на
одну строку, мы получим заполненную вторую строку (рис. 7.13).
Рис. 7.12
Рис. 7.13
11
В силу выпуклости квадратного трехчлена с ПО матрицей А
имеет место разложение
F
k
(α) = f (x
k
+ αg
k
) = f (x
k
) – α (g
k
, p
k
) +
1
α
2
(Ap
k
, p
k
)
2
где при положительном старшем коэффициенте единственная
точка минимума α
k
≥ 0 может быть найдена из необходимого
условия экстремума F'
k
(α) = – (g
k
, p
k
) + α(Ap
k
, p
k
) = 0. Тогда, не-
зависимо от направления спуска p
k
, для квадратичной функции
решение задачи (3.4) α
k
имеет вид
α
k
=
(p
k
, g
k
)
(Ap
k
, p
k
)
. (3.5)
Градиентный метод, в котором на каждой итерации использу-
ется шаг, являющийся решением задачи (3.4), был предложен в
1845 г. О. Коши и называется методом наискорейшего спуска.
Отметим, что минимум по направлению не является миниму-
мом целевой функции, если направление не указывает на точку
минимума.
3.3. Метод наискорейшего градиентного спуска
Опишем алгоритм метода наискорейшего градиентного спуска
для квадратичной функции (2.1). Пусть построена точка
nk
Rx ∈
.
1°. Вычислим g
k
= – (Ax
k
+ b)
n
R∈
– градиентное направление
спуска.
2°. Определим
1
R
k
∈α
– шаг метода в данном направлении –
из формулы (3.5) при условии, что
0≠
k
g
:
α
k
=
(g
k
, g
k
)
(Ag
k
, g
k
)
. (3.6)
Очевидно, что при подстановке α
k
в (3.2) построенная точка
x
k+1
удовлетворяет условию (3.1).
3°. Вычисляем следующую итерацию x
k+1
по формуле (3.2).
Проверяется выполнение критерия окончания итераций (см.
(3.7)–(3.9) для i = k + 1). Если критерий выполняется, то итерации
прекращаем и полагаем
1* +
≈
k
xx
. В противном случае возвра-
щаемся к п. 1°. Продолжая указанные построения, получим ми-
нимизирующую f (x) последовательность {x
k
}.
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
