Matemātika DU TSC
Nākamais: 2.3. Minimuma punkta meklēšanas metodes vairāku Augstāk: 2.2. Minimuma punkta meklēšanas metodes Iepriekšējais: 2.2.2. Fibonači skaitļu metode

2.2.3. Zelta šķēluma metode

Iepriekšējā apakšparagrāfā unimodālas funkcijas ekstrēma meklēšanas procesā nogrieznis $[a;b]$ tika sadalīts trīs daļās $[a;x]$, $[x;y]$ un $[y;b]$, kur punkti $x$ un $y$ tika definēti ar Fibonači skaitļu palīdzību. Lietojot zelta šķēluma metodi, izmanto tā saucamos zelta šķēluma punktus. Aplūkosim zīmējumā attēloto nogriezni $[a;b]$ ar dalījuma punktiem $x$ un $y$. Nogriežņa $[a;b]$ punktu $x$ sauc par zelta šķēluma punktu, ja mazākā nogriežņa $[a;x]$ attiecība pret lielāko nogriezni $[x;b]$ ir vienāda ar lielākā nogriežņa attiecību pret visu nogriezni $[a;b]$ (skat. 2.1. zīm.), t.i.,

$$\frac{x - a}{b - x} = \frac{b - x}{b - a}.$$

Analoģiski punkts $y$ tiek definēts tā, lai

$$\frac{b - y}{y - a} = \frac{y - a}{b - a}.$$

Viegli redzēt, ka

$$x = a + (b - a){\frac{3 - \sqrt 5 }{2}},\quad y = a + (b - a){\frac{\sqrt 5 - 1}{2}}.$$

Var pārbaudīt, ka punkti $x$ un $y$ ir novietoti nogrieznī $[a,b]$ simetriski, t.i., $b - y = x - a$.

2.1. zīm. Nogriežņa $[a;b]$ zelta šķēluma punkti $x$ un $y$.

Zelta šķēluma metodes būtību izsaka nākamā teorēma.

2.1. teorēma. 

Nogriežņa $[a;b]$ zelta šķēluma punkts $x$ ir zelta šķēluma punkts lielākajam no nogriežņiem, kuros nogriezni $[a;b]$ sadala otrs zelta šķēluma punkts, t.i., $x$ ir zelta šķēluma punkts nogrieznim $[a;y]$. Analoģiski $y$ ir zelta šķēlums nogrieznim $[x;b]$.

$\blacktriangleright$ Jāpierāda, ka

$$x = a + (y - a){\frac{\sqrt 5 - 1}{2}}.$$

Tiešām,

$$x = \;a + (b - a){\frac{3 - \sqrt 5 }{2}}=$$

$$= \;a + (b - a)\left( {\frac{\sqrt 5 - 1}{2}} \right)^2- {(b - a)}\left( {\frac{\sqrt 5 - 1}{2}} \right)^2 + (b - a){\frac{3 - \sqrt 5 }{2}}=$$

$$= \;a + \Biggl[ {a + (b - a){\frac{\sqrt 5 - 1}{2}} - a} \Biggr]{\frac{\sqrt 5 - 1}{2}}+$$

$$\qquad\qquad\qquad\qquad\qquad\qquad\; + (b - a)\Biggl[ {\frac{3 - \sqrt 5 }{2} - \left( {\frac{\sqrt 5 - 1}{2}} \right)^2} \Biggr]=$$

$$= \;a + (y - a){\frac{\sqrt 5 - 1}{2}}.\blacktriangleleft$$

Analoģiski var pierādīt, ka $y$ ir nogriežņa $[x,b]$ zelta šķēluma punkts.

Minimuma punkta meklēšana saskaņā ar zelta šķēluma metodi notiek šādi.

Salīdzina funkcijas $f(x)$ vērtības zelta šķēluma punktos $x$ un $y$. Ir iespējami divi gadījumi:
a) ja $f(x) < f(y)$, tad $[a;y]$ ir minimuma punkta lokalizācijas intervāls;
b) ja $f(x) > f(y)$, tad $[x;b]$ ir minimuma punkta lokalizācijas intervāls.

a) gadījumā jaunais intervāls ir $[a_{1};b_{1}]=[a;y]$ un lielākais zelta šķēluma punkts $y_{1}=x$ ir zināms, bet otro, mazāko, var aprēķināt pēc formulas

$$x_1 = a_1 + (b_1 - a_1 ){\frac{3 - \sqrt 5 }{2}}.$$

Tālāk salīdzina $f(x_{1})$ un $f(y_{1})$ un atkārto procedūru.

b) gadījumā jaunais intervāls ir $[a_{1};b_{1}]=[x;b]$ un $x_{1} = y$ ir jaunā intervāla mazākais zelta šķēluma punkts. Otrais, lielākais, zelta šķēluma punkts ir

$$y_1 = a_1 + (b_1 - a_1 ){\frac{\sqrt 5 - 1}{2}}.$$

Tālāk salīdzina $f(x_{1})$ un $f(y_{1})$ un atrod jauno lokalizācijas intervālu.

Aprēķinu precizitāte. Cik iterāciju jāņem, lai ekstrēma punkts būtu aprēķināts ar doto precizitāti, t.i., lai lielums $\vert x_{min}-a_{n}\vert$ (vai lielums $\vert x_{min}-b_{n}\vert$) būtu mazāks par doto precizitāti $\varepsilon$?

Lai sniegtu atbildi uz šo jautājumu, ievērosim, ka

$$\frac{y - a}{b - a} = \frac{(b - a){\frac{\sqrt 5 - 1}{2}} }{(b - a)} = \frac{\sqrt 5 - 1}{2} < \frac{2}{3}.$$

Analoģiski iegūsim

$$\frac{b - x}{b - a} = \frac{\sqrt 5 - 1}{2} < \frac{2}{3}.$$

Tas nozīmē, ka, gan a) gadījumā, gan b) gadījumā, jaunā lokalizācijas intervāla $[a_{1};b_{1}]$ garums ir mazāks par $\frac{2}{3}$ no iepriekšējā intervāla garuma. Nākamajā solī intervāla $[a_{2};b_{2}]$ garums apmierina nevienādību

$$b_2 - a_2 < \frac{2}{3}(b_1 - a_1 ) < \left( {\frac{2}{3}} \right)^2(b - a).$$

Acīmredzot, ir spēkā novērtējums

$$b_n - a_n < \left( {\frac{2}{3}} \right)^n(b - a).$$

Tas nozīmē, ka, lai aprēķinātu $x_{min}$ ar precizitāti $\varepsilon$, pietiek ar tādu $n$, lai izpildītos nevienādība

$$b_n - a_n < \left( {\frac{2}{3}} \right)^n(b - a) < \varepsilon .$$

Tas ir iespējams: par $x_{min}$ tuvinājumu var ņemt gan $a_{n}$, gan $b_{n}$, gan intervāla viduspunktu $\frac{b_{n}+a_{n}}{2}$.

2.4. piemērs. 

Atradīsim funkcijas f(x) = $\vert E(x)\vert+\vert x\vert$ minimumu intervālā $[a;b] = [-1;1]$.

Pirmajā solī

$$x = - 1 + 2 \cdot \frac{3 - \sqrt 5 }{2} = 2 - \sqrt 5 ,\quad y = - 1 + 2 \cdot \frac{\sqrt 5 - 1}{2},$$

$$f(x) = 1 + \left(\sqrt 5 - 2\right) = \sqrt{5} - 1 > 0 + \left(\sqrt 5 - 2\right) = f(y).$$

Jaunais intervāls

$$[a_{1};b_1]= [x,b]=\left[2 -\sqrt{5};1\right].$$

Nākamajā solī

$$x_1 = y = \sqrt 5 - 2,\quad y_1 = a_1 + (b_1 - a_1 ) {\frac{\sqrt 5 - 1}{2}}= 5 - 2\sqrt 5 .$$

Salīdzinot funkcijas vērtības, iegūstam

$$\begin{multline*} f(x_1 ) = f\left(\sqrt 5 - 2\right) = 0 + \left(\sqrt 5 - 2\ri... ...- 2 < f(y_1 ) =\ = f\left(5 - 2\sqrt 5 \right) = 5 - 2\sqrt 5 . \end{multline*}$$

Jaunais intervāls

$$\left[ {a_{2};b_2 } \right] = \left[ {a_1;y_1 } \right] = \left[ {2 - \sqrt 5;5 - 2\sqrt 5 } \right].$$

Jaunie dalījuma punkti

$$y_2 = \; x_1 = \sqrt 5 - 2,$$

$$x_2 = \; a_2 + (b_2 - a_{2} ) {\frac{3 - \sqrt 5 }{2}}= \left(2 - \sqrt 5 \right) + \left(3 - \sqrt 5 \right)\frac{3 - \sqrt 5 }{2} = 9 - 4\sqrt 5 .$$

Salīdzinot $f(x_2)=f\left(9 - 4\sqrt 5\right)$ un $f(y_2) = f\left(\sqrt 5 - 2\right)$, iegūstam jaunu lokalizācijas intervālu utt., kamēr minimuma punkts nebūs atrasts ar vajadzīgo precizitāti.

Matemātika DU TSC
Nākamais: 2.3. Minimuma punkta meklēšanas metodes vairāku Augstāk: 2.2. Minimuma punkta meklēšanas metodes Iepriekšējais: 2.2.2. Fibonači skaitļu metode