Ctrl+K

Lösung linearer Gleichungssysteme

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

\[\begin{split}A= \begin{bmatrix} -2 & 1 & 0 & \dots &0 & 0 & 1 \\ 1 & -2 & 1 & \dots &0 & 0 & 0 \\ 0 & 1 & -2 & \dots &0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & \dots &-2 & 1 & 0 \\ 0 & 0 & 0 & \dots &1& -2 & 1 \\ 0 & 0 & 0 & \dots &0& 1 & -2 \end{bmatrix} \qquad\text{und}\qquad b= \begin{bmatrix} 0 \\ 1 \\ 1\\\vdots\\1\\0\\0 \end{bmatrix}\end{split}\]

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?

Anmerkung

Der folgende Code ist ein ein Code-Schnipsel und nicht direkt ausführbar. Um die Funktionen auszuprobieren zu können sind Anpassungen notwendig.

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
Contents