Pravila za vnos funkcij:

Ustvari navodila za iskanje, v v večji meri ki ustreza geometriji funkcije, ki jo minimiziramo.
Opredelitev . Imenujemo dva n-dimenzionalna vektorja x in y konjugiran glede na matriko A (ali A-konjugat), če skalarni produkt(x, Aу) = 0 . Tukaj je A simetrična pozitivno določena matrika velikosti n x n.

Shema algoritma metode konjugiranega gradienta

Metoda Fletcher-Reeves

Algoritem metode Fletcher-Reeves

Konvergenca metode

Primer. Poiščite minimum funkcije z metodo konjugiranega gradienta: f(X) = 2x 1 2 +2x 2 2 +2x 1 x 2 +20x 1 +10x 2 +10.
rešitev. Kot smer iskanja izberite vektor gradienta na trenutni točki:

Newtonova metoda in kvazi-Newtonove metode, obravnavane v prejšnjem odstavku, so zelo učinkovite kot sredstvo za reševanje problemov neomejenega minimiziranja. Vendar pa predstavljajo precej visoke zahteve glede na količino uporabljenega računalniškega pomnilnika. To je posledica dejstva, da izbira smeri iskanja zahteva reševanje sistemov linearne enačbe, kot tudi z nastajajočo potrebo po shranjevanju matrik tipa Zato je za velike uporaba teh metod morda nemogoča. V veliki meri so metode konjugirane smeri osvobojene te pomanjkljivosti.

1. Koncept metod konjugirane smeri.

Razmislite o problemu minimiziranja kvadratne funkcije

s simetrično pozitivno določeno matriko A. Spomnimo se, da njena rešitev zahteva en korak Newtonove metode in ne več kot korake kvazi-Newtonove metode. Metode konjugirane smeri prav tako ne omogočajo, da najdete minimalno točko funkcije (10.33). kot koraki. To lahko dosežemo s posebnim izborom smeri iskanja.

Rekli bomo, da so neničelni vektorji medsebojno konjugirani (glede na matriko A), če za vse

Z metodo konjugiranih smeri za minimiziranje kvadratne funkcije (10.33) razumemo metodo

pri katerem so smeri medsebojno sprežene, in koraki

dobimo kot rešitev enodimenzionalnih problemov minimizacije:

Izrek 10.4. Metoda konjugiranih smeri vam omogoča, da najdete najmanjšo točko kvadratne funkcije (10 33) v največ korakih.

Metode konjugiranih smeri se med seboj razlikujejo po načinu konstruiranja konjugiranih smeri. Najbolj znana med njimi je metoda konjugiranega gradienta.

2. Metoda konjugiranega gradienta.

Pri tej metodi navodila sestavljajo pravilo

Ker prvi korak te metode sovpada s korakom metode najstrmejšega spusta. Lahko se pokaže (tega ne bomo storili), da so smeri (10.34) res

konjugiran glede na matriko A. Poleg tega se izkaže, da so gradienti medsebojno pravokotni.

Primer 10.5. Uporabimo metodo konjugiranega gradienta za minimiziranje kvadratne funkcije – iz primera 10.1. Zapišimo ga v obliki kje

Vzemimo začetni približek

1. korak metode sovpada s prvim korakom metode najstrmejšega spusta. Zato (glej primer 10.1)

2. korak. Izračunajmo

Ker se je rešitev izkazala v dveh korakih.

3. Metoda konjugiranega gradienta za minimiziranje nekvadratnih funkcij.

Da bi se ta metoda uporabila za zmanjšanje poljubnega gladko delovanje Formula (10.35) za izračun koeficienta se pretvori v obliko

ali na razgled

Prednost formul (10 36), (10.37) je, da ne vsebujejo eksplicitno matrike A.

Funkcijo minimiziramo z metodo konjugiranega gradienta v skladu s formulami

Koeficienti se izračunajo po eni od formul (10.36), (10.37).

Iterativni proces se tukaj ne konča več končno število koraki in smeri na splošno niso konjugirane glede na neko matriko.

Enodimenzionalne minimizacijske probleme (10.40) je treba rešiti numerično. Opažamo tudi, da pogosto pri metodi konjugiranega gradienta koeficient ni izračunan z uporabo formul (10.36), (10.37), ampak se predpostavlja enako nič. V tem primeru se naslednji korak dejansko izvede po metodi najstrmejšega spusta. Ta »posodobitev« metode nam omogoča zmanjšanje vpliva računske napake.

Za močno konveksno gladko funkcijo za nekatere dodatni pogoji Metoda konjugiranega gradienta ima visoko superlinearno konvergenčno stopnjo. Hkrati je njegova delovna intenzivnost nizka in je primerljiva s kompleksnostjo metode najstrmejšega spusta. Kot kaže računalniška praksa, je po učinkovitosti nekoliko slabša od kvazi-Newtonovih metod, vendar postavlja bistveno nižje zahteve za uporabljeni računalniški pomnilnik. V primeru, ko je problem minimiziranja funkcije z zelo veliko število spremenljivk se zdi metoda konjugiranega gradienta edina primerna univerzalna metoda.

Računalniške poskuse za oceno učinkovitosti vzporedne različice metode zgornje relaksacije smo izvedli pod pogoji, navedenimi v uvodu. Da bi oblikovali simetrično pozitivno določeno matriko, so bili elementi podmatrike generirani v območju od 0 do 1, vrednosti elementov podmatrike so bile pridobljene iz simetrije matrik in , elementi na glavna diagonala (podmatrika) je bila generirana v območju od do , kjer je velikost matrike.

Kot merilo ustavljanja smo uporabili kriterij ustavljanja za točnost (7.51) s parametrom a iteracijski parameter . V vseh poskusih je metoda v 11 ponovitvah našla rešitev z zahtevano natančnostjo. Kot pri prejšnjih poskusih bomo popravili pospešek v primerjavi z vzporedni program, ki teče v eni niti.

7.50.

Poskusi kažejo dobro pospeševanje (približno 4 na 8 niti).

Metoda konjugiranega gradienta Razmislite o sistemu linearnih enačb (7.49) s simetrično, pozitivno določeno matriko velikosti . Osnova metoda konjugiranega gradienta je naslednja lastnina

: reševanje sistema linearnih enačb (7.49) s simetrično pozitivno določeno matriko je enakovredno reševanju problema minimiziranja funkcije

Gre na ničlo. Tako lahko rešitev sistema (7.49) iščemo kot rešitev problema brezpogojne minimizacije (7.56).

Zaporedni algoritem

Da bi rešili problem minimizacije (7.56), je organiziran naslednji iterativni proces.

Pripravljalni korak () je določen s formulami

Osnovni koraki

) določajo formule

Tukaj je neskladje th približka, koeficient se ugotovi iz pogoja konjugacije

Navodila in ; je rešitev problema minimiziranja funkcije v smeri Analiza računskih formul metode pokaže, da vključujejo dve operaciji množenja matrike z vektorjem, štiri operacije skalarnega produkta in pet operacij na vektorjih. Vendar je pri vsaki ponovitvi dovolj, da zmnožek izračunamo enkrat in nato uporabimo shranjen rezultat. Skupaj

število operacij, izvedenih v eni ponovitvi, je

Operacije. Lahko se pokaže, da za iskanje natančne rešitve sistema linearnih enačb s pozitivno določeno simetrično matriko ni potrebno izvesti več kot n iteracij, zato je kompleksnost algoritma za iskanje natančne rešitve reda velikosti . Vendar zaradi napak pri zaokroževanju ta proces Običajno obravnavan kot iterativen, se proces konča, ko je izpolnjen običajen pogoj zaustavitve (7.51) ali ko je izpolnjen pogoj majhnosti relativne norme ostanka

Organizacija vzporednega računalništva

Pri razvoju vzporedne različice metode konjugiranega gradienta za reševanje sistemov linearnih enačb je treba najprej upoštevati, da se iteracije metode izvajajo zaporedno, zato je najprimernejši pristop paralelizacija izračunov. izvajajo med ponovitvami.

Analiza zaporednega algoritma kaže, da so glavni stroški pri th iteraciji sestavljeni iz množenja matrike z vektorji in . Posledično je mogoče uporabiti dobro znane metode za organiziranje vzporednih izračunov vzporedno množenje matrik na vektor.

Dodatni izračuni nižjega reda zahtevnosti so različne operacije vektorske obdelave (skalarni produkt, seštevanje in odštevanje, množenje s skalarjem). Organizacija takih izračunov seveda mora biti skladna z izbranim na vzporeden način izvajanje operacije množenja matrike z vektorjem.

Za nadaljnjo analizo učinkovitosti nastalih vzporednih izračunov bomo izbrali vzporedni algoritem množenja matrike-vektorja s pasovno horizontalno delitvijo matrike. V tem primeru se bodo operacije na vektorjih, ki so računsko manj intenzivne, izvajale tudi v večnitnem načinu.

Računalniška prizadevanja sekvenčna metoda konjugiranih gradientov določa relacija (7.58). Določimo čas izvedbe vzporedno izvajanje metoda konjugiranega gradienta. Računska kompleksnost vzporedne operacije množenja matrike z vektorjem pri uporabi tračne vodoravne matrične delitvene sheme je

Kje je dolžina vektorja, je število niti in je režijski strošek za ustvarjanje in zapiranje vzporednega odseka.

Vse druge operacije na vektorjih (točkovni produkt, seštevanje, množenje s konstanto) se lahko izvedejo v enonitnem načinu, ker niso odločilni za celotno kompleksnost metode. Zato lahko celotno računsko kompleksnost vzporedne različice metode konjugiranega gradienta ocenimo kot

Kje je število ponovitev metode.

Rezultati računalniških poskusov

Računalniške eksperimente za ovrednotenje učinkovitosti vzporedne različice metode konjugiranega gradienta za reševanje sistemov linearnih enačb s simetrično pozitivno določeno matriko smo izvedli pod pogoji, navedenimi v uvodu. Elementi na glavni diagonali matrike ) so bili generirani v območju od do , kjer je velikost matrike, ostali elementi pa so bili generirani simetrično v območju od 0 do 1. Zaustavitveni kriterij za točnost (7.51) s parametrom je bil uporabljen kot merilo za zaustavitev

Rezultati računalniških poskusov so podani v tabeli 7.21 (čas delovanja algoritmov je naveden v sekundah).

Metoda najstrmejšega spusta

Pri uporabi metode najstrmejšega spusta pri vsaki ponovitvi velikost koraka A k je izbran iz minimalnega pogoja funkcije f(x) v smeri sestopa, tj.
f(x[k]-a k f"(x[k])) = f(x[k] -af"(x[k])) .

Ta pogoj pomeni, da se gibanje vzdolž antigradienta dogaja, dokler je vrednost funkcije f(x) zmanjša. Z matematična točka pogled pri vsaki iteraciji je treba rešiti problem enodimenzionalne minimizacije glede na A funkcije
j (a) = f(x[k]-af"(x[k])) .

Algoritem metode najstrmejšega spusta je naslednji.

1. Nastavite koordinate začetne točke X.

2. Na točki X[k], k = 0, 1, 2, ... izračuna vrednost gradienta f"(x[k]) .

3. Velikost koraka je določena a k, z enodimenzionalno minimizacijo nad A funkcije j (a) = f(x[k]-af"(x[k])).

4. Določene so koordinate točke X[k+ 1]:

X jaz [k+ 1]= x jaz [k]- A k f" jaz (X[k]), i = 1,..., str.

5. Preverijo se pogoji za zaustavitev steracijskega procesa. Če so izpolnjeni, se izračuni ustavijo. V nasprotnem primeru pojdite na 1. korak.

Pri obravnavani metodi je smer gibanja od točke X[k] se v točki dotakne nivojske črte x[k+ 1] (slika 2.9). Pot spuščanja je cik-cak, s sosednjimi cik-cak povezavami pravokotnimi druga na drugo. Res, korak a k je izbran z minimiziranjem z A funkcije q (a) = f(x[k] -af"(x[k])) . Predpogoj minimalna funkcija d j (a)/da = 0. Po izračunu derivata kompleksna funkcija, dobimo pogoj za ortogonalnost vektorjev smeri spuščanja v sosednjih točkah:

d j (a)/da = -f"(x[k+ 1]f"(x[k]) = 0.

Gradientne metode konvergirajo na minimum z visoka hitrost(s hitrostjo geometrijsko napredovanje) za gladke konveksne funkcije. Takšne funkcije imajo največje M in najmanj m lastne vrednosti matrike drugih odvodov (Hessova matrika)

se med seboj malo razlikujejo, tj N(x) dobro kondicionirano. Naj to spomnimo lastne vrednosti jaz, jaz =1, …, n, so matrike korenine karakteristične enačbe

Vendar pa imajo v praksi funkcije, ki jih minimiziramo, praviloma slabo pogojene matrike drugih odvodov (t/m<< 1). Vrednosti takšnih funkcij v nekaterih smereh se spreminjajo veliko hitreje (včasih za več vrst velikosti) kot v drugih smereh. Njihove ravne ploskve so v najpreprostejšem primeru močno podolgovate, v zahtevnejših primerih pa se upognejo in izgledajo kot grape. Funkcije s takimi lastnostmi imenujemo gully. Smer antigradienta teh funkcij (glej sliko 2.10) bistveno odstopa od smeri do minimalne točke, kar vodi do upočasnitve hitrosti konvergence.

Poskusi kažejo dobro pospeševanje (približno 4 na 8 niti).

Zgoraj obravnavane gradientne metode najdejo minimalno točko funkcije v splošnem primeru samo v neskončnem številu ponovitev. Metoda konjugiranega gradienta ustvari smeri iskanja, ki so bolj skladna z geometrijo funkcije, ki jo minimiziramo. To bistveno poveča hitrost njihove konvergence in omogoča, na primer, minimiziranje kvadratne funkcije

f(x) = (x, Hx) + (b, x) + a

s simetrično pozitivno določeno matriko n v končnem številu korakov P, enako številu funkcijskih spremenljivk. Vsako gladko funkcijo v bližini točke minimuma je mogoče dobro aproksimirati s kvadratno funkcijo, zato se metode konjugiranega gradienta uspešno uporabljajo za minimiziranje nekvadratnih funkcij. V tem primeru prenehajo biti končni in postanejo iterativni.

Po definiciji dve n-dimenzionalni vektor X in pri klical konjugiran glede na matrico H(oz H-konjugat), če je skalarni produkt (x, No) = 0. Tukaj N - simetrična pozitivno določena matrika velikosti p X p.

Eden najpomembnejših problemov pri metodah konjugiranega gradienta je problem učinkovite konstrukcije smeri. Metoda Fletcher-Reeves rešuje to težavo s transformacijo antigradienta na vsakem koraku -f(x[k]) v smeri str[k], H-konjugiran s predhodno najdenimi smermi R, R, ..., R[k-1]. Najprej razmislimo o tej metodi v povezavi s problemom minimiziranja kvadratne funkcije.

Navodila R[k] se izračuna po formulah:

str[k] = -f"(x[k]) +b k-1 str[k-l], k>= 1;

str = -f"(x) .

b vrednosti k-1 so izbrani tako, da so smeri str[k], R[k-1] so bili H-konjugat:

(str[k], HP[k- 1])= 0.

Kot rezultat, za kvadratno funkcijo

iterativni postopek minimizacije ima obliko

x[k+l] =x[k]+a k str[k],

Kje R[k] - smer sestopa do k- m korak; A k - velikost koraka. Slednji je izbran iz minimalnega pogoja funkcije f(x) Avtor: A v smeri gibanja, tj. kot rezultat reševanja problema enodimenzionalne minimizacije:

f(x[k] + A k R[k]) = f(x[k] + ar [k]) .

Za kvadratno funkcijo

Algoritem metode konjugiranega gradienta Fletcher-Reeves je naslednji.

1. Na točki X izračunano str = -f"(x) .

2. Vklopljeno k- m korak, z uporabo zgornjih formul se določi korak A k . in pika X[k+ 1].

3. Vrednosti so izračunane f(x[k+1]) in f"(x[k+1]) .

4. Če f"(x) = 0, nato točka X[k+1] je najmanjša točka funkcije f(x). V nasprotnem primeru je določena nova smer str[k+l] iz relacije

in izvede se prehod na naslednjo ponovitev. Ta postopek bo našel minimum kvadratne funkcije v največ p koraki. Pri minimiziranju nekvadratnih funkcij Fletcher-Reevesova metoda iz končne postane iterativna. V tem primeru po (p+ 1) ponovitev postopka 1-4 se ciklično ponavlja z zamenjavo X na X[p+1] in izračuni se končajo pri, kjer je dano število. V tem primeru se uporablja naslednja modifikacija metode:

x[k+l] = x[k]+a k str[k],

str[k] = -f"(x[k])+ b k- 1 str[k-l], k>= 1;

str= -f"( x);

f(x[k] + a k str[k]) = f(x[k] +ap[k];

Tukaj jaz- veliko indeksov: jaz= (0, n, 2 p, plača, ...), tj. metoda se posodobi vsakih p koraki.

Geometrični pomen metode konjugiranega gradienta je naslednji (slika 2.11). Iz danega izhodišča X sestop izvedemo v smeri R = -f"(x). Na točki X vektor gradienta je določen f"(x). Zaradi X je najmanjša točka funkcije v smeri R, to f"(x) pravokoten na vektor R. Nato je vektor najden R , H-konjugiran na R. Nato poiščemo minimum funkcije vzdolž smeri R itd.

riž. 2.11 .

Metode konjugirane smeri so med najbolj učinkovitimi za reševanje problemov minimizacije. Vendar je treba upoštevati, da so občutljivi na napake, ki se pojavijo med postopkom štetja. pri veliko število spremenljivk, se lahko napaka toliko poveča, da bo treba postopek ponoviti tudi za kvadratno funkcijo, tj. postopek zanjo ne sodi vedno v p koraki.

Gradientne metode, ki temeljijo le na izračunu gradienta R(x), so metode prvega reda, saj na intervalu koraka nadomestijo nelinearno funkcijo R(x) linearni.

Učinkovitejše so lahko metode drugega reda, ki ne uporabljajo le prvega, ampak tudi druge derivate R(x) na trenutni točki. Vendar pa imajo te metode svoje težave, ki jih je težko rešiti - izračunavanje drugih odvodov v točki, poleg tega pa je matrika drugih odvodov daleč od optimalnega lahko slabo pogojena.

Metoda konjugiranega gradienta je poskus združitve prednosti metod prvega in drugega reda, hkrati pa odpraviti njihove pomanjkljivosti. Vklopljeno začetnih fazah(daleč od optimuma) se metoda obnaša kot metoda prvega reda, v bližini optimuma pa se približuje metodam drugega reda.

Prvi korak je podoben prvemu koraku metode najstrmejšega spusta, drugi in naslednji koraki se vsakič izberejo v smeri, ki je oblikovana kot linearna kombinacija gradientnih vektorjev v dani točki in prejšnji smeri.

Algoritem metode lahko zapišemo na naslednji način (v vektorski obliki):

x 1 = x 0 – h grad R(x 0),

x i+1 = x i – h .

Vrednost α lahko približno najdemo iz izraza

Algoritem deluje na naslednji način. Od izhodišča X 0 išče min R(x) v smeri gradienta (z uporabo metode najstrmejšega spusta), nato pa se od najdene točke dalje določi smer iskanja min z drugim izrazom. Iskanje minimuma v smeri je mogoče izvesti na kakršenkoli način: lahko uporabite metodo zaporednega skeniranja brez prilagajanja koraka skeniranja pri prehodu minimuma, tako da je natančnost doseganja minimuma v smeri odvisna od velikosti koraka h.

Za kvadratno funkcijo R(x) rešitev je mogoče najti v p koraki (P– dimenzija problema). Pri drugih funkcijah bo iskanje počasnejše in v nekaterih primerih morda sploh ne bo doseglo optimalnega rezultata zaradi močan vpliv računske napake.

Ena od možnih poti za iskanje minimuma dvodimenzionalne funkcije z uporabo metode konjugiranega gradienta je prikazana na sliki 1. 1.

Algoritem metode konjugiranega gradienta za iskanje minimuma.

Prva stopnja. Izvedba gradientne metode.

Nastavite začetni približek x 1 0 ,X 20. Določitev vrednosti kriterija R(x 1 0 ,X 20). Nastavite k = 0 in pojdite na 1. korak začetne stopnje.

Korak 1. in
.

2. korakČe modul gradienta

3. korak

x k+1 = x k – h dipl R(x k)).

4. korak R(x 1 k +1 , X 2 k +1). če R(x 1 k +1 , X 2 k +1)< R(x 1k, X 2 k), nato nastavite k = k+1 in pojdite na korak 3. Če R(x 1 k +1 , X 2 k +1) ≥ R(x 1k, X 2 k), nato pojdite na glavni oder.

Glavni oder.

Korak 1. Izračunajte R(x 1 k + g, x 2 k), R(x 1 k – g, x 2 k), R(x 1 k , x 2 k + g), R(x 1 k , x 2 k) . V skladu z algoritmom iz centralnega ali parnega vzorca izračunamo vrednost parcialnih odvodov in . Izračunajte vrednost modula gradienta
.

2. korakČe modul gradienta
, nato ustavite izračun in upoštevajte točko (x 1 k, x 2 k) kot optimalno točko. V nasprotnem primeru pojdite na 3. korak.

3. korak Izračunajte koeficient α po formuli:

4. korak Izvedite delovni korak z izračunom po formuli

x k+1 = x k – h .

5. korak Določite vrednost kriterija R(x 1 k +1 , X 2 k +1). Nastavite k = k+1 in pojdite na 1. korak.

Primer.

Za primerjavo razmislite o rešitvi prejšnjega primera. Prvi korak naredimo po metodi najstrmejšega spusta (Tabela 5).

Tabela 5

Najboljša točka je najdena. Na tej točki izračunamo derivate: dR/ dx 1 = –2.908; dR/ dx 2 =1.600; Izračunamo koeficient α, ki upošteva vpliv gradienta v prejšnji točki: α = 3,31920 ∙ 3,3192/8,3104 2 =0,160. Naredimo delovni korak v skladu z algoritmom metode, dobimo X 1 = 0,502, X 2 = 1,368. Nato se vse ponovi na enak način. Spodaj v tabeli. 6 prikazuje trenutne iskalne koordinate za naslednje korake.

Tabela 6