Numeriska Metoder

Tja,

Har stött på ett problem som jag inte förstår och tänke kolla ifall någon här vet hur man räknar ut svaren.
Hjälp uppskattas!



U4.
a) En dator löser ett linjärt ekvationssystem med 100 ekvationer och 100 obekanta på en sekund. Hur lång tid tar det att lösa ett system med 500 ekvationer och 500 obekanta?

b) Antag att du mäter tidsåtgången för en dator att lösa ett n × n ekvationssystem, för ett antal olika n. Du antar att tidsåtgången, T = cnα. Hur skall du plotta dina data för att med hjälp av detta kunna bestämma ett värde på α?

Sedan även

Antag att matrisen A med dimension n × n har normen
∥A∥∞ = max_[y∈Rn],y=~0(inte noll), [∥Ay∥∞/ ∥y∥∞] = 10^4

där ∥y∥∞ = max1≤i≤n |yi|. Dessutom gäller ∥A^−1∥∞ = 10^3.
a) Vad blir konditionstalet cond(A) för matrisen A baserat på detta?
b) En vektor y ∈ Rn har norm ∥y∥∞ = 2. Hur stort kan då ∥Ay∥∞ maximalt vara?
c) Givet systemet Ax = b. Antag att man fått indata, d v s b genom mätningar med ett mätinstrument som har en mätnoggrannhet på 0.2%, dvs relativt fel på 0.002. Vilket fel kan man ha i resultatet x i värsta fall?


mvh thuuuug

a) Eftersom gauss elimination är av ordningen O(n^3) så kommer det alltså att ta 5^3 gånger längre tid. Alltså 125 sekunder.

b) Jag antar att det ska stå T = cn^α, då blir det ju lämpligt att plotta ln(T) = ln(c) + αln(n). Då bör datat ligga efter en linje och linjens lutning är α värdet.

Tack så hemskt mycket för snabbt svar! Är helt ny på programmering så förstår inte alltför mycket.. Du råkar inte veta någon källa som tex förklarar koden för backsubstitution i ett upper triangular matrix osv? Jag hittar koden, vet självfallet hur man gör för hand, men förstår nada annars.


Tex

x=zeros(n,1);
x(n)=y(n)/A(n,n);
for i=n-1:-1:1
x(i)=(y(i)-A(i,i+1:n)*x(i+1:n))/A(i,i);
end

Säg att du har ett 3x3 matrix, alltså n=length(b)=3
Skulle så gärna vilja förstå istället bara för att copy paste

Jag vet ingen sida där dom förklarar vad som händer i den där koden, men ett tips är att du försöker utföra den för hand och ser vad som händer. Är det någon specifik notation du inte hänger med på eller inte vet vad någon funktion gör så kan man ju alltid söka på det eller ställa en fråga här, samt att Matlab har så att man skriver "help zeros" så får man en förklaring på vad funktionen gör. Men du kan ju få lite guidning om vad det är som händer i den där koden.

x = zeros(n, 1);
Definierar en vektor med n element. Argumenten betyder helt enkelt att du skapar en matris som är n x 1, vilket kan ses som en vektor.

x(n) = y(n)/A(n, n)
Är helt enkelt att du löser den sista ekvationen, notera att den är på formen a_{n, n} x_n = y_n, så lösningen på den sista ekvationen är alltså den som är skriven.

I loopen så går du från den näst sista ekvationen till den första. Koden A(i, i + 1 : n) betyder att du plockar ut den i:te raden och kolumn i + 1 till kolumn n. Så raden i loopen motsvara att du löser ekvationen

sum_{k = i} A_{i, k} * x_k = y_i.

Notera att alla x värden i denna ekvation är känd förutom x_i eftersom de x_k för k > i har du redan löst vad dom är i tidigare skede i bakåtsubstitutionen.

a) Konditionstalet är ∥A∥∥A^(-1)∥ så det är helt enkelt 10^4 * 10^3 = 10^7.

b) Då ∥Ay∥ ≤ ∥A∥∥y∥ så är alltså ∥Ay∥ ≤ 2*10^4.

c) Låt e_1 vara relativa felet i x och e_2 vara relativa felet i mätningen. Då är e_1/e_2 ≤ cond(A) vilket ger att e_1 ≤ cond(A) e_2 = 10^7 * 0.002 = 2*10^4.

Tack så mycket för all hjälp! Uppskattar det verkligen. Har en labb idag om de två frågorna. Dock undrar jag vart du har lärt dig denna kunskap? Alltså om du kommer ihåg vilken bok eller hemsida? Jag har ju min egna kursbok men den förklarar så uselt. Engelska källor är inga problem

Har ingen källa att rekommendera. När jag läste kurserna som tog upp detta så hade jag en urusel kursbok som inte innehöll något av detta mer eller mindre, så man får söka runt lite på internet om de olika koncepten.