Ta fram L,U,P matrisen och komplexitet!

Tjena!

Som rubriken lyder vill jag gärna veta hur man löser uppgifter där man tar fram L, U och P matrisen och även hur man bör tänka på en uppgift som har med komplexitet att göra. Läser kursen beräkningsvetenskap och fick nyligen veta att jag blev underkänd och då var detta en av uppgifterna som bidrog till att jag blev underkänd. Har bifogat själva uppgiftsfrågan och min lösning (och lärarnas lösning på komplexitet).

Uppgiftfråga för LUP-uppgift och komplexitet samt lösning för samtliga uppgifter.

http://imgur.com/ruVwvr1,xunkRHX

min lösning för LUP uppgiften:

http://imgur.com/ruVwvr1,xunkRHX#1

Uppskattar hjälp från någon kunnig som kan hjälpa mig med tankesättet. Omtenta på lördag så sitter och nöter på gamla tentor atm.

/Shahin

På deluppgift a) så har du gjort fel i elimineringen. På raden där det står ett rött "?" så har du av din notation att döma subtraherat 1 gånger rad 1 från rad 2, men bortsett från effekten detta skulle ha fått på det första elementet på rad 2. Du hade ju 0 i första kolumnen på rad 2 och subtraherar 1 i första kolumnen till följd av att du subtraherar 1 gånger rad 1. Det skulle alltså leda till att du skulle få -1 i första kolumnen på rad 2. Det du skulle ha gjort istället är att med hjälp av rad 2 eliminera siffran i andra kolumnen på rad 3.

Ett annat fel du gör är att du normerar rad 1 i U-matrisen genom att dividera med 3. Det ska du inte göra vid LU-faktorisering (eller om du gör det så måste du justera L-matrisen motsvarande för att produkten av L och U ska bli den ursprungliga matrisen A).

På deluppgift b) så är det ju ett rätt enkelt fel du gjort. Du har korrekt skrivit ut komplexiteten som C*n³ men sedan har du inte använt det för att uppskatta tiden det skulle ta för en matris med dubbelt så många rader och kolumner. Att antalet rader och kolumner dubblas betyder alltså att n dubblas, och eftersom n förekommer i potensen n³ så blir tidsåtgången därför 2³ = 8 gånger så lång.

Sättet du bör tänka på är att du vet att C*n³ = 11,5 sekunder och du vill veta hur mycket längre C*(2n)³ tar. C*(2n)³ = C*8n³ = 8*C*n³, vilket alltså blir 8*11,5 sekunder eller alltså 8 gånger så lång tid som för den ursprungliga matrisstorleken.

Tack för guidandet i A!

Angående b uppgiften så var det inte mitt svar där utan lärarens

Det som gör mig sjukt förvirrad är hur man börjar med C*n^3. Varför just 3? de skriver "komplexiteten för att lösa ett linjärt ekvationssystem är n^3". Låter med andra ord som något jag bör alltid komma ihåg. Vidare att det är 500 i ena potensen och 1000 i den andra verkar man inte ha i åtanke när man utför beräkningen. Eller ser jag fel?

Nu sa de att det var dubbelt så många rader och då multiplicerade vi n med 2. om vi hade haft exakt samma fråga men med låt oss säga... 3 gånger så många rader, hade vi helt enkelt multiplicerat in en 3:a med n istället? då hade vi alltså fått C*n^3 -> C*(3n)^3 -> c*27n^3 -> 27*Cn^3 . Dvs. 27 gånger längre tid. Rätt?

Gäller C*n^3 ALLTID när det kommer till såna här typer av komplexitet frågor? ska se om jag hittar en till tenta och kan utföra samma metod och se ifall jag förstod metodiken.

Det där med 3 och så vidare stämmer med ditt resonomang om 27 gånger längre tid. Och vad gäller C*n^3 för sådant där så nej, det gäller inte alltid. Det finns olika bra metoder för allt möjligt. Alltså måste man veta vilken metod som används för att veta komplexitet.

Stött på ett liknande problem nu igen fast omvända vägen.

http://imgur.com/jorfTgW,AFoILfZ#0

Och lösningen:

http://imgur.com/jorfTgW,AFoILfZ#1


Jag vet ju sedan tidigare angående sambandet Ly = Pb.

Hur ska jag börja härifrån med det i åtanken?