Octave

i kursen linjär algebra, ht10/vt11 och ht11/vt12

Nedladdning

Octave är ett program för numeriska beräkningar. Det har många likheter med det kommersiella programmet MatLab, men också den väsentliga skillnaden att det är gratis. Tycker man inte det är roligt att arbeta med en DOS-prompt laddar man dessutom ned QtOctave som är ett lättförståeligt och behändigt grafiskt gränssnitt. Länkar till programmen och instruktioner hur man laddar ner och får igång dem finns här (Malin Christerssons hemsida). Gå till rubriken "Octave for Windows och Mac" och följ instruktionerna för att ladda ner Octave. Gå sedan till rubriken "Using Windows" längre ner för att ladda ner OtOctave och få det att fungera ihop med Octave.

Komma igång

När man fått igång programmet är det dags att bekanta sig med funktioner och kod. Ett lämpligt sätt är att botanisera i dokumentet (ofärdigt men tillräckligt)

Octave och QtOctave – ett matematiskt beräkningsprogram

av Per Jönsson. Tar man sig igenom avsnitt 1 till 13 och 18 så kan man grunderna och kan klara det mesta av laboration 1. Undantaget är den sista uppgiften, där man behöver ha läst igenom kapitel 22 om programmering.

Eftersom Octave påminner om MatLab kan man använda många av MatLabs kommandon. En samling av sådana finns här. Observera att det finns kommando i MatLab som inte fungerar i Octave.

Laborationer

I delkurs 1 gör vi laboration 1 och 2, i delkurs 2 de båda återstående. Meningen är att ni ska få en introduktion till Octave och se hur det kan användas i linjär algebra, inte att ni måste göra exakt ett visst antal uppgifter på ett visst sätt. Det ska vara (någorlunda) roligt!

Troliga laborationer

Laboration 1, introduktion
Laboration 2, matriser och vektorer
Laboration 3, minsta kvadratanpassning/regression
Laboration 4, pagerank

Laboration 1, introduktion

I några av problemen dyker det upp intressant matematik och man kan efter undersökningar i Octave formulera hypoteser. Det är inte meningen att ni ska lägga tid på detta under själva laborationen, men kanske kan ni fundera när ni får tid över. Inrikta er i första hand på att få koll på Octave-syntaxen. Kika i Per Jönssons dokument vid behov. Känner ni för att testa andra eller fler saker och kommando än det som finns i uppgifterna så är det såklart bara bra.

Uppgifter

1. Beräkna

(1)
\begin{align} 8 \cdot 8 +13\\ 8 \cdot 88 +13\\ 8 \cdot 888 +13\\ 8 \cdot 8888 +13\\ 8 \cdot 88888 +13\\ 8 \cdot 888888 +13\\ 8 \cdot 8888888 +13\\ 8 \cdot 88888888 +13 \end{align}

Du ser ett ''mönster''. Kan du förklara varför det alltid blir så?


2. Tilldela variablerna $m$ och $v$ värdena 20 respektive 10. Beräkna sedan $E=\frac{mv^2}{2}$.


3. Konstruera vektorerna u=(1,2,3) och v=(-2,1,4) (läs i avsnitt 12).

a) Beräkna 2u och u+v.

b) Vad händer om du skriver u*v respektive u.*v i kommandoraden?

c) Vad händer om du skriver 2^u respektive 2.^u i kommandoraden?


4. a) Konstruera en vektor/lista x som består av heltalen från 0 till 10.

a) Konstruera en vektor/lista y som består av kvadraterna på talen 0 till 10.

b) Plotta vektorn y mot vektorn x (kommandot plot).


5. a) Konstruera en vektor/lista x som består av de 50 första heltalskuberna (listan ska alltså börja $1, 8, \ldots$). Bestäm summan av dessa (kommandot sum)!

b) Summera de 50 första heltalen ($1+ \ldots +50$). Kvadrera denna summa. Slutsats?

c) Undersök vad som händer i a) och b) om du tar ett annat antal än 50.

d) Kan du bevisa din hypotes? Överkurs, kräver (nog) tekniker från minst Matematik diskret. Men överraska gärna!


6. a) Konstruera funktionen $f(x)=\sin x + \cos x$ (se avsnitt 11). Observera att vinkelmåttet blir radianer automatiskt om du använder $\sin(x)$ och $\cos(x)$.

a) Bestäm funktionvärdet för $x=\pi$.

b) Rita en snygg graf till funktionen i intervallet $0 \leq x \leq 2\pi$. Lägg till beskrivande text i grafen (se avsnitt 18).

c) Konstruera $g(x)= \sqrt{2} \sin (x+\pi/4)$ och plotta grafen till denna funktion i samma fönster, men med annan färg.

d) Slutsats? Bevis?


7. Samla all kod från föregående uppgift i en m-fil. Spara m-filen och kör den sedan i kommandoraden.


8. Betrakta funktionerna $f(x)=\tan(\arctan x)$ och $g(x) = \arctan(\tan x)$ ($\arctan$ heter atan i Octave). Undersök med hjälp av Octave (utan att nödvändigtvis tänka efter) hur graferna till dessa funktioner ser ut. Tänk sedan efter varför de ser ut som de gör. Hur definerar man $\tan$ och $\arctan$? Utgå t.ex. från enhetscirkeln.


9. Extrauppgift för den som kan/vill lära sig att skriva ett kortare program.

Betrakta följande process: Starta med ett godtyckligt positivt heltal n. Om n är jämnt bilda n/2, om n är udda bilda 3n+1. Fortsätt så tills du får talet 1. Om man t.ex. startar med 34 fås sekvensen

(2)
\begin{align} 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1. \end{align}

Skriv ett program som till ett givet n genererar den tillhörande sekvensen. Räkna hur många steg som behövs innan det stannar. Kommer programmet alltid att stanna (oavsett vilket tal du startar med)? Problemet är känt, det förmodas att det alltid stannar och denna förmodan kallas bl.a. Collatz förmodan. Ett säkert, men inte särskilt enkelt, sätt att göra sig känd i resten av mänsklighetens historia är att lösa problemet!

Tips: om man vill ange ett villkor för att n är jämnt kan man skriva mod(n,2)==0, vilket betyder att n är kongruent med 0 modulo 2, vilket är det samma som att n innehåller en faktor 2, dvs att n är jämnt. För den som läst Matematik diskret är koden helt naturlig.

Laboration 2, matriser

I nedanstående uppgifter handlar det om att bekanta sig med (enkla) vektor- och matrisräkningar i Octave. I princip är det fråga om räknesätten, inverser och lösning av ekvationssystem med hjälp av matriser. I Per Jönssons dokument (länkar överst på denna sida) kan man i kapitel 12 till 16 läsa hur man matar in vektorer och matriser i Octave. Hur man sedan räknar är ofta logiskt och ni får upptäcka det själva med hjälp av övningarna nedan.

Uppgifter

1. Skalärprodukten mellan vektorerna u=(1,3,-5) och v=(-3,2,1) (koordinatsatta i en ON-bas) ges i Octave av dot(u,v). Beräkna $u \cdot v$!


2. Vektorprodukten (kryssprodukten) mellan vektorerna u och v ges i Octave av cross(u,v). Beräkna $u \times v$!


3. Lös från häftet 7.1a, 7.2c, 7.4a, 7.9ab. I Octave skriver man A^(-1) eller inv(A) för att invertera matrisen A. Notera vad som händer i 7.9b. Vad beror det på? Obs: matriserna i 7.9 behövs i nästa uppgift så "spara" dem t.ex. som A=… B=…

Vill man undvika decimaler/grundpotensform kan man först ge kommandot format rat som instruerar Octave att svara med rationella tal. Vill man byta tillbaka ger man kommandot format short.


4. Lös, om möjligt, ekvationssystemen nedan med Octave.

(3)
\begin{align} a) \begin{cases} x + 2y = 1 \\ 4x + y - z =2 \\ 2x + 3y =3 \end{cases} b) \begin{cases} x + z = 2 \\ x + y =2 \\ 2x + y +z=4 \end{cases} c) \begin{cases} x + z = 2 \\ x + y =2 \\ 2x + y +z=5 \end{cases} \end{align}

När kan man använda invers matris och när inte? Varför?


5. I Octave (och MatLab) kan man lösa överbestämda system, dvs system med fler ekvationen är obekanta. Detta gör man genom att skriva A\B om A är koefficientmatrisen och B är matrisen för konstanterna (högerledet) i ekvationssystemet. Lös på detta sätt systemet

(4)
\begin{cases} 2x -2y+4z= 1 \\ 6x + 8y - 6z =-1 \\ 9x - 5y +z=4\\3x+2y-2z=-5 \end{cases}

Octave kommer att generera värden på de obekanta som är bäst i en viss mening (genom insättning ser ni att de inte löser systemet). Observera också att matrisen A inte är kvadratisk och inte kan inverteras. Hur detta hänger ihop och vad som egentligen händer får ni reda på i vårens kurs.


6. System som har oändligt många lösningar kan inte hanteras fullt ut i Octave. Däremot kan man utföra gaussingar med kommandot rref (reduced row echelon form) och man arbetar då med en matris för hela systemet. Gaussa systemen i 4b och 4c och se om ni känner igen er/kan lösa systemet.


7. Determinanten av en kvadratisk matris bestäms i Octave med kommandot det(). Beräkna determinanterna för koefficientmatriserna från uppgift 4. Vilka samband kan du misstänka mellan determinanten och ekvationssystemens lösbarhet?


8. Lös uppgift 9.5 och 9.6.


9. Undersök med några egna exempel om det verkar finnas något samband mellan $\det(A)$ och $\det(A^{-1})$? Hypotes? Bevis? Till våren kommer beviset för den som orkar vänta!


10. (om man får tid över) Ge kommandot magic(n) där n är ett positivt heltal. Vad svarar Octave? Vad är intressant med dessa matriser (eller snarare magiska kvadrater)? Googla på "magic squares" t.ex. Såvitt jag vet har inte detta så mycket med matriser att göra men magiska kvadrater är intressanta ändå! Euler pysslade med dylika kvadrater och konstruerade själv en med sidlängd 8. Och om Euler sysslade med det så måste det vara intressant (men inte enkelt!).

Laboration 3, minsta kvadratanpassning/regression

I denna laboration kommer du att lära dig hur regression med polynom fungerar. I princip handlar det om att bland ett antal tillåtna vektorer finna den som är närmst en given vektor. Om geometrin utspelar sig i tre dimensioner är det ekvivalent med att ortogonalprojicera i plan eller på linje, och man kan använda samma ''bild'' i högre dimensioner.

Uppgifter

1. Du har gjort nedanstående ''mätningar'' av storheten y för tre olika x-värden.

x 0 1 2
y 2 5 6

Detta kan t.ex. tolkas som koordinaterna för tre punkter i planet. Antag att du vill finna en rät linje på formen $y=kx+m$ som approximerar dina punkter så bra som möjligt (det är ju klart att ingen rät linje går genom alla tre punkterna). Vi börjar med att låta GeoGebra plocka fram en ''bra'' linje. Starta GeoGebra genom att t.ex. klicka på knappen:

  • Lägg in punkterna som svarar mot tabellen. Det kan göras i grafik- eller tabellmiljön.
  • Välj kommandot RegressionPoly (görs enklast i kommandorullgardinen längs ner till höger). Lista ut vad som ska ges i kommandot RegressionPoly (tryck F1 eller fråga). GeoGebra tar fram en linje.
  • Notera k- och m-värde.

2. Nu ska vi se hur ovanstående fungerar geometriskt och vad det har med en kurs i linjär algebra att göra.

  • Snickra ett överbestämt ekvationssystem med två obekanta (k och m) och tre ekvationer genom att sätta in tabelldata i linjens ekvation.
  • Skriv ekvationssystemet på vektorform;
(5)
\begin{align} k \cdot v_1 + m \cdot v_2 = v_3 \end{align}


för lämpliga vektorer $v_1, v_2, v_3$. Att ekvationssystemet är överbestämt betyder precis att vektor $v_3$ inte ligger i det plan som spänns upp av $v_1$ och $v_2$, vilket alltså betyder att vi inte kan finna värden på k och m så att vektorekvation ''stämmer''.

  • Vilken vektor i det plan som spänns av $v_1$ och $v_2$ är rimligen den bästa approximationen av $v_3$ (gör gärna en skiss)?
  • Bestäm denna vektor och därmed k och m med tekniker från kapitel 4 (projektionsformel etc). Räkna för hand eller med Octave.
  • Jämför dina framräknade k och m med GeoGebras förslag.

Den bästa approximationen får man alltså genom att minimera avståndet mellan den önskade vektorn $v_3$ och de vektorerna som kan skrivas som linjärkombinationer av $v_1$ och $v_2$.

3. Betrakta följande ''mätningar"

x 0 1 2 3 4 5 6 7 8
y 2 5 6 10 15 17 22 25 27

Ska man snickra en funktionsgraf som säkert passerar genom alla punkterna behövs ett åttondegradspolynom. Antag att vi istället vill finna ett tredjegradspolynom som approximerar bäst möjligt.

  • Skriv upp motsvarande ekvationssystem. Vilken blir vektorekvationen? Du bör inse att det utspelar sig i $\mathbb{R}^9$, att det handlar om att i ett fyrdimensionellt underrum hitta den vektor som ligger närmst en given vektor.
  • Räkningarna förenklas dramatiskt om man använder matriser. På sid 155-156 i läroboken beskrivs hur man överför det geometriska problemet till ett matrisproblem. Om en datamängd, vid funktionsanpassning, leder fram till det överbestämda och icke-kvadratiska ekvationssystemet
(6)
\begin{equation} AX=Y \end{equation}

så får man den bästa approximativa lösning (i minsta kvadrat mening) genom att lösa matrisekvationen

(7)
\begin{equation} A^TAX=A^TY \end{equation}
  • Skriv ditt ekvationssystem på matrisform och lös det med hjälp av Octave.
  • Som du kanske minns från laboration 2 så kunde man i Octave ''lösa'' (eller snarare hitta bästa approximativa lösning) till överbestämda system. Detta gör man genom att skriva A\Y. Prova och jämför.
  • Lägg in punkterna i GeoGebra och gör regressionen. Jämför!
Laboration 4, Googles pagerank

I denna laboration ska ni kika på hur Google (i princip) bär sig åt för att ranka sidor på nätet. Denna rankning ligger sedan till grund för i vilken ordning sidorna visas efter en sökning. Kanske kan man köpa sig till en mera framskjuten placering, men det bortser vi från här. Metoden är generell och kan användas för att rangordna i många andra sammanhang.

Uppgiften framgår om ni tittar här. Längst upp till höger på denna sida ser ni ett system av "sidor" med länkar mellan. En cirkel motsvarar en sida och en riktad pil betyder en länk. Alltså har t.ex. sida D en länk till sida A (men inte omvänt). I varje cirkel står dess vikt (100% är fördelade på samtliga sidor). Ni ska beräkna dessa procentsatser.

Vill man ha ordentlig reda på hur pagerank fungerar kan man t.ex. börja med att gå igenom hela artikeln i Wikipedia. Det som följer nedan är en kortare lista som räcker för att bestämma vikterna i vårt system, men som inte förklarar alla detaljer.

Principen i pagerank:

1) Vi utgår från en riktad graf (ett antal noder med pilar emellan), och ska vikta noderna efter betydelse. Vikterna på noderna anger i princip sannolikheten för att en person som slumpvis klickar på länkar landar på en viss sida.
2) Det ska spela roll hur många inkommande länkar en nod har men också hur viktiga de inkommande länkarna är.
3) En nod som saknar utgående pilar (länkar) räknas som att den har utgående pilar (länkar) till varje annan nod. (Om man hamnar på en sida utan utgående länk går man till en godtycklig sida.)
4) Man har en dämpningsfaktor, som anger chansen för att man stannar på en viss sida (och inte klickar vidare). Tydligen (empiriskt) är 0.15 en lämplig sådan faktor.

För att rigga vårt konkreta exempel:

1) Varje nod (det finns 11 stycken) tilldelas ursprungligen vikten 1/11. Detta kan beskrivas med kolonnmatrisen/vektorn

(8)
\begin{align} X_0 = \dfrac{1}{11}[1 \; 1 \; 1 \; 1 \; 1 \; 1 \; 1\; 1 \; 1 \; 1\; 1]^{T} \end{align}

där talet $x_i^0$ på plats i anger vikten för nod i (de noder som saknar bokstavsnamn får ni själva "bokstavera"/numrera).

2) Dessa ursprungsvikter ska nu omfördelas som följer. Varje nod behåller 15% av den vikt den ursprungligen hade ($X_0$). Resten (85%) fördelas (skickas) jämnt till de noder som det finns pil till. Detta ska göras upprepade gånger (jfr Sparrs dynamiska system). Om t.ex. $x_1^j$ är vikten på nod 1(A) efter $j$ "gånger" får vi

(9)
\begin{align} x_1^{j+1} = 0.15 \cdot 1/11 + 0.85(1/11 x_1^j + 1/2 x_4^j ) \end{align}

eftersom 15% av den ursprungliga vikten ska behållas, och det tillkommer 85% av 1/11 av dess egen vikt (noden har ju inte utgående pilar) och 85% av halva D:s vikt (resten skickar ju D till E).
För t.ex. nod 2(B) får vi

(10)
\begin{align} x_2^{j+1} = 0.15 \cdot 1/11 + 0.85(1/11 x_1^j + 1 x_3^{j} + 1/2 x_4^j + 1/3 x_5^j+ 1/2 x_6^j + 1/2 x_7^j + 1/2 x_8^j + 1/2 x_9^j) \end{align}

Gör man detta för varje nod får man följande på matrisform

(11)
\begin{equation} X_{j+1} = 0.15X_0 + 0.85AX_j \end{equation}

där $A$ är matrisen som ''hanterar'' de riktade pilarna. Kör vi detta upprepade gånger får vi

(12)
\begin{align} X_1=0.15X_0+0.85AX_0\\ X_2=0.15X_0+0.85AX_1=0.15X_0+0.85A(0.15X_0+0.85AX_0)=0.15X_0+0.85\cdot 0.15 AX_0 + 0.85^2A^2X_0\\ osv. \end{align}

För att studera detta system snickrar man matrisen $X_0$ och $A$ i Octave. Gör det!

3) Vi ska nu studera vad som händer om man kör systemet ovan många gånger (oändligt många gånger). Enligt [wikipedia:Perron–Frobenius_theorem Perron-Frobenius sats] (som man inte snyter ur näsan precis) har matrisen A ett egenvärde som är 1 (inte så svårt att inse), en till detta hörande egenvektor med enbart positiva tal (egenvektorn kan antas ha längden 1) och för A:s övriga egenvärden $\lambda$ gäller att $|\lambda| < 1$ så iterationen kommer att konvergera (gå mot) en kolonnvektor $X$ som ges av

(13)
\begin{equation} X=0.15X_0+0.85AX \end{equation}

(ersätt $X_j$ och $X_{j+1}$ med $X$). Denna matrisekvation har lösningen

(14)
\begin{equation} X=(I-0.85A)^{-1}0.15X_0 \end{equation}

Bestäm $X$ i Octave. Jämför detta med vikterna i bilden i Wikipedia. Samma?

Tips: En enhetsmatris av storlek n bildas i Octave med eye(n).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License