Розвиток теорії надання банківських послуг на прикладі ДФ АБ "Правексбанк" (стр. 9 из 13)
і взяти як наступне наближення рішення рівняння:
(2.24)
то ми отримаємо формулу (2.22).
Стосовно задачі (2.20) ці міркування виглядають так. Нехай так само, у нас вже є деяке наближене рішення xn задачі (2.20). Замінимо в ній функцію f її наближенням другого порядку:
і як наступне наближення візьмемо рішення задачі:
(2.25)Та на початку для подальшого використання виведених формул, необхідно довести деякі твердження - якщо f (xn) > 0, то рішення задачі (2.25) задається формулою (2.23).
Рис. 2.3- Геометрична інтерпретація формул (2.22) і (2.23) відповідно
Метод Ньютона відноситься до методів другого порядку, оскільки дляобчислення кожної ітерації потрібне знання другої похідної функції f. По тих же міркуваннях градієнтний метод відносять до методів першого порядку. Підкреслимо, що тут йдеться не про порядок збіжності методу, а про порядок використовуються методом похідних функції, що мінімізується.
2.2.2 Теорема про локальну надлінійну збіжність методу Ньютона
Хай f двічі безперервно і може бути диференційована, а x* - не вироджена стаціонарна точка. Тоді знайдеться околиця Vx* точки x* така, що наближення (2.13), початі з довільної початкової точки x0Vx*сверх лінійно сходяться до x*.
Доведемо: так як F = f C1 і тому
(2.26)Оскільки F (x*) не вироджений, в силу (2.26) при x достатньо близьких до x* не вироджений і оператор F (x) і більш того,
Тому, зокрема, при x достатньо близьких до x*
||[F (x)]1|| C. (2.27)
Далі, внаслідок того, що F можна диференціювати, а x*- стаціонарна точка
F(x) = F(x*) + F (x*)(xx*) + o(x-x*) = F (x*)(xx*) + o(x-x*),
Але тоді в силу (2.27)
xx* [F (x)]1F(x) = [F (x)]1F (x)(xx*) [F (x)]1F(x) =
[F (x)]1[F (x)(xx*) F(x)] = o(xx*).
або
x [F (x)]1F(x) x* = o(xx*).
Зокрема, при x = xn
(2.28)Візьмемо тепер як Vx*, наприклад, околиця {x Rm: ||(xx*)|| ||xx*||/2}. В силу (2.28), очевидно, якщо x0Vx*, то
отже, xnx*при n. Більш того, для довільного q(0, 1) знайдеться >0 таке, що ||(xx*)|| q||xx*|| при ||xx*||.Але тоді, якщо ||xnx*|| то ||xn+1x*|| q||xnx*||. З останнього твердження очевидним чином витікає потрібне співвідношення ||xnx*|| Cqn.
Таким чином метод Ньютона, з одного боку, може сходитися з більш високим ніж градієнтний методпорядком, а, з другого боку, для його збіжності потрібні достатньо добрі початкові наближення (принаймні так потрібен в доведеній теоремі). Простий геометричний приклад (див. рис. 2.4) підтверджує цю особливість методу (ми наводимо приклад для рівняння (2.21); відповідний приклад для задачі (2.20) виходить „інтеграцією” рис. 2.4).
Рис. 2.4 - Геометричне відображення прикладу
Зрозуміло, як метод другого порядку, метод Ньютона вимагає більшого об'єму обчислювальної роботи, оскільки доводиться обчислювати другі похідні функції f.
До цього зводяться основні переваги (високий порядок збіжності) і недоліки (локальний характер збіжності і більший об'єм обчислень) методу Ньютона.
Якщо функція f додатково сильно опукла, то можна затверджувати збіжність саме до рішенню задачі (1), а не тільки до стаціонарної точки функції f, і, крім того, оцінити радіус околиці, з якої наближення Ньютона сходяться.
2.2.3 Теорема про квадратичну збіжність методу Ньютона
Хай fC2і, більш того, f задовольняє умові Липшиця з константою L. Хай f сильно випукла с константою. Хай Vx* - околиця рішення задачі (2.10), що складається з точок x Rm таких, що
Тоді для x0Vx*метод Ньютонаквадратично сходиться:
де q = L||f (x0)||/22 < 1.
По теоремі 2.9 і 2.10 в умовах нашої теореми рішення x* задачі (2.10) існує і єдино. Скористаємося аналогом формули Ньютона-Лейбніца для функції f :
Віднімаючи з обох частин цієї рівності
враховуючи, що f задовольняє умову Липшиця, одержуємо (ср.): 
Покладемо в отриманій оцінці h = [f (xn)]1f (xn):
(2.29)Також необхідно довести, що якщо оборотний лінійний оператор АнаRmзадовольняє оцінціА і , то ||A1|| .
Оскільки f сильно опукла, в силу задачі (2.25), f (xn) і тому (див. попер. задачу) ||[f (xn)]1|| 1. Продовжуючи нерівність (2.19), одержуємо:
(2.30)З допомогою (2.30) індукцією по n легко доводиться нерівність:
(2.31)Нарешті, в силу сильної випуклості f, оскільки x* — рішення задачі (2.20) і, отже, f (x*) = Q,
0 f(x*) f(xn) (f (xn), x* xn) + ||xnx*|| 2,
або
(f (xn), xnx*) || xnx*|| 2.
Але тоді
||xnx*|| 2 (f (x*), xnx*) ||f (x*)|| · ||xnx*||,
звідки ||f (x*)|| || xnx*||. Тоді з (2.31) слідує потрібна нерівність.
З доведеної теореми витікає, що чим менше константа Липшиця відображення x f (x), тобто чим ближче це відображення до константи, і, отже, чим ближче функція f до квадратичної, тим швидше сходиться метод Ньютона. Зокрема, якщо f квадратична: f(x) = (Ax, x)/2 + (b, x) + c, то метод Ньютона кінцевий, а саме, сходиться за один крок, причому з будь-якої початкової точки.
Якщо понизити вимоги гладкості на функцію f, наприклад, відмовитися від умов Липшиця для f , то швидкість збіжності, взагалі кажучи, падає.
Покажемо, що f(x)= |x|5/2 метод Ньютона сходиться лише лінійно.
Метод Ньютона навіть для сильно випуклих функцій в загальному випадку сходиться лише локально. Опишемо модифікації цього методу, які можуть володіти властивістю глобальної збіжності. Ці методи ще називають методами Ньютона — Рафсона, або демпфованими методами Ньютона. Вони будуються аналогічно з градієнтними методами с перемінним кроком. Загальний вид їх такий:
xn+1 = xnn[f (xn)]1f (xn).
Довжина кроку може вибиратися за допомогою алгоритму дроблення кроку, вимагаючи, наприклад, виконання нерівності:
f(xn+1)=f(xnn[f (xn)]1f (xn))
f(xn) n(f (xn), [f (xn)]1f (xn)),
або, як в методі самого скорішого спуска, вважаючи
n = argmin0{f(xn[f (xn)]1f (xn))}.
Можна показати, що методи Ньютона — Рафсона для сильно випуклих функцій глобальноквадратично сходяться (принаймні для описаних вище алгоритмів вибору кроку), причому оддалік точки мінімуму вони сходяться лінійно.
3. ОПТИМІЗАЦІЯ БАНКІВСЬКИХ ПОСЛУГ