Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

§ 8)

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

113

Обозначим иа= и п+'а(ип— ип),

0 < ;« ^ 1 . Из выпуклости функ­

ции J n (и)

следует, что

J n («а) < a J n (ип) + (1 — а) J n (ип) = a J n (ип) < О,

Тогда из формулы

J (Иа) — J (и„) =

J n («а) +

((J" (иа +

0а (ип — Un)) —

— Г ( и п))(ип — ип) , й п — ип),

0 < а < 1

(11)

будем иметь

j («„) — J Ы

> — J n («а) — — (M — ll)\un — Un \2> 0.\Jn (un)\ —

- \ ^ М \ й п- и п\\

0 < а < 1 .

(12)

Так как /п {и)

сильно выпуклая функция и достигает своего мини­

мума на U в точке ип, то согласно теореме 1.6

\чп — «„12 <

— Un(4n) — J n(u„)] =

—

|/„(“*) I»

n = 0, 1 , . . .

!*■

(13)

Подставим эту оценку в (12). Получим

J

(un) — J (иа) > а ^ 1 ----- ~

а ) \J n(un)\> ае| J n (un)\

при всех

а,

а ■< —

^ ** < 1 .

Таким образом,

2М

множество тех а = а п, для которых выполнено условие (10),

непу­

сто. Из непрерывности J (и) следует, что множество таких а зам­

кнуто и, следовательно, это множество

содержит

свою верхнюю

грань a „ ^ l . В соответствии с (9) полагаем

ип+\=

ыа„.

J

{чп)

J

(Wn+l) ^ &<ХП|J n (ип) | 68]^ |J п (ип) |

0,

п = 0,

1, . . .

(14)

Следовательно, { J (ип)}

монотонно убывает и,

кроме того,

J (ип) >

>

J* =

inf J

(ы) > — оо.

Тогда существует l i mJ (« J

и |Пш [/(un+I) —

U

П—>оо

П-^оо

116

М И Н И М И З А Ц И Я Ф У Н К Ц И И М НОГИ Х ПЕРЕМЕННЫ Х

[Гл. 2

(постоянные R, е являются параметрами алгоритма). Если нера­

венство

(17)

выполняется,

то останавливаются

на

выборе

а п= а п,

находят

un+1

по формуле

(15)

и переходят к

следующей

итера­

ции. Если же

неравенство

(17)

не выполняется

пр_и а„ = а„, то

Если при каком-либо

п ^ т — 1

матрица Л„, определенная из

системы

(16),

окажется

вырожденной

или

же

(ДГ1

J'

(ип),

/ ' ( и , ) ) а

то

либо

изменяют вектор

гп

и

-заново

строят

матрицу Ап, либо полагают Ап= Е

(Е — единичная матрица) и

ап в (15)

выбирают, пользуясь каким-либо

вариантом

'градиент­

ного мет.ода; п-й шаг метода

при

всех п ^ т — 1

описан.

Если

0 -^ / г ^ т —2, то

в

(15)

можно

принять

Ап= Е

и

а,г

при

/г=0,1, . . . ,

т— 2 выбирать, как в градиентном методе.

векторы гп,

Пусть Rn— матрица, столбцами

которой являются

гп-\, ■•- ,

гп—т+\, a

Qn— матрица,

составленная

из

столбцов

•7 fan 'l- ^n)i

J fan)t • • •

i

>7 fan—m+1 Д ?n—n»+l)

J' fan—in-\-l)-

Отдельно остановимся на случае,

когда векторы гп в (16)

вы­

бираются по закону: rn— Xnei+1,

где i — остаток

от деления

п

на

т,

О ^ г^ / п — 1, числа Л „>0 и Д п->-0

при

оо,

е ^=( 0, ...,

0,

1,

0,

. . . , 0) — единичный вектор

по

оси

Ou\

i— 1, 2, . . . ,

т.

Тогда система (16)

решается в явном виде и, как нетрудно видеть,

матрица Ап будет состоять из столбцов

7 ' (“п -г +

К —I ei) — 7 ' (un—j)

7* (un—._j_| Н- 7n_ i+ |gg) — J' Kt-t-|-i)

K -i

’

V - w

J ’ (“n +

—

J ’ (un)

J '(u„_m + |+

e [+2) — J ' (un_ m + l)

X

'

x m+1

’

(ип—i—1 ~t~^n—t—1e”»)

J

(un—i—l)

.

h - l - l

Для

сравнения

вспомним, что матрица J" (и)

состоит из столбцов

" дЧ (и ) -

“ ’дЧ (и ) ~

дихди1

5u15um

д ]' (и)

_

•

dJ'

(и)

ди1

’ " ’ ’

дит

^

дЧ (и)

дЧ (и)

ди"‘ди1

дитдит

Отсюда видно, что столбцы матрицы Ап представляют собой

разностную аппроксимацию

соответствующих столбцов матрицы

Г (и)

в специально

выбираемых точках,

и метод (15) — (17) пре­

ким

образом, метод (15) — (17) имеет

скорость

сходимости,

близ­

кую

к скорости сходимости метода

Ньютона

и в то же

время

шаге.

Для

квадратичной

функции,

определяемой

равенством

(7.7),

метод

(15) — (17)

сходится за

конечное

число

шагов [86].

Различные варианты метода

(15)— (17), обзор

близких

методов и

библиографию см. в [84],

[86],

[258].