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

Всі методи, розглянуті вище, відносяться до методів першого порядку, оскільки вони використовують лише перші похідні мінімізуємої функції. В усіх цих методах для визначення напрямку зменшення функції використовується лише лінійна частина розкладення функції в ряд Тейлора. Якщо мінімізуєма функція двічі неперервно диференційована і похідні ./'(«), Л{и) обчислюютьсядостатньо просто, то можна застосовувати методи мінімізації другого порядку, які використовують квадратичну частину розкладення цієї функції в ряд Тейлора.

Розглянемо один з таких методів - метод Ньютона, який сходиться з квадратичною швидкістю.

Розглянемо метод Ньютона для задачі

./(«)->тіп;  и<=и = Е„ (3.28)

де Ли)<=С2{Еп). Нехай щ<=Еп - деяке початкове наближення.

Якщо відоме наближення ик, то прирощення функції J(u) є С2 (Еп) в точці щ можна представити в вигляді

J(u)-J(uk) = {J\uk),u-uk) + ^(J\uk)(u-uk),u-uk} + ()^]iu-uk\2'j

Розглянемо квадратичну частину цього прирощення

л(«)-И«і).«-«і)+^'Ю(«-«* ).«-«*> <3-29)

і відзначимо допоміжне наближення Щ з умови

Л(«*)=«*Л(«)- (з-зо)

А,

Наступне (к +1) - е наближення будемо шукати у вигляді

=«*+«*(«*-«*),  0 <    < 1. (3.31)

В залежності від способу вибору величини ак в (4) можна

одержати різні варіанти методу (3.29) - (3.31). Найбільш часто використовують такі: 1) покладемо

а* = ІД = 0,1,... (3.32)

в цьому випадку =Щ (£ = 0,1,...,), тобто умова (3.30) одразу визначає (к+1)-е наближення. Іншими словами,

Л(«і+і)=и^Л(«Х *=о,і,..., (3.33)

Відомо, що то в точці мінімуму функції Jt(u) її похідна дорівнює 0, тобто

4(иш) = 4(ч) + Г(щ)(щ+і-щ) = 0. (3.34)

Це означає, що на кожній ітерації методу (3.29) - (3.32) або (3.33) треба розв'язувати систему лінійних алгебраїчних рівнянь (3.34) відносно невідомої різниці Якщо матриця цієї системи

•/"(и* ) - не вироджена, то з (3.34) маємо

Ч«=Ч-(Лч))~1А»к),  * = 0Л... (3.35)

2) в якості ак в (3.31) можна прийняти ак=Л'°,

де ц - мінімальний серед / > 0 номер, для них виконується нерівність

Кч )"•/("*+ * (ч -»к))*    |л (»к )|, (3.36) де Л,є - параметри метода, Л>0, є<1.

3) можливий вибір ак в (3.31) зумов [8]

0<ак<1, А((Гі)=шшЛ(а),

_ °£а£І (3.37)

/к(а) = -і{ч+а(ик-ч))-

Відзначимо, що метод Ньютона з вибором довжини кроку щ за

правилами (3.36), (3.37) являється аналогічним відповідним варіантам методу умовного градієнта.

Метод Ньютона для розв'язання задачі (3.28) звичайно застосовується в тих випадках, коли обчислення похідних У'(и),/"(«)

не викликає особливих труднощів і допоміжна задача (3) розв'язується достатньо просто. Достоїнством методу Ньютона являється висока швидкість сходимості. Тому хоч трудомісткість кожної ітерації цього методу вище ніж в методах першого порядку, але   загальний   об'єм   обчислювальної  роботи,   необхідної длярозв'язання задачі (3.28) з заданою точністю, з застосуванням методу Ньютона може виявитися меншим ніж коли будуть використовуватися більш прості методи.

Сходимість   методу   Ньютона   встановлюється наступною теоремою.

Теорема 1.    Нехай функція j(u) сильно випукла на Е„,

J(u) є С2 (Еп) і, крім того,

||y(M)-J'(v)||<or|M-v|, u,v<=En, j а = const > 0.

нехай початкове наближення к0 вибране таким, що

a\j'(u0]<2M2g> (3.39) де /і >0 - стала, така, що

(Г{и)и,и)±цЦ2,Чи^Ел,

q - деяка стала 0 < q <1. Тоді послідовність {ик}, яка визначається умовами (3.35), існує, сходиться до точки и, мінімуму j{u) на Еп, причому, справедлива оцінка

|в, -и.| < 2рГ^2\к = 0,1,..., (3.40)

(без доведення).