Matemātika DU TSC
Nākamais: 2.3.2. Šķēlumu metode Augstāk: 2.3. Minimuma punkta meklēšanas metodes vairāku Iepriekšējais: 2.3. Minimuma punkta meklēšanas metodes vairāku

2.3.1. Gradientu metode

Aplūkosim funkciju $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$, kurai eksistē nepārtraukti pirmās kārtas parciālie atvasinājumi. Par funkcijas gradientu sauc vektoru

$$\grad f(x) = \left(\frac{\partial f}{\partial x_1 };\ldots ;\frac{\partial f}{\partial x_n }\right).$$

No matemātiskas analīzes kursa ir zināms [3, 184. lpp.], ka $\grad f(x)$ ir vektors, kas vērsts funkcijas straujākās augšanas virzienā.

Piemēram, aplūkosim divu argumentu funkciju $f(x_{1};x_{2})$ un tās pieaugumu punktā $(u_{1};u_{2})$:

$$f(u_{1}+h_{1};u_{2}+h_{2})-f(u_{1};u_{2})=\frac{\partial f}{\part... ... h_1 + \frac{\partial f}{\partial x_2 }(u_1 ;u_2 ) \cdot h_2 + o(\vert h\vert),$$

kur $o(\vert h\vert)$ ir augstākas kārtas loceklis nekā $\vert h\vert=\sqrt{h_1^2+h_2^2}$, t.i.,

$$\frac{o(\vert h\vert)}{\vert h\vert}\xrightarrow[{\vert h\vert\to 0}]{}0.$$

Ir spēkā formula

$$\frac{\partial f}{\partial x_1 } \cdot h_1 + \frac{\partial f}{\p... ...} \right\rangle = \vert \grad f(u)\vert \cdot \vert h\vert \cdot \cos \varphi,$$

kur $\varphi$ ir leņķis starp vektoriem $\grad f(u)$ un $h=(h_{1};h_{2})$. Pieņemsim, ka vektors $(h_{1};h_{2})$ ir normēts, t.i., $\vert h\vert=1$. Viegli redzēt, ka summa

$$\frac{\partial f}{\partial x_1 }(u_1;u_2 ) \cdot h_1 + \frac{\partial f}{\partial x_2 }(u_1;u_2 ) \cdot h_2$$

būs vislielākā tad, kad pieauguma vektors $(h_{1};h_{2})$ ir vērsts funkcijas $f$ gradienta virzienā (t.i., vektori $\grad f(u)$ un $(h_{1};h_{2})$ ir kolineāri), jo tad $\cos\varphi=1$.

2.1. piezīme. 

Atzīmēsim, ka vektors $-\grad f(u)$, kuru sauc par antigradientu, ir vērsts funkcijas straujākās dilšanas virzienā.

2.5. piemērs. 

Funkcijas $f(x;y)=x^{2}+y^{2}$, kuras grafiks ir eliptiskais paraboloīds ar virsotni koordinātu sākumpunktā, antigradienta vektors $(-2x;-2y)$ jebkurā nenulles punktā $(x;y)$ ir vērsts uz koordinātu sākumpunktu.

Gradientu metodes centrālā ideja - virzīties uz funkcijas iespējamo minimuma punktu pa lauztu līniju tā, lai katrā lūzuma punktā kustības virziens sakristu ar antigradienta virzienu.

Gradientu metodes iteratīva formula:

$$u_{n + 1 }= u_{n} -\alpha _{n + 1} \cdot \grad f(u_{n}),$$

kur $\alpha_{n + 1}$ - pozitīvs skaitlis.

Parametra $\alpha$ izvēle. Katrā solī ir jāizvēlas parametra $\alpha$ vērtība. Ja skaitļa $\alpha$ vērtība ir pārāk liela, tad funkcijas $f$ vērtība punktā $u_{n+1}$ var kļūt lielāka par $f(u_{n})$.

2.6. piemērs. 

Apskatīsim problēmu

$$f(x;y)=x^{2}+y^{2}\longrightarrow min.$$

Pieņemsim, ka sākumpunkts ir $u_{0}=(1;1)$. Tad $\grad f(1;1)=(2;2)$. Ja $\alpha_{1}=2$, tad tuvinājums

$$u_{1} = u_{0} - \alpha _{1} \cdot \grad f (1;1) = (1;1) - 2 \cdot (2;2) = (-3;-3).$$

Acīmredzot,

$$f (u_{1}) = f (-3;-3) = 9 + 9 > f (u_{0}) = 2.$$

Var arī gadīties, ka process kļūs oscilējošs. Tā, pieņemsim, ka iepriekšējā piemērā

$$\alpha _{1} = \alpha_{2} = \cdots = 1,\;\;u_{0} = (1;1).$$

Tad

$$u_{1} = \; u_{0} - \alpha _{1} \cdot \grad f (u_{0}) = (1;1) - (2;2) = (-1;-1),$$

$$f(u_{1}) = \; 2,$$

$$u_{2 } = \; u_{1} - \alpha _{2} \cdot \grad f (u_{1}) = (-1;-1) - (-2;-2) = (1;1),$$

$$f(u_{2}) = \; 2\;\;$$

Katrā solī parametrs $\alpha$ ir jāizvēlās tā, lai funkcijas $f$ vērtība punktā $u_{n+1}$ būtu pēc iespējas mazāka. Meklējam $\alpha$ kā viena argumenta funkcijas minimizēšanas problēmas

$$f(u_{n + 1}) = F(\alpha ) = f\left (u_{n }-\alpha \grad f(u_{n})\right)\longrightarrow min$$

atrisinājumu.

2.7. piemērs. 

Apskatīsim problēmu

$$f(x;y)=x^{2}+y^{2}\longrightarrow min.$$

Pieņemsim, ka sākumpunkts ir $u_{0}=(1,1)$. Tad

$$f(u_{1}) = f (u_{0 }- \alpha _{1} \cdot \grad f(u_{0})) = f (1 - 2\alpha _{1};1- 2\alpha _{1}),$$

kur $\alpha_{1}$ ir problēmas

$$f (1- 2\alpha;1- 2\alpha)\longrightarrow min$$

atrisinājums. Funkcijas

$$f(1-2\alpha;1-2\alpha)=(1-2\alpha)^{2}+(1-2\alpha)^{2}$$

minimuma punkts ir $\alpha=\frac{1}{2}$. Tad

$$f(u_{1})=f\left(1- 2\cdot\frac{1}{2};1- 2\cdot\frac{1}{2}\right)=f(0;0)=0$$

un funkcijas $f$ minimums (un minimuma punkts) ir atrasts jau pirmajā solī.

2.8. piemērs. 

Apskatīsim problēmu

$$f(x;y)=2x^{2}+xy+y^{2}\longrightarrow min.$$

Funkcijas $f$ gradients $\grad f=(4x+y;x+2y)$. Pieņemsim, ka sākumpunkts ir $u_{0}=(1;1)$.

Pirmajā solī

$$u_{1}=u_{0}-\alpha_{1}\cdot\grad f(u_{0}),$$

no kurienes izriet

$$x_{1}= \;x_{0}-\alpha_{1}\cdot(4x_{0}+ y_{0}) =1-5\alpha_{1},$$

$$y_{1} = \;y_{0}-\alpha_{1}\cdot(x_{0}+2y_{0})= 1-3\alpha _{1}.$$

Meklējam optimālo $\alpha_{1}$, risinot minimizēšanas problēmu

$$f(x_{1};y_{1})=2(1-5\alpha_{1})^{2}+(1-5\alpha_{1})(1-3\alpha _{1})+(1-3\alpha_{1})^{2}\longrightarrow min.$$

Pēc $\alpha_{1}=\frac{17}{74}$ atrašanas aprēķinām

$$x_1=-\frac{17}{74},\;\;y_1=\frac{23}{74}.$$

Atrodam

$$f(u_1)=2\left(-\frac{11}{74}\right)^2+\left(-\frac{11}{74}\right)\left( \frac{23}{74}\right)+\left(\frac{23}{74}\right)^{2}= 5\frac{27}{74}$$

un aprēķinus var turpināt tālāk.

2.9. piemērs. 

Apskatīsim problēmu

$$f(x;y)=x^{2}+xy+y^{2}\longrightarrow min.$$

Funkcijas $f$ gradients $\grad f=(2x+y;x+2y)$. Pieņemsim, ka sākumpunkts ir $u_{0}=(1;1)$.

Pirmajā solī

$$u_{1}=u_{0}-\alpha_{1}\cdot\grad f(u_{0}),$$

no kurienes izriet

$$x_{1}= \;x_{0}-\alpha_{1}\cdot(2x_{0}+y_{0})=1-3\alpha_1,$$

$$y_{1} = \;y_{0}-\alpha_1\cdot(x_0+ 2y_0)=1-3\alpha_1.$$

Meklējam optimālo $\alpha_1$, risinot minimizēšanas problēmu

$$f(x_1;y_1)=(1-3\alpha_1)^2+(-3\alpha_1)(1-3\alpha_1)+(1-3\alpha _1)^2\longrightarrow min.$$

Pēc $\alpha_1=\frac{1}{3}$ atrašanas aprēķinām

$$x_1=y_1=1-3\cdot\frac{1}{3}=0.$$

Atrodam

$$f(u_1)=f(0;0)=0$$

un, acīmredzot, tā ir funkcijas $f$ minimālā vērtība.

2.2. piezīme. 

Gadījumos, kad antigradienta vektors sākumpunktā $u_{0}$ ir vērsts uz minimuma punktu, gradientu metode dod precīzu atbildi jau pirmajā solī.

2.3. piezīme. 

Izvērstāku informāciju par gradientu metodi var iegūt grāmatās [1], [3], [5].

Matemātika DU TSC
Nākamais: 2.3.2. Šķēlumu metode Augstāk: 2.3. Minimuma punkta meklēšanas metodes vairāku Iepriekšējais: 2.3. Minimuma punkta meklēšanas metodes vairāku