Aufwand des Gauß-Verfahrens < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
Guten Morgen alle zusammen!
Bin gerade dabei, mir die L-R-Zerlegung klar zu machen und bin beim Aufwand hängen geblieben. Der wird in meinem Skript mit
Zerlegung: [mm] \bruch{n^{3}}{3}+O(n^{2}) [/mm] multiply adds
Auflösung: [mm] (\bruch{n^{2}}{3}+O(n))\*2 [/mm] = [mm] n^{2}+O(n) [/mm] multiply adds
Meine Frage: Ich habe nicht verstanden, was die beiden Terme aussagen, vor allem wegen des O(...). Könnte mir das jemand bitte erklären?
Ich habe diese Frage auch in keinem anderen Forum gestellt.
Wäre nett und holfreich, von jemandem zu hören!
Grüße
Loecksche
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:58 Do 03.02.2011 | | Autor: | nooschi |
den Aufwand misst man ja daran, wieviele Rechenschritte gemacht werden müssen. bei der L-R-Zerlegung hängt das davon ab, wie gross die Matrix ist, die zerlegt werden soll. Dies ist hier wohl eine [mm] $n\times [/mm] n$ Matrix.
Jetzt bei dem Aufwand will man eine grob Abschätzung, es interessiert vor allem, was bei grossen Problemen, also bei riesigen Matrizen (grosse n) passiert. Wenn da zum Beispiel der Aufwand (genau ausgerechnet) [mm] $\frac{1}{3}n^3+23n^2-12n+3445$ [/mm] ist, dann ist [mm] $23n^2-12n+3445$ [/mm] für grosse n eigentlich irrelevant, man kürzt ab mit [mm] $O(n^2)$. [/mm] Damit meint man, dass dies ein Polynom ist, wo die grösste Potenz die vorkommt [mm] n^2 [/mm] ist. Insgesamt schreibt man dann
[mm] $\frac{1}{3}n^3+23n^2-12n+3445=\frac{1}{3}n^3+O(n^2)$
[/mm]
(wir hatten damals sogar nicht einmal die erste Potenz genau ausgeschrieben sondern direkt mit [mm] O(n^3) [/mm] abgekürzt)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Mi 09.02.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
