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

2.2.1. Dihotomijas metode (jeb intervāla dalīšanas uz pusēm metode)

Uzdevums. Atrast unimodālas funkcijas minimuma punktu ar precizitāti $\varepsilon>0$.

Te nepieciešams paskaidrojums. Atrast funkcijas minimuma punktu $x_{min}$ (kura vērtība nav zināma) ar precizitāti $\varepsilon$ nozīme atrast tādu punkta $x_{min}$ tuvināto vērtību $x_{tuv}$, kura apmierina nosacījumu $\vert x_{min}-x_{tuv}\vert<\varepsilon$.

Uzdevuma risinājums. Pieņemsim, ka unimodāla funkcija $f$ ir definēta segmentā $[a;b]$. Sadalīsim segmentu $[a;b]$ trīs daļās

$$[a;x_1],\;\;(x_1;x_2),\;\;[x_2;b],$$

kur punkti $x_{1}$ un $x_{2}$ apmierina nosacījumus

$$x_1=\frac{a + b}{2}-\delta\;$$ un $$\;x_2=\frac{a + b}{2}+\delta;$$

$\delta$ - pietiekami mazs skaitlis ( $2\delta<\varepsilon$). Atzīmēsim, ka punkts $\frac{a+b}{2}$ ir intervāla $[a;b]$ viduspunkts, un punkti $x_{1}$ un $x_{2}$ atrodas gandrīz intervāla vidū (ja $\delta$ ir mazs), taču dažādās pusēs no viduspunkta.

Salīdzināsim funkcijas $f(x)$ vērtības punktos $x_{1}$ un $x_{2}$. Gadījumā, ja $f(x_{1})= f(x_{2})$, meklētais minimuma punkts noteikti atrodas intervālā $(x_{1};x_{2})$ (jo pretējā gadījumā funkcija $f$ nebūtu unimodāla). Tā kā intervāla garums ir $2\delta<\varepsilon$, tad par minimuma punkta tuvinājumu var izvēlēties intervāla viduspunktu. Gadījumā, ja $f(x_{1})<f(x_{2})$, no Apgalvojuma izriet, ka minimuma punkts $x_{min}$ (tas ir viens vienīgs, jo $f$ ir unimodāla) atrodas intervālā $(a,x_{2})$. Ja $f(x_{1})>f(x_{2})$, tad $x_{min}\in(x_1;b)$. Abos gadījumos jaunā intervāla, kuru apzīmēsim ar $[a_{1};b_{1}]$, garums ir viens un tas pats:

$$b_1 - a_1 = \; x_2 - a = \frac{a + b}{2} + \delta - a = \frac{b - a}{2} + \delta;$$

$$b_1 - a_1 = \; b - x_1 = b - \frac{a + b}{2} + \delta = \frac{b - a}{2} + \delta .$$

Atkārtojot analoģisku procedūru jaunajā intervālā $[a_{1};b_{1}]$, iegūstam jaunus dalījuma punktus:

$$y_1=\frac{a_1 + b_1 }{2}-\delta,\;\; y_2= \frac{a_1 + b_1 }{2}+\delta.$$

Ja $f(y_{1})<f(y_{2})$, tad jaunais intervāls $[a_{2};b_{2}]= [a_{1},y_{2}]$, bet, ja $f(y_{1})>f(y_{2})$, tad jaunais intervāls $[a_{2};b_{2}]=[y_{1};b_{1}]$. Abos gadījumos jauniegūtā intervāla garums ir viens un tas pats:

$$b_2 - a_2 = \; y_2 - a_1 = \frac{a_ + b_1 }{2} + \delta - a_1 = \frac{b_1 - a_1 }{2} + \delta =$$

$$\qquad\qquad\qquad\qquad\qquad\; =\frac{\frac{b - a}{2} + \delta }{2} + \delta = \frac{b - a}{2^2} + \frac{\delta }{2} + \delta;$$

$$b_2 - a_2 = \; b_1 - y_1 = b_1 - \frac{a_ + b_1 }{2} + \delta = \frac{b_1 - a_1 }{2} + \delta = \frac{b - a}{2^2} + \frac{\delta }{2} + \delta .$$

Nākamajā (trešajā) solī iegūstam intervālu $[a_{3};b_{3}]$ ar garumu

$$b_3 - a_3 = \frac{b_2 - a_2 }{2} + \delta = \frac{b - a}{2^3} + \frac{\delta }{2^2} + \frac{\delta }{2} + \delta .$$

Pēc indukcijas, $n$-tajā solī

$$\begin{multline*} b_n - a_n = \frac{b - a}{2^n} + \frac{\delta }{2^{n - 1}} + \... ...\cdots + \frac{1}{2^n} + \cdots ) = \frac{b - a}{2^n} + 2\delta. \end{multline*}$$

Pēdējās izteiksmes iegūšanai tika lietota bezgalīgi dilstošas ģeometriskās progresijas locekļu summas formula. Aprēķini ir jābeidz, ja $b_{n}-a_{n}<\varepsilon$, iegūstot minimuma punkta tuvinājumu ar vajadzīgo precizitāti.

Viens no svarīgākajiem metodes efektivitātes parametriem - aprēķinu apjoms. Metode skaitās efektīva, ja ir jāaprēķina pēc iespējas mazāk funkciju vērtību utt. Lietojot dihotomijas metodi, funkcijas $f$ vērtības ir jāaprēķina $2n$ reizes.

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