01_Metodichka_bezuslovny екстремум

Спомнете си, че н - измерение на пространството на независимите променливи. Вариант Б) се различава от вариант А), който съдържа така наречената процедура по обновяване - за всеки к, множествена п. преход от точка до точка х к х к 1 се извършва както в метода от стръмните произход. Имайте предвид, че преходът от точка до точка х 0 х 1 се извършва по метода на най-стръмната произход, и в случай, че А) и в случай В).

4. Сближаване. Конвергенция на всеки метод, зависи от свойствата на е (х), началната точка х 0 и параметри на итеративен процес. Следната теоремата е полезно.

Теорема 1 ([1], s.47,83; [4], s.265). Да предположим, че F функция (х) е ограничен от по-долу, и градиент Lipschitz. Ако конструкцията на минимизиране последователност произведен по метода, съгласно претенция 1 или претенция 2, B) или претенция 3, В), след това независимо от началната точка х 0,

Ако точката х 0 е такава, че множеството К (х 0) = Неограничен, последователността се доближава до зададената S = стационарни точки на функцията F (х), т.е.

INF х - х к → 0. к → ∞.

Имайте предвид, че функциите на класа, определени в Теорема 1, много широк и включва стационарни точки като тези функции могат да бъдат не само глобални екстремуми точки, но и от гледна точка на локален екстремум и ездитни точки. Въпреки това, както е посочено в [5], градиентни методи, например, "почти никога" се събират на максималната точка или точка седло. В същото време, те не се прави разлика между местно и глобално минимум точка и се сближат и да е от тях (или по-скоро, вижте. [5], p.168).

Определи скоростта на сближаване за последователността на всеки от методите от претенции 1 - 3, може да се даде достатъчно тесни класове функции, показва много строги изисквания за гладкост и изпъкналост на F (х) функции. Помислете, например, в класа на два пъти непрекъснато диференцируема силно изпъкнали функции. Два пъти непрекъснато диференцируема функция е (х) се нарича силно изпъкнала в R п. ако е налице постоянна л. л> 0, така че за всички х R п имат

л у 2 ≤ (2 е (х) Y, Y). Y R п,

2, когато е (х) Hessian матрица (Hessian) на функцията F (х),

Ако конструкцията на последователността, произведен по метода съгласно претенция 2, B) или претенция 1, след това за всяка начална точка х 0, последователността клони към минималната точка х ¯ линейна скорост. В случая на метод съгласно претенция 1 константа Q = (L - L) / (L + L).

Ако повърхностният слой има сложна функция да бъде сведена до минимум силно удължен (канавки) структура, antigradient посока различава от посоката на минималната точка

и конвергенцията на градиентни методи се забавя. Това явление се нарича ефект на дере. Индикатор дере в съседство на функцията F минималната х ¯ (х) е съотношението на най-голямата собствена стойност на Hessian матрица 2 е (¯ X) до най-малкия ([5], вижте стр.28.). Колкото по-висока оценка, по-продълговати и стръмен "дере" ниво повърхност е (х) в съседство на х ¯

и се събират по-бавно в съседство с методите на градиент (виж [5]., стр.150).

Методът на конюгат градиент - скоростта на най-счита метод от първи порядък (виж [5], Ch.3 § 2 ..). За метода на конюгат градиент в случай на броя повторения значително по-голям размер п. следните резултати (виж [5]., стр.74).

Теорема 3. Нека функция F (х) три пъти диференцируема силно изпъкнала функция. След това последователността. изработена по метода съгласно претенция 3, В) клони към минималната точка х ¯ функция е (х) и в съседство на х ¯ притежава скорост конвергенция

х (к 1) п - х ¯ ≤ С х Кн - х ¯ 2. к = 1. 2.

За квадратна функция е (х) = 1 Февруари (Ах, х) - (Ь, х) (А - положително определен симетрична матрица) метод конюгат градиент клони в краен брой стъпки, които не надвишава броя п. Така последователни посоки р к отговарят на връзката (Ap т. Р к) = 0, I = ̸ J. т.е. Те са ортогонални в показателя дадено от матрица А, - ортогонална (А - конюгирано). Следователно - името на метода (виж [1] глава 2 § 3 ..).

Ролята на конвергенция теорема за практически изчисления види. Напр [5], c.39-43.

5. Критериите за край на процеса на повторение. теорема

1 дава възможност за края на итеративния процес за използване на състоянието на формата

Изборът на даден точност определя δ δ

Въпреки това, правилният избор на δ за дадена стойност на δ зависи от изкуството на калкулатора. "За съжаление, надеждни критерии за край на сметка, която ще гарантира получаването на решението на (1) до необходимата точност, и които са приложими към широк клас проблеми, но все пак" ([4], c.264). Тази забележка важи и за други методи, описани по-долу.

§2. втори методи ред.

Сред основните методи от втори ред са техники, свързани с идеята за местно сближаване на дадена функция от квадратна функция.

Нютон 1.Metod. За итеративни формули на този метод се използват следните евристичен съображения (вж. [5], стр.36). Ние напише функция F (х) в съседство на х к Taylor формула втория ред

е (х) = Q к (х) + о (х - х к 2). х - х к → 0;

Q к (х) = F (х к) + (е (х к). (Х-Х к)) + 01 февруари (2 е (х к) (х-х к). (Х-Х к)). (10)

В случая, когато Hessian 2 е (х к) е положително определена, на квадратна функция Q к (х) достигне глобален минимум в точка

х к 1 = х к - [2 е (х к)] - 1 е (х к),

(Q к (х к 1) = 0). Ако х к една точка е достатъчно близо до х к. след това от (10) неравенството

е (х к 1)

т.е. х к 1 е естествено да следното за х к приближение към разтвора на проблема (1). Формула (11) е итеративен метод формула Нютон. Така, в този метод, α к = 1,

р к = - [2 е (х к)] - 1 е (х к).

P к е почти по-удобно да не изглежда от формула (12) и решаването на системата от линейни уравнения

[2 е (х к)] р к = -f (х к)

един от най-преките и итерационни методи (вж. съответния лаборатория работата), като по този начин се елиминира Hessian на лечение на работа. Имайте предвид, че за квадратна функция F на (х) метод Newton клони в един етап. За достатъчно гладка функция е (х) с положителен определен Hessian матрица в правилния избор на първоначалната сближаване х 0 итеративен метод последователност Newton клони към минималната точка на квадратичен скорост. Въпреки това, да се намери добър начален приближение - задачата е доста сложна, изискваща определена чл. Промяна на Нютон въвеждане метод променлив фактор α к. приготвени методи слизане, че се събират за всяка първоначална сближаване на х 0.

2. Метод съгласно Newton-Raphson. При този метод, посоката на спускане се определя от формула (12), и α к фактор. коригиране на дължината на стъпалото, могат да бъдат избрани по следните начини:

А) съгласно метода от стръмните произход от минимум

е (х к + α к р к) = мин е (х к + αp к)

(Виж бележка в претенция 1, §1.); B), така че неравенството

е (х к + α к р к) ≤ е (х к) + εα к (е (х к). р к),

където ε (0,1 / 2) -napered предварително определена константа, еднакви за всички повторения. Алгоритъмът за намиране на коефициента α к са същите, както в градиент метода с смачкване стъпка. Първоначалната стойност

Теорема 4. (см. [2], Ch.2. § 2, алинея 2). Да предположим, че F функция (х) е два пъти непрекъснато диференцируема и изпълнена (6) и втората производни е удовлетворяват условието Lipschitz. Тогава един повтарящ