OBSAH WEBU
ČTĚTE!
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
temata:23-numericke_metody_pravdepodobnosti:main [2011/03/19 14:25] vagabund [Numerické metody rešení soustav nelineárních rovnic] |
temata:23-numericke_metody_pravdepodobnosti:main [2012/03/05 13:58] (aktuální) conyx [Numerické metody rešení nelineárních rovnic] |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| + | ~~ODT~~ | ||
| + | |||
| ====== 23. Numerické metody a matematická pravděpodobnost ====== | ====== 23. Numerické metody a matematická pravděpodobnost ====== | ||
| Řádek 317: | Řádek 319: | ||
| Skončíme, pokud platí: <m>b_k - a_k < 2\epsilon</m> | Skončíme, pokud platí: <m>b_k - a_k < 2\epsilon</m> | ||
| - | Řešením je potom <m>x_k = {b_k - a_k}/2</m> | + | Řešením je potom <m>x_k = {b_k + a_k}/2</m> |
| </box> | </box> | ||
| Řádek 465: | Řádek 467: | ||
| </box> | </box> | ||
| - | === metoda prosté iterace === | + | === Metoda prosté iterace === |
| <box round blue 90%> | <box round blue 90%> | ||
| Řádek 663: | Řádek 665: | ||
| <m>\vec{F} = (f_1, ..., f_n)^T</m> | <m>\vec{F} = (f_1, ..., f_n)^T</m> | ||
| - | Řešení se počítá podle vztahu: | + | Vychází se ze vztahu: |
| <m>\vec{x^{(k+1)}} = \vec{x^{(k)}} − (\vec{F\prime (\vec{x^{(k)}}))}^{-1} \vec{F(\vec{x^{(k)}})}</m> | <m>\vec{x^{(k+1)}} = \vec{x^{(k)}} − (\vec{F\prime (\vec{x^{(k)}}))}^{-1} \vec{F(\vec{x^{(k)}})}</m> | ||
| + | |||
| + | Je potřeba spočítat inverzní matici, což je pracné, proto vztah upravíme: | ||
| + | |||
| + | <m>\vec{F\prime (\vec{x^{(k)}})}(\vec{x^{(k+1)}} - \vec{x^{(k)}}) = -\vec{F(\vec{x^{(k)}})}</m> | ||
| + | |||
| + | Označme <m>{\delta}^{(k)} = x^{(k+1)} − x^{(k)} = ({\delta_1}^{(k)}, ..., {\delta_n}^{(k)})^T</m> | ||
| + | |||
| + | Řešíme potom soustavu: | ||
| + | |||
| + | <m>\vec{F\prime (\vec{x^{(k)}})}{\delta}^{(k)} = -\vec{F(\vec{x^{(k)}})}</m> | ||
| + | |||
| + | s neznámými <m>{\delta_1}^{(k)}, ..., {\delta_n}^{(k)}</m>. | ||
| + | |||
| + | Novou aproximaci potom dostaneme: | ||
| + | |||
| + | <m>x^{(k+1)} = x^{(k)} + {\delta}^{(k)}</m> | ||
| + | |||
| + | Počítáme, dokud není splněno: | ||
| + | |||
| + | <m>||x^{(k)} − x^{(k−1)}|| < \epsilon</m> neboli <m>||{\delta}^{(k−1)}|| < \epsilon||</m> | ||
| </box> | </box> | ||
| + | <box round green 90%|**Příklad**> | ||
| + | |||
| + | Newtonovou metodou najdete rešení soustavy rovnic | ||
| + | |||
| + | <m>\matrix{2}{3}{ | ||
| + | {(x − 1)^2 + y^2 − 4} {=} {0} | ||
| + | {x + (y + 1)^2 − 1} {=} {0} | ||
| + | }</m> | ||
| + | |||
| + | s presností <m>\epsilon = 0.01</m>. | ||
| + | |||
| + | {{:temata:23-numericke_metody_pravdepodobnosti:newtonexampl.jpg|}} | ||
| + | |||
| + | \\ | ||
| + | \\ | ||
| + | |||
| + | Řešení: | ||
| + | |||
| + | Zvolme <m>x^(0) = (0,−2)</m>. | ||
| + | |||
| + | <m>f_1(x, y) = (x − 1)^2 + y^2 − 4</m>\\ | ||
| + | <m>f_2(x, y) = x + (y + 1)^2 − 1</m>\\ | ||
| + | |||
| + | <m>F\prime = (\matrix{2}{2}{ | ||
| + | {{\partial f_1}/{\partial x}} {{\partial f_1}/{\partial y}} | ||
| + | {{\partial f_2}/{\partial x}} {{\partial f_2}/{\partial y}} | ||
| + | }) = (\matrix{2}{2}{ | ||
| + | {2(x − 1)} {2y} | ||
| + | {1} {2(y + 1)} | ||
| + | })</m> | ||
| + | |||
| + | \\ | ||
| + | **1. krok** | ||
| + | \\ | ||
| + | |||
| + | <m>F\prime(0,−2) = (\matrix{2}{2}{ | ||
| + | {−2} {−4} | ||
| + | {1} {−2} | ||
| + | })</m> | ||
| + | |||
| + | <m>F(0,−2) = (\matrix{2}{1}{1 0})</m> | ||
| + | |||
| + | <m>\matrix{2}{5}{ | ||
| + | {−2\delta_1} {−} {4\delta_2} {=} {−1} | ||
| + | {\delta_1} {−} {2\delta_2} {=} {0} | ||
| + | }</m> | ||
| + | |||
| + | <m>\delta_1 = 1/4 = 0.25, \delta_2 = 1/8 = 0.125</m> | ||
| + | |||
| + | <m>x^(1) = (0 + 0.25,−2 + 0.125) = (0.25, −1.875)</m>. | ||
| + | |||
| + | \\ | ||
| + | **2. krok** | ||
| + | \\ | ||
| + | |||
| + | <m>\delta_1 = 0.01225</m>, <m>\delta_2 = 0.01593</m> | ||
| + | |||
| + | <m>x^(2) = (0.26225, −1.85907)</m>. | ||
| + | |||
| + | \\ | ||
| + | **3. krok** | ||
| + | \\ | ||
| + | |||
| + | <m>\delta_1 = −0.00004</m>, <m>\delta_2 = 0.00012</m> | ||
| + | |||
| + | <m>x^(3) = (0.26221, −1.85894)</m>. | ||
| + | |||
| + | <m>\delim{|}{\delta_1}{|} < 0.01</m> a <m>\delim{|}{\delta_2}{|} < 0.01</m>, můžeme skončit. | ||
| + | |||
| + | </box> | ||
| ===== Numerické rešení obyčejných diferenciálních rovnic ===== | ===== Numerické rešení obyčejných diferenciálních rovnic ===== | ||
| Řádek 705: | Řádek 797: | ||
| <m>h_i = x_{i + 1} - x_i</m> ... krok | <m>h_i = x_{i + 1} - x_i</m> ... krok | ||
| - | Podle počtu kroků dělíme metody na: | + | Podle toho, jestli metoda využívá předchozí hodnoty nebo ne, dělíme metody na: |
| * jednokrokové | * jednokrokové | ||
| - | * vícekrokové | + | * vícekrokové (<m>y_{n-1}, y_{n-2}, ...</m>) |
| **Počáteční úloha** | **Počáteční úloha** | ||
| Řádek 731: | Řádek 823: | ||
| <m>y_{i + 1} = y_i + hf(x_i, y_i)</m> | <m>y_{i + 1} = y_i + hf(x_i, y_i)</m> | ||
| + | |||
| + | </box> | ||
| + | |||
| + | <box round green 90%|**Příklad**> | ||
| + | |||
| + | Eulerovou metodou s krokem <m>h = 0.1</m> řešte počáteční úlohu | ||
| + | |||
| + | <m>y\prime = x^2 − y, y(0) = 1</m> | ||
| + | |||
| + | na intervalu <m><0, 0.5></m>. | ||
| + | |||
| + | Řešení: | ||
| + | |||
| + | <m>y_{i+1} = y_i + 0.1({x_i}^2 − y_i)</m> | ||
| + | |||
| + | ^<m>i</m>|0|1|2|3|4|5| | ||
| + | ^<m>x_i</m>|0|0.1|0.2|0.3|0.4|0.5| | ||
| + | ^<m>y_i</m>|1|0.9|0.811|0.7339|0.6695|0.6186| | ||
| + | ^<m>y(x_i)</m>|1|0.9052|0.8213|0.7492|0.6897|0.6435| | ||
| </box> | </box> | ||
| Řádek 778: | Řádek 889: | ||
| <m>k_3 = f(x_n + 1/2 h, y_n + 1/2 hk_2)</m>\\ | <m>k_3 = f(x_n + 1/2 h, y_n + 1/2 hk_2)</m>\\ | ||
| <m>k_4 = f(x_n + h, y_n + hk_3)</m> | <m>k_4 = f(x_n + h, y_n + hk_3)</m> | ||
| + | |||
| + | </box> | ||
| + | |||
| + | <box round green 90%|**Příklad**> | ||
| + | |||
| + | Rungovou-Kuttovou metodou řešte počáteční úlohu | ||
| + | |||
| + | <m>y\prime = x^2 − y, y(0) = 1</m> | ||
| + | |||
| + | s krokem <m>h = 0.1</m> na intervalu <m><0, 0.5></m>. | ||
| + | |||
| + | Řešení: | ||
| + | |||
| + | <m>\matrix{5}{3}{ | ||
| + | {k_1} {=} {f(0, 1) = 0^2 − 1 = −1} | ||
| + | {k_2} {=} {f(0 + 1/2 0.1, 1 + 1/2 0.1(−1)) = f(0.05, 0.95) = −0.9475} | ||
| + | {k_3} {=} {f(0 + 1/2 0.1, 1 + 1/2 0.1(−0.9475)) = f(0.05, 0.952625) = −0.950125} | ||
| + | {k_4} {=} {f(0 + 0.1, 1 + 0.1(−0.950125)) = f(0.1, 0.9049875) = −0.8949875} | ||
| + | {y_1} {=} {y_0 + 1/6 0.1(k_1 + 2k_2 + 2k_3 + k_4) \approx 0.9051627} | ||
| + | }</m> | ||
| + | |||
| + | ^<m>n</m>^<m>x_n</m>^<m>y_n</m>^<m>y(x_n)</m>^<m>x</m>^<m>y</m>^ | ||
| + | |0|0|1|1|<m>\matrix{4}{1}{0 0.05 0.05 0.1}</m>|<m>\matrix{4}{1}{1 0.95 0.952625 0.9049875}</m>|<m>\matrix{4}{1}{{k_1 = −1} {k_2 = −0.9475} {k_3 = −0.950125} {k_4 = −0.8949875}}</m>| | ||
| + | |1|0.1|0.9051627|0.9051626|<m>\matrix{4}{1}{0.1 0.15 0.15 0.2}</m>|<m>\matrix{4}{1}{0.9051627 0.8604046 0.8632675 0.8210860}</m>|<m>\matrix{4}{1}{{k_1 = −0.8951627} {k_2 = −0.8379046} {k_3 = −0.8407675} {k_4 = −0.7810860}}</m>| | ||
| + | |2|0.2|0.8212695|0.8212693|<m>\matrix{4}{1}{0.2 0.25 0.25 0.3}</m>|<m>\matrix{4}{1}{0.8212695 0.7822060 0.7852842 0.7489911}</m>|<m>\matrix{4}{1}{{k_1 = −0.7812695} {k_2 = −0.7197060} {k_3 = −0.7227842} {k_4 = −0.6589911}}</m>| | ||
| + | |3|0.3|0.7491822|0.7491818|<m>\matrix{4}{1}{0.3 0.35 0.35 0.4}</m>|<m>\matrix{4}{1}{0.7491822 0.7162230 0.7194960 0.6894826}</m>|<m>\matrix{4}{1}{{k_1 = −0.6591822} {k_2 = −0.5937230} {k_3 = −0.5969960} {k_4 = −0.5294826}}</m>| | ||
| + | |4|0.4|0.6896804|0.6896800|<m>\matrix{4}{1}{0.4 0.45 0.45 0.5}</m>|<m>\matrix{4}{1}{0.6896804 0.6631964 0.6666456 0.6432659}</m>|<m>\matrix{4}{1}{{k_1 = −0.5296804} {k_2 = −0.4606964} {k_3 = −0.4641456} {k_4 = −0.3932659}}</m>| | ||
| + | |5|0.5|0.6434699|0.6434693| | | | | ||
| </box> | </box> | ||
| Řádek 856: | Řádek 995: | ||
| <m>D(X) = Np(1 - p)</m> | <m>D(X) = Np(1 - p)</m> | ||
| + | |||
| + | </box> | ||
| + | |||
| + | <box round green 90%|**Příklad**> | ||
| + | |||
| + | Stanovte pravděpodobnost jevu, že ve 4 hodech kostkou padnou právě 3 šestky. | ||
| + | |||
| + | Řešení: | ||
| + | |||
| + | <m>P(X = i) = (\matrix{2}{1}{n i}) p^i (1 - p)^{n-i}</m>, | ||
| + | |||
| + | <m>P(X = 3) = (\matrix{2}{1}{4 3}) (1/6)^i (1 - 1/6)^{n-i} \approx 0.015</m> | ||
| </box> | </box> | ||
| Řádek 875: | Řádek 1026: | ||
| </box> | </box> | ||
| + | <box round green 90%|**Příklad**> | ||
| + | |||
| + | Na určítém území dopadí každoročně v určitém období průměrně 7 meteoritů. Jaká je pravděpodobnost, že daný rok v tomto období dopadnou 3 meteority. | ||
| + | |||
| + | Řešení: | ||
| + | |||
| + | <m>P(Y = 3) = {7^3 e^{-7}}/{3!} \approx 0.052129</m> | ||
| + | |||
| + | </box> | ||
| ==== Spojité náhodné veličiny ==== | ==== Spojité náhodné veličiny ==== | ||
| Řádek 884: | Řádek 1044: | ||
| <m>F(t) = \lbrace \matrix{3}{1}{{0 ... t \le a} {{t - a}/{b - a} ... t \in (a, b)} {1 ... t \ge b}}</m> | <m>F(t) = \lbrace \matrix{3}{1}{{0 ... t \le a} {{t - a}/{b - a} ... t \in (a, b)} {1 ... t \ge b}}</m> | ||
| + | |||
| + | <m>E(X) = {a + b}/2</m> | ||
| + | |||
| + | <m>D(X) = {(b - a)^2}/{12}</m> | ||
| <m>Ro(od, do)</m> | <m>Ro(od, do)</m> | ||
| Řádek 903: | Řádek 1067: | ||
| <m>D(X) = {\sigma}^2</m> | <m>D(X) = {\sigma}^2</m> | ||
| - | <m>No(\mu, \sigma)</m> | + | <m>N(\mu, \sigma^2)</m> |
| {{:temata:23-numericke_metody_pravdepodobnosti:normal.jpg|}} | {{:temata:23-numericke_metody_pravdepodobnosti:normal.jpg|}} | ||
| Řádek 929: | Řádek 1093: | ||
| === Exponenciální rozložení === | === Exponenciální rozložení === | ||
| + | <box round blue 90%> | ||
| + | |||
| + | <m>f(x) = \lambda e^{-\lambda x}, \lambda > 0</m> pro <m>x > 0</m> a nulové pro <m>x \le 0</m> | ||
| + | |||
| + | <m>E(x) = 1/{\lambda}</m> | ||
| + | |||
| + | <m>D(x) = 1/{\lambda^2}</m> | ||
| + | |||
| + | </box> | ||
| ===== Generování pseudonáhodných čísel ===== | ===== Generování pseudonáhodných čísel ===== | ||
| + | |||
| + | Základem pro generování jakéhokoli rozložení je generátor rovnoměrně rozložených čísel v intervalu <0, 1). Nejčastějí se používají generátory využívající princip **lineárního kongruentního generátoru**: | ||
| + | |||
| + | <m>x_{i + 1} = (ax_i + b) mod m</m>, | ||
| + | |||
| + | kde <m>a, b, m</m> jsou vhodně zvolené konstanty. | ||
| + | |||
| + | Generátor generuje čísla v rozsahu <m>0 \le x_i \le m</m>.Pro převod na interval <0, 1) je potřeba výsledné pseudonáhodné číslo podělit <m>m</m>, též perioda generátoru. | ||
| + | |||
| + | Pro dobré statistické výsledky je potřeba zvolit vhodné konstanty. Na počítačích se volí <m>m = 2^n</m>, kde <m>n</m> je počet bitů typu unsigned integer (operace modulu se potom děje automaticky). | ||
| + | |||
| + | Nevýhody: | ||
| + | |||
| + | * zhoršení statistických vlastností generátoru špatnou volbou konstant | ||
| + | * závislost po sobě jdoucích generovaných čísel u lineárních generátorů | ||
| + | * pro převod na <m><0, 1)</m> je potřeba vydělit | ||
| + | * málo náhodné poslední významné bity | ||
| + | |||
| + | {{:temata:23-numericke_metody_pravdepodobnosti:generatorwrong.jpg?300|}} | ||
| + | |||
| + | ** příklad generátoru ** | ||
| + | <code> | ||
| + | static unsigned long ix = seed; // počáteční_hodnota | ||
| + | double Random(void) { | ||
| + | ix = ix * 69069L + 1; // implicitní operace modulo | ||
| + | return ix / ((double)ULONG_MAX + 1); | ||
| + | } | ||
| + | </code> | ||
| + | |||
| + | Další možností je **Mersenne twister**. Nemá většinou problémů předchozího generátoru. | ||
| + | |||
| + | ==== Transformace rozložení ==== | ||
| + | |||
| + | Převod rovnoměrného rozložení na jiné, které požadujeme. | ||
| + | |||
| + | metody | ||
| + | |||
| + | * inverzní transformace | ||
| + | * vylučovací metoda | ||
| + | * kompoziční metoda | ||
| + | |||
| + | === inverzní transformace === | ||
| + | |||
| + | * využívá inverzní fuknci k distribuční fci požadovaného rozložení | ||
| + | * vhodná tam, kde je snadné inverzní fci spočítat | ||
| + | |||
| + | **postup**: | ||
| + | |||
| + | * 1. inverze distribuční funkce: <m>F^{-1}</m> | ||
| + | * Generování náhodného čísla s rovnoměrným rozložením: <m>x = R(0, 1)</m> | ||
| + | * Výsledek: <m>y = F^{−1}(x)</m> | ||
| + | |||
| + | <box round green 90%|**Příklad**> | ||
| + | |||
| + | <m>F(x) = 1 − e^{−{{x−A}/b}}</m> | ||
| + | |||
| + | <m>F^{−1}(x) = A − b ∗ ln (1 − x)</m> | ||
| + | |||
| + | pro <m>A = 0, b = 1</m> | ||
| + | |||
| + | {{:temata:23-numericke_metody_pravdepodobnosti:inverzni.jpg?300|}} | ||
| + | |||
| + | Generování: | ||
| + | |||
| + | <m>y_i = A − b ∗ ln (1 − x_i)</m> | ||
| + | |||
| + | </box> | ||
| + | |||
| + | === vylučovací metoda === | ||
| + | |||
| + | Máme graf fce hustoty pravděpodobnosti. Náhodně generujeme body s rovnoměrným rozložením v obdélníku daného grafu, pokud bod leží pod grafem, vrátíme ho, jinak opakujeme generování. | ||
| + | |||
| + | {{:temata:23-numericke_metody_pravdepodobnosti:vylucovaci.jpg|}} | ||
| + | |||
| + | Náhodnou veličinu <m>\xi</m> s funkcí hustoty f(x), x <m>\in</m> <x1, x2), f(x) <m>\in</m> <0,M) (<m>M</m> je max. hodnota <m>f(x)</m>) generujeme takto: | ||
| + | |||
| + | * Generování souřadnice <m>x = R(x_1, x_2)</m> | ||
| + | * Generování souřadnice <m>y = R(0,M)</m> | ||
| + | * Je-li <m>y \le f(x)</m>, pak <m>x</m> prohlásíme za hodnotu náhodné veličiny <m>\xi</m>, jinak jdeme znovu na bod 1 | ||
| + | |||
| + | === kompoziční metoda === | ||
| + | |||
| + | Rozdělíme fci hustoty pravděpodobnosti na několik oblastí a na každou z nich aplikujeme jinou metodu | ||
| + | |||
| + | ===== Zdroje ===== | ||
| + | |||
| + | * Opora IMS | ||
| + | * Skripta INM | ||
| + | * jiný zdroj | ||
| + | |||
| + | ===== Potvrzení ===== | ||
| + | |||
| + | <doodle single login|23> | ||
| + | ^ OK ^ !!! ^ | ||
| + | </doodle> | ||
| + | |||
| + | {{tag>vagabund INM numericke_metody numericke_derivovani numericke_integrovani numericke_reseni_soustav_rovnic rozlozeni_pravdepodobnosti generatory_nahodnych cisel}} | ||
| + | |||
| + | ~~DISCUSSION~~ | ||
