12 Dæmi um hagnýtingu fylkjareikninga¶

12.1 Fylkjamargföldun og tölvugrafík¶

Nokkrar myndavarpanir

Hægt er að líta á flatarmyndir, t.d. hringi, þríhyrninga, eða myndir af húsum sem mengi af punktum í plani, og punktarnir jafngilda svo auðvitað tvívíðum vigrum. Ef við höfum gefið fylki \(A\) þá er hægt að skilgreina vörpun eða fall frá planinu yfir í sjálft sig sem svarar til margföldunar með \(A\), með öðrum orðum:

\[f_A: \Bbb{R}^2 \to \Bbb{R}^2, f_A(x) = Ax\]

Svo má beita fallinu á alla punkta flatarmyndar og skoða myndmengið sem kemur út. Nokkrar tegundir af fylkjum svara til vel þekktra breytinga á flatarmyndunum, þeirra á meðal eru:

snúningur (rotation) um tiltekið horn miðað við \((0,0)\)
skölun (scaling) í x- og/eða y-stefnu
skekking (shear deformation) um tiltekið horn
speglun (reflection) um x-ás eða y-ás

Sem dæmi er fylkið:

\[\begin{split}K = \begin{pmatrix} 1 & \sin 30° \\ 0 & 1 \end{pmatrix}\end{split}\]

skekkingarfylki sem hallar lóðréttum línum um 30° til hægri. Aftar í þessum kafla eru formúlur fyrir fleiri fylkjum, en skoðum þær fyrst myndrænt með dæmum:

Svona fylkjamargföldunarvarpanir eru kallaðar línulegar varpanir (linear mappings). Þær hafa þann eiginleika að línustrik varpast í línustrik, þannig að til að finna myndmengi slíks striks nægir að varpa endapunktum þess.

Samskeyting varpana er fylkjamargföldun

Með því að skeyta slíkum vörpunum saman má svo t.d. spegla um hvaða ás sem er (snúa, spegla, snúa til baka) eða bæði skala og skekkja (feitletra og skáletra). Svona samskeyting varpananna svarar til fylkjamargföldunar því að:

\[\begin{split}&f_A(f_B(x)) = f_A(Bx) = ABx\quad\text{þ.e.a.s.}\\ &f_A \circ f_B = f_{AB}\end{split}\]

Svo er hægt að framkvæma hliðrun með því að leggja hliðrunarvigur, \(h\) við alla punkta mengisins. Þá erum við að nota fallið

\[g_h: \Bbb{R}^2 \to \Bbb{R}^2, g_h(x) = x + h\]

Með því að skeyta saman hliðrun og fylkjavörpununum er svo t.d. hægt að snúa miðað við hvaða punkt sem er (hliðra, snúa og hliðra til baka).

Myndmengi fundið með einni fylkjamargföldun

Ef mynd samanstendur af punktunum \((x_1, y_1), (x_2, y_2),\ldots (x_n, y_n)\) og strikum milli þeirra má varpa myndinni með fylki \(A\) með því að byrja á að búa til fylkið

\[\begin{split}B = \begin{pmatrix}x_1 & x_2 & \cdots & x_n\\y_1 & y_2 & \cdots & y_n\end{pmatrix}\end{split}\]

reikna svo

\[\begin{split}AB = C = \begin{pmatrix}c_1 & c_2 & \cdots & c_n\\d_1 & d_2 & \cdots & d_n\end{pmatrix}\end{split}\]

Svo eru búnir til punktar \((c_1, d_1), (c_2, d_2), \ldots\) úr dálkunum í C og nýja myndin fæst með því að tengja þá saman með strikum. Í Python er hægt að „lyfta pennanum“ og hoppa á nýjan stað með því að hafa dálka af svokölluðum ekki-tölum (not-a-number) sem hægt er að búa til með nan eftir innflutning from math import nan.

Sýnidæmi: Rétthyrningur með striki

Hér er dæmi um fylki sem lýsir rétthyrningi með striki inni í sér (sjá mynd):

\[\begin{split}M = \begin{pmatrix} 0 & 3 & 3 & 0 & 0 & \text{nan} & 1 & 2 \\ 0 & 0 & 2 & 2 & 0 & \text{nan} & 1 & 1 \end{pmatrix}\end{split}\]

Ef \(K\) er skekkingarfylkið sem gefið er hér neðar myndi fylkið

\[C = KM\]

lýsa samsíðungi með striki.

Formúlur fyrir tvívíðum vörpunarfylkjum

SNÚNINGSFYLKI sem snýr mynd rangsælis um hornið \(\theta\) með snúningspunkt \((0,0)\) er gefið með

\[\begin{split}R_{\theta} = \begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}\end{split}\]

Til að spegla réttsælis má nota neikvætt \(\theta\).

SKÖLUNARFYLKI sem skalar um \(a\) í \(x\)-stefnu og \(b\) í \(y\)-stefnu er

\[\begin{split}S_{a,b} = \begin{pmatrix}a & 0 \\ 0 & b \end{pmatrix}\end{split}\]

SKEKKINGARFYLKI:

\[\begin{split}K_{x,\theta} = \begin{pmatrix} 1 & \sin \theta \\ 0 & 1 \end{pmatrix} \;\text{ og }\; K_{y,\theta} = \begin{pmatrix} 1 & 0 \\ \sin \theta & 1 \end{pmatrix}\end{split}\]

\(K_{x,\theta}\) hallar lóðréttum línum um horn \(\theta\) til hægri en varðveitir láréttar línur, og \(K_{y,\theta}\) hallar láréttum línum upp en varðveitir þær lóðréttu. Til að halla til vinstri eða niður má nota neikvætt \(\theta\).

SPEGLUNARFYLKI sem spegla um \(x\)-ás og \(y\)-ás eru

\[\begin{split}M_x = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \;\text{ og }\; M_y = \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix}\end{split}\]

Fylki í tölvugrafík

Allar þessar aðgerðir eru grunnaðgerðir í tölvugrafík. Hliðranir eru stundum líka útfærðar með fylkjamargföldun með því að bæta við gervihniti og vinna með svonefnd jafnþætt eða hómógen (homogeneous) hnit, þrívíða vigra og \(3 \times 3\) fylki.

Nútíma tölvugrafík er svo auðvitað oftast þrívíð og þar þarf að takast á við þrívíða snúninga, speglanir og skalanir, og auk þess bæði hliðranir og fjarvídd (perspective). Allt þetta er hægt að útfæra með fjórvíðum vigrum og \(4 \times 4\) fylkjum, þar sem eitt hnitið er gervihnit.

Æfing: Snúið, skekkt og speglað.

Leysið verkefni 30: Æfing í tölvugrafík.

Athugasemd:

Til að varpanirnar sem hér hefur verið lýst gefi réttar myndir í Matplotlib teiknigluggum þarf að gæta þess að einingar á x- og y-ás séu jafnar. Það má gera með því að láta stærð myndarinnar (sem stilla má með figure(figsize=...)) passa við fjölda eininga á hvorum ás fyrir sig, en svo er líka hægt að enda með skipuninni plt.axis('scaled') sem mjókkar eða breikkar myndina til að einingar á x- og y-ás verði jafnar, eða skipuninni plt.axis('equal') sem breytir mörkum á x-ás til að einingarnar verði jafnar.

12.2 Fylki og net¶

Net (graph eða network) er safn af hnútum (eða punktum) (vertices, nodes*) og leggjum (edges) milli hnútanna. Net geta verið stefnd (directed) eða óstefnd, og þegar þau eru stefnd eru leggirnir stundum kallaðir örvar. Net geta líka haft leggi sem tengja punkta við sjálfa sig, kallaðir snörur (loops). Mynd 12.1: sýnir dæmi um net. Netið í miðjunni er það sama og netið til hægri.

Mynd 12.1: Óstefnt net (t.v.) og stefnt net (í miðju og t.h.).¶

Margar fleiri myndir af netum má skoða með því að gúgla graph mathematics og smella á images.

12.2.1 Grannafylki¶

Skilgreining: Grannafylki

Grannafylki (adjacency matrix) stefnds nets er fylki \(A\) með

\[\begin{split}a_{ij} = \left\{\begin{array}{ll} 1 &\text{ef það er ör frá hnút } i \text{ yfir í hnút } j \\ 0 &\text{annars} \end{array} \right.\end{split}\]

Grannafylki óstefnds nets er samhverft fylki \(A\) með

\[\begin{split}a_{ij} = a_{ji} = \left\{\begin{array}{ll} 1 &\text{ef leggur tengir hnút } i \text{ og hnút } j \\ 0 &\text{annars} \end{array} \right.\end{split}\]

Sýnidæmi

Grannafylki netanna á Mynd 12.1: eru

\[\begin{split}\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} \;\text{ (netið t.v.) og }\; \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \;\text{ (hin tvö)}\;\end{split}\]

12.2.2 Vegir í netum¶

Vegur (path) með lengd \(L\) í neti er runa af \(L + 1\) hnút þannig að leggur tengi hnút 1 við hnút 2, hnút 2 við hnút 3, o.s.frv. Sagt er að vegurinn tengi fyrsta hnútinn við þann síðasta. Veg með lengd 3 frá \(v_1\) til \(v_4\) má rita

\[v_1 \to v_2 \to v_3 \to v_4 \;\text{ eða }\; (v_1, v_2, v_3, v_4).\]

Skemmtileg regla tengir fjölda vega milli hnúta og veldi grannafylka:

Regla: Vegafjöldi

Grannafylki nets sé \(A\). Þá er \((i,j)\)-stak \(A^n\) jafnt og fjöldi mismunandi vega með lengd \({} = n\) frá hnút \(i\) til hnúts \(j\) og \((i,j)\)-stak fylkisins

\[B = A + A^2 + A^3 + \ldots + A^n`\]

gefur fjölda mismunandi vega með lengd \({} \leq n\) (hér er \(A^n\) fylkjaveldi, sbr. kafla 11.1).

Þessi skilgreining og reglan sömuleiðis eiga bæði við um stefnd og óstefnd net.

Sýnidæmi

Skoðum stefnda netið á eftirfarandi mynd:

Grannafylkið og annað veldi þess eru gefin með

\[\begin{split}A = \begin{pmatrix}0&1&0&1&0\\1&0&0&0&0\\0&1&1&0&0\\0&0&1&0&1\\1&0&1&0&0\end{pmatrix} \;\text{ og }\; A^2 = B = \begin{pmatrix}1&0&1&0&1\\0&1&0&1&0\\1&1&1&0&0\\1&1&2&0&0\\0&2&1&1&0\end{pmatrix}\end{split}\]

Við sjáum að \(b_{11} = 1\) og að það er nákvæmlega einn vegur sem tengir hnút 1 við sjálfan sig, nefnilega vegurinn \(1 \to 2 \to 1\). Til að taka annað dæmi þá eru tveir vegir frá hnút 4 til hnúts 3, nefnilega \(4 \to 5 \to 3\) og \(4 \to 3 \to 3\), enda er \((4,3)\)-stak \(A^2\) \({}= b_{43} = 2\).

Æfing

Stefnt net hefur leggi:

\[\begin{split}\begin{array}{ll} 1 \to 2 &\qquad 2 \to 3 \\ 1 \to 3 &\qquad 2 \to 4 \\ 1 \to 4 &\qquad 3 \to 4 \end{array}\end{split}\]

Teiknið netið
Finnið grannafylkið \(A\)
Reiknið \(A^2\) og \(A^3\)
Reiknið \(B = A + A^2 + A^3\). Þið ættuð að fá út að \(b_{14} = 4\). Finnið vegina fjóra frá hnút 1 til hnúts 4.

12.2.3 Legufylki¶

Skilgreining: Legufylki

Ef bæði hnútar og leggir nets eru tölusettir þá er hægt að skilgreina legufylki (incidence matrix) þess. Fyrir óstefnt net með \(n\) hnútum og \(m\) leggum er það \(n \times m\) fylki \(A\) með

\[\begin{split}a_{ij} = \left\{\begin{array}{ll} 1 &\text{ef hnútur } i \text{ er endi á legg } j \\ 0 &\text{annars} \end{array} \right.\end{split}\]

Ef netið er stefnt þá er sett formerki á stök legufylkisins til að sýna stefnu örvanna:

\[\begin{split}a_{ij} = \left\{\begin{array}{ll} -1 &\text{ef ör } j \text{ byrjar í hnút } i \\ 1 &\text{ef ör } j \text{ endar í hnút } i \\ 0 &\text{annars} \end{array} \right.\end{split}\]

Það eru sem sé tveir ásar (stak sem er \(= 1\)) í dálki hvers leggs óstefnds nets, nema hann sé snara, þá er bara einn ás. Ef netið er stefnt og leggurinn ekki snara er \(-1\) í línu hnútsins þar sem leggurinn byrjar og \(1\) í línu hnútsins þar sem hann endar Stundum er þetta samt haft öfugt. Fyrir snörur látum við formerkið vera \({}+{}\).

Sýnidæmi

Netið á myndinni hefur legufylki:

\[\begin{split}\begin{pmatrix}-1&-1&0&1&0\\1&0&-1&0&0\\0&0&1&-1&-1\\0&1&0&0&1\end{pmatrix}\end{split}\]

Æfing

Óstefnt net hefur leggi \(e_1: v_1\)—\(v_2\), \(e_2: v_2\)—\(v_2\) og \(e_3: v_2\)—\(v_3\).

Teiknið netið.
Ákvarðið grannafylki þess.
Ákvarðið legufylki þess.
Ákvarðið legufylkið fyrir tilsvarandi stefnt net með örvar \(v_1 \to v_2\), \(v_2 \to v_2\) og \(v_2 \to v_3\)

12.2.4 Flæðinet¶

Net sem lýsir kerfi þar sem eitthvað flæðir eftir hverjum legg, rafmagn, vatn, umferð, vörur o.s.frv. er kallað flæðinet (network). Hnútpunktarnir eru þá t.d. tengibox/tengivirki, tengipunktar, gatnamót eða dreifistöðvar. Í slíkum netum eru tölur tengdar hverjum legg, stundum fleiri en ein. Fyrir legg \(e_k\) gæti t.d. gilt:

\[\begin{split}&\text{flæði } = x_k \\ &\text{hámarksflæði eða burðargeta } = b_k \\ &\text{kostnaður á flutta einingu } = c_k\end{split}\]

Aðrir möguleikar á upplýsingum um leggi gætu t.d. verið lengdir þeirra eða viðnám í þeim. Þessar upplýsingar mætti setja fram með fylki sem hefur ekki-núll í sömu sætum og í grannafylki netsins (því þar er jú ás í sæti \((i,j)\) ef leggur tengir hnúta \(i\) og \(j\)). Flæðinet eru oft stefnd, en þá táknar stefna örvanna/leggjanna ekki stefnu flæðisins, heldur einungis í hvaða stefnu flæðið telst jákvætt. Ef flæði er á móti ör verður \(x_{ij} < 0\).

12.2.5 Lindir og ósar¶

Legufylki eru oft gagnleg fyrir verkefni sem tengjast flæðinetum. Það er ekki erfitt að sjá að ef \(x\) er flæðivigur með \(x_j\) = flæði eftir ör \(j\) í stefndu neti með legufylki \(A\) og \(y = Ax\) þá gefur \(y_i\) nettóflæði inn í hnút \(i\) fyrir öll \(i\). Ef \(y_i > 0\) þá er yfirflæði í hnútnum sem við hugsum okkur að renni út úr netinu, og slíkur hnútur er kallaður ós (sink). Ef hinsvegar \(y_i < 0\) þá þarf að bæta í flæðið í hnút \(i\) til að flæðið í netinu sé allsstaðar varðveitt; slíkur hnútur kallast lind (source). Ef \(s\) er vigur með

\[\begin{split}&s_i = \text{ nettóflæði inn í hnút } i \text{, og þar með:} \\ &s_i \left\{\begin{array}{l} {} < 0 \text{ fyrir ósa}\\ {} > 0 \text{ fyrir lindir}\\ {} = 0 \text{ fyrir aðra hnúta} \end{array}\right.\end{split}\]

Regla: Varðveisla flæðis

Ef \(A\) er legufylki nets með flæðivigur \(x\) og \(s\) lýsir nettó innflæði þá gildir:

\[Ax + s = 0\]

Ef netið er tré (hringalaust) þá má leysa þessa jöfnu til að finna flæði í öllum leggjum, en annars þarf meiri upplýsingar t.d. um viðnám eða þrýsting/spennu.

Eftirfarandi mynd sýnir flæðinet. Myndin segir ekkert um formerki flæðigilda svo það er ekki hægt að sjá hvaða hnútpunktar eru lindir og hverjir eru ósar. Öll \(s_i\)-in eru látin stefna inn í netið. Þar sem \(s_i\) er jákvætt passar sú stefna, þar eru lindir sem skila flæði inn í netið, en þar sem \(s_i\) er neikvætt er raunverulega að flæða út úr netinu.

Æfing

Gerið ráð fyrir að flæðivigur á myndinni hér á undan sé \(x = (1, 3, 2, 4, -1)\). Ákvarðið legufylkið \(A\) og í framhaldi nettóinnflæðið \(s\). Flokkið svo hnútana í lindir, ósa og aðra hnúta.

12.2.6 Hámarksflæði¶

Til að ákvarða hámarksflæði í gegn um net frá lind til óss má nota svonefnt Ford-Fulkerson reiknirit, sem lýsa má svo:

Lát flæði x[i,j] = 0 fyrir alla leggi i→j
Meðan til er vegur (lind=v0, v1,..., vn=ós) þannig
         að hægt er að auka flæðið í öllum leggjum vi→vj:
   c = hámarkið sem hægt er að auka flæðið um
   x[i,j] += c fyrir alla leggi í veginum

Svo eru til ýmsar útgáfur af þessu reikniriti eftir því hvernig vegurinn er fundinn, m.a. Edmonds-Karp reikniritið reikniritið og reiknirit Dinic. Það fyrrnefnda er til í SciPy, í falli sem heitir maximum_flow, sbr. eftirfarandi sýnidæmi.

Sýnidæmi: Hámarksflæði með Edmonds-Karp

import numpy as np, scipy.sparse as ssp
B = ssp.csr_matrix([[0,3,2,0],[0,0,1,3],[0,0,0,2],[0,0,0,0]])
flow = ssp.csgraph.maximum_flow(B, source=0, sink=3)
res = flow.residual.todense()
X = np.where(res > 0, res, 0)
print(f"Hámarksflæði = {flow.flow_value}")
print("Tilsvarandi flæðinet:")
print(X)

Við sjáum að fallið maximum_flow tekur burðargetuna inn í fylki sem svarar til grannafylkis. Skipunina np.where sem ekki hefur komið við sögu áður má nota til að velja stök fylkis sem uppfylla tiltekið skilyrði. Forritið prentar út:

Hámarksflæði = 5
Tilsvarandi flæðinet:
[[0 3 2 0]
 [0 0 0 3]
 [0 0 0 2]
 [0 0 0 0]]

Æfing: Tilraunir með hámarksflæði

Teiknið netið sem unnið er með í sýnidæminu að framan. Merkið inn númer hnúta og burðargetu.
Afritið forritið í vinnubók og keyrið. Prófið að breyta einhverri burðargetu.
Prentið líka út flow.residual og res

12.3 Línuleg hreyfikerfi¶

Í þessari grein kynnumst við notkun fylkjamargföldunar til að lýsa kerfum sem breytast með tíma. Tekin verða dæmi um stofnstærð/mannfjölda þar sem svonefnd Leslie fylki koma við sögu, og um hreyfingu massa sem kraftar verka á.

12.3.1 Skilgreining línulegra hreyfikerfa¶

Lát \(x_t\) vera \(n\)-vigur sem lýsir einhverju ástandi (state) kerfis á tíma \(t\), \(t = 0, 1, 2, \ldots\) (stundum er state líka þýtt með staða). Við skoðum sem sé kerfið á gefnum tímapunktum: tíminn líður í strjálum (discrete) skrefum sem gætu verið sekúndur eða ár.

Skilgreining: Línulegt hreyfikerfi

Línulegt hreyfikerfi (linear dynamical system) er líkan af kerfi með ástandsvigur \(x_t\) þar sem \(x_{t+1}\) er línulegt fall af \(x_t\):

\[x_{t+1} = A_t x_t\quad (t = 0, 1, 2, \ldots)\]

Fylkin \(A_t\) (sem eru \(n \times n\)) eru kölluð hreyfifylki (dynamics matrices). Ef þessi fylki og \(x_0\) eru þekkt þá er hægt að nota líkanið til að reikna öll framtíðargildi ástandsvigursins \(x_t\). Hér er fylkinu leyft að vera háð \(t\) en oft er \(A\)-fylkið fast og óháð \(t\).

Ef ytri aðstæður hafa áhrif á þróun kerfisins er hægt að útvíkka hugtakið:

Skilgreining: Hliðrað línulegt hreyfikerfi

Hliðruðu línulegu hreyfikerfi (non-homogeneous…) er lýst með líkani:

\[x_{t+1} = A_t x_t + B_t u_t \quad (t = 0, 1, 2, \ldots)\]

\(B_t\) er inntaksfylki (input matrix) og \(u_t\) eru ytri (exogenous) breytur („\(B\) tekur ytri breyturnar inn í kerfið“).

Eins og að ofan eru fylkin \(A_t\) og/eða \(B_t\) oft föst og óháð \(t\): \(A_t = A\) fyrir öll \(t\), \(B_t = B\) fyrir öll \(t\).

12.3.2 Þróun mannfjölda eða stofnstærðar¶

Við byrjum á að tala um mannfjölda, en augljóslega má nota sömu stærðfræði til að lýsa stofnstærð dýrategunda. Gerum ráð fyrir að \(x_t\) sé \(n\)-vigur með \(i\)-ta stak jafnt og fjöldi fólks í tilteknu landi sem eru á \(i\)-ta aldursári (sem sé \(i-1\) ára gamlir), \(t\) árum eftir tiltekinn byrjunartíma. Við gætum látið \(n = 120\). Oft er svona vigur kallaður aldursdreifing í landinu og hér er mynd sem sýnir aldursdreifingu fólks yngra en 100 ára í Bandaríkjunum árið 2010.

Mynd 12.2: Aldursdreifing Bandaríkjamanna árið 2010.
Milljónir á \(y\)-ás og aldur á \(x\)-ás.¶

Látum fæðingartíðni og dánartíðni vera gefna með vigrum \(b\) og \(d\): \(b_i\) = árlegur meðalfjöldi lifandi fæddra barna foreldra sem eru að meðaltali á \(i\)-ta aldursári og \(d_i\) = hlutfall fólks á \(i\)-ta aldursári sem deyr. Til að vera nákvæmur mætti síðan skoða karla og konur aðskilið. Hér er mynd af \(b\) og \(d\) fyrir Bandaríkin í kring um árið 2010. Á þessum myndum er aftur miðað við fólk yngra en 100 ára.

Mynd 12.3: Fæðingartíðni (t.v.) og dánartíðni (t.h.) í prósentum eftir aldri í Bandaríkjunum í lok árs 2010.¶

Leslie-fylki

Smá skoðun leiðir nú í ljós að ef horft er framhjá aðfluttum og brottfluttum má lýsa þróun mannfjöldans með línulega hreyfikerfinu:

\[\begin{split}x_{t+1} = A x_t = \begin{pmatrix} b_1 & b_2 & b_3 & \cdots & b_{119} & b_{120} \\ 1-d_1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1-d_2 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots && \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1-d_{119} & 0 \end{pmatrix} x_t\end{split}\]

Svona mannfjöldafylki (eða stofnstærðar-) er kallað Leslie-fylki. Það er sett saman úr þremur þáttum:

Fæðingartíðni eftir ári í efstu línu
Dánartíðni eftir ári á skálínu neðan hornalínu
Ásar á sömu skálínu sem færa \(i\) ára á ári \(t\) í \(i+1\) ára árið \(t+1\).

Ef taka skal tillit til aðfluttra og brottfluttra má nota hliðrað hreyfikerfi:

\[x_{t+1} = A x_t + B u_t\]

þar sem \(B\) er einingafylkið og \((i+1)\)-ta stak \(u_t\) er fjöldi \(i\) ára gamalla aðfluttra umfram brottflutta á ári \(t\).

Æfing

Tegund lifir í hámark 3 ár. Hver 0 ára gefur 0.2 núll-ára afkvæmi árið eftir, hver 1 árs 0.6 afkvæmi ári síðar og hver 2 ára 0.8. 20% núll-ára eru dauð ári seinna, og dánartíðni eins-árs er 50%.

Í upphafi er stofnstærðin 3000 einstaklingar, 1200 núll-ára, 1000 eins árs og 800 tveggja ára.

Ákvarðið Leslie-fylkið
Ákvarðið stofnstærð eftir 1 ár
Ákvarðið stofnstærð eftir 2 ár

12.3.3 Diffurjafna fyrir hreyfingu hlutar¶

Línuleg hreyfikerfi má nota til að líkja eftir hreyfingu margvíslegra aflfræðilegra kerfa, t.d. flugféla, skipa, bíla eða bygginga í jarðskjálfta. Hér lýsum við mjög einföldu kerfi, massa sem færist í beina línu fyrir áhrif drifkrafts og verður jafnframt fyrir núningsmótstöðu. Við getum hugsað okkur að um sé að ræða bát með utanborðsmótor.

Mynd 12.4: Hraðbátur á Khövsgöl vatni í Mongólíu¶

Um slíka hreyfingu gildir 2. lögmál Newtons:

\[\text{kraftur} = \text{massi} \cdot \text{hröðun}\]

Auk þess gildir að núningsmótstaðan verkar eins og kraftur sem er í réttu hlutfalli við hraðann, sem sé

\[\text{núningskraftur} = n \cdot \text{hraði}\]

þar sem \(n\) er núningsstuðull. Ef:

\[\begin{split}&m = \text{massi} \\ &t = \text{tími} \\ &f(t) = \text{drifkraftur á tíma } t\\ &v(t) = \text{hraði á tíma } t \text{ og} \\ &a(t) = \text{hröðun á tíma } t\end{split}\]

og hugað er að formerkjum liða þá fæst:

\[(*)\qquad\qquad m a(t) = -n v(t) + f(t) \qquad\qquad\quad{}\]

Ef við látum líka \(p(t)\) vera staðsetningu á tíma \(t\) þá segir eðlisfræðin okkur að \(v(t) = p'(t)\) og \(a(t) = p''(t)\) og þar með verður \((*)\) að diffurjöfnunni:

\[m p''(t) = -n p'(t) + f(t)\]

Þessa annarsstigs diffurjöfnu er einfalt að umrita sem fyrsta stigs diffurjöfnukerfi í tvívíða fallinu \((p(t), v(t))\):

\[\begin{split}\begin{pmatrix}p'(t)\\mv'(t)\end{pmatrix} = \begin{pmatrix}v(t)\\-nv(t) + f(t)\end{pmatrix}\end{split}\]

12.3.4 Diffurjöfnu breytt í línulegt hreyfikerfi¶

Nálgun við diffurjöfnukerfið að framan fæst með því að umrita staðsetningu og hraða á tíma \(t^+ = t+1\) útfrá sömu stærðum á tíma \(t\) með fyrsta stigs Taylor-nálgun, sem fjallað er um í stærðfræðigreiningu. Hún segir að

\[f(x) \approx f(a) + f'(a)(x-a)\]

Við beitum þessari setningu annarsvegar á \(p\) og hinsvegar á \(v\) og það gefur:

\[\begin{split}p(t^+) &\approx p(t)+p'(t)(t^+-t) \text{ þ.e. }p'(t) \approx p(t^+)-p(t)\\ v(t^+) &\approx v(t)+v'(t)(t^+-t) \text{ þ.e. }v'(t) \approx v(t^+)-v(t)\end{split}\]

Þessi nálgun verður góð ef við veljum tímaeininguna nógu litla (t.d. 1 sekúndu). Ef þessari nálgun er stungið inn í diffurjöfnukerfið og við notum ritháttinn \(p_t, v_t\) og \(f_t\) í stað \(p(t), v(t)\) og \(f(t)\) fæst:

\[\begin{split}\begin{pmatrix}p_{t+1}-p_t \\ m(v_{t+1} - v_t)\end{pmatrix} = \begin{pmatrix}v_t\\-nv_t + f_t\end{pmatrix}\end{split}\]

það er að segja:

\[\begin{split}\begin{pmatrix}p_{t+1} \\ v_{t+1}\end{pmatrix} &= \begin{pmatrix}p_t + v_t\\ (1 - n/m) v_t + (1/m)f_t\end{pmatrix}\\ &= \begin{pmatrix}1 & 1\\ 0 & 1-n/m\end{pmatrix} \begin{pmatrix}p_t\\ v_t\end{pmatrix} + \begin{pmatrix}0\\ 1/m\end{pmatrix} f_t\end{split}\]

Þetta kerfi er greinilega hliðrað línulegt hreyfikerfi:

\[(**)\qquad\qquad x_{t+1} = Ax_t + Bf_t\qquad\qquad\;\;{}\]

með ástandsvigri \(x_t = (p_t, v_t)\), ytri breytum \(f_t\), og hreyfifylki og inntaksfylki:

\[\begin{split}A = \begin{pmatrix}1 & 1\\ 0 & 1-n/m\end{pmatrix}\;\text{ og }\; B = \begin{pmatrix}0\\1/m\end{pmatrix}\end{split}\]

Sýnidæmi

Látum hreyfikerfið líkja eftir ferð 500 kg báts með utanborðsmótor í 50 sekúndur. Mótorinn er settur í gang eftir 5 sekúndur með 3000 newtona krafti áfram, 10 sekúndum seinna er skipt í bakkgír, með 2500 newtona krafti í 15 sekúndur og svo er drepið á mótornum. Núningsstuðull er \(n = 100\).

Byrjað er með \(x_0 = (0,0)\) og svo er \(x_{t+1}\) reiknað 50 sinnum með \((**)\). Hér eru myndir með niðurstöðum reikninganna (kN eru kílónewton):

Æfing

Notið tölurnar sem gefnar eru í sýnidæminu hér á undan og ákvarðið hreyfifylkið \(A\) og inntaksfylkið \(B\).
Báturinn er kyrr í 5 sekúndur en þá fer hann af stað. Reiknið staðsetningu og hraða hans eftir 6 og 7 sekúndur með blaði og blýanti.
Notið nú Python til að líkja eftir hreyfingu bátsins í 50 sekúndur og endurskapa þannig línuritin í sýnidæminu.
Notið Python til að finna hámarkshraða bátsins.