Aufwandsabschätzung für LR-Zerlegung

Bachelor Algorithmik kontinuierlicher Systeme
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Aufwandsabschätzung für LR-Zerlegung
Hallo,
könnte mir jemand erklären, wie man auf die Zahl der Multiplikationen und Additionen bei der LR-Zerlegung kommt (VL-Folie 29, Direkte Verfahren für LGS). Ich verstehe nicht, wo das (2n-1)/3 herkommt.
Danke schon mal!

3

Summenformel :slight_smile:

Attachment:
summenformel.jpg: https://fsi.cs.fau.de/unb-attachments/post_166532/summenformel.jpg

4

Dann versuche ich das mal näher zu erläutern. Wir betrachten nun hier den Algorithmus von Seite 28 und dort auch nur den ersten Teil.
[m]Zwischenfrage 1: Warum nur den ersten Teil? – Weil im zweiten Teil des Algorithmus keinerlei relevante Rechenoperationen mehr durchgeführt werden, die uns interessieren. Wir sind hier in der NLA (numerischen linearen Algebra) eher an flops interessiert, also an Operationen mit Gleitpunktzahlen.[/m]
Jetzt betrachten wir eben diesen Pseudocodeteil:

T <- A                                    ; A sei eine nxn-Matrix
für j von 1 bis n-1 tue
  |  für i von j+1 bis n tue
  |    |  T[i,j] <- T[i,j] / T[j,j]       ; Bestimmung von L[i,j]
  |    |  für k von j+1 bis n tue
  |    |    |  T[i,k] <- T[i,k] - T[i,j] * T[j,k]
  |    |    \___
  |    \___
  \___

Ich gehe jetzt immer an solche Aufgaben heran und betrachte welche „Zeilen“ die gewünschten Operationen wie oft beinhalten. Dann stellen wir fest:

  • Divisionen tauchen nur in Zeile 4 auf und dort nur eine.
  • Multiplikationen tauchen nur in Zeile 6 auf und dort ebenfalls nur eine.
  • Subtraktionen/Additionen tauchen nur in Zeile 6 auf und dort ebenfalls nur eine.

Jetzt schauen wir noch nach wie oft die einzelnen Zeilen jeweils ausgeführt werden. Einerseits werde ich die Schleife von Zeile 2-9 als „äußere“ Schleife, die Schleife von Zeile 3-8 als „innere“ Schleife und die Schleife von Zeile 5-7 als „Vektorschleife“ bezeichnen, andererseits verwende ich hier eine verkürzte Summenschreibweise in TeX-Notation, welche aber (hoffentlich) einfach und verständlich zu lesen sein sollte:

  • Zeile 4 (Divisionen): Zeile 4 wird in der inneren Schleife jeweils einmal ausgeführt, sprich in der äußeren Schleife dann \sum_{i = j+1}^{n} 1 = n-j-mal. Insgesamt dann \sum_{j=1}^{n-1} n-j = (n-1)*n - \sum_{j = 1}^{n-1} j = (n-1)*n - ½ * (n-1)*n = [b]½ * (n-1) * n[/b] mal.
  • Zeile [color=green]6 (Multiplikationen/Subtraktionen/Additionen):[/color] Zeile 6 wird in der Vektorschleife genau einmal ausgeführt, sprich in der inneren Schleife dann \sum_{k = j+1}^{n} 1 = n - j-mal. In der äußeren Schleife somit \sum_{i = j+1}^{n} n-j = (n-j) * \sum_{i = j+1}^{n} 1 = (n - j)²-mal. Insgesamt dann \sum_{j = 1}^{n - 1} (n - j)² = \sum_{j = 1}^{n - 1} (n² - 2nj + j²) = (n - 1) * n² - 2 * n * ½ * n * (n - 1) + 1/6 * (n - 1) * n * (2n - 1) = [b]1/6 * (n - 1) * n * (2n - 1)[/b] mal.

Zusammengefasst ergibt sich damit dann:

  • Anzahl Divisionen: ½ * (n-1) * n.
  • Anzahl Multiplikationen: 1/6 * (n - 1) * n * (2n - 1).
  • Anzahl Subtraktionen/Additionen: 1/6 * (n - 1) * n * (2n - 1).

Ich hoffe, dass dir das zumindest ein bisschen weitergeholfen hat. Die genauen Summenvereinfachungen gehen dann über die Summenformeln, sprich das hier (Wikipedia) und das hier (Wikipedia).

3 „Gefällt mir“
5

Jetzt hab ichs kapiert. Vielen Dank für die ausführliche Antwort!