Modely a modelování Definice modelu: Model je napodobenina originálu nebo jeho popis pomocí vymezených prvků a vztahů mezi nimi. Vlastnosti dobrého modelu: Validita - schopnost modelu vystihnout podstatné vlastnosti originálu. Je vyjádřena stupněm shody modelu s originálem v podstatných vlastnostech. Reliabilita - míra spolehlivosti a opakovatelnosti modelu. Vysoká reliabilita znamená, že výsledek modelování je jen nepatrně ovlivněn náhodou a podstatné vlivy jsou v modelu zohledněny. Reliabilní model také umožňuje při opakovaném použití za stejných podmínek získat podobné výsledky. Druhy modelu: - fyzikální model: fyzicky vytvořený objekt, který napodobuje originál (model automobilu, města, stroje, atomu, ...) - abstraktní model: soubor vzorců a pravidel, které zjednodušeně popisují originál. Zjednodušení spočívá ve výběru těch typických vlastností originálu, které jsou významné pro popis jeho chování. Druhy abstraktních modelů: - deterministický model - prvky a vztahy mezi nimi jsou pevně dány. Chování modelu za určitých podmínek je plně předvídatelné (např. modely různých fyzikálních dějů) - stochastický model - prvky modelu a vztahy mezi nimi mají charakter náhodných jevů či náhodných veličin nebo náhodných procesů. V modelu vystupuje jedna nebo více náhodných složek (např. regresní model vysvětlující závislost jedné veličiny na jiných veličinách). Příklady stochastických modelů: - modely systémů hromadné obsluhy - markovské řetězce a procesy popisující vývoj dynamických systémů - modely zásob (umožňují optimalizovat velikost skladu) - modely obnovy (popisují proces náhrady těch prvků, které selhaly) - modely přežití (využití ve zdravotnictví, pojišťovnictví, průmyslu) - modely nabídky a poptávky Speciální metody pro práci se stochastickými modely: - stochastické programování - stochastická teorie řízení - simulační metody Specifika simulačních metod: - používají se při studiu složitějších dějů stochastické povahy, kde se analytické řešení získává j en obtížně - pro experimenty jsou použita náhodná čísla. Tak lze simulovat průběhy reálných dějů při různých hodnotách parametrů a pozorovat vlastnosti modelovaného děje. Možné problémy při simulacích: - neadekvátní popis modelovaného děje - nesprávná volba pravděpodobnostních rozložení náhodných veličin vyskytujících se v modelu - chybné odhady parametrů - nekvalitní generátory pseudonáhodných čísel. Generátory náhodných čísel Definice náhodné posloupnosti čísel: Posloupnost čísel je náhodná, pokud neexistuje kratší způsob vyjádření dané posloupnosti než tato posloupnost samotná, tj. tuto posloupnost nemůžeme zhustit do kratší podoby. Proto žádná posloupnost čísel vzniklých výpočtem nemůže být náhodná, ale jen pseudonáhodná. Náhodná čísla vznikají např. jako výsledky náhodných fyzikálních procesů. Nelze předvídat výskyt určité hodnoty a jednotlivé hodnoty jsou nezávislé. Náhodná čísla potřebujeme např. v těchto situacích: - generování náhodných výběrů - simulace fyzikálních procesů - simulované úlohy používané k řešení složitých matematických problémů, které nelze řešit analyticky - modelování dějů, kde se vyskytují náhodné jevy nebo náhodné veličiny - kryptografie - počítačové hry - atd. Způsoby generování náhodných čísel Mechanický způsob: losování čísel z osudí, házení kostkami, ruleta. Pro většinu aplikací je tento způsob příliš pomalý. Fyzikální způsob: je založen na měření určitého jevu, který nastává náhodně (např. rozpad radioaktivní látky). Lze také v pravidelných intervalech měřit šum na polovodičových přechodech. Problémem je připojení generátoru šumu k počítači. Použití tabulek náhodných čísel: K jejich tvorbě se používaly rozsáhlé soubory dat získané k jiným účelům (např. čísla v telefonním seznamu apod.). Např. z roku 1927 pocházejí Tippetovy tabulky. Pro počítačové experimenty většího rozsahu jsou ovšem nevhodné. Softwarový způsob: na základě nějakého algoritmu vytváří počítač posloupnost čísel, která má zdánlivě vlastnosti náhodné posloupnosti, ale je pouze pseudonáhodná. Ukázka prvních 30 čtveřic náhodných čísel z Tippetovy tabulky: 2952 6641 3170 5624 7203 5356 I34O8 2769 0560 5246 3992 9792 4167 9525 1300 2693 3563 6107 1112 9025 7979 5911 1545 13% 2370 7483 6913 7691 6008 8126 Generování pseudonáhodných čísel Většina algoritmů pro generování pseudonáhodných čísel má rekurentní tvar xn+i = F(xn, xn_i, ..x0), kde x0 je vhodná počáteční hodnota zvaná násada nebo semínko (seed) a F je příslušná funkce. Tyto algoritmy umožňují vytváření jen periodické posloupnosti. Nej rozšířenějšími zdroji pro generování pseudonáhodných čísel jsou tzv. kongruenční generátory. Příklady kongruenčních generátorů: - aditivní generátor (Fibonacciův): xn+i= xn + xn_i (mod M) - multiplikativní generátor (Lehmerův): xn+i= axn (mod M) - smíšený generátor: xn+i= axn + b (mod M) V praxi: kombinují se dva (nebo i více) kongruenční generátory, aby se eliminovala případná závislost mezi členy posloupnosti. Požadavky kladné na pseudonáhodná čísla používaná v simulacích: - dostatečně dlouhé posloupnosti bez opakování (řádově aspoň 109 hodnot) - rychlý výpočetní algoritmus generování pseudonáhodných čísel - splnění důležitých vlastností (musí se řídit daným typem rozložení, musí projít testy náhodnosti a nezávislosti). Náhodná čísla a náhodné číslice V užším slova smyslu jsou za náhodná čísla považovány realizace nezávislých náhodných veličin z Rs(0,l), tj. hustota u}. Kroky 1 a 2 se opakují n-krát. Příklad: Opakovaně vypisovaných výběrových řízení se účastní vždy 4 firmy, označme je A, B, C, D. Pravděpodobnost, že jejich nabídky budou vybrány, jsou postupně 0,2; 0,3; 0,4 a 0,1. Pro n = 10 simulujte výsledky opakovaných výběrových řízení. Řešení: Zavedeme náhodnou veličinu X, která nabývá hodnoty 1, když vyhraje firma A, hodnoty 2, když vyhraje B, hodnoty 3, když vyhraje C a hodnoty 4, když vyhraje D. Najdeme distribuční funkci náhodné veličiny X. Oprox g 0,2 pro x g (l, 2) 0(x) = j 0,5 pro x g (2,3) 0,9 pro x g (3,4) lprox g (4, co) Vygenerujeme číslo u g (o,l) a transformujeme ho takto: 1 pro 0 < u < 0,2 2 pro 0,2 < u < 0,5 3 pro 0,5 0,7654321 je 3, tedy v tomto případě vyhraje firma C. x = < Simulaci provedeme v MATLABu pomocí funkce simulace_DNV(n,v): function [realizace]=simulace_DNV(n,v) % autor: Petra Cabalková % funkce generuje n realizaci diskrétni náhodne veličiny % pravdepodobnosti realizace zádava vektor rozloženi pravdepodobnosti v % syntaxe: [realizace]=simulace_DNV(n,v) % vstupní parametr: n ... počet kroku simulace % v ... vektor rozloženi pravdepodobnosti diskrétni nah.veličiny % výstupní parametr: % realizace ... vektor realizaci diskrétni náhodne veličiny realizace=[]; m=length(v); for i=l:n u=unifrnd(0,1,1,1); if usum(v(l,l:m-l)) x=m;end; for j=2:(m-l) if (u>sum(v(l,l:j-l))) & (u<=sum(v(l,l:j))) x=j;end; end realizace=[realizace x]; end plot(realizace,'o') Funkci zavoláme s parametry n = 10, v = [0.2 0.3 0.4 0.1]. Dostaneme výstup: realizace = 2331 124232 Vidíme, že při 1. konkurzu vyhraje firma B, při 2. a 3. firma C atd. Simulaci můžeme doplnit tabulkou rozložení četností: tabulate(realizace) Value Count Percent 1 2 20.00% 2 4 40.00% 3 3 30.00% 4 1 10.00% b) Spojitá náhodná veličina Metoda inverzní transformace je založena na dvou následujících větách. Věta 1.: Nechť spojitá náhodná veličina X má rostoucí distribuční funkci <3>(x) (tzn., že k ní existuje inverzní funkce 0-1(y) - tzv. kvantilová funkce). Pak transformovaná náhodná veličina Y = <3>(X) má rozložení Rs(0,l). Důkaz: Označme <3>*(y) distribuční funkci náhodné veličiny Y. 0,(y)= P(Y < y) = P(0(X)< y)= p(x < ®l(y))= ®{®l(y)) = y pro y e (0,l), O* (y) = 0 pro y g (- oo, O) ? ® * (y) = 1 pro y g (l, co) Tedy Y~Rs(0,l). Věta 2.: Nechť X ~ Rs(0,l) a nechť <3> je rostoucí spojitá distribuční funkce. Pak transformovaná náhodná veličina Y = 0_1(X) má distribuční funkci O. Důkaz: Označme <3>*(y) distribuční funkci náhodné veličiny Y. 0>,(y)= P(Y < y)=?(®-1{x)(x) = ?ie~Xxprox>0 , , 0 n •• , . Odtud odvodíme: 0 jinak u = O(x) = 1 - q~Xx => x = - - ln(l - u). V našem případě X = 0,5, tedy x = -21n(l - u). Samotnou simulaci provedeme v MATLABu pomocí funkce sim_expon(n,lambda): function x=sim_expon(n, lambda) % funkce generuje n realizaci spojité náhodne veličiny s exp. rozlozenim % s exponencialnim rozlozenim % syntaxe: x=sim_expon(n,lambda) % vstupni parametry: % n ... počet realizaci % lambda ... parametr exponenciálního rozloženi % vystupni parametr: % x ... vektor realizaci náhodne veličiny s exp. rozlozenim u=unifrnd(0,1 ,n, 1); x=-( 1/lambda)* log( 1 -u); plot(x/o') pocet=[l:n]'; t=cumsum(x); figuře stairs(t,pocet) X = 3.3718 4.7245 0.2716 4.8924 2.0013 0.2053 0.6528 1.5832 6.3168 6.6985 6h 1 2 3 4 5 6 7 10 Znamená to, že při této simulaci první auto přijede 3,3718 min po začátku sledování, druhé auto přijede 4,7245 min po prvním autu atd. Příklad: Generování z normálního rozložení Náhodná čísla z normálního rozložení nemůžeme generovat metodou inverzní transformace, x j (t~n)2 protože nelze analyticky vyjádřit inverzní funkci k distribuční funkci ®(x)= í aj^Q 2° ^ • a) Metoda založená na centrální limitní větě Nechť {Xn}^=1 je posloupnost náhodných veličin definovaných na témž pravděpodobnostním prostoru, která splňuje tyto podmínky: - náhodné veličiny X1; X2, ... jsou stochasticky nezávislé - náhodné veličiny X1; X2, ... mají všechny stejné rozložení se střední hodnotou \i a rozptylem o2. Pak posloupnost standardizovaných součtů Un= ,n=l,2,... konverguje v distribuci k náhodné veličině U ~ N(0,1), tj. platí: Vx e R : i1™1^11* " x) = °(x) > kde °(x) Je distribuční funkce rozložení N(0,1). Zvolíme náhodné veličiny s Rs(0,l): Nechť Xi, Xn jsou stochasticky nezávislé náhodné veličiny, Xl ~ Rs(0,l), tedy E(X>±D(X>^,i = l,...,n.Pak^^ 12 V i=l J i=l 12 Podle CLV náhodná veličina n n n u„ = —-f=—= 1=1 ^- ~ n(o,i) o 12 Stačí volit n = 12 a pak u12 = Xx> -6 « n(0,l). i=l Generování provedeme v MATLABu pomocí funkce clv(mi,sigma,n): function [realizace]=clv(mi, sigma,n) % funkce generuje cisla z normálního rozloženi pomoci CL V % syntaxe: realizace=clv(mi,sigma, n) % výstupní parametr: % realizace ... vektor realizaci náhodne veličiny s rozložením N(mi, sigmaA2) % vstupní parametry: % mi... stredni hodnota % sigma ... směrodatná odchylka % n ... počet realizaci realizace=[]; for i=l:n u=unifrnd(0,1,12,1); x=sum(u)-6; realizace=[realizace;x]; end sh=mi*ones(n,l); realizace=sh+sigma*realizace; hist(realizace) Nevýhody: - najedno náhodné číslo z N(|i, a2) je zapotřebí vygenerovat 12 čísel z Rs(0,l); - rozložení takto vygenerovaných náhodných čísel je oboustranně useknuté v bodech -6, 6; - Aproximace není uspokojivá vně intervalu (n -3a,\x + 3o). Tento nedostatek lze částečně napravit tak, že vygenerovaná náhodná čísla budeme transformovat pomocí polynomu. b) Aproximace polynomem Realizace generované v bodě (a) upravíme takto: y=0,25x u=aiy + a3y3 + a5y5 + a7y7 + a9y9, kde koeficienty jsou: ^ = 3,949846138 a3 = 0,252408784 a5 = 0,076542912 a7 = 0,008355968 a9 = 0,029899776. Hodnoty u lze považovat za realizace náhodné veličiny s rozložením N(0,1). Funkci clv.m upravíme tak, aby poskytovala uspokojivější realizace normálního rozložení: fimction [realizace]=clv_polynom(mi,sigma,n) % funkce generuje cisla z normálního rozloženi pomoci CLV % pouziva aproximaci polynomem % syntaxe: realizace=clv_polynom(mi,sigma, n) % výstupní parametr: % realizace ... vektor realizaci náhodne veličiny s rozložením N(mi, sigmaA2) % vstupní parametry: % mi ... strední hodnota % sigma ... směrodatná odchylka % n ... počet realizaci al =3.949846138; a3 = 0.252408784; a5 = 0.076542912; a7 = 0.008355968; a9 = 0.029899776; realizace=[]; for i=l:n u=unifrnd(0,1,12,1); x=sum(u)-6; y=0.25*x; u=al*y+a3*yA3+a5*yA5+a7*yA7+a9*yA9; realizace=[realizace ;u]; end sh=mi*ones(n,l); realizace=sh+sigma* realizace; hist(realizace) c) Metoda založená na Boxově - Miillerově transformaci Nechť Xi, x2 jsou dvě nezávislá čísla z Rs(0,l). Pak transformovaná čísla Zj = A/-21nx1 cos27ix2,z2 = >/-21nx1 sin27ix2 lze považovat za realizace náhodné veličiny s rozložením N(0,1). Funkce B M_transformace(mi, sigmám) generuje náhodná čísla z normálního rozložení právě tímto způsobem. function [realizace]=BM_transformace(mi, sigma,n) % funkce generuje cisla z normálního rozloženi pomoci BM transformace % syntaxe: realizace=BM_transformace(mi, sigma, n) % výstupní parametr: % realizace ... vektor realizaci náhodne veličiny s rozložením N(mi, sigmaA2) % vstupní parametry: % mi... stredni hodnota % sigma ... směrodatná odchylka % n ... počet realizaci (musi byt sude cislo) realizace=[]; for i=l:n/2 u 1 =unifrnd(0,1,1,1); u2=unifrnd(0,1,1,1); xl=sqrt(-2*log(ul))*cos(2*pi*u2) x2=sqrt(-2* log(u 1 ))* sin(2* pi* u2) realizace=[realizace;xl ;x2]; end sh=miílíones(n,l); realizace=sh+sigmaílírealizace; hist(realizace) Poznámky k metodě Monte Carlo (MMC) Je to stochasticko - numerická metoda založená na generování (pseudo)náhodných čísel. Modeluje chování náhodných veličin a na základě statistického odhadu jejich charakteristik umožňuje řešit různé matematické problémy i problémy z praxe. Používá se zvláště k řešení takových úloh, kde analytické řešení je obtížné nebo dokonce nemožné. Využití v matematice: Výpočet určitých integrálů (včetně vícenásobných) Řešení systémů rovnic (algebraických i diferenciálních) Výpočet hodnoty funkce Využití v praxi: V oblasti financí a pojišťovnictví Při analýze rizika Ve studiu životního prostředí V počítačové grafice Při předpovědi počasí Historicky nejstarší využití MMC - Buffonuv problém házení jehlou (r. 1777) Zadání: Vodorovná rovina je rozdělena stejně od sebe vzdálenými rovnoběžkami, jejich vzdálenost označíme d. Hodíme na ni jehlu délky h, která je menší než vzdálenost rovnoběžek. Každou polohu jehly považujeme za stejně nadějnou. Jaká je pravděpodobnost, že jehla protne některou rovnoběžku? Polohu jehly v rovině můžeme popsat úhlem cp, který jehla svírá s rovnoběžkami a souřadnicemi [x, y] jejího středu. Vodorovnou souřadnici ztotožníme s rovnoběžkou, která je nejbližší středu jehly. Hodnota y je tedy vzdálenost středu jehly od nejbližší rovnoběžky, 0 < y < d/2 . Je zřejmé, že na hodnotě x nezáleží. Protože každá poloha jehly je stejně nadějná, stačí se omezit na úhel Řešení: Oblast G lze popsat takto: G = j( 71 Když Y 2 h . , dojde k protětí pro ty hodnoty cp, pro něž je y < — sin