Diskretizace

Řešení diskretizované parciální diferenciální rovnice, získané metodou konečných prvků.

Diskretizace je v aplikované matematice proces převodu spojitých funkcí, modelů, proměnných, a rovnic na diskrétní protějšky. Tento proces se obvykle provádí jako první krok pro numerické vyhodnocování a implementaci na digitálním počítači. Speciálním případem diskretizace je dichotomizace, při níž je počet diskrétních tříd roven 2, kterou můžeme aproximovat spojitou proměnnou pomocí binární proměnné (vytváření dichotomie pro účely modelování, jako při binární klasifikaci).

Diskretizace také souvisí s diskrétní matematikou, a je důležitou komponentou granulárních výpočtů. V tomto kontextu se může diskretizace také odkazovat na modifikace proměnné nebo kategorie granularity, když se např. agreguje více diskrétních proměnných nebo když se slučuje více diskrétních kategorií.

Při diskretizaci spojitých dat dochází k určité diskretizační chybě. Je snahou omezit její velikost na úroveň považovanou za zanedbatelnou pro požadované účely modelování.

Termíny diskretizace a kvantizace často mají stejnou denotaci ale ne vždy stejnou konotaci. (Konkrétně, oba termíny sdílí sémantické pole.) Totéž platí o diskretizační chybě a kvantování.

Mezi matematické metody používané pro diskretizaci patří Eulerova–Maruyamova metoda a extrapolace nultého řádu.

Diskretizace lineárních modelů stavového prostoru

Diskretizace se také zabývá transformacemi spojitých diferenciálních rovnic na diskrétní diferenční rovnice vhodné pro numerické výpočty.

Model stavového prostoru se spojitým časem

${\dot {\mathbf {x} }}(t)=\mathbf {A} \mathbf {x} (t)+\mathbf {B} \mathbf {u} (t)+\mathbf {w} (t)$

$\mathbf {y} (t)=\mathbf {C} \mathbf {x} (t)+\mathbf {D} \mathbf {u} (t)+\mathbf {v} (t)$

kde v a w jsou spojité zdroje bílého šumu s nulovým průměrem s výkonovými spektrálními hustotami

$\mathbf {w} (t)\sim N(0,\mathbf {Q} )$

$\mathbf {v} (t)\sim N(0,\mathbf {R} )$

které lze, pokud předpokládáme extrapolace nultého řádu vstupu u a spojitou integraci šumu v, diskretizovat do tvaru

$\mathbf {x} [k+1]=\mathbf {A} _{d}\mathbf {x} [k]+\mathbf {B} _{d}\mathbf {u} [k]+\mathbf {w} [k]$

$\mathbf {y} [k]=\mathbf {C} _{d}\mathbf {x} [k]+\mathbf {D} _{d}\mathbf {u} [k]+\mathbf {v} [k]$

s kovariancemi

$\mathbf {w} [k]\sim N(0,\mathbf {Q} _{d})$

$\mathbf {v} [k]\sim N(0,\mathbf {R} _{d})$

kde

$\mathbf {A} _{d}=e^{\mathbf {A} T}={\mathcal {L}}^{-1}\{(s\mathbf {I} -\mathbf {A} )^{-1}\}_{t=T}$

$\mathbf {B} _{d}=\left(\int _{\tau =0}^{T}e^{\mathbf {A} \tau }d\tau \right)\mathbf {B} =\mathbf {A} ^{-1}(\mathbf {A} _{d}-I)\mathbf {B}$, pokud $\mathbf {A}$ není singulární

$\mathbf {C} _{d}=\mathbf {C}$

$\mathbf {D} _{d}=\mathbf {D}$

$\mathbf {Q} _{d}=\int _{\tau =0}^{T}e^{\mathbf {A} \tau }\mathbf {Q} e^{\mathbf {A} ^{\top }\tau }d\tau$

$\mathbf {R} _{d}=\mathbf {R} {\frac {1}{T}}$

a $T$ je vzorkovací interval, kde $\mathbf {A} ^{\top }$ je transponovaná matice $\mathbf {A}$. Rovnice pro diskretizované měření šumu je důsledkem faktu, že spojité měření šumu je definováno výkonovou spektrální hustotou.

Chytrým trikem pro výpočet A_d a B_d v jednom kroku je využití následující vlastnosti:

$e^{{\begin{pmatrix}\mathbf {A} &\mathbf {B} \\\mathbf {0} &\mathbf {0} \end{pmatrix}}T}={\begin{pmatrix}\mathbf {A_{d}} &\mathbf {B_{d}} \\\mathbf {0} &\mathbf {I} \end{pmatrix}}$

Kde $\mathbf {A} _{d}$a $\mathbf {B} _{d}$jsou diskretizované matice stavového prostoru.

Diskretizace procesního šumu

Numerické vyhodnocení $\mathbf {Q} _{d}$ může být poněkud obtížné, kvůli maticovému exponenciálnímu integrálu. Je však možné jej vypočítat tak, že nejdříve zkonstruujeme matici, a pak vypočítáme její exponenciální funkci

$\mathbf {F} ={\begin{pmatrix}-\mathbf {A} &\mathbf {Q} \\\mathbf {0} &\mathbf {A} ^{\top }\end{pmatrix}}T$

$\mathbf {G} =e^{\mathbf {F} }={\begin{pmatrix}\dots &\mathbf {A} _{d}^{-1}\mathbf {Q} _{d}\\\mathbf {0} &\mathbf {A} _{d}^{\top }\end{pmatrix}}.$

Diskretizovaný procesní šum pak lze vyčíslit znásobením transponované spodní pravé části matice G a horní pravé části matice G:

$\mathbf {Q} _{d}=(\mathbf {A} _{d}^{\top })^{\top }(\mathbf {A} _{d}^{-1}\mathbf {Q} _{d})=\mathbf {A} _{d}(\mathbf {A} _{d}^{-1}\mathbf {Q} _{d}).$

Odvození

Začneme spojitým modelem

$\mathbf {\dot {x}} (t)=\mathbf {A} \mathbf {x} (t)+\mathbf {B} \mathbf {u} (t)$

víme, že exponenciála matice je

${\frac {d}{dt}}e^{\mathbf {A} t}=\mathbf {A} e^{\mathbf {A} t}=e^{\mathbf {A} t}\mathbf {A}$

a přednásobením modelu dostaneme

$e^{-\mathbf {A} t}\mathbf {\dot {x}} (t)=e^{-\mathbf {A} t}\mathbf {A} \mathbf {x} (t)+e^{-\mathbf {A} t}\mathbf {B} \mathbf {u} (t)$

což rozpoznáváme jako

${\frac {d}{dt}}(e^{-\mathbf {A} t}\mathbf {x} (t))=e^{-\mathbf {A} t}\mathbf {B} \mathbf {u} (t)$

a integrováním dostaneme

$e^{-\mathbf {A} t}\mathbf {x} (t)-e^{0}\mathbf {x} (0)=\int _{0}^{t}e^{-\mathbf {A} \tau }\mathbf {B} \mathbf {u} (\tau )d\tau$

$\mathbf {x} (t)=e^{\mathbf {A} t}\mathbf {x} (0)+\int _{0}^{t}e^{\mathbf {A} (t-\tau )}\mathbf {B} \mathbf {u} (\tau )d\tau$

což je analytické řešení spojitého modelu.

Nyní chceme diskretizovat výše uvedený výraz. Předpokládáme, že u je v rámci každého časového kroku konstantní.

$\mathbf {x} [k]\ {\stackrel {\mathrm {def} }{=}}\ \mathbf {x} (kT)$

$\mathbf {x} [k]=e^{\mathbf {A} kT}\mathbf {x} (0)+\int _{0}^{kT}e^{\mathbf {A} (kT-\tau )}\mathbf {B} \mathbf {u} (\tau )d\tau$

$\mathbf {x} [k+1]=e^{\mathbf {A} (k+1)T}\mathbf {x} (0)+\int _{0}^{(k+1)T}e^{\mathbf {A} ((k+1)T-\tau )}\mathbf {B} \mathbf {u} (\tau )d\tau$

$\mathbf {x} [k+1]=e^{\mathbf {A} T}\left[e^{\mathbf {A} kT}\mathbf {x} (0)+\int _{0}^{kT}e^{\mathbf {A} (kT-\tau )}\mathbf {B} \mathbf {u} (\tau )d\tau \right]+\int _{kT}^{(k+1)T}e^{\mathbf {A} (kT+T-\tau )}\mathbf {B} \mathbf {u} (\tau )d\tau$

Výraz v hranatých závorkách je $\mathbf {x} [k]$, a druhý člen lze zjednodušit substitucí za funkci $v(\tau )=kT+T-\tau$. Všimněme si, že $d\tau =-dv$. Také předpokládáme, že $\mathbf {u}$ je při integraci konstantní, což dává

${\begin{matrix}\mathbf {x} [k+1]&=&e^{\mathbf {A} T}\mathbf {x} [k]-\left(\int _{v(kT)}^{v((k+1)T)}e^{\mathbf {A} v}dv\right)\mathbf {B} \mathbf {u} [k]\\&=&e^{\mathbf {A} T}\mathbf {x} [k]-\left(\int _{T}^{0}e^{\mathbf {A} v}dv\right)\mathbf {B} \mathbf {u} [k]\\&=&e^{\mathbf {A} T}\mathbf {x} [k]+\left(\int _{0}^{T}e^{\mathbf {A} v}dv\right)\mathbf {B} \mathbf {u} [k]\\&=&e^{\mathbf {A} T}\mathbf {x} [k]+\mathbf {A} ^{-1}\left(e^{\mathbf {A} T}-\mathbf {I} \right)\mathbf {B} \mathbf {u} [k]\end{matrix}}$

což je přesné řešení problému diskretizace.

Pokud $\mathbf {A}$ není regulární, druhý výraz můžeme stále použít po nahrazení $e^{\mathbf {A} T}$ jeho Taylorovým rozvojem,

$e^{{\mathbf {A} }T}=\sum _{k=0}^{\infty }{\frac {1}{k!}}({\mathbf {A} }T)^{k}.$

Toto dává

${\begin{matrix}\mathbf {x} [k+1]&=&e^{{\mathbf {A} }T}\mathbf {x} [k]+\left(\int _{0}^{T}e^{{\mathbf {A} }v}dv\right)\mathbf {B} \mathbf {u} [k]\\&=&\left(\sum _{k=0}^{\infty }{\frac {1}{k!}}({\mathbf {A} }T)^{k}\right)\mathbf {x} [k]+\left(\sum _{k=1}^{\infty }{\frac {1}{k!}}{\mathbf {A} }^{k-1}T^{k}\right)\mathbf {B} \mathbf {u} [k],\end{matrix}}$

což je tvar používaný v praxi.

Aproximace

Přesná diskretizace může někdy být neproveditelná, protože zahrnuje obtížně vypočitatelnou exponenciálu matice a integrální operace. Mnohem snazší je vypočítat aproximaci diskrétního modelu založenou na malých časových krocích $e^{\mathbf {A} T}\approx \mathbf {I} +\mathbf {A} T$. Aproximací řešení pak bude:

$\mathbf {x} [k+1]\approx (\mathbf {I} +\mathbf {A} T)\mathbf {x} [k]+T\mathbf {B} \mathbf {u} [k]$

Tento postup se nazývá (dopředná) Eulerova metoda. Jinou možnou aproximací je $e^{\mathbf {A} T}\approx \left(\mathbf {I} -\mathbf {A} T\right)^{-1}$, což se nazývá zpětná Eulerova metoda nebo $e^{\mathbf {A} T}\approx \left(\mathbf {I} +{\frac {1}{2}}\mathbf {A} T\right)\left(\mathbf {I} -{\frac {1}{2}}\mathbf {A} T\right)^{-1}$, což se nazývá bilineární nebo Tustinova transformace. Každá z těchto aproximací má jiné podmínky stability. Bilineární transformace zachovává nestabilitu systému se spojitým časem.

Diskretizace spojitých vlastností

Diskretizace ve statistice a strojovém učení se týká procesu převodu spojitých vlastností nebo proměnných na diskretizované nebo nominální vlastnosti. To může být užitečné při vytváření pravděpodobnostních funkcí.

Diskretizace hladkých funkcí

V teorii zobecněných funkcí se diskretizace objevuje jako speciální případ konvoluční věty pro temperované distribuce

${\mathcal {F}}\{f*\operatorname {III} \}={\mathcal {F}}\{f\}\cdot \operatorname {III}$

${\mathcal {F}}\{\alpha \cdot \operatorname {III} \}={\mathcal {F}}\{\alpha \}*\operatorname {III}$

kde $\operatorname {III}$ je Diracův hřeben, $\cdot \operatorname {III}$ je diskretizace, $*\operatorname {III}$ je periodizace, $f$ je rychle klesající temperované rozdělení (například Diracovo delta $\delta$ nebo jiná funkce s kompaktním nosičem), $\alpha$ je hladká, pomalu rostoucí obyčejná funkce (například funkce, která je identicky rovna $1$ nebo jiná funkce s omezeným pásmem) a ${\mathcal {F}}$ je (unitární, s normální frekvencí) Fourierova transformace. Funkce $\alpha ,$ které nejsou hladké, lze převést na hladké použitím vyhlazení před diskretizací.

Například diskretizace funkce, která je identicky rovna $1,$ dává posloupnost $\langle ..,1,1,1,..\rangle$ která, pokud je interpretována jako koeficienty lineární kombinace Diracových delta funkcí, tvoří Diracův hřeben. Pokud se navíc aplikuje zkracování, dostaneme konečné posloupnosti, například $\langle 1,1,1,1\rangle$, které jsou diskrétní jak v čase tak ve frekvenci.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Discretization na anglické Wikipedii.

Literatura

• DECARLO, Raymond, 1989. Linear Systems: A State Variable Approach with Numerical Implementation. [s.l.]: Prentice Hall, NJ. Dostupné online. 
• GELB, Arthur, 1974. Analytic Sciences Corporation. Technical Staff.. Applied optimal estimation.. Cambridge, Mass.: M.I.T. Press. S. 121. Dostupné online. ISBN 0-262-20027-9. 
• VAN LOAN, Charles, 1978. Computing integrals involving the matrix exponential. IEEE Transactions on Automatic Control. Roč. 23, čís. 3, s. 395–404. 
• Robert Grover Brown & Patrick Y. C. Hwang, 1997. Introduction to random signals and applied Kalman filtering. 2. vyd. [s.l.]: [s.n.]. ISBN 978-0471128397. 
• Chi-Tsong Chen, 1984. Linear System Theory and Design. Philadelphia, PA, USA: Saunders College Publishing. ISBN 978-0030716911. 
• C. Van Loan. Computing integrals involving the matrix exponential. IEEE Transactions on Automatic Control. Jun 1978, roč. 23, čís. 3, s. 395–404. Dostupné online. DOI 10.1109/TAC.1978.1101743. 
• R.H. Middleton & G.C. Goodwin, 1990. Digital control and estimation: a unified approach. [s.l.]: [s.n.]. ISBN 978-0132116657. S. 33f. 

Související články

• Diskrétní simulace
• Diskrétní prostor
• Diskrétní čas a spojitý čas
• Metoda konečných diferencí
• Metoda konečných objemů pro neustálený tok
• Vyhlazování
• Stochastická simulace
• Počet na časové škále

Externí odkazy

• Obrázky, zvuky či videa k tématu Diskretizace na Wikimedia Commons

Autoritní data	LCCN: sh2016001385 NLI: 987007396296605171