LGS mit Nebenbedingungen an Lösung

[Vlad T. (vlad_tepesch)]

Hi,
Eine Frage an die mathematisch Begabteren hier.

Ich habe ein ziemlich großes überbestimmtes LGS (durchaus mehrere 10000 
Zeilen und mehrere 100 Spalten).

$$\mathbf{A} \cdot b = \mathbf{C}$$

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.

[Arc N. (arc)]

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...

[Vlad T. (vlad_tepesch)]

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.

[M. V. (-_-)]

Vlad Tepesch schrieb:
> überbestimmtes LGS

Meintest du "unterbstimmt"?

> möchte jeweils das bestmögliche (oder wenigstens ein möglichst gutes) b
> berechnen, indem alle elemente >= 0 sind.

Wann ist b "gut"? Oder soll die Nebenbedingung einfach nur 
Nichtnegativität sein?

[Vlad T. (vlad_tepesch)]

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

$$\mathbf{A} \cdot b = \mathbf{C}$$

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.

[Arc N. (arc)]

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
>

$$> \mathbf{A} \cdot b = \mathbf{C} >$$

> 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

[Vlad T. (vlad_tepesch)]

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.

[ich (Gast)]

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.

[Johann L. (gjlayde)]

Zur Bestimmung einer Lösung mit kleinstem quadratischen Fehler löst man

$$A^tAb=A^tc$$

anstatt

$$Ab=c$$

Anschaulich würde ich dann in Richtung der kleinsten Fehlers gehen, d.h. 
in den Transversalraum der orthogonal zum Gradienten ist, und den 
nächsten Punkt suchen, bei dem alle Komponenten >= 0 sind.