М Бартіш - Модифікація рекурсивного методу ньютона - страница 1

Страницы:
1  2 

ВІСНИК ЛЬВІВ. УН-ТУ Серія прикл. матем. інформ. 2010. Вип. 16. C. 3-9

VISNYK LVIVUNIV. Ser. Appl. Math. Inform. 2010. Is. 16. P. 3-9

ОБЧИСЛЮВАЛЬНА МАТЕМАТИКА

УДК 519.6

МОДИФІКАЦІЯ РЕКУРСИВНОГО МЕТОДУ НЬЮТОНА М. Бартіш, Н. Огородник

Львівський національний університет імені Івана Франка, вул. Університетська, 1, Львів, 79000, e-mail: ogorodnyk.nataly@gmail.com

Розглянуто ітераційний рекурсивний процес на базі методу типу Ньютона для розв'язування задач безумовної мінімізації. В запропонованому процесі протягом t кроків зберігається незмінним значення другої похідної функції. Досліджено збіжність рекурсивного процесу та визначено порядок збіжності. Досліджено проблему вибору оптимальної глибини рекурсії. Проведено числові експерименти.

Ключові слова: метод Ньютона, рекурсивний процес, оптимальна глибина рекурсії.

1. ВСТУП

Математичне моделювання реальних процесів часто потребує розв'язування задач оптимізації. Знайти явний розв'язок задачі на екстремум вдається дуже рідко, проте з появою обчислювальної техніки стало можливим будувати алгоритми, які допомагають знайти наближений розв'язок задачі з певною точністю. Сьогодні складність задач постійно збільшується, крім того, не завжди вдається вдало підібрати метод розв'язування, тому і надалі залишається актуальною проблема побудови та дослідження нових методів обчислювальної математики.

Відомим класом розв' язування операторних рівнянь і задач мінімізації є ітераційні рекурсивні процеси. В працях [1, 4] запропоновано підхід до побудови ітераційних формул, які виводять за допомогою рекурсії. В методах такого типу значення матриці Якобі або Гессе обчислюють у деякій точці і використовують незмінним протягом наступних t кроків. Зрозуміло, що важливо правильно підібрати значення t для отримання оптимальної, в сенсі кількості обчислень, глибини рекурсії і, відповідно, мінімальних загальних витрат для отримання розв'язку [2]. Методи розв'язування систем нелінійних рівнянь подібного типу запропоновано в [6, 7], проте автори досліджують лише випадки з глибиною рекурсії 2 та 3.

В статті запропоновано та досліджено рекурсивний процес на базі методу типу Ньютона, визначено швидкість збіжності, показано, що вона залежить від глибини рекурсії. Проведено числовий експеримент.

2. ФОРМУЛЮВАННЯ ЗАДАЧІ Розглянемо задачу безумовної мінімізації

f (x) — min,     x є Rn. (1) Одними з базових методів розв'язування задачі (1) вважають метод Ньютона та  градієнтний   метод   [3].  Використовуючи   ці   методи,  запропонували таку модифікацію методу Ньютона для розв' язування (1):

© Бартіш М., Огородник Н., 2010

= xt -[Г(^)]1 f'(xt), (2)

де проміжне наближення vk обчислюємо за допомогою градієнтного методу.

На підставі алгоритму (2) побудовано такий ітераційний рекурсивний процес vk = xk -akf \xt ),

*t = 4 - [f {^jV //), (3)

= xk,     4 = 0,1,...,'-\, at = arg min f (/ - qf ,(xk)).

a

TT - r»[ Xk + vk )

Цей процес використовує значення матриці других похідних f І —-- І

незмінними протягом t проміжних кроків. Процес (3) доцільно використовувати у випадку, коли обчислення матриці других похідних трудомістке.

3. ОБҐРУНТУВАННЯ ЗБІЖНОСТІ

Теорема 1. Нехай:

1) функція f (x)e C2(я") сильно опукла і для xє D , y є Я" виконується

НМІ2 —(/ "(x)y> У)- МІНІ',

де 0 < m — M , M, m = const , D = -|x : ||x - x0|| - 1| f '(x|j - опукла область;

2) Vx, y є D, f (x) задовольняє умову Ліпшиця

|f"( x) - f"( y)\\ L\\x - y||,

де 0 < L < °°;

3) початкове наближення x0 вибирають таким, що виконується умова

М = C||x0 - x»| < 1.

Тут C = —(3 + Y), -<Y< 1.

2m M + m

Тоді послідовність  {xk} породжена рекурсивним процесом (3), коректно визначена та збігається до x, і справджується оцінка

ґ   і-\(t+i)k

М',1

x0 - x<

Доведення.

Існування та єдиність розв'язку випливає з властивості сильно опуклих функцій [3]. Із сильної опуклості також випливає оцінка

||(/"(x НІ — 1.

2

2

f '{xl)- x* f"( ^ j - f'(/ + t(x° - x,

m

x0 + vk

2

x,   Tl xk x,

де 0 < t < 1.

З того, що vk обчислюємо за допомогою градієнтного методу, одержуємо

оцінку

ІЬ - x,|| Yxk - x-|, (4)

тоді

2

x,   t\ xk x,

1 - 2d,

Y\\. о

(1 + r)\\x о

|xk - x.|| + j| |xk - x-| ^Y^         - x'll

Отримаємо

II і      II L (1 + r)) о      II2   C 1 + r || 0 II2

xk - x, —-(1 + Y))xk - xA = C-\\xk - x,

II k      II   2m        ^ k       11        3 + y" 11

Для 4 = 1 одержуємо

VI - x,

x0 + vk

2

x,   t\x k x,

x1 - x,

L   IIx0 - x' II+1 lxk- x^l )llx1 - x^l2mm(3+rr)x0 - x,l И- x

m \ 2

C 21    1 )||    0 II

C І--IIxk - x.

\ + r)

оцінка

Використаємо метод математичної індукції. Нехай для деякого s правильна

xk - x, C

1 jll 3 + rf

тоді для s +1 аналогічно отримаємо

■xA—-

L

2

x,   t 1 x k x,

xk - x, 

mm [1^llx0 - x,l+1 lxk- x,ll )l xk- x,l2mm(3+rlx- x,l lxk- x,l

2m

Cllxk -x.llCІ ^llx0 -xJIS+1 = CsA 1+L\x0 -x,ir

i + rf

s + r)

-1

­-1

f

L

s+1

m

Тобто,

ы - хЛC'|i +r iix0

3

+ r)

Застосуємо   метод   математичної   індукції   для   k = 0,1,....   Для   k = 0, використавши умову 3, одержимо

II ' ......^nt І 1 + r III      II'+1

x0 - x,\\ = x - x, C I-I x0 - x.ll =

II 0 1      "       1 3 + r)

Ml

3 + r

x0 - x-

1 + r

K\ 3 + r J

x0 - x-

При k = 1 11x^1   x, II I jxx 2   x, II CC

1m

1 + r

ll'+1 s x1 - xA

,[1+7

Ct

1 + r

[+r

1 + r

ГУ 3+r j

) (+1)+

x0 - x-

1 + r

Припустимо, що ця оцінка виконується для x3, x4 ..., xk, тобто,

lx0- x4 =

x0 - x-

1 + r

)((+

Ь + r J x0 - x4

Тоді

ll'+1

1 + r

{ \3 +r

1 + r

Страницы:
1  2 


Похожие статьи

М Бартіш - Модифікація рекурсивного методу ньютона

М Бартіш - Модифікація методу стеффенсена для розв'язування систем нелінійних рівнянь

М Бартіш - Трикрокові методи розв'язування задач безумовної мінімізації