Brauche Hilfe bei linearem Gleichungssystem

[BAGZZlash]

Hi, Mathefreaks!

Ich bräuchte mal Hilfe bei einem Problem, das ich hier (http://matheraum.de/read?t=468469) beschrieben habe. Hat da jemand 'ne Idee?

Gruß
BAGZZlash

[pest]

Damit ist das Gleichungssystem unterbestimmt und nicht lösbar


das GLS ist auch unterbestimmt lösbar, mit Hilfe von freien Variablen.
Lösungsraum bestimmen und nach der Nebenbedingung auflösen, gesetzt den Fall das GLS wurde richtig aufgestellt.

[BAGZZlash]

das GLS ist auch unterbestimmt lösbar, mit Hilfe von freien Variablen.
Lösungsraum bestimmen und nach der Nebenbedingung auflösen, gesetzt den Fall das GLS wurde richtig aufgestellt.

Hi!

Okay, danke. Hm, kannst Du genauer erklären, wie das gemacht wird? Alternativ: Mit der letzten Gleichung ist's ja "auch so" lösbar. Vielleicht stelle ich nochmal den Hinweis in den Vordergrund, den ich hingeschrieben hatte: Die yi sind alle entweder -1 oder 1. Damit hat Summe aiyi = 0 (wenn man mal ai als "Alpha i" durchgehen lässt :smile:) eine ziemlich einfache Struktur, nämlich beispielsweise so: a1y1 + a2y2 - a3y3 + a4y4 mit y1 = 1, y2 = 1, y3 = -1 und y4 = 1 (wie gesagt, nur ein Beispiel). a1 + a2 - a3 + a4 = 0 <=> a1 = a2 - a3 + a4. Hilft das weiter?

Danke und Gruß
BAGZZlash

[pest]

Hi!

Okay, danke. Hm, kannst Du genauer erklären, wie das gemacht wird?


also z.B.

a + 3b = 2 NB: a+b=1


a = 2 - 3b

Lösungsraum (1 freie Variable):

L = {(a,b)^T: (2-3b,1)^T,b aus R} (besitzt unendlich viele Lösungen)

Nebenbedingung einarbeiten:

2-3b + b = 1
-2b = -1

=> b = 1/2
=> a = 1/2

natürlich könnte man diese Variante in ein GLS packen, aber der Sinn wird klar




Alternativ: Mit der letzten Gleichung ist's ja "auch so" lösbar. Vielleicht stelle ich nochmal den Hinweis in den Vordergrund, den ich hingeschrieben hatte: Die yi sind alle entweder -1 oder 1. Damit hat Summe aiyi = 0 (wenn man mal ai als "Alpha i" durchgehen lässt :smile:) eine ziemlich einfache Struktur, nämlich beispielsweise so: a1y1 + a2y2 - a3y3 + a4y4 mit y1 = 1, y2 = 1, y3 = -1 und y4 = 1 (wie gesagt, nur ein Beispiel). a1 + a2 - a3 + a4 = 0 <=> a1 = a2 - a3 + a4. Hilft das weiter?



Meinem derzeitigen Geisteszustand nicht ;)

du löst das GLS einfach als wären die Lambda Zahlen (mit Mathematica z.b. wenn n > 4)
aus dem Lösungsraum und deiner angegebenen Summe berechnest du Lambda, und dann "rückwärts" die ai


ah ein Geistesblitz :D

du erweiterst Z um eine Zeile in der die yi stehen und b um eine Zeile in der 0 steht...
so wie oben geht es natürlich auch, das macht handschriftlich aber auch nicht unbedingt Spass ;)
was du bevorzugst liegt an deiner persönlichen Neigung, ich mache es gern wie oben, obwohl es auf den ersten Blick komplizierter aussieht

[BAGZZlash]

also z.B.





Meinem derzeitigen Geisteszustand nicht ;)

du löst das GLS einfach als wären die Lambda Zahlen (mit Mathematica z.b. wenn n > 4)
aus dem Lösungsraum und deiner angegebenen Summe berechnest du Lambda, und dann "rückwärts" die ai


ah ein Geistesblitz :D

du erweiterst Z um eine Zeile in der die yi stehen und b um eine Zeile in der 0 steht...
so wie oben geht es natürlich auch, das macht handschriftlich aber auch nicht unbedingt Spass ;)
was du bevorzugst liegt an deiner persönlichen Neigung, ich mache es gern wie oben, obwohl es auf den ersten Blick komplizierter aussieht

Hi!

Okay, tausend Dank!! (y) Damit versuche ich mal, weiterzukommen. Handschriftlich gut aussehen muss das nicht, ich versuche nämlich, damit einen Algo zu coden. Mal sehen, ob ich irgendwann am Ziel ankomme... :rolleyes:

Nochmal danke :smile:
BAGZZlash

[pest]

ich versuche nämlich, damit einen Algo zu coden. Mal sehen, ob ich irgendwann am Ziel ankomme...

achso, für diese spezielle Aufgabe und zum Programmieren ist letztere Variante
natürlich besser geeignet, sie funktioniert nur nicht immer,
z.b. wenn es mehrere Lambda gäbe und deren Summe eine Bedingung erfüllt

so musst du einfach "nur" den Gauss-Algorithmus implementieren.
Da gibt es (einfache) Erweiterungen bei denen auch eine gute numerische Stabilität gewährleistet wird.

was brauchst du denn?
ich habe hier ne C++-Klasse die genau das leistet, du müsstest nur noch die Berechnung der b-Spalte anpassen um an das Lambda zu kommen

[BAGZZlash]

achso, für diese spezielle Aufgabe und zum Programmieren ist letztere Variante
natürlich besser geeignet, sie funktioniert nur nicht immer,
z.b. wenn es mehrere Lambda gäbe und deren Summe eine Bedingung erfüllt

so musst du einfach "nur" den Gauss-Algorithmus implementieren.
Da gibt es (einfache) Erweiterungen bei denen auch eine gute numerische Stabilität gewährleistet wird.

was brauchst du denn?
ich habe hier ne C++-Klasse die genau das leistet, du müsstest nur noch die Berechnung der b-Spalte anpassen um an das Lambda zu kommen


Hi!

Danke, aber ich code in VB6. Mal sehen, in wie weit ich den eigentlichen Algo zum Lösen selbst implementiere, dafür gibt's schon schöne Samples im Internet. Ich muss das Problem eben nur in eine Form bringen, die sich automatisiert lösen lässt. Ziel ist eigentlich, ein Programm zum Aufstellen von Support Vector Machines (http://de.wikipedia.org/wiki/Support_Vector_Machine) zu basteln. Auch da gibt es zwar tolle fertig implementierte Lösungen, aber so ganz richtig verstehen tut man es eben doch nur, wenn man sich selbst mit genau solchen Problemen wie hier 'rumschlägt, sozusagen auf dem Weg von der Idee zur Lösung.

Gauss kann ich auf jeden Fall nehmen. Numerische Stabilität ist nicht sooo entscheidend, das Ganze wird später sowieso auf stochastische Modelle angewendet, da kommt's auf die fünfte Nachkommastelle nicht so an... :smile:

Ich halte Dich auf jeden Fall auf dem Laufenden.

Nochmal vielen Dank
BAGZZlash

[pest]

wenn du magst kannst du mir ja mal Daten für n=4 od. 5 geben
also A und alle yi (oder gibt es für die yi auch eine Bildungsvorschrift?)
und ich code es mal quick&dirty

[BAGZZlash]

wenn du magst kannst du mir ja mal Daten für n=4 od. 5 geben
also A und alle yi (oder gibt es für die yi auch eine Bildungsvorschrift?)
und ich code es mal quick&dirty

Hi!

Klar, sehr gerne!

Also:


Z = 10 6 7 -22 -21
6 10 13 -18 -23
7 13 5 -24 -29
-22 -18 -24 52 54
-21 -23 -29 54 61


und


y = (1 1 1 -1 -1)T


Wie gesagt, bestimme alphai für alle i und lambda. Nebenbedingung: Summe alphai x yi = 0.

Bonusfrage: Gibt es eine eindeutige Lösung? Falls nicht, gibt es eine Lösung, für die gilt alphai >= 0 für alle i?

Tausend Dank. Wenn Du mal nach Köln kommst, geb' ich Dir 'n paar Kölsch aus. :smile:

Danke und Gruß
BAGZZlash

[pest]

hey ich habe deinen Thread total vergessen, programmiert habe ich noch nix, weil ich Selbst noch an einem Programm der Lin.Opt. arbeite, da kann ich aber ein paar Sachen weiterverwenden.

Ich habe dein Beispielproblem trotzdem mal mit Mathematica durchgerechnet um meine Idee auszuprobieren. Das hat einwandfrei funktioniert :)
die Lösung ist hier eindeutig

http://www.abload.de/img/mathematicabaggd2aa.png

[pest]

ich seh grad das du auf deine Frage in dem anderen Forum auch ne Antwort bekommen hast, und das ist noch besser als meins :(
das hat mir nen Kommilitone zwar auch geraten aber ich habe da einfach unreflektiert gegenargumentiert ohne es aufzuschreiben :D

jetzt brauchst du nur noch den Gauss, und ich muss nix mehr coden ;)

http://www.abload.de/img/mathematicabagg267zx.png

also sorry, falls ich dich verwirrt hab', an meinen antworten war nix falsch, ich hab nur nicht zuende gedacht

[BAGZZlash]

Hi!

Vielen Dank! In's andere Forum hätte ich schon gar nicht mehr geschaut, wenn Du es nicht gesagt hättest.
Tausend Dank nochmal! :smile:

Viele Grüße
BAGZZlash

[BAGZZlash]

Hi!

Nochmal danke für die Antwort! Das Ganze klappt wunderbar. :smile: Allerdings: Falls die Parameterkonstellation so ist, dass einige alphas < 0 sind, wird das Problem zwar natürlich trotzdem richtig gelöst, allerdings ist eine solche Lösung für mich ungültig. Ich müsste vorgeben können, dass alphai >= 0 für alle i. Geht das auch noch oder ist Gauss hier nun definitiv mit seinem Latein am Ende?

Danke und Gruß
BAGZZlash

[Pinoccio]

Gauss kann ich auf jeden Fall nehmen. Numerische Stabilität ist nicht sooo entscheidend, das Ganze wird später sowieso auf stochastische Modelle angewendet, da kommt's auf die fünfte Nachkommastelle nicht so an... :smile:Unterschätze mal die Anfälligkeit von Gauß nicht!

Mit
-46 -67 5
A = -61 -60 81
33 32 -45
und b=(108, 40, -20) ist die exakte Lösung von Ax=b gleich x=(-1,-1,-1). Wenn bei dir viel anderes rauskommt, ist dein Algo zu anfällig.

mfg

[BAGZZlash]

[...] ist die exakte Lösung von Ax=b gleich x=(-1,-1,-1). Wenn bei dir viel anderes rauskommt, ist dein Algo zu anfällig.


Kommt bei mir 'raus. Doubles sind also wohl genau genug. Aber erstens ist das hier nicht das diskutierte Problem und zweitens ist meine A-Matrix symmetrisch, was noch ein Bißchen numerische Stabilität mitbringen würde. Dennoch danke für den Einwand. Es gibt da ja noch schöne Spielereien wie Cholesky-Faktorisierung und so Scherze.
Es bleibt dabei: Was ist, wenn ich fordere, dass alle alphas >= 0?

[pest]

Unterschätze mal die Anfälligkeit von Gauß nicht!


mit der richtigen Pivotstrategie und z.B. Preprocessing der Matrix kann man da schon viel Luft rausnehmen, wobei ich den Schwerpunkt eher auf Ersterem sehe.

Geht das auch noch oder ist Gauss hier nun definitiv mit seinem Latein am Ende?


dumme Frage, aber warum verwirfst du die Lösung dann nicht?
Schließlich wird nur eine exakte Lösung berechnet.

Das alle ai noch zusätzlich > 0 sind, kann man auch mit dem Gauss erreichen, lässt sich aber nicht mehr in das GLS packen.

Ich erinnere mich dunkel, das beim minimierenden Basistausch des Simplexalgorithmus (der auf dem Gauss aufbaut) auch Lösungen des GLS enstehen.
Prob ist aber, das das Ganze auf Ungleichungen aufbaut und du Schnittmengen von Hyperebenen betrachtest.

Du müsstest also dein Problem abändern oder es einfach so machen, wie ich vorgeschlagen habe, oder du wartest bis ich mal wieder einen Geistesblitz habe :wink:

[pest]

Es gibt da ja noch schöne Spielereien wie Cholesky-Faktorisierung und so Scherze.


Cholesky funktioniert nur bei pos. def. Matrizen

[BAGZZlash]

Hi!

Angenommen, ich mache folgendes:

Nehmen wir an, ich habe, sagen wir, 5 alphas. Ich berechne wie beschrieben "Ax = b", wobei x der Vektor mit den alphas und dem Lambda ist und A die erweiterte Matrix, bei der der letzte Zeilen- und Spaltenvektor die yi wie beschrieben enthält. Also:

x = (
alpha1;
alpha2;
alpha3;
alpha4;
alpha5;
lambda).

Nun berechne ich das Ganze. Sagen wir, es kommt 'raus:

alpha1 = 2;
alpha2 = 3;
alpha3 = -5;
alpha4 = 6;
alpha5 = -1;
lambda = 4.

Also: alpha3; alpha5 < 0. Dann ändere ich den x-Vektor so ab:

x = (
alpha1;
alpha2;
0;
alpha4;
0;
lambda).

Dieses GLS rechne ich wieder aus. Kommt dabei 'ne (vernünftige) Lösung 'raus?

Gruß
BAGZZlash

[pest]

Dann ändere ich den x-Vektor so ab:

x = (
alpha1;
alpha2;
0;
alpha4;
0;
lambda).

Dieses GLS rechne ich wieder aus. Kommt dabei 'ne (vernünftige) Lösung 'raus?


wie (nochmal) ausrechen? A*x? dann hast du ein Neues b

Auf jeden Fall ist dieser Lösungsvektor, keine Lösung zu deinem ursprünglichen GLS.
Wenn die Matrix keine lin. abhängigen Zeilen/Spalten besitzt, gibt es nur 1 Lösung.