Gradient metoder

Gradientmetoder er numeriske metoder til at løse problemer ved hjælp af en gradient , som reduceres til at finde yderpunkterne af en funktion.

Udtalelse af problemet med at løse et ligningssystem i form af optimeringsmetoder

Opgaven med at løse et ligningssystem :

(en)

c svarer til problemet med at minimere funktionen

(2)

eller en anden stigende funktion af de absolutte værdier af residualer (fejl) , . Problemet med at finde minimum (eller maksimum) af en funktion af variable er i sig selv af stor praktisk betydning.

For at løse dette problem ved hjælp af iterative metoder , starter man med vilkårlige værdier og konstruerer successive tilnærmelser:

eller koordineret:

(3)

som konvergerer til en eller anden løsning for .

Forskellige metoder adskiller sig i valget af "retning" for det næste trin, det vil sige valget af relationer

.

Trinværdien (afstanden til at bevæge sig i en given retning på jagt efter et ekstremum) bestemmes af værdien af ​​parameteren, der minimerer værdien som funktion af . Denne funktion tilnærmes normalt ved dens Taylor-udvidelse eller ved et interpolationspolynomium over tre til fem valgte værdier . Den sidste metode er anvendelig til at finde max og min for en tabelfunktion .

Gradientmetoder

Hovedideen med metoderne er at gå i retning af den stejleste nedstigning, og denne retning er givet af antigradienten :

hvor er valgt:

Stejleste nedstigningsmetode ( gradientmetode )

Vælg , hvor alle afledede er beregnet til , og formindsk trinlængden , når du nærmer dig minimum af funktionen .

Til analytiske funktioner og små værdier giver Taylor-udvidelsen mulighed for at vælge den optimale trinstørrelse

(5)

hvor alle derivater er beregnet til . Parabolisk funktionsinterpolation kan være mere praktisk.

Algoritme
  1. Indledende tilnærmelse og beregningsnøjagtighed er indstillet
  2. Tæl hvor
  3. Tjek stoptilstanden:
    • Hvis , så gå til trin 2.
    • Ellers stop.

Gauss-Seidel metode til koordinatnedstigning

Denne metode er navngivet i analogi med Gauss-Seidel-metoden til løsning af et system af lineære ligninger. Forbedrer den tidligere metode på grund af det faktum, at nedstigningen ved næste iteration udføres gradvist langs hver af koordinaterne, men nu er det nødvendigt at beregne nye én gang i et trin.

Algoritme
  1. Indledende tilnærmelse og beregningsnøjagtighed er indstillet
  2. Tæl hvor
  3. Tjek stoptilstanden:
    • Hvis , så gå til trin 2.
    • Ellers stop.

Konjugeret gradientmetode

Den konjugerede gradientmetode er baseret på koncepterne fra den direkte metode til multidimensionel optimering  - metoden for konjugerede retninger .

Anvendelse af metoden på kvadratiske funktioner i bestemmer minimum i trin.

Algoritme
  1. De er givet ved den indledende tilnærmelse og fejl:
  2. Beregn startretningen:
    • Hvis eller , så stop.
    • Ellers
      • hvis , så gå til 3;
      • ellers gå til 2.

Se også

Litteratur

  • Akulich I.L. Matematisk programmering i eksempler og opgaver: Proc. godtgørelse for studerendes økonomi. specialist. universiteter. - M . : Højere. skole, 1986.
  • Gill F., Murray W., Wright M. Praktisk optimering. Om. fra engelsk. — M .: Mir, 1985.
  • Korshunov Yu.M., Korshunov Yu.M. Matematisk grundlag for kybernetik. — M .: Energoatomizdat, 1972.
  • Maksimov Yu.A., Filipovskaya E.A. Algoritmer til løsning af problemer med ikke-lineær programmering. - M .: MEPhI, 1982.
  • Maksimov Yu.A. Algoritmer til lineær og diskret programmering. — M .: MEPhI, 1980.
  • Korn G., Korn T. Håndbog i matematik for videnskabsmænd og ingeniører. - M . : Nauka, 1970. - S. 575-576.