Tridiagonalni sistemi
Slučajni sprehod
Poglejmo si primer slučajnega sprehoda v eni dimenziji. Slučajni sprehod je vrsta stohastičnega procesa, ki ga lahko opišemo z Markovsko verigo z množico stanj enako celim številom. Če se trenutno nahajamo v stanju $n$, se lahko v naslednjem koraku z verjetnostjo $p$ premaknemo v stanje $n-1$ ali z verjetnostjo $q=1-p$ pa v stanje $n+1$.
# Primer prvih 100 korakov slučajnega sprehoda p=q=1/2
using Plots
scatter(cumsum(2*round.(rand(100)).-1))
savefig("sprehod.png")
Naloga
Izračunaj povprečno število korakov, ki jih potrebujemo, da se od izhodišča oddaljimo za $k$ korakov.
Markovske verige
Markovsko verigo lahko opišemo z zaporedjem slučajnih spremenljivk $X_k$, $k=1,\ldots$, ki opisujejo trenutno stanje Markovske verige z Markovsko lastnostjo
\[P(X_{n+1}=x_{n+1}|X_1=x_1, X_2=x_2, \ldots, X_{n}=x_n) = P(X_{n+1}=x_{n+1}|X_{n}=x_n),\]
ki pomeni, da je verjetnost za prehod v naslednje stanje odvisna le od prejšnjega stanja in ne od starejše zgodovine stanj. Matriko $P$, katere elementi so prehodne verjetnosti prehodov med stanji Markovske verige
\[p_{ij} = P(X_n = j| X_{n-1} = i)\]
imenujemo prehodna matrika Markovske verige. Za prehodno matriko velja, da vsi elementi ležijo na $[0,1]$ in je vsota elementov po vrsticah enaka 1
\[P\mathbf{1} = \mathbf{1}\]
Absorpcijska stanja
Absorpcijsko stanje je stanje, iz katerega se ne moremo več premakniti, medtem ko je prehodno stajne stanje, ki ga obiščemo le končno mnogo krat. Markovske verige z absorpcijskimi takimi stanji imenujemo absobirajoča Markovska veriga. Vrstica v prehodni matriki, ki ustreza absorpcijskemu stanju ima le diagonalni element enak 1, vsi ostali so nič.
Če ima Markovska veriga absorpcijska stanja, lahko prehodno matriko zapišemo v naslednji bločni obliki
\[P = \begin{bmatrix}Q & T\\ 0 & I\end{bmatrix},\]
kjer vrstice $[Q, T]$ ustrezajo prehodnim stanjem, med tem ko vrstice $[0, I]$ ustrezajo absorpcijskim stanjem. Matrika $Q$ opiše prehodne verjetnosti za sprehod med prehodnimi stanji, matrika $Q^k$ prehodne verjetnosti po $k$ korakih, če se sprehajamo le po prehodnih stanjih.
\[N = \sum_{k=0}^\infty Q^k = (I-Q)^{-1}\]
imenujemo fundamentalna matrika absorbirajoče markovske verige. Elementi $n_{ij}$ predstavlja pričakovano število obiskov stanja $j$, če začnemo v stanju $i$.
Pričakovano število korakov, da dosežemo absorpcijsko stanje iz začetnega stanja $i$ je $i$-ta komponenta produkta fundamentalne matrike $N$ z vektorjem samih enic
\[\mathbf{k} = N\mathbf{1} = (I-Q)^{-1}\mathbf{1}.\]
Če želimo poiskati pričakovano število korakov, moramo rešiti sistem linearnih enačb
\[(I-Q)\mathbf{k} = \mathbf{1}.\]
Prehodna in fundamentalna matrika slučajnega sprehoda
Če nas zanima le kdaj bo sprehod za $k$ oddaljen od izhodišča, lahko začnemo v $0$ in stanji $k$ in $-k$ proglasimo za absorpcijska stanja. Prehodna matrika, ki jo dobimo je tridiagonalna z 0 na diagonali. Matrika $I-Q$ je prav tako tridiagonalna z $1$ na diagonali in z negativnimi verjetnostmi $-p$ in $-q = p-1$ na obdiagonalnih elementih:
\[I-Q = \begin{pmatrix} 1 & -q & 0 & \ldots & 0\\ -p & 1 & -q & \ldots & 0\\ \vdots & \ddots & \ddots & \ddots & \vdots\\ 0 & \ldots & -p & 1 & -q\\ 0 & \ldots & 0 & -p & 1 \end{pmatrix}\]
Prilagojen podatkovni tip
Naj bo $A\in\mathbb{R}^{n\times n}$ tri-diagonalna, diagonalno dominantna matrika. Primer tridiagonalne $4\times 4$ matrike
\[A=\left( \begin{array}{rrrr} 3 & 1 & 0 & 0\\ 2 & 4 & -1 & 0\\ 0 & 1 & 3 & -1\\ 0 & 0 & -1 & 8 \end{array}\right).\]
Definirajte podatkovni tip Tridiagonalna, ki hrani le neničelne elemente tridiagonalne matrike. Za podatkovni tip Tridiagonalna definirajte metode za naslednje funkcije:
- indeksiranje:
Base.getindex,Base.setindex!,Base.firstindexinBase.lastindex - množenje z desne
Base.*z vektorjem - „deljenje“ z leve
Base.\
Časovna zahtevnost omenjenih funkcij naj bo linearna. Več informacij o tipih in vmesnikih.
Poissonova enačba na krogu
Drug primer, ko dobimo tridiagonalni sistem lineranih enačb, če iščemo rešitev za robni problem na krogu $x^2+y^2\le 1$ za Poissonovo enačbo
\[\triangle u(x,y) = f(r)\]
z robnim pogojem $u(x,y)=0$ za $x^2 + y^2 = 1$. Pri tem je $f(r) = f(\sqrt{x^2+y^2})$ podana funkcija, ki je odvisna le od razdalje do izhodišča.
Laplaceov operator zapišemo v polarnih koordinatah in enačbo diskretiziramo z metodo končnih diferenc.