LGS mit Nebenbedingungen an Lösung

OP #3531044
Hi,
Eine Frage an die mathematisch Begabteren hier.

Ich habe ein ziemlich großes überbestimmtes LGS (durchaus mehrere 10000 
Zeilen und mehrere 100 Spalten).
die linke Seite (A) ist konstant und die Rechte ändert sich und ich 
möchte jeweils das bestmögliche (oder wenigstens ein möglichst gutes) b 
berechnen, indem alle elemente >= 0 sind.

Was nehm ich da am besten (programmbibliothekstechnisch)? Und um das 
ganze richtig interessant zu machen, spielt Geschwindigkeit auch noch 
eine Rolle.

für den Fall ohne Nebenbedingungen wäre es ja ziemlich einfach.
Die Pseudoinverse von A berechnen und mit C multiplizieren.
Da A konstant ist, würde sich das Problem auf Vorberechnung von A^-1 und 
auf einfache Matrixmultiplikation zur Laufzeit reduzieren.


Wär toll, wenn es auch für meine Anforderungen so eine relativ schnelle 
Lösung geben würde.
#3531344
Vlad Tepesch schrieb:
> Was nehm ich da am besten (programmbibliothekstechnisch)? Und um das
> ganze richtig interessant zu machen, spielt Geschwindigkeit auch noch
> eine Rolle.
>
> ...
>
> Wär toll, wenn es auch für meine Anforderungen so eine relativ schnelle
> Lösung geben würde.

Wenn's Intel oder AMD ist, die entsprechenden Bibliotheken der 
Hersteller:
http://software.intel.com/en-us/intel-mkl

http://developer.amd.com/tools-and-sdks/cpu-development/amd-core-math-library-acml/
Beides sind die üblichen BLAS- und LAPACK-Implementierungen mit ein paar 
Extras...
OP #3532387
mir gings jetzt weniger darum, auf bestimmte CPUs optimierte 
Bibliotheken zu finden, sondern eher um ein Verfahren, wie man das 
möglichst gut in aufwendig Vorausberechnetes und möglichst einfach zu 
rechnende Laufzeitanteile aufteilt.

Das ist eher der 2. Schritt.
Als erstes weiß ich nicht, wie man das überhaupt mit Nebenbedingungen 
löst. Ich hab was von Lagrange-Multiplikatoren gelesen, aber ehrlich 
gesagt, fehlt mir da ne Ecke zum Verständnis.

Daher wär ich für ein Snippet (basierend auf irgend einer Lib) oder ne 
einfache Erklärung dankbar, wie man die Nebenbedingung in das LSG mit 
reinbekommt.
OP #3532445
M. V. schrieb:
> Meintest du "unterbstimmt"?

mit 100 mal mehr Zeilen als Spalten ist das System stark überbestimmt.

M. V. schrieb:
> Wann ist b "gut"?
b ist gut, wenn der quadratische fehler von
möglichst klein ist.

> Oder soll die Nebenbedingung einfach nur
> Nichtnegativität sein?
genau, dies unter der Bedingung, dass alle Elemente von b>=0 sind.
#3532632
Vlad Tepesch schrieb:
> M. V. schrieb:
>> Meintest du "unterbstimmt"?
>
> mit 100 mal mehr Zeilen als Spalten ist das System stark überbestimmt.
>
> M. V. schrieb:
>> Wann ist b "gut"?
> b ist gut, wenn der quadratische fehler von
>
> möglichst klein ist.

Also eher eine Optimierungsaufgabe...
U.a. Conjugate gradients und diverse andere Verfahren die häufig im 
Bereich des maschinellen Lernens genutzt werden
http://de.wikipedia.org/wiki/CG-Verfahren

Subgradientenverfahren und (orthogonale) Projektion
http://en.wikipedia.org/wiki/Subgradient_method

Gradient Descent with constraints
http://math.stackexchange.com/questions/54855/gradient-descent-with-constraints

LU-Dekomposition
http://en.wikipedia.org/wiki/LU_decomposition

SVD Singular Value Decomposition (zur Berechnung der Pseudoinversen)
http://en.wikipedia.org/wiki/Singular_value_decomposition
OP #3532731
hmm das hilft mir nicht wirklich weiter.

CG, LU und SVD sind ja zur Lösung des LGS. Aber wie ich die 
Nebenbedingungen da berücksichtigen soll versteh ich ja gerade nicht.

die anderen Verfahren beziehen sich ja, soweit ich sie überhaupt 
verstehe auf Funktionen. Ich hab ja hier aber ein Gleichungssystem, bzw 
eine Funktion mit hunderten x und y werten.
Gast #3533012
Wär es eventuell eine Option zuerst die Lösung zu berechnen, welche den 
quadratischen Fehler minimiert (mit QR-Zerlegung oder SVD, Lösung der 
Fehlergleichung ist numerisch schlecht konditioniert) und anschliessend 
alle negativen Einträge in b einfach auf Null zu setzen? Ich habe leider 
keine Ahnung ob die so erhaltene Lösung den Fehler minimiert.

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 12 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.