| |
13. Minimum funkce f(x) |
|
|
| |
- Motto: Má-li funkce jedno lokální minimum, je to
nuda. Nevíme-li, kolik má funkce lokálních minim, pak
se nikdy nedozvíme, zda to naše je globální a nuda se
prudce změní v nejistotu, apatii nebo ignoranci.
Důsledek: Začněte úvahou. Nejde-li to, použijte hrubou sílu.
Nejde-li to, ignorujte.
Předpoklad: Funkce f(x) je na
daném intervalu spojitá a unimodální. Pak lze nalézt
globální minimum.
Doporučení: Připravte si zásobu
funkcí k minimalizaci a určete graficky přibližnou polohu
minima.
|
|
|
| |
Příklad 13A.1: |
|
| |
Sestavte funkci pro určení odhadu globálního
minima funkce f(x) hrubou silou.
Instrukce: Funkci vyčíslíme
v ekvidistantně rozdělených bodech. Volte nmax úměrně složitosti
funkce f(x). |
|
| |
Řešení: |
|
| |
| function [xmin,fmin]=MinimumBrutal(jmenof,a,b,nmax) |
| % Nalezeni minima funkce f(x) metodou hrube sily |
| % [xmin,fmin]=MinimumBrutal(jmenof,a,b,nmax); |
| % xmin ... souradnice minima |
| % fmin ... nalezena minimalni hodnota f(x) |
| % jmenof ... nazev funkce f(x) jako retezec znaku |
| % a ... dolni mez definicniho oboru f(x) |
| % b ... horni mez definicniho oboru f(x) |
| % nmax ... maximalni pocet vycisleni funkce f(x) |
| h=(b-a)/(nmax-1); |
% krok vycisleni funkce |
| fmin=inf; |
% doposud nejlepsi reseni |
| for k=1:nmax |
% bezpecny cykl |
| x=a+h*(k-1); |
% novy bod |
| f=feval(jmenof,x); |
% vycislit v novem bode |
| if f<fmin |
% je to lepsi? |
| fmin=f; |
% aktualizace hodnoty minima |
| xmin=x; |
% aktualizace polohy minima |
| end |
| end |
|
|
| |
| |
Příklad 13A.2: |
|
| |
Sestavte funkci pro nalezení globálního
minima unimodální funkce f(x) metodou půlení intervalu.
Instrukce: Krokujte a věřte, že f(x) má jen jedno
lokální minimum. |
|
| |
Řešení: |
|
| |
| function [x]=MinimumPuleni(jmenof,a,b) |
| % Nalezeni souradnice minima funkce f(x) metodou puleni |
| % [x]=MinimumPuleni(jmenof,a,b); |
| % x ... nalezena souradnice minima |
| % jmenof ... nazev funkce f(x) jako retezec znaku |
| % a ... dolni mez intervalu |
| % b ... horni mez intervalu |
| h=Epsilon((a+b)/2); |
% automaticka volba diference |
| nmax=40; |
% maximalni pocet vycisleni |
| for k=1:floor(nmax/2) |
% proc? |
| x=(a+b)/2; |
% stred intervalu |
| f=feval(jmenof,x); |
% vycislit v polovine |
| g=feval(jmenof,x+h); |
% vycislit o kousek vedle |
| if f<g |
% je neco v intervalu <a;x>? |
| b=x+h; |
% zahozeni intervalu (x+h;b> |
| else |
| a=x; |
% zahozeni intervalu <a;x) |
| end |
| end |
| x=(a+b)/2; |
% kompromis |
|
|
| |
| |
Příklad 13A.3: |
|
| |
Sestavte funkci pro nalezení globálního minima
unimodální funkce f(x) metodou zlatého řezu.
Instrukce:
Krokujte promyslete detaily algoritmu. Co se stane, když f(x)
má více lokálních minim? |
|
| |
Řešení: |
|
| |
| function [x]=MinimumGold(jmenof,a,b,nmax) |
| % Nalezeni souradnice minima funkce f(x) metodou zlateho rezu |
| % [x]=MinimumGold(jmenof,a,b,nmax); |
| % x ... nalezena souradnice minima |
| % jmenof ... nazev funkce f(x) jako retezec znaku |
| % a ... dolni mez intervalu |
| % b ... horni mez intervalu |
| % nmax ... pocet vycisleni funkce |
| gold=(sqrt(5)-1)/2; |
% pomer zlateho rezu |
| % vycisleni v pravem bode |
| x1=a+(b-a)*gold;f1=feval(jmenof,x1); |
| % vycisleni v levem bode |
| x2=b+(a-b)*gold;f2=feval(jmenof,x2); |
| for k=3:nmax |
% proc? |
| % je minimum v intervalu <x2;b>? |
| if f1<f2 |
| a=x2;x2=x1;f2=f1; |
% posunout dolni mez |
| x1=a+(b-a)*gold; |
% vytvorit pravy bod |
| f1=feval(jmenof,x1); |
% vycisleni v pravem bode |
| else |
| b=x1;x1=x2;f1=f2; |
% posunout horni mez |
| x2=b+(a-b)*gold; |
% vytvorit levy bod |
| f2=feval(jmenof,x2); |
% vycisleni v levem bode |
| end |
| end |
| x=(a+b)/2; |
% kompromis |
|
|
| |
| |
Příklady pro samostatné vypracování |
|
| |
Příklad 13B.1: |
|
| |
Z plechu o rozměrech 100 x 200 mm vyřízněte
v rozích čtyři stejné čtverce tak, aby ohnutím a spájením vznikla
krabička maximálního objemu. |
|
| |
| |
Příklad 13B.2: |
|
| |
Nejhorší střelec soutěže vůbec netrefil
svůj terč. Za trest musel vysbírat všechny prázdné nábojnice
a vajgly na celé střelnici. Pod jakým úhlem musel stočit
kruhový terč do kužele, aby se do něj
vešlo co nejvíce odpadu? |
|
| |
| |
Příklad 13B.3: |
|
| |
Jaký průměr dna má 500 ml
uzavřená konzerva, na kterou se spotřebuje co nejméně
plechu? Spotřebu materálu na švy zanedbejte.
Odpad je recyklovatelný. |
|
| |
| |
Příklad 13B.4: |
|
| |
Metodu MinimumPuleni vylepšete tak,
aby po dosažení požadované přesnosti v x předčasně
ukončila činnost. |
|
| |
| |
Příklad 13B.5: |
|
| |
V podobném duchu upravte i metodu
zlatého řezu. |
|
| |
| |
Příklad 13B.6: |
|
| |
Powellova metoda vyčísluje na počátku
funkci v krajních bodech intervalu a v jeho středu.
Pak je proložena třemi body parabola. Je-li její minimum
uvnitř jednoho z podintervalů, pak funkci vyčíslíme. Jinak rozpůlíme
podinterval s nižší krajní hodnotou a funkci vyčíslíme.
Provedeme diskusi funkčních hodnot a jeden ze dvou krajních
podintervalů vyloučíme. Tak postupujeme až do požadovaného
zúžení intervalu. Vytvořte funkci pro Powellovu metodu. |
|
| |
| |
Příklad 13B.7: |
|
| |
Všechny předchozí funkce doplňte tak,
aby vracely také hodnotu funkce a počet vyčíslení funkce. |
|
| |
| |
Seznam použitých příkazů |
|
| |
|
|
|