Github Repository
Lösung linearer Gleichungssysteme
Contents
Voraussetzungen
Matrizen-Grundlagen
Lerninhalte
numerische Lösung linearer Gleichungssysteme
Umgang mit Sparse-Matrizen und deren Vorteile
Lösung linearer Gleichungssysteme¶
Anmerkung
Diese Übung behandelt die Lösung linearer Gleichungssysteme mit Matlab. Im Kapitel “Modellierung einer Highline” finden Sie ein anspruchsvolles anwendungsnahes Beispiel, bei dem das Gleichungssystem erst aufgestellt werden muss, bevor es mit den hier erlernten Methoden gelöst werden kann.
Gegeben ist das LGS \(Ax=b\) der Dimension \(N\) mit
Alle Diagonalelemente der Matrix \(A\) seien also \(-2\), die Nachbarelemente der Diagonalelemente seien allesamt \(1\). Das letzte Element der ersten Zeile sei ebenfalls \(1\). Für den Vektor \(b\) gelte \(b_i = 1\) für \(i = \frac{N}{4}\) … \(\frac{3N}{4}\), sonst \(b_i = 0\). Dabei soll \(N\) ein Vielfaches von 4 sein.
Aufgabe 1 - Erstellung der Matrix und des Lösungsvektors¶
Erstellen Sie die Matrix \(A\) und den Lösungsvektor \(b\) in Abhängigkeit von \(N\).
N = %YOUR CODE HERE
b = zeros(N,1); b(N/4:3*N/4)=1;
A = %YOUR CODE HERE
Aufgabe 2 - Lösung des Gleichungssystems¶
Lösen Sie das Gleichungssystem jeweils für die Dimensionen \(N=4, 8, 12, 40, 400, \cdots\) mit dem Backslash-Operator A\b. Matlab analysiert die Struktur der Matrix und wählt automatisch einen geeigneten Löser für dieses Gleichungssystem. Berechnen Sie jeweils die Genauigkeit der berechneten Lösung mit max(abs(A*x-b)). Messen Sie jeweils die benötigte Rechenzeit mit Hilfe der Matlab-Funktionen tic und toc.
Anmerkung
In “Modellierung einer Highline” wählen Sie den Löser selbst aus und vergleichen die Performanz der verschiedenen Löseverfahren.
tic
%YOUR CODE HERE
time=toc
Aufgabe 3 - Erstellung einer Matrix im Sparse-Matrix-Format¶
Unsere Matrix \(A\) enthält sehr viele Nullen. Eine solche Matrix nennt man eine “dünnbesetzte Matrix” oder englisch “sparse matrix”. Dünnbesetzte Matrizen tauchen bei der Diskretisierung von Differentialgleichungen auf, wie Sie bei vielen Simulationsmethoden (Strömungssimulation, FEM, Mehrkörpersimulationen, …) gelöst werden müssen. Die ganzen Nullen benötigen leider viel Speicherplatz und führen auch zu vielen überflüssigen Rechenoperationen, wie z.B. Multiplikationen oder Additionen mit Null, wodurch die Performance von Algorithmen leidet.
Viele numerische Algorithmen werden hinsichtlich solcher dünnbesetzter Matrizen optimiert. Wir werden nun die Matrix A in einem speziellen Format für dünnbesetzte Matrizen erzeugen und anschließend das Gleichungssystem erneut lösen.
a. Kommentieren Sie den Matlab-Code zur Erzeugung der dünnbesetzten Matrix A im Sparse-Matrix-Format an den vorgesehenen Stellen.
b. Welche Bedeutung, welchen Datentyp und welche Größe haben die Variablen k, row, column und value?
k = 0;
# Comment this loop here
for i=1:N
# Comment this next line here
k = k+1; row(k) = i; column(k) = i; value(k) = -2;
# Comment this if statement here
if (i > 1)
k = k+1; row(k) = i; column(k) = i-1; value(k) = 1;
end
# Comment this if statement here
if (i<N)
k = k+1; row(k) = i; column(k) = i+1; value(k) = 1;
end
end
# Comment this next line here
k = k+1; row(k) = 1; column(k) = N; value(k) = 1;
Asparse = sparse(row,column,value,N,N);
Aufgabe 4 - Lösung des LGS im Sparse-Matrix-Format¶
Lösen Sie nun das LGS mit der Matrix im Sparse-Matrix-Format mit den selben Dimensionen \(N\). Messen Sie wieder die Rechenzeit der Lösungsverfahren und berechnen Sie die Genauigkeit.
Vergleichen Sie Rechenzeiten und Genauigkeiten mit denen aus Aufgabe 2. Stellen Sie die Rechenzeiten aus Aufgabe 2 und Aufgabe 4 anschaulich graphisch gegenüber.
% space for the solution
Aufgabe 5 - Speicherbedarf der Matrizen¶
a. Schätzen Sie ab und begründen Sie, wie hoch der Speicherbedarf einer NxN-Matrix im “normalen” Matrix-Format ist! Wieviel mehr Speicherplatz benötigt eine 2Nx2N-Matrix?
b. Schätzen Sie ab und begründen Sie, wie hoch der Speicherbedarf einer NxN-Matrix der hier vorliegenden Form im Sparse-Matrix-Format ist! Wieviel mehr Speicherplatz benötigt eine 2Nx2N-Matrix im Sparse-Matrix-Format?
c. Schätzen Sie ab und begründen Sie, wie groß eine “normale” Matrix sein darf, dass Ihr Computer diese noch verarbeiten kann!
d. Schätzen Sie ab und begründen Sie, wie groß eine Sparse-Matrix sein darf, dass Ihr Computer diese noch verarbeiten kann!
e. Prüfen Sie Ihre Abschätzungen zu c. und d. mit Matlab. Was passiert jeweils, wenn Sie versuchen ein LGS mit \(N=4000000\) zu lösen?
% space for the solution
Zusatzaufgabe¶
Versuchen Sie Ihre Abschätzungen aus Aufgabe 5a. und 5b. mit Matlab zu überprüfen!
% space for the solution