Komplexität Gauß-Algorithmus < Matrizen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Bestimmen Sie die Komplexität des Gauß-Algorithmus in Abhängigkeit von n, wenn dieser auf eine n x n Matrix A angewandt wird. |
Hi,
durch meine Internetrecherche habe ich herausgefunden, dass die Komplexität O(n³) sein soll. Allerdings komme ich nicht darauf.
Eine allgemeine Frage zuerst: Wird bei der Komplexität auch das zurückrechnen mit betrachtet?
Angenommen ich habe eine 3x3 Matrix. Dann suche ich mir erst eine Pivotzeile (angenommen das ist Zeile 1) und multipliziere diese, damit der 1. Koeffizient gleich 1 wird. (4 einzelne Multiplikationen). Dann multipliziere ich die Pivotzeile (4 Multipl.), um sie danach mit der 2. Zeile zu addieren (4 Additionen). Das gleiche für die 3. Zeile (nochmal 4 Multipl. und 4 Additionen). Beim 2. Durchlauf wieder dasselbe, aber nur noch je 3 Operationen. (also 3 mal 3 Operationen). Damit komme ich am Ende auf 29 Operationen, was aber mehr als n³ (27) ist.
Danke für die Hilfe!
neo
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:42 So 06.01.2008 | | Autor: | zahllos |
Mit dem Gauß-Algorithmus braucht man ca. [mm] \frac{n^3}{3} [/mm] Operationen um die LR-Zerlegung einer quadratischen Matrix zu berechnen.
Man kann sich das folgendermaßen überlegen:
Es sind bei einer n-reihigen Matrix n-1 Iterationen erforderlich.
In jeder Iteration müssen die Zeilen unterhalb der Hauptdiagonalen ausgeräumt werden.
In der ersten Iteration sind das n-1 Zeilen der Länge n, in der zweiten Iteration n-2 Zeilen der Länge n-1 usw.
Insgesamt bekommt man also ca. [mm] \sum_{k=1}^{n-1} [/mm] (n-k)(n-k+1) Operationen
(eine Operation ist dabei eine Multiplikation oder Division in Kombination mit einer Addition oder Subtraktion).
Wenn man diese Summe berechnen will , so erhält man im Wesentlichen: [mm] \sum_{k=1}^{n} n^2
[/mm]
Diese Summe steht z.B. in der Formelsammlung, der führende Term (und nur der interessiert bei der Komplexitätsbetrachtung) ist [mm] \frac{2n}{6} [/mm] also gleich [mm] \frac{n^3}{3}
[/mm]
Damit hat man die Zerlegung der Matrix. Der Rechenaufwand für die eigentliche Lösung des Gleichungssystems (die sich dann als Lösung von zwei gestaffelten Gleichungssystemen ergibt) ist dann ca. [mm] n^2 [/mm] Operationen.
Man kann mit dem Gauß-Algorithmus auch nur die rechte obere Dreiecksmatrix R berechnen und auf die Berechnung von L verzichten, dann muß aber die rechte Seite des Gleichungssystems mit umgeformt werden und der Rechenaufwand ist der gleiche wie oben angegeben.
|
|
|
| |
|
Danke für die Antwort zu so später Stunde!
Ich vermute, sie meinten statt [mm]\sum_{k=1}^{n} n^2[/mm] eher [mm]\sum_{k=1}^{n} k^2[/mm] (da man sonst nicht die Formel aus der Formelsammlung nehmen könnte). Allerdings ist mir nicht ganz klar, wie man [mm]\sum_{k=1}^{n-1}[/mm] (n-k)(n-k+1) auf [mm]\sum_{k=1}^{n} k^2[/mm] reduzieren kann. Immerhin ist ja, wenn man es ausmultipliziert, n² und k² vorhanden, wobei n² stärker wäre (z.B. n=3, dann wäre es für n² 3*3 + 3*3 + 3*3 und für k² nur 1*1 + 2*2 + 3*3). Wobei eine Reduzierung auf [mm]\sum_{k=1}^{n} n^2[/mm] ja [mm] n*n^2 [/mm] = n³ entsprechen würde, was sofort auf die Komplexität führt.
Oder sind beide Lösungen richtig?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:31 Mi 09.01.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
