Flops < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:04 Fr 07.01.2005 | | Autor: | aka |
hallo,
ich verstehe das nicht mit den flops. kann mir jemand das mal erklären. Z. B. anhand des guass algorithmus, ich komme einfach nicht auf die Summe
X
j=1
Kj =
1
3
n3 + O(n2)
Auch für dummies, bitte.
danke.Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo aka,
flops sind zunächst mal die Anzahl der benötigten Grundrechenoperationen. Hier muß man sich überlegen was genau gerechnet wird bzw. wie oft. Welche Lösungsansätze hast Du denn?
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:40 Di 11.01.2005 | | Autor: | aka |
hallo,
ich habe selbst keine lösungsansätze, es ist keine hausaufgabe. wir hatten die aufgabe in der übung, aber kaum was dazu aufgeschrieben. ich habe sie damals nicht verstanden. deshalb wollte ich nachfragen.
|
|
|
| |
|
Hallo aka,
Den Gaussalgorithmus kann man in 2 Schritte aufteilen.
Start Ax=b
1. Umformen zum Dreieckssystem
(Rx=c)( R obere Dreiecksmatrix) Das ist der Schritt wo in jeder Spalte entsprechend Nullen erzeugt werden.
2. Lösen von Rx=c
Zum Schritt
Zunächst will man in der ersten Spalte Nullen erzeugen. Dazu muß fast die gesamte Matrix umgeformt werden. Bei intelligenter Berechnung hat man pro Element 2 Operationen durchzuführen. Insgesamt [mm] 2*n^2 [/mm] Operationen Danach lässt man die erste Spalte ersteZeile "links liegen" und formt nur noch die Restmatrix um sonst passiert aber das gleiche Also [mm] 2*(n-1)^2 [/mm] Operationen usw. usf. Also insgesamt
[mm] 2\summe_{i=1}^{n}n^2 = 2\bruch{n(n+1)(2n+1)}{6} \approx \bruch{2}{3} n^3[/mm]
![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
Jetzt komm ich auf 2/3 Ich dachte es wäre 1/3 Naja ich überleg vielleicht Morgen nochmal.
gruß
mathemaduenn
|
|
|
| |
|
Hallo aka,
Das mit den 2/3 hat schon seine Richtigkeit. Das lösen des Dreieckssystems Rx=c hat dann einen Aufwand [mm] O(n^2) [/mm] wobei das große O bedeutet das es einen Vorfaktor gibt. Der ist aber weniger von Bedeutung da für große n Der Schritt 1(Aufwand [mm] \bruch{2}{3}n^3) [/mm] der mit dem höheren Aufwand ist.
gruß
mathemaduenn
|
|
|
|
