Gleichungssystem lösen für Matrix mit vielen Nullen

Neue Frage »

Anna91 Auf diesen Beitrag antworten »
Gleichungssystem lösen für Matrix mit vielen Nullen
Wir haben uns in der Vorlesung mit dem Lösen von Gleichungssystemen befasst. Nun ist mir bei einer Frage jedoch überhaupt nicht klar, auf welches Verfahren es hinauslaufen soll, wenn eine Matrix habe, in der viele Einträge 0 sind.

Wir hatten:
Gaußverfahren, LR, QR- und Cholesky-Zerlegung, Verfahren zur Nullstellenberechnung (Newton, Sekanten, Bisektion), Jacobi- und Gauß-Seidelverfahren.

Kann mir jemand helfen?

Ich würde in Richtung iterativ denken bzw. bei der Cholesky-Zerlegung könnte das auch noch sinnvoll sein.
wopi Auf diesen Beitrag antworten »
RE: Gleichungssystem lösen für Matrix mit vielen Nullen
Bei sehr vielen Nullen in der Koeffizientenmatrix eines LGS kannst du durch Zeilen- und Spaltenvertauschungen beim Gauß-Verfahren sehr schnell zur Dreiecksmatrix kommen und so schnell die allgemeine Lösung finden.
Anna91 Auf diesen Beitrag antworten »

Danke für eine Antwort! Ich hab nun in einem Skript folgende Bemerkung gefunden:
Zitat:
Bei großen schwach besetzten Matrizen führen dei auf Dreieckszerlegung basierenden Verfahren (Gaußscher Algorithmus, Householder-oRthogonalisierung) zu großen Rechenzeiten (obwohl meist nur Nullen multipliziert oder addiert werden) und evtl. auch zu Speicherplatzproblemen (da die entstehenden Dreiecksmatrizen häufig "voll besetzt" sind). Zum Beispiel benötigt der Gaußsche Algorithmus \frac{m^3}{3}+O(m^2) Operationen. Steht nun ein Computer mit Operationen pro Sekunde zu Verfügung, so führt dieser etwa Operationen im Jahr aus. Es es ergeben sich folgende (hohe) Rechenzeiten bei variierendem m: (da bin ich nun nicht in der Lage die Tabelle abzutippen, aber als Beispiel) für sind das \frac{1}{3}*10^{17-x} Sekunden Rechnenzeit!

Ausweg: Iterative Verfahren, die pro Schritt nur eine Multiplikation von Matrix und Vektor erfordern, also etwa Operationen


Also war ich dann doch wohl auf dem richtigen Tripp Freude
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »