LR Zerlegung mit zeilenweise Berechnung Laufzeitabschätzung?

05.10.2017, 17:21	JessicaDownunder	Auf diesen Beitrag antworten »
LR Zerlegung mit zeilenweise Berechnung Laufzeitabschätzung? Folgender Algorithmus ist gegeben: $\begin{eqnarray} for \quad i=1,..,n: \quad \quad \end{eqnarray}$ $\begin{eqnarray} for \quad j= 1,...,i-1: \end{eqnarray}$ $\begin{eqnarray} l_{i,j} = \frac{a_{i,j}-\sum_{k=1}^{j-1} l_{i,k}r_{k,j}}{r_{j,j}} \end{eqnarray}$ $\begin{eqnarray} for \quad j=i,...,n: \end{eqnarray}$ $\begin{eqnarray} r_{i,j}=a_{i,j}-\sum_{k=1}^{i-1} l_{i,k} r_{k,j} \end{eqnarray}$ (ich bekomme das Spacing leider nicht gut hin. Die obere for-Schleife umfasst die beiden unteren. Die unteren Schleifen laufen unabhängig voeinander, sind also nicht verschachtelt.) Mein Ansatz ist: i-1 Subtraktionen und Divisionen und (i-1)(j-1) Multiplikationen und Additionen in der ersten Schleife. i-n Subtraktionen und (i-n)(i-1) Multiplikationen und Additionen in der zweiten Schleife Insgesamt: $\begin{eqnarray} \sum_{i=1}^n (i-1)(j-1) \in \Theta(n^2) \end{eqnarray}$ für die erste Schleife und $\begin{eqnarray} \sum_{i=1}^n (i-1)(j-1) \in \Theta(n^2) \end{eqnarray}$ für die zweite Schleife. Ich bin mir jetzt leider nicht sicher, ob ich da richtig gerechnet habe. Die normale LR Zerlegung liegt ja in $\begin{eqnarray} \Theta(n^3) \end{eqnarray}$ , also wäre dieser Algorithmus nach meiner Berechnung eine Verbesserung, oder?
12.10.2017, 21:11	sibelius84	Auf diesen Beitrag antworten »
Hallo JessicaDownunder, dein Ergebnis finde ich merkwürdig, da ja in der dritten Schleife viel mehr Rechenoperationen stattfinden. Müsstest du nicht über j noch von 1 bis i summieren? Generell würde ich mir erst für jede Zeile innerhalb einer Schleife überlegen, wie viele Rechen-OPs da stattfinden (in Abhängigkeit von i und j), und dann entsprechend über den Schleifenindex summieren. LG sibelius84
20.10.2017, 07:53	RomanGa	Auf diesen Beitrag antworten »
Aufwandabschätzung Hallo Jessica, der Aufwand der normalen LR-Zerlegung ist, wie du schreibst, O(n^3). Dies ist auch hierfür plausibel. Denn: Die äußere Schleife läuft n-mal. Die beiden „mittleren“ Schleifen kann man zusammenfassen. Wir haben insgesamt auch n Durchläufe. Die Summe kann man als innere Schleife programmieren. Sie wird, grob gesprochen, von 1 bis i durchlaufen. Die mittlere und die innere Schleife zusammen ergeben 1 + 2 + 3 + … + n = O(n^2). Damit erhalten wir O(n^3).

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »