Matemātika DU TSC
Nākamais: 2.2.3. Zelta šķēluma metode Augstāk: 2.2. Minimuma punkta meklēšanas metodes Iepriekšējais: 2.2.1. Dihotomijas metode (jeb intervāla dalīšanas

2.2.2. Fibonači skaitļu metode

Dotā metode balstās uz Fibonači skaitļu izmantošanu. Fibonači skaitļi ir veseli skaitļi, kurus iegūst pēc rekurentas formulas:

$$F_{n + 1} = F_{n} + F_{n-1}\;(n\geq 2),\;\; F_{1} = F_{2} = 1.$$

Pirmie Fibonači skaitļi ir uzrādīti tabulā.

$n$	1	2	3	4	5	6	7	8	9	10	11	12
$F(n)$	1	1	2	3	5	8	13	21	34	55	89	144

Ar matemātiskas indukcijas metodi var pierādīt, ka Fibonači skaitli $F_{n}$ var aprēķināt pēc formulas

$$F_n=\frac{1}{\sqrt 5 }\left[ {\left( {\frac{1 + \sqrt 5 }{2}} \right)^n - \left( {\frac{1 - \sqrt 5 }{2}} \right)^n} \right]\;\;(n = 1,2,\ldots).$$

Pieņemsim, ka $f(x)$ ir unimodāla funkcija intervālā $[a;b]$. Minimuma punkta meklēšanas shēma saskaņā ar Fibonači metodi ir šāda.

Dalām intervālu $[a;b]$ trīs daļās ar punktiem

$$x_1 = a + (b - a )\frac{F_n }{F_{n + 2} },\quad y_1 = a + (b - a)\frac{F_{n + 1} }{F_{n + 2} }$$

(uzskatām, ka $n\geq 2$). Punkti $x_{1}$ un $y_{1}$ ir novietoti simetriski intervālā $[a,b]$, jo

$$x_{1}-a = \frac{(b - a) F_{n }}{F_{n + 2}}$$

un

$$b - y_{1 }= (b - a) - (b - a)\frac{ F_{n + 1 }}{ F_{n + 2}} = (b ... ...frac{ (F_{n + 2} - F_{n + 1 })}{F_{n + 2}} = (b - a)\frac{ F_{n }}{F_{n + 2}} .$$

Tālāk izvēlēsimies jaunu intervālu $[a_{2};b_{2}]$ atkarībā no tā, kura vērtība, $f(x_{1})$ vai $f(y_{1})$, ir lielāka:
a) ja $f(x_{1})<f(x_{2})$, tad jaunais intervāls ir $[a_{2};b_{2}] = [a;y_{1}]$;
b) ja $f(x_{1})>f(x_{2})$, tad jaunais intervāls ir $[a_{2};b_{2}] = [x_{1};b]$.
Abos gadījumos iegūto intervālu garumi ir vienādi, jo

$$y_{1} - a = (b - a) - (b - y_{1}) (b - a) -(x_{1}-a)=b-x_{1}.$$

Jaunā intervāla $[a_{2};b_{2}]$ garums ir

$$b_{2} - a_{2} = y_{1} - a = (b - a) \frac{F_{n + 1 }}{F_{n + 2}}.$$

Aplūkosim a) gadījumu, kad $[a_{2};b_{2}] = [a;y_{1}]$. Jaunie dalījuma punkti ir

$$x_2 = a_2 + (b - a)\frac{F_{n - 1} }{F_{n + 2} },\quad y_2 = a_2 + (b - a)\frac{F_n }{F_{n + 2} }.\quad$$

Atzīmēsim, ka

$$y_{2 }= a + (b - a)\frac{ F_{n }}{F_{n + 2}} = x_{1},$$

tātad jaunajā intervālā lielākais sadalījuma punkts sakrīt ar iepriekšējā intervāla mazāko sadalījuma punktu. Tālāk salīdzinām vērtības $f(x_{2})$ un $f(y_{2})$ un, atkarībā no salīdzināšanas rezultātiem, par jauno minimuma punkta lokalizācijas intervālu $[a_{2};b_{2}]$ izvēlamies vai nu intervālu $[a_{2};y_{2}]$ (ja $f(x_{2})< f(y_{2})$), vai arī intervālu $[x_{2};b_{2}]$ (ja $f(x_{2})>f(y_{2})$). Iesakām lasītājam patstāvīgi pārliecināties, ka jaunā intervāla garums ir

$$b_{3} - a_{3} = (b - a) \frac{F_{n }}{F_{n + 2}}.$$

Aplūkosim b) gadījumu, kad $[a_{2};b_{2}] = [x_{1};b]$. Jaunie dalījuma punkti ir

$$x_2 = a_2 + (b - a)\frac{F_{n - 1} }{F_{n + 2} },\quad y_2 = a_2 + (b - a)\frac{F_n }{F_{n + 2} },$$

bet tagad $a_{2}= x_{1}$ atšķirībā no a) gadījuma. Atzīmēsim, ka

$$x_{2 }= x_{1} + (b - a) \frac{F_{n - 1 }}{F_{n + 2}} = (b - a) \f... ...) \frac{F_{n - 1 }}{F_{n + 2}} = (b - a) \frac{F_{n + 1 }}{F_{n + 2 }} = y_{1},$$

t.i., jaunajā intervālā mazākais dalījuma punkts sakrīt ar iepriekšējā intervāla lielāko dalījuma punktu. Salīdzinām vērtības $f(x_{2})$ un $f(y_{2})$ un, atkarībā no salīdzināšanas rezultāta, par jauno minimuma punkta lokalizācijas intervālu $[a_{2};b_{2}]$ izvēlamies vai nu intervālu $[a_{2};y_{2}]$ (ja $f(x_{2})< f(y_{2})$), vai arī intervālu $[x_{2};b_{2}]$ (ja $f(x_{2})>f(y_{2})$). Jaunā intervāla $[a_{3};b_{3}]$ garums ir

$$b_3-a_3= (b - a)\frac{F_{n }}{F_{n + 2}} .$$

Rezumēsim iegūtos rezultātus. Solī ar numuru $i$ iegūstam jaunu lokalizācijas intervālu $[a_{i};b_{i}]$ (uzskatām ka $a_{1}=a$, $b_{1}=b$), kura garums ir

$$b_{i} - a_{i} = (b- a) \frac{F_{n - i + 3 }}{F_{n + 2}} .$$

Dalījuma punkti:

$$x_i = a_i + (b - a)\frac{F_{n - i + 1} }{F_{n + 2} },\quad y_i = a_i + (b - a)\frac{F_{n - i + 2} }{F_{n + 2} }.$$

Pēc $n$ soļiem

$$x_n = a_n + (b - a)\frac{F_1 }{F_{n + 2} },\quad y_n = a_n + (b - a)\frac{F_2 }{F_{n + 2} },$$

un $x_{n} = y_{n}$. Intervāla $[a_{n};b_{n}]$ garums ir

$$(b - a)\frac{F_3 }{F_{n + 2} } = 2(b - a)\frac{1}{F_{n + 2} }.$$

Aprēķinu algoritms ir skaidrs, paliek viens neatrisināts jautājums: kādu $n$ izvēlēties?

Jo lielāks ir $n$, jo precīzāk varam atrast minimuma punktu, bet līdz ar to būs jāveic vairāk aprēķinu. Tātad, ja ir uzdots skaitlis $\varepsilon>0$ (- precizitāte) un ir jāaprēķina minimuma punkta $x_{min}$ tuvinājumu $x_{tuv}$ tā, lai izpildītos nevienādība $\vert x_{min}-x_{tuv}\vert<\varepsilon$, tad $n$ ir jāizvēlās tā, lai

$$\frac{2(b- a)}{F_{n + 2} } < \varepsilon .$$

Šajā gadījumā intervāla $[a_{n};b_{n}]$ garums nepārsniegs $\varepsilon$, un par minimuma punkta tuvinājumu var ņemt jebkuru šī intervāla punktu, piemēram, tā viduspunktu $\frac{b_{n}+a_{n}}{2}$.

2.3. piemērs. 

Aprēķināt funkcijas $f(x) = \vert E(x)\vert +\vert x\vert$ minimuma punktu intervālā $[-1, 1]$ ar precizitāti $\varepsilon = 0,2$.

1. solis. Skaitļa $n$ izvēle.
Izvēlēsimies tādu $n$, lai

$$2(b - a)\frac{1}{F_{n + 2} } = \frac{2 \cdot 2}{F_{n + 2} } < 0,2.$$

Ja $n = 6$, tad

$$\frac{2 \cdot 2}{F_{6 + 2} }=\frac{2 \cdot 2}{21} < 0,2.$$

2. solis. Dalījuma punkti:

$$x_{1}= \; a + (b - a) \cdot \frac{F_{6}}{F_{8}} = - 1+2 \cdot \frac{F_{6}}{F_{8}} = - \frac{5}{21},$$

$$y_{1} = \; a + (b - a) \cdot \frac{F_{7}}{F_{8}}= - 1+2\cdot \frac{F_{7}}{F_{8}} =\frac{5}{21},$$

pie tam

$$f(x_{1})=\vert-1\vert+\left\vert-\frac{5}{21}\right\vert>\left\vert \frac{5}{21}\right\vert=f(y_{1}).$$

Jaunais intervāls

$$[a_{2};b_{2}]=[x_{1};b]=\left[-\frac{5}{21};1\right],\;\; x_{2}=y_{1}=\frac{5}{21}.$$

3. solis. Dalījuma punkti

$$x_{2}= \;(a_{2}+(b - a)\cdot \frac{F_{5}}{F_{8}}=-\frac{5}{21} + 2 \cdot \frac{F_{5}}{F_{8}} = \frac{5}{21},$$

$$y_{2}= \; a_{2} + (b - a) \cdot \frac{F_{6}}{F_{8}}= -\frac{5}{21} +2 \cdot \frac{F_{6}}{F_{8}} = \frac{11}{21},$$

pie tam

$$f(x_{2}) = \frac{5}{21}< \frac{11}{21} = f(y_{2}).$$

Jaunais intervāls

$$[a_{3};b_{3}]=[a_{2};y_{2}]=\left[-\frac{5}{21};\frac{11}{21}\right],\;\; y_{3}=x_{2}=\frac{5}{21}.$$

4. solis. Dalījuma punkti

$$x_{3}= \; a_{3} + (b - a) \cdot \frac{F_{4}}{F_{8}} = - \frac{5}{21} + 2 \cdot \frac{3}{21} = \frac{1}{21},$$

$$y_{3} = \; a_{3} + (b - a) \cdot \frac{F_{5}}{F_{8}}= - \frac{5}{21} 1+2 \cdot \frac{5}{21} = \frac{5}{21},$$

pie tam

$$f(x_{3}) = \frac{1}{21} < \frac{5 }{21} = f(y_{3}).$$

Jaunais intervāls

$$[a_{4};b_{4}] = [a_{3};y_{3}] = \left[-\frac{5}{21};\frac{5}{21}\right],\;\; y_{4} = x_{3} = \frac{1 }{21}.$$

5. solis. Dalījuma punkti

$$x_{4} = \; a_{4} + (b - a) \cdot \frac{F_{3}}{F_{8}}= - \frac{5}{21} + 2 \cdot \frac{2}{21} = -\frac{1}{21},$$

$$y_{4} = \; a_{4} + (b - a) \cdot \frac{F_{4}}{F_{8}}= - \frac{5}{21} + 2 \cdot \frac{3}{21} = \frac{1}{21},$$

pie tam

$$f(x_{4}) = \frac{22}{21} > \frac{1}{21} = f(y_{4}).$$

Jaunais intervāls

$$[a_{5};b_{5}]=[x_{4};b_{4}]=\left[-\frac{1}{21};\frac{5}{21}\right],\;\; x_{5} = y_{4} = \frac{1}{21}.$$

6. solis. Dalījuma punkti

$$x_{5}= \;(a_{5} +(b - a) \cdot\frac{ F_{2}}{F_{8}}=-\frac{1}{21} + 2\cdot \frac{1}{21}=\frac{1}{21},$$

$$y_{5}= \; a_{5} + (b - a) \cdot \frac{F_{3}}{F_{8}}=-\frac{1}{21} + 2 \cdot \frac{2}{21} =\frac{3}{21},$$

pie tam

$$f(x_{5}) = \frac{1 }{21}< \frac{3}{21} = f(y_{5}).$$

Jaunais intervāls

$$[a_{6};b_{6}]=[a_{5};y_{5}]=\left[-\frac{1}{21};\frac{3}{21}\right].$$

7. solis. Pēdējā intervāla garums $\frac{4}{21}< \varepsilon= 0,2$. Prasītā precizitāte ir sasniegta. Procesu var beigt. Par funkcijas minimuma punktu var ņemt intervāla viduspunktu $\frac{1}{21}$. Viegli redzēt, ka reālais minimuma punkts ir nulle, un tuvinājums atšķiras no tā par vērtību, kas ir mazāka par $\varepsilon$.

Matemātika DU TSC
Nākamais: 2.2.3. Zelta šķēluma metode Augstāk: 2.2. Minimuma punkta meklēšanas metodes Iepriekšējais: 2.2.1. Dihotomijas metode (jeb intervāla dalīšanas