01_Metodichka_bezuslovny extremelor

Să ne amintim că n - dimensiunea spațiului variabilelor independente. Opțiunea B) diferă de varianta A), care conține o procedură de actualizare așa-numita - pentru fiecare k, multiplu de n. tranziția de la un punct la x k x k + 1 este executat ca în metoda cea mai abruptă coborâre. De notat că trecerea de la punct la punct x 0 x 1 se realizează în metoda cea mai abruptă coborâre, iar în cazul A) și în cazul B).

4. Convergența. Convergența oricărei metode depinde de proprietățile f (x), punctul inițial x 0 și parametrii procesului iterativ. Următoarea teoremă este utilă.

Teorema 1 ([1], s.47,83; [4], s.265). Să presupunem că funcția f (x) este delimitată de mai jos, iar gradientul sau Lipschitz. În cazul în care construcția secvenței minimizând produsă prin metoda conform revendicării 1 sau 2 B) sau revendicarea 3 B), atunci oricare ar fi punctul inițial x 0,

Dacă punctul x 0 este astfel încât setul K (x 0) = nelimitat, secvența converge mulțimii S = punctele staționare ale funcției f (x), adică

inf x - x k → 0. k → ∞.

Rețineți că funcțiile clasei specificate în Teorema 1, foarte larg, și includ puncte de staționare astfel de funcții pot fi nu numai un puncte Extrema, la nivel mondial, dar și în ceea ce privește punctele locale și a extremelor șa. Cu toate acestea, după cum se menționează în [5], metode de gradient, de exemplu, „aproape niciodată“ converg către punctul maxim sau punctul de șa. În același timp, ele nu fac distincție între punctul minim local și global și converg către oricare dintre ele (sau, mai degrabă, a se vedea. [5], p.168).

Estima rata de convergență pentru secvența fiecăreia dintre metodele de revendicările 1 - 3 poate fi dat un clase suficient de înguste de funcții, care prezintă cerințe foarte stricte pentru finețe și convexitate f (x) funcții. Luați în considerare, de exemplu, clasa de funcții puternic convexe de două ori continuu diferentiabile. De două ori în mod continuu funcția diferențiabilă f (x) este numit un puternic convex în R n. în cazul în care există un l constant. l> 0, astfel încât pentru orice x R n au

l y 2 ≤ (2 f (x) y, y). y R n,

2 unde f (x) matricea Hessian (Hessiană) a funcției f (x),

În cazul în care construcția secvenței produse prin metoda conform revendicării 2 B) sau revendicarea 1, atunci pentru orice punct inițial x 0, secvența converge la punctul x minim ¯ o viteză lineară. În cazul metodei conform revendicării 1, constanta q = (L - l) / (L + l).

În cazul în care stratul de suprafață au o funcție complexă care trebuie minimizate (rigole) foarte alungită structură, direcția antigradient diferă de direcția punctului minim

și convergența metodelor de gradient este încetinirea. Acest fenomen se numește efectul viroage. Indicator făgaș în vecinătatea minimă x ¯ funcția f (x) este raportul dintre cea mai mare valoare proprie a matricei Hessian 2 f (¯ x) la cea mai mică ([5], vezi p.28.). Cu cât mai mare scor, mai alungite și un abrupt „gully“ suprafață orizontală f (x) într-o vecinătate a lui x ¯

și converg mai lent în vecinătatea metodelor de gradient (vezi [5]., p.150).

Metoda gradient conjugat - viteza metodei de ordinul cel mai bine luate în considerare (a se vedea [5], Cap.3 § 2 ..). Pentru metoda de gradient conjugat în cazul în care numărul de iterații semnificativ mai mare dimensiune n. rezultatul următor (a se vedea [5]., p.74).

Teorema 3. Fie de trei ori diferențiabilă funcția puternic convexă funcția f (x). Apoi, secvența. construite prin metoda din revendicarea 3 B) converge la punctul de minim x ¯ funcția f (x), și într-o vecinătate a lui x ¯ deține rata de convergență

x (k + 1) n - x ¯ ≤ C x kuna - x ¯ 2. k = 1. 2.

Pentru funcția pătratică f (x) = 1 februarie (a Ax, x) - (b, x) (A - definit simetrică matrice pozitiv) metoda de gradient conjugat converge într-un număr finit de pași care nu depășește numărul n. Astfel direcții succesive p k satisfac relația (Ap i. P j) = 0, i = ̸ j. și anume Ele sunt ortogonale în metrica dată de matricea A, A - ortogonale (A - conjugat). De aici - numele metodei (vezi [1] Capitolul 2 § 3 ..).

Rolul teoremă de convergență pentru calcule practice vezi. De exemplu, [5], c.39-43.

5. Criteriile de sfârșitul procesului iterativ. teoremă

1 face posibilă încheierea procesului iterativ pentru a utiliza condiția formei

Alegerea unui anumit precizie determinată δ δ

Cu toate acestea, alegerea dreptul de δ pentru o anumită valoare a δ depinde de arta calculator. „Din păcate, criterii fiabile pentru sfârșitul contului, ceea ce ar garanta obținerea soluției de (1) la precizia necesară și care se aplică la o clasă largă de probleme, dar“ ([4], c.264). Această observație se aplică și altor metode descrise mai jos.

§ 2. metode de ordinul doi.

Printre metodele de bază de ordinul a doua sunt tehnici legate de ideea de o aproximare locală a unei funcții date de o funcție pătratică.

Newton 1.Metod. Pentru formulele iterative ale acestei metode folosesc următoarele considerații euristice (vezi [5]., P.36). Scriem functia f (x) într-o vecinătate a lui x k Taylor formula de ordinul 2

f (x) = Q k (x) + o (x - x k 2). x - x k → 0;

Q k (x) = f (x k) + (f (x k). (X-x k)) + 1 februarie (a 2 f (x k) (x-x k). (X-x k)). (10)

În cazul în care Hessian 2 f (x k) este pozitiv definită, quadratic funcția Q k (x) atinge un minim global la punctul

x k + 1 = x k - [2 f (x k)] - 1 f (x k),

(Q k (x k + 1) = 0). Dacă x k + 1 punct este suficient de aproape de x k. apoi prin (10) inegalitatea

f (x k +1)

și anume x k +1 este natural să ia următoarele pentru x k aproximarea la soluția problemei (1). Formula (11) este formula iterativa metoda Newton. Astfel, în această metodă, α k = 1,

p k = - [2 f (x k)] - 1 f (x k).

P k este aproape mai convenabil să nu se uite de formula (12) și rezolvând sistemul de ecuații liniare

[2 f (x k)] p k = -f (x k)

una dintre metodele directe sau iterativă (vezi. lucrarea de laborator corespunzătoare), eliminând astfel Hessianul tratament operație. Rețineți că pentru funcția pătratice f (x) Metoda Newton converge într-un singur pas. Pentru funcționare suficient de netedă f (x) cu o matrice Hessiană pozitiv definită la alegerea corectă a aproximarea inițială a x 0 secvență iterative metoda Newton converge la punctul minim la o rată pătratică. Cu toate acestea, pentru a găsi o aproximare inițială bună - sarcina este destul de complex, care necesită o anumită artă. Modificarea metodei Newton introducere factor variabil α k. metode de coborâre preparate care converg pentru orice aproximare inițială a x 0.

2. Metoda Newton-Raphson. În această metodă, direcția de coborâre este definită prin formula (12), și factorul α k. ajustarea lungimii pas poate fi selectat în următoarele moduri:

A) în metoda cea mai abruptă coborâre din minimul

f (x k + α k p k) = min f (x k + αp k)

(A se vedea nota în revendicarea 1 § 1.); B) astfel încât inegalitatea

f (x k + α k p k) ≤ f (x k) + εα k (f (x k) p. k),

unde ε (0,1 / 2) -napered constantă predeterminată, aceeași pentru toate iterații. Algoritmul de a găsi factorul α k sunt aceleași ca și în metoda de gradient cu strivire pas. Valoarea inițială

Teorema 4. (cm. [2], Ch.2. § 2, paragraful 2). Să presupunem că funcția f (x) este de două ori continuu diferențiabilă și executat (6) și al doilea derivatele f satisfac condiția Lipschitz. Apoi o iterativ