11 Reiknað með fylkjum¶

Línuleg algebra (linear algebra) er undirgrein stærðfræði sem fjallar meðal annars um vigra og fylki, vigurrúm (vector spaces), línuleg jöfnuhneppi (systems of linear equations) og línuleg föll. Hægt er að beita línulegri algebru bæði fræðilega og tölulega, og þegar það er gert tölulega koma fylkjareikningar oftar en ekki við sögu, og þá er NumPy ómissandi. Oft tengjast reikningarnir því að vigrar og fylki eru notuð til að vinna með talnagögn (data).

Í nýlegri kennslubók um línulega algebru eru talin upp fjölbreytt notkunarsvið hennar, svo sem leikjafræði, skógrækt, tölvugrafík, sneiðmyndataka, dulmálsfræði, erfðafræði, stofnstærðarspár, líkön af heyrn, netleit og andlitskennsl.

Í 12. kafla verður fjallað um nokkur notkunarsvið fylkjareikninga, en í þessum kafla höldum við okkur að mestu við útskýringar á NumPy vigur- og fylkjaaðgerðum, og hvernig hægt er að leysa jöfnuhneppi með NumPy.

11.1 Grunnreikniaðgerðir¶

Í grein 10.3.1 var rætt hverning hægt er að leggja saman tvo vigra, draga annan frá hinum og margfalda vigur með tölu. Þessum aðgerðum má líka beita á fylki, og þá verka þær á tilsvarandi stök, eins og fyrir vigrana. Þannig gildir:

\[\begin{split}\begin{pmatrix}1 & 2\\3 & 4\end{pmatrix} + \begin{pmatrix}2 & 2\\5 & 5\end{pmatrix} = \begin{pmatrix}3 & 4\\8 & 9\end{pmatrix}\end{split}\]

og

\[\begin{split}2\cdot\begin{pmatrix}2 & 2\\5 & 6\end{pmatrix} = \begin{pmatrix}4 & 4\\10 & 12\end{pmatrix}\end{split}\]

Python: Stakvísar fylkjaaðgerðir

Í Python eru venjulegu reikniaðgerðirnar, \(+\) \(-\) og \(*\) notaðar til að reikna með öllum stökum fylkis samtímis, og auk þess má beita \(*\) til að margfalda saman tvö fylki sem gefur það stærðfræðilega óvenjulega svar að tilsvarandi stök eru margfölduð saman. Og eins og hægt var með vigrana er líka hægt að beita stærðfræðiföllum stakvíst á fylki með því að nota np.-útgáfur af þeim í staðinn fyrir að nota math-eininguna.

Sýnidæmi: Stakvís margföldun og logri

Ef eftirfarandi forritsbútur er framkvæmdur:

A = np.array([[1,2],
              [3,4]])
B = np.array([[1,  10  ],
              [100,1000]])
C = A*B
print(C)
print(np.log10(B))

þá prentast út:

[[   1   20]
 [ 300 4000]]
[[0. 1.]
 [2. 3.]]

Eins og fyrr segir er það óvenjulegt í stærðfræði að margföldun með fylkjum sé framkvæmd stakvís. Í línulegri algebru er slík margföldun nefnilega skilgreind sem útvíkkun á innfeldi og felur í sér margföldun staka og samlagningu í kjölfarið. Þetta á bæði við um margföldun fylkis og vigurs og margföldun tveggja fylkja.

Skilgreining: Margföldun fylkis og vigurs

Ef \(A\) er \(m \times n\) fylki og \(x\) er \(n\)-vigur þá er margfeldi \(A\) og \(x\), táknað \(Ax\) eða \(A \cdot x\), \(m\)-vigur með \(i\)-ta stak jafnt og innfeldi \(i\)-tu línu \(A\) og \(x\). Nánar tiltekið gildir að

\[\text{ef}\;y = Ax\;\text{þá er}\;y_i = \sum_{j=1}^n a_{ij}x_j\;\:(i=1,...,m)\]

Sýnidæmi: Fylki sinnum vigur handreiknað

Margfeldi fylkisins \(\,A = \begin{pmatrix}1 & 2 & 3\\4 & 5 & 6\end{pmatrix}\,\) og vigursins \(\,x = (3, 1, -2)\,\) er

\[\begin{split}Ax = \begin{pmatrix} 1\cdot 3 + 2\cdot 1 - 3\cdot 2\\ 4\cdot 3 + 5\cdot 1 - 6\cdot 2\end{pmatrix} = \begin{pmatrix} 3 + 2 - 6\\ 12 + 5 - 12 \end{pmatrix} = \begin{pmatrix} -1\\ 5 \end{pmatrix}\end{split}\]

Stundum er gerður greinarmunur á dálkvigri (column vector) og línuvigri (row vector), t.d. \(\begin{pmatrix}1\\2\end{pmatrix}\) og \((1, 2)\). Þegar \(x\) og \(y\) eru báðir dálkvigrar þá er innfeldið \(x \cdot y\) stundum táknað með \(x^\text{T}y\). Þá er nefnilega \(x^\text{T}\) línuvigur og ef við lítum á hann sem \(1 \times n\) fylki þá er margfeldi þess og vigursins \(y\) einmitt jafnt og innfeldið \(x\cdot y\).

Reglur: Dreifireglur

Um margfeldi fylkja og vigra gilda dreifireglurnar

\[\begin{split}&A(x + y) = Ax + Ay\;\:\text{og}\\ &(A + B)x = Ax + Bx\end{split}\]

þar sem \(A\) og \(B\) eru fylki og \(x\) og \(y\) vigrar. Hér má setja \(-\) í stað \(+\).

Python: @-virkinn

Í NumPy fæst margfeldi fylkis og vigurs með aðgerðinni @, t.d. reiknar y = A @ x margfeldi fylkisins A og vigursins x.

Æfing: Reiknað með Python

Gefnir eru vigrarnir \(a = (2, 0, 3)\), \(b = (1, -1, 2)\) og \(c = (1, 2, 3)\) og fylkin

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

Reiknið með NumPy:

\(a + b + c\)
\(3a - 2b\)
\(a\cdot b\)
\(Bc\)
\(A^\text{T}a\)
\(2A + B^\text{T}\)

Skilgreining: Fylkjamargföldun

Margfeldi \(m \times p\) fylkis \(A\) og \(p \times n\) fylkis \(B\) er \(m \times n\) fylkið \(C = AB\) sem hefur \((i,j)\)-stak

\[c_{ij} = \sum_{k=1}^p a_{ik} b_{kj}\]

Samkvæmt skilgreiningunni fæst \((i,j)\) stak margfeldisins \(C\) með því að taka innfeldi af \(i\)-tu línu \(A\) og \(j\)-ta dálki B.

Önnur leið til að lýsa fylkjamargfeldi er að segja að \(j\)-ti dálkur útkomunnar sé margfeldi af \(A\) og \(j\)-ta dálki \(B\). Ef \(B = [b_1|b_2|\ldots|b_n]\) gildir sem sé að:

\[C = [c_1|c_2|\ldots|c_n]\]

þar sem \(c_i = Ab_i\).

Sýnidæmi

Reiknum margfeldi tveggja \(2 \times 2\) fylkja \(A\) og \(B\):

\[\begin{split}\begin{pmatrix}1 & 2 \\ 3 & 4 \end{pmatrix} \begin{pmatrix}5 & 6 \\ 0 & -2 \end{pmatrix}\end{split}\]

og fáum \(c_{11} = 1 \cdot 5 + 2 \cdot 0 = 5\), \(c_{12} = 1 \cdot 6 - 2 \cdot 2 = 2\), \(c_{21} = 3 \cdot 5 + 4 \cdot 0 = 15\) og \(c_{22} = 3 \cdot 6 - 4 \cdot 2 = 10\), sem sé

\[\begin{split}C = \begin{pmatrix}5 & 2 \\ 15 & 10 \end{pmatrix}\end{split}\]

Veldi af ferningsfylkjum eru skilgreind með endurtekinni margföldun: \(A^2\) er \(A \cdot A = AA\), \(A^3 = AAA\) o.s.frv. Í kafla 12.2 verður sýnd skemmtileg hagnýting á fylkjaveldum.

Python: Fylkjamargföldun og -veldi

Í NumPy má margfalda saman fylki með virkjanum @ og fallið la.matrix_power má nota til að hefja fylki í veldi, t.d.

import numpy as np
A = np.array([[1,2],[3,4]])
B = np.array([[5,6],[0,-2]])
C = A @ B
D = la.matrix_power(A,2)
print(C); print(D)
# ---prentar [[ 5  2]
#             [15 10]]
#            [[ 7 10]
#             [15 22]]

Python: Samanburður vigra og fylkja

Til að kanna hvort tveir vigrar eða tvö fylki séu eins er ekki hægt að nota virkjann == því hann verkar stakvíst og gefur auk þess villu ef vigrarnir eða fylkin eru misstór. NumPy er með séstakt fall sem er ætlað í svona samanburð, np.array_equal. Ef

A = [[2 2]     og   B = [[4 4]
     [2 2]]              [4 4]]

þá skilar np.array_equal(A + A, B) gildinu True.

11.2 Núllfylki og einingafylki¶

Skillgreining: Núllfylki og einingafylki

Núllfylki (zero matrix) hefur öll stök = 0 og einingafylki (identity matrix) hefur hornalínustökin = 1 og öll önnur stök = 0.

Einingafylki er oftast táknað með \(I\) og stærð þess ræðst yfirleitt af samhenginu. Núllfylki eru stundum táknuð með \(0\) eða \(O\) (núll eða bókstafurinn O), og stærðin ræðst líka af samhenginu.

Hér eru \(2 \times 2\) og \(3 \times 3\) einingafylki og \(2 \times 3\) núllfylki:

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

Núllfylkið er samlagningarhlutleysa (neutral element) og eingarfylkið er margföldunarhlutleysa (identity element) því \(O + A = A + O = A\) og \(I\cdot A = A\cdot I = A\) fyrir öll A

Python: zeros og eye

Í NumPy má búa til \(m \times n\) núllfylki með np.zeros((m,n)) og \(n \times n\) einingafylki með np.identity(n) eða np.eye(n) (eye er borið fram eins og I ).

Æfing: Hlutleysur

Notið NumPy til að búa til fylkið: \(A = \begin{pmatrix}1.2 & 3.4 \\ 5.6 & 7.8 \end{pmatrix}\)
og auk þess \(2 \times 2\) núllfylki og einingarfylki. Notið fallið np.array_equal til að sannreyna það sem sagt er um hlutleysur að ofan.

11.3 Lausn jöfnuhneppa¶

Ein mikilvæg hagnýting fylkja er að leysa saman margar jöfnur í mörgum línulegum jöfnum. Það er nefnilega hægt að setja slíkar jöfnur fram sem fylkja- og vigurjöfnu. Ef jöfnurnar eru jafn margar og óþekktu stærðirnar er yfirleitt til nákæmlega ein lausn.

Sýnidæmi: Tvær jöfnur í tveimur óþekktum

Leysum jöfnurnar:

\[\begin{split}2 x_1 + 3 x_2 &= 8 \\ 5 x_1 - 2 x_2 &= 1\end{split}\]

Við margföldum fyrri jöfnuna með \(2\) og þá seinni með \(3\) og leggjum saman (til að losna við \(x_2\)) og fáum \(19x_1 = 19\) svo \(x_1=1\). Seinni jafnan gefur svo \(2x_2 = 5x_1 - 1 = 4\) svo \(x_2=2\). Til að undirstrika að hér var miðað við lausn með blaði og blýanti voru stök \(x\) og y tölusett með 1 og 2 í staðinn fyrir 0 og 1.

Jöfnurnar í þessu sýnidæmi má líka rita með fylki og vigrum:

\[A x = b\]

þar sem \(A = \begin{pmatrix}2 & 3\\5 & -2\end{pmatrix}\) og \(b = \begin{pmatrix}8\\1\end{pmatrix}\), sbr. kafla 11.1.

Æfing: Fylkjaframsetning

Gefnar eru jöfnurnar

\[\begin{split}x + 2y &= z + t + 8 \\ z – x &= 3 \\ x + y + z + t &= 12 \\ y + 3 &= 2x\end{split}\]

Ákvarðið tilsvarandi fylki \(A\) og vigur \(b\) þannig að þessar jöfnur svari til \(Av = b\) þar sem \(v = (x, y, z, t)\)

Python: Lausn jöfnuhneppis

Fylkjaframsetning á jöfnuhneppi einfaldar kannski ekki mikið lausn með blaði og blýanti en með því að nota fallið la.solve verður lausnin beint af augum:

import numpy as np, numpy.linalg as la
A = np.array([[2, 3], [5, -2]])
b = np.array([8, 1])
x = la.solve(A, b)
print(x)
#--- prentar [1., 2.]

Það sem NumPy gerir bak við tjöldin er að umrita jöfnurnar með svipuðum hætti og gert var í sýnidæminu hér á undan og einangra þannig óþekktu stærðirnar hverja á fætur annari og ákvarða gildi þeirra.

Æfing: Hollur matur

Sigga hefur ákveðið að borða bara skyr, rúgbrauð og kæfu, en þessar fæðutegundir innihalda næringarefni í 100 g sem hér segir:

Skyr

Rúgbrauð

Kæfa

Kolvetni

3.7

36

2.4

Prótein

11

8.6

12.8

Fita

0.2

6.7

29.3

Notið NumPy til að ákvarða hvað hún á að borða mikið af hverju á dag ef hún vill fá 100 g af kolvetnum, 150 g af próteini og 150 g af fitu úr matnum?

Aðvörun

Sigga ætti að borða eitthvað grænmeti líka.

11.4 Jöfnuhneppi með n óþekktum¶

Til að átta sig á sambandi jöfnuhneppa og fylkja getur gagnast að skoða eftirfarandi algenga framsetningu almenns \(n \times n\) jöfnuhneppis:

\[\begin{split}&a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n =\; &b_1 \\ &\vdots &\vdots \\ &a_{n1} x_1 + a_{n2} x_2 + \ldots + a_{nn} x_n =\; &b_n\end{split}\]

Á fylkjaformi verður þetta:

\[\begin{split}\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ \vdots & & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix} & \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix}\;&= \begin{pmatrix} b_1 \\ \vdots \\ b_n \end{pmatrix}\\ \\ A & x& = b\end{split}\]

Hér hefur verið byrjað að telja í einum eins og algengast er í stærðfræði. Til að reikna í NumPy þarf að taka tillit til þess að það byrjar að telja í núll.

Sýnidæmi: Jöfnunheppi byggt í skrefum

Í raunverulegum verkefnum eru jöfnuhneppi oftast gefin með því að setja fram einstakar jöfnur í þeim, sem þarf svo að stinga inn á réttan stað í fylki sem búið er til smám saman. Hér er einfalt dæmi:

Um \(x_1, x_2,\ldots x_n\) gildir

\[\begin{split}2x_{i+1} - x_i &= 0\quad(i=1,...,n-1)\\ \sum_{i=1}^n x_i &= 3n\end{split}\]

Skrifum Python-fall sem leysir þessar jöfnur. Byrjum á að endurskrifa jöfnurnar miðað við að fyrsta breytan heiti \(x_0\):

\[\begin{split}2x_{i+1} - x_i &= 0\quad(i=0,...,n-2)\\ \sum_{i=0}^{n-1} x_i &= 3n\end{split}\]

Svo byrjum við með \(n \times n\) núllfylki og núll í hægri hlið, og tökum eftir að fyrir \(i<n-1\) verður lína nr. \(i\) í fylkinu:

\[\begin{split}(0,\ldots,0,-1&,2,0,\ldots,0)\\ \uparrow&\\ i\text{-ta}&\text{ sæti}\end{split}\]

og neðsta línan er svo full af ásum. Hægri hlið hneppisins er núll, nema í neðsta sætinu, þar stendur \(3n\). Við fáum því fallið:

def leysa(n):
   A = np.zeros((n,n))
   b = np.zeros(n)
   for i in range(n-1):
      A[i,(i,i+1)] = [-1, 2]  # setjum tvö stök í einu
   for j in range(n):
      A[n-1,j] = 1            # ásar í neðstu línu
   b[n-1] = 3*n
   x = la.solve(A, b)
   return x

Til að skýra betur hvað er að gerast í sýnidæminu fylgir jöfnuhneppið í tilfellinu \(n = 5\) hér:

\[\begin{split}\begin{pmatrix} -1 & 2 & 0 & 0 & 0\\ 0 & -1 & 2 & 0 & 0\\ 0 & 0 & -1 & 2 & 0\\ 0 & 0 & 0 & -1 & 2\\ 1 & 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} x_0\\x_1\\x_2\\x_3\\x_4 \end{pmatrix} \begin{pmatrix} 0\\0\\0\\0\\15 \end{pmatrix}\end{split}\]

Æfing: Jöfnuhneppi búin til í lykkju

Leysið jöfnuhneppið í sýnidæminu fyrir \(n=4\) (ætti að gefa \(x = (6.4, 3.2, 1.6, 0.8)\)).
Búið til fall lausn(a,n) sem leysir jöfnurnar

\[- a\sum_{j=1}^{i-1}x_j + x_i = 1\quad(i=1,...,n)\]

Prófið með lausn(2,4) sem ætti að gefa \((1,3,9,27)\).

11.5 Andhverfur og ákveður¶

Flest fylki eru það sem kallað er andhverfanleg (nonsingular), og eins og ráða má af orðinu er hægt að reikna andhverfu (inverse) slíkra fylkja, nánar tiltekið margföldunarandhverfu.

Skilgreining: Andhverfa

Andhverfa fylkis \(A\) er annað fylki \(B\) sem uppfyllir

\[AB = BA = I\]

þar sem \(I\) er einingafylkið úr kafla 11.2.

Andhverft fylki \(A\) er táknað \(A^{-1}\). Ef andhverfa fylkis \(A\) er þekkt, þá er hægt að leysa jöfnuhneppi

\[Ax = b\]

með því að margfalda í gegn með \(A^{-1}\):

\[\begin{split}A^{-1}Ax &= A^{-1}b\\ Ix &= A^{-1}b\\ x &= A^{-1}b\end{split}\]

Annar eiginleiki fylkis sem kemur við sögu í línulegri algebru er ákveða þess (determinant), táknuð \(\det A\), sem reyndar verður ekki mikið notuð í þessum fyrirlestrarnótum.

Python:

Það er fremur flókið að reikna andhverfur og ákveður með blaði og blýanti, en talsvert einfaldara með NumPy:

import numpy as np, numpy.linalg as la
A = np.array([[2,3,4], [2,4,8], [3,4,9]])
B = la.inv(A)
d = la.det(A)

Æfing: Andhverfa og ákveða

Sláið inn eða afritið forritið hér á undan og ákvarðið með því andhverfu og ákveðu fylkisins \(\begin{pmatrix}2&3&4\\2&4&8\\3&4&9\end{pmatrix}\).

Aðvörun

Það er bæði nákvæmara og hraðvirkara að leysa jöfnuhneppi með np.solve heldur en með því að reikna andhverfu. Í útreikningum fyrir raunveruleg verkefni ætti alltaf að reyna að umrita reiknirit með fylkjaandhverfum yfir í reiknirit sem leysa jöfnuhneppi.