Оптимізація балансу АКБ "Правекс-Банк" з метою покрашення його фінансових показників
Дипломная работа - Банковское дело
Другие дипломы по предмету Банковское дело
рацію шукають з умови
,
де ln деякий параметр (свій на кожному кроці). Перші три додатки у визначенні функції ??є квадратичною апроксимацією функції f, а останній доданок "штраф", що не дозволяє точці xn+1 відходити далеко від точки xn. Мінімум (принаймні стаціонарна точка) функції ??обчислюється в явному вигляді з наступного рівняння (щодо x):
Q = ??(x) = f?(xn) + f??(xn)(x ?xn) + ln(x? xn).
Як легко побачити:
xn+1 = argmin?(x) = xn ? [f??(xn) + lnI]?1f?(xn). (2.16)
Остання формула і є метод Льовенберга-Маркардта.
Очевидно, що якщо ln= 0, то (2.22) і є метод Ньютона, а якщо ln велике, то (оскільки [f??(xn) + lnI]?1 ? (ln)?1I при великих ln) формула (2.16) близька до градієнтного метода. Тому, підбираючи значення параметра ln, можна добитися, щоб метод (2.16), по-перше сходиться глобально, і по-друге квадратично. Можна, наприклад, вибирати ln з наступних міркувань: кут між напрямами кроку і антиградієнтом повинен бути гострим, а значення функції на кожному кроці повинне кваліфіковано убувати. В цьому випадку ln повинне задовольняти наступним умовам (тут ми позначаємо „анти напрямок” кроку [f??(xn) + lnI]?1f?(xn) через yn):
f(xn+1) ? f(xn) ? ?2(yn, f?(xn)),
де ?1 ? (0, 1) и ?2 ? (0, 1/2) - параметри.
Проте, як завжди, існує ще один недолік методу Ньютона, тому розглянемо - модифікований метод Ньютона. В деяких задачах більш істотним недоліком методу Ньютона є його велика обчислювальна трудність: на кожному кроці потрібне обчислення оператора (матриці) f??(xn) і його (її) обіг, що при великих розмірностях коштує в обчислювальному плані дуже дорого. Один із способів обходу цих труднощів полягає в „заморожуванні” оператора f??(xn) - використовуванні на [f??(x0)]?1 замість [f??(xn)]?1:
xn+1 = xn ? [f??(x0)]?1f?(xn). (2.17)
Рисунок 2.2 - Геометрична інтерпретація модифікованого методу Ньютона
Можна показати, що при природних обмеженнях модифікований метод Ньютона сходиться лише лінійно (це платня за зменшення обєму обчислень). Можна також не заморожувати оператор [f??(xn)]?1 назавжди, а обновляти його через певне число кроків, скажімо до:
xn+1 = xn ? [f??(x[n/k]k)]?1f?(xn), (2.18)
Можна довести, що якщо функція f сильно випукла і f?? задовольняє умові Липшиця, то
||xn+k ? x*|| ? C||xn ? x*||k+1,
тобто за k кроків порядок погрішності зменшується в k+1 разів, що відповідає наступній оцінці погрішності на кожному кроці:
||xn+1 ? x*|| ? C||xn ? x*||k?k+1.
Іншими словами, метод (2.18) є методом k?k+1-го порядку збіжності. Таким чином, метод (2.18) займає проміжне положення між методом Ньютона (k=1) і модифікованим методом Ньютона (2.17) (k=?) як по швидкості збіжності, так і за обємом обчислень.
Інший спосіб зменшення обєму роботи, повязаного з обчисленням функції f??(xn) можна описати так. Метод січних рішення рівняння (2.11) полягає в наближеній заміні функції F в рівнянні не дотичної y=F(xn)+F?(xn)(x-xn), а січною гіперплощиною. Наприклад, в одновимірному випадку - прямою y=F(xn)+(F(xn)?F(xn?1))(x-xn)/(xn?xn?1) (див. рис.2.3). Ця заміна призводить (в скалярному випадку!) до наступного методу рішення задачі (2.10):
(2.19)
який і називається методом січних. Відомо, що для достатньо гладких випуклих функцій порядок сходимісті цього методу рівний ?, де ?=(??+1)/2?1.618 - відома константа (звана золотим перетином).
Рисунок 2.3. - Геометрична інтерпретація одновимірного випадку метода січних рішень
В багатовимірному випадку поступають таким чином. Хай xn, xn?1, ..., xn?m - вже обчислені m + 1 ітерації. Для кожної компоненти fj? функції f?(j=1..., m) побудуємо в Rm+1 гіперплощину Sj, що проходить через m+1 точку (xi, fj?(xi)) (i = n?m,..., n) графіка цієї компоненти. Хай P „горизонтальна гіперплощина, яка проходить через нуль” в Rm+1: P = {(x, y)? RmR; y = 0}. Як xn+1 візьмемо точку перетину гіперплощин P і Sj:
(в загальному положенні ця точка єдина).
Нескладні міркування показують, що xn+1 можна обчислювати так. Хай ?0,...,?n - рішення системи
(2.20)
Тоді
Потім описані дії повторюються для точок xn+1, xn, ..., xn?m+1.
Відзначимо, що оскільки на кожному кроці в системі (2.20) змінюється лише один стовпець, то її рішення на кожному кроці можна обновляти за допомогою спеціальної процедури, що не вимагає великого обєму обчислень.
Відзначимо, що метод сікучих, на відміну від методів, що раніше розглядалися, не є одно кроковим в тому значенні, що для обчислення наступної ітерації йому не достатньо інформації, отриманої на поперед?/p>