| |
| Autor |
  Aufwand der Gauß-Elimination |
|
Kleine_Meerjungfrau
Senior 
Dabei seit: 29.10.2003
Mitteilungen: 3302
Wohnort: Köln
 |  Themenstart: 2004-03-03
|
Hallo zusammen!
Irgendwie ist die Sache mit dem Aufwand immer noch ein Buch mit sieben Siegeln für mich :-/
Also wir haben zunächst mal gesagt, dass man ein LGS durch Vorwärts- und Rückwärtssubstitution lösen kann und dass der Aufwand dafür insgesamt O(m^2) ist.
Dann kam die Gauß-Elimination ohne Pivotsuche ins Spiel, wobei wir unter Gauß-Elimination nur die LU-Zerlegung verstehen und nicht die Lösung des LGS. Der Aufwand für die Gauß-Elimination ohne Pivotsuche war dann 1/3*m^3. Kurze Zwischenfrage: Kann man hier schreiben 1/3*O(m^3) oder kann man vielleicht sogar das 1/3 weglassen?
Soweit ist mir das auch klar und ich kann halbwegs nachvollziehen, wie man auf den Aufwand kommt.
Als nächstes haben wir dann die Gauß-Elimination mit Spaltenpivotsuche gemacht, wobei der Algorithmus wohl eher dem Lösen eines LGS dient, man braucht nämlich die LU-Zerlegung, die Permutation vom Lösungsvektor, eine Vorwärts- und eine Rückwärtssubstitution. Der Aufwand von dem Ganzen soll jetzt O(m^2) betragen und das verstehe ich nicht. Ist der Aufwand für die Gauß-Elimination mit Pivotsuche kleiner als der für die Gauß-Elimination ohne Pivotsuche? Aber warum wird dann die Gesamtkomplexität nicht beeinträchtigt?
Vielleicht kann mir ja jemand von euch weiterhelfen.
Gruß
kleine Meerjungfrau
|
 Profil
|
LutzL
Senior 
Dabei seit: 06.03.2002
Mitteilungen: 10094
Wohnort: Berlin-Mahlsdorf
 | Beitrag No.1, eingetragen 2004-03-03
|
Hi,
sieht seltsam aus, es sollte O(m^3) rauskommen. Das 1/3 kann weggelassen werden, allerdings lautet eines der Gebote von Schoenhage, dass man die Konstanten nicht vernachlaessigen soll, denn daraus ergeben sich Grenzen der praktischen Anwendbarkeit.
Uebrigens ist die 3. Potenz nur fuer Computer gueltig, die uneingeschraenkt mit reellen Zahlen zu Einheitskosten rechnen koennen, eine Matrix rational zu invertieren unter Beruecksichtigung der Bitlaenge ist schon etwas haesslicher (Gauss-Bareiss und schlimmer).
|
Profil
|
Kleine_Meerjungfrau
Senior
Dabei seit: 29.10.2003
Mitteilungen: 3302
Wohnort: Köln
| Beitrag No.2, vom Themenstarter, eingetragen 2004-03-03
|
Hm, also ich hab hier noch ein Buch, da steht auch drin, dass für den Aufwand O(m^2) rauskommen soll (nur für Spalten- bzw. Zeilenpivotsuche, bei totaler Pivotsuche kommt schon O(m^3) raus). Ich frag mich sowieso, wieso man nicht immer eine Pivotsuche macht, wenn es nicht aufwendiger ist als ohne...
|
Profil
|
susi0815
Senior
Dabei seit: 20.11.2003
Mitteilungen: 1559
Wohnort: Hannover
 | Beitrag No.3, eingetragen 2004-03-03
|
Hallo kleine Meerjungfrau,
es wird unterstellt, dass Du gaaaaaaaaaaanz viele LGS mit einer Matrix und vielen rechten Seiten lösen willst.
Jetzt bist Du aber clever und machst das, was Arbeit macht, nämlich die LU_Zerlegung mit O(m^3) Aufwand nur einmal.
Und gehst Du her und löst die LGS für die vielen rechten Seiten nur noch mit Vorwärts- und Rückwärtseinsetzen, was viel billger ist.
Zugegebenermaßen lohnt sich das Ganze aus asymtotischer Sicht nur mit sehr viel mehr LGS als Unbekannten, aber aus praktischer Sicht lohnt es sich schon viel früher.
Gruß, Susi
|
Profil
|
Kleine_Meerjungfrau
Senior
Dabei seit: 29.10.2003
Mitteilungen: 3302
Wohnort: Köln
| Beitrag No.4, vom Themenstarter, eingetragen 2004-03-03
|
Hilfe, was willst du mir damit jetzt sagen???
Mal noch ne kurze Frage nur so für mich als Rückversicherung: Ich hab ein anderes Problem dazu schon heute mittag mit einer Freundin am Telefon diskutiert. Wir wollten den Aufwand bestimmen, wenn man ein LGS löst und sind drauf gekommen, dass man den Aufwand für die LU-Zerlegung und den für die Rückwärtssubstitution addieren müsste. Also: O(m^3)+1/2*m^2. Jetzt hab ich mir aber so im Nachhinein gedacht, dass man das 1/2*m^2 doch eigentlich weglassen kann, weil das in den Rest vom Aufwand der LU-Zerlegung mit rein fällt. Sehe ich das so richtig?
|
Profil
|
Fabi
Senior 
Dabei seit: 03.03.2002
Mitteilungen: 4587
 | Beitrag No.5, eingetragen 2004-03-03
|
Hi!
Es ist sowieso O(m³+1/2*m²) = O(m³), daher ist das erlaubt.
Die 1/2*m² fallen gegen die m³ so wenig ins Gewicht, dass das Wachstum der Funktion nur durch das m³ bestimmt wird, daher schreibt man O(m³). Schau dir am besten auch nochmal eure genauen Definitionen von O(...) an, du scheinst da nicht besonders sicher zu sein.
Was verstehst du eigentlich genau unter einer LU-Zerlegung? Zeilenstufenform?
Gruß
Fabi
|
Profil
|
Buri
Senior 
Dabei seit: 02.08.2003
Mitteilungen: 46890
Wohnort: Dresden
 | Beitrag No.6, eingetragen 2004-03-03
|
Hi Kleine_Meerjungfrau,
bei deinen O(m2) ist wahrscheinlich der durch die Pivotisierung hinzukommende Aufwand gemeint, dazu kommen dann noch die m3 / 3 + O(m2) für die eigentliche Elimination.
Wenn du auf den Faktor (hier 1 / 3) keinen Wert legst (sollte man aber doch tun), dann wird das O(m2) in der Summe O(m3) + O(m2) von dem O(m3) absorbiert, das wurde hier schon gesagt. Wenn du aber den Faktor mit angeben willst, dann mußt du m3 / 3 + O(m2) so stehen lassen.
Wenn man genau zählt, benötigt die Elimination ohne Pivotisierung (m3 - m) / 3 Multiplikationen und ebensoviele Additionen / Subtraktionen und m Divisionen, wenn man (1 Multiplikation + 1 Addition / Subtraktion) als Einheit des Aufwands nimmt, kann man also hierfür auch m3 / 3 + O(m) schreiben.
Bei partieller Pivotisierung kommt hierzu noch O(m2) und bei vollständiger Pivotisierung noch O(m3), hier gibt es allerdings nur Subtraktionen bzw. Größenvergleiche.
Gruß Buri
|
Profil
|
susi0815
Senior
Dabei seit: 20.11.2003
Mitteilungen: 1559
Wohnort: Hannover
| Beitrag No.7, eingetragen 2004-03-03
|
Ja natürlich kannst Du bei der O-Notation dann die O(m^2) weglassen, weil das im O(m^3) eigentlich schon drin ist.
Trotzdem wird es hin und wieder mitgeschrieben um zu kennzeichnen, was noch dazu kommt.
Da sind die Numeriker meist nicht so.
Es könnte ja sein (zumindest in anderen Beispielen), dass für einen Teil mal ein schnellerer Algorithmus gefunden wird, dann muss man die Erbsen nur für diesen Teil neu zählen und kann den Rest übernehmen.
War das jetzt zu lax ?
Gruß, Susi
|
Profil
|
Kleine_Meerjungfrau
Senior
Dabei seit: 29.10.2003
Mitteilungen: 3302
Wohnort: Köln
| Beitrag No.8, vom Themenstarter, eingetragen 2004-03-03
|
Vielen Dank euch allen für eure Antworten!
@Fabi
Wir hatten keine genaue Definition von dem O(...), nicht mal ne ungenaue. Das ist einfach so aufgetaucht und, wie ich schon früher mal mit susis Hilfe festgestellt hab, auch nicht immer eindeutig verwendet worden. Aber du hast schon recht, dass ich da nicht besonders sicher mit umgehen kann. Mein Vorteil scheint allerdings zu sein (einen Vorteil müssen Lehrämtler ja haben  ), dass die Diplomer den Aufwand herleiten können müssen und die Lehrämtler müssen ihn einfach nur so wissen aber nicht herleiten können. 
Also LU-Zerlegung heißt ja, dass man die Matrix in eine obere und untere Dreiecksmatrix bringt. Wenn ich das richtig durchschaut habe (aber Algorithmen lesen war noch nie meine Stärke), dann baut man die Matrix so um, dass am Ende nur noch auf der Diagonalen Werte ungleich 0 stehen.
@Buri
So langsam wird einiges klarer  Also ich glaube, ich lass den Faktor nicht weg, denn wir vergleichen dann im folgenden irgendwann mal LU- und QR-Zerlegung und da unterscheidet sich der Aufwand ja nur durch den Faktor.
@susi
nö, ich glaub, das ist ok so und mit dem Abzählen hab ich eh so meine Probleme, das ändert sich glaub auch nicht mehr. Aber in 4 Wochen werde ich dann hoffentlich sowieso das Thema Numerik für immer hinter mir lassen
So, ich lass den Thread mal noch 1-2 Tage offen, falls mir doch noch was dazu unklar sein sollte.
Viele Grüße
kleine Meerjungfrau
|
Profil
|
Kleine_Meerjungfrau hat die Antworten auf ihre/seine Frage gesehen.
Kleine_Meerjungfrau hat selbst das Ok-Häkchen gesetzt. | | Kleine_Meerjungfrau wird per Mail über neue Antworten informiert. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
