Suche geeignetes Lösungsverfahren linearer Gleichungssysteme

Neue Frage »

Bebbo Auf diesen Beitrag antworten »
Suche geeignetes Lösungsverfahren linearer Gleichungssysteme
Hallo Forum.
Ich habe nun die 11. Klasse abgeschlossen und begebe mich nun im Rahmen einer Besonderen Lernleistung auf die Suche nach einem schnellen geeignetem Lösungsverfahren für lineare Gleichungssysteme:

Ax = b

Dabei trifft für die Matrix A folgendes zu:
Alle Elemente sind entweder 0 oder 1. Das bedeutet (wenn ich mich richtig informiert habe) dass so ziemlich alle Splitting-Verfahren wie z.B. das Gauß-Seidel-Verfahren nicht anwendbar sind, da es unwahrscheinlich ist, dass die Hauptdiagnonale keine Null enthält.
Zusätzlich ist die Matrix in keiner Form symmetrisch. Eine quadratische Form lässt sich zwar herstellen, ist aber ungünstig.

Ich hab mich bei Wikipedia ein bisschen belesen und glaube dass ich so gut wie alle iterativen Verfahren auf Grund der gegebenen Bedinungen ausschließen kann, ebenso die Cholesky-Zerlegung. Die QR-Zerlegung fällt weg, da dort bereits steht, dass sie zu langsam ist.

Mir geht es im wesentlichen um die Programmierung eines solchen Lösungsverfahrens und dieses soll zunächst einmal mathematisch effizient gestaltet sein. Was ich jetzt noch habe ist das Gaußsche Eliminationsverfahren bzw. die LR-Zerlegung... Kennt ihr noch schnellere Verfahren oder Tricks für dieses Problem?
tigerbine Auf diesen Beitrag antworten »
RE: Suche geeignetes Lösungsverfahren linearer Gleichungssysteme
Rückfrage

Welche Abmessung hat die Matrix? m=?, n=?

wird sie zufällig erzeugt, also so dass man vorher nur weiß .

Die einzelnen Einträge sind aber unabhängig erzeugt?
Bebbo Auf diesen Beitrag antworten »

Ja, die Abmessungen der Matrix sind unbekannt und abhängig von praktischen Parametern... Ich könnte die Matrix wie gesagt zwar in eine Quadratische Form bringen, aber das wäre mit großen Verlusten bei der Umsetzung des gesamten Problems verbunden...
Fest steht, dass die Matrix enorm große Ausmaße hat, sowohl zeilen-, als auch spaltenmäßig. Deswegen ist ein schnelles Verfahren von großer Bedeutung.
Die einzelnen Einträge entsprechen im praktischen Fall pseudozufällig erzeugten Werten zur Kodierung. In diesem Sinne kann man sagen, dass sie voneinander zufällig erzeugt und auch relativ gleichmäßig verteilt sind...
tigerbine Auf diesen Beitrag antworten »

Rückfrage 2

Welches LGS soll dann gelöst werden? Homogen /Inhomogen / unbekannt
swerbe Auf diesen Beitrag antworten »

Natürlich gibt es häufig einen eleganten Weg. Ohne zusätzliche Informationen würde ich als "Holzhammer-Methode" einen direkten Löser, wie die LR-Zerlegung ansetzen und später nachiterieren, z.B. mit dem cg-Verfahren.

Der Nachteil ist natürlich, das eine simple LR-Zerlegung nicht immer existiert bzw. zusätzlich zu speichernde Permutationsmatrizen benötigt werden.
Eine Erweiterung der LR-Zerlegung ist das Thomas-Verfahren, dies setzt aber eine Tridiagonalisierung der Koeffizientenmatrix voraus, ist aber sehr schnell.

Einen Königsweg zwischen "Schnelligkeit" und "Approximationsgüte" ist i.d.R. aber schwierig zu finden...
swerbe Auf diesen Beitrag antworten »

ohh, kann meinen Beitrag durch das gerade eben erst gelesene erweitern:

Bei dünnbesetzen Matrizen würde ich fast immer auf iterative Verfahren (mit Vorkonditionierung) setzen. Direkte produzieren i.d.R. viele nicht-null-Elemente an den Stellen, wo vorher Nullen standen.
 
 
Bebbo Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Rückfrage 2

Welches LGS soll dann gelöst werden? Homogen /Inhomogen / unbekannt


Ich denke, das LGS ist mit größter Wahrscheinlichkeit nach Inhomogen, zumal der b-Vektor ebenso zufällig aus Nullen und Einsen als Elementen besteht.

@swerbe
Ich werde mich bezüglich deiner vorgeschlagenen Verfahren gleich mal informieren! Nur verstehe ich nicht, wie ich iterative Verfahren anwenden kann, da diese Verfahren doch meistens eine Division(meinem Fall durch 0) vorraussetzen....
tigerbine Auf diesen Beitrag antworten »

Ok, dann sieht es formal also so aus:




D.h. es kann gelten:

  • m < n

  • m= n

  • m > n




@ swerbe:

Alle von Dir bislang angesprochenen Verfahren sind aber doch für quadratische (reguläre) Matrizen, oder? verwirrt
Bebbo Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine

[...]

D.h. es kann gelten:

  • m < n

  • m= n

  • m > n






Also die Grafik stimmt genau, bei den Bedingungen habe ich vergessen zu erwähnen, dass als Bedinung gilt:
  • m = n
    oder
  • m < n



m > n darf nicht gelten...
swerbe Auf diesen Beitrag antworten »

@tigerbine: Du hast natürlich absolut recht. Ich sollte mir langsam mal angewöhnen, die Beiträger genauer zu lesen Augenzwinkern

Das cg-Verfahren benötigt natürlich eine positiv definite Matrix (natürlich quadratisch). Ohne die EW der Matrix zu kennen, ist die positive definitheit natürlich schwer nachzuweisen Augenzwinkern

Das LR-Verfahren benötigt ebenfalls eine quadr. (reguläre) Matrix, ebenso QR, Cholesky, diverse iterative Löser.


Mmmhhh bei dem Fall m>n könnte man vielleicht noch eine diskrete L_2 -Approximation (Ausgleichsrechnung) versuchen, dieser scheint hier aber nicht verlangt zu sein.

Für unterbestimmte LGS fällt mir spontan keine "schöne" numerische Methode ein, sorry.

Ist es vielleicht möglich, die entsprechende Matrix, falls sie nicht quadratisch ist, quadratisch zu erweitern (durch hinzufügen(!) von Spalten/Zeilen) ohne die Konditionalität und den Lösungsraum zu verändern?
Vielleicht weiß tigerbine hier bescheid??
Bebbo Auf diesen Beitrag antworten »

@swerbe
Ja, die Idee mit dem Ergänzen hatte ich auch, diese bringt wie gesagt noch ein paar Probleme mit sich...
Ich versuche euch einmal das Problem etwas näher zu erläutern...

Es gibt einen sogenannten Nachrichtenvektor m der Länge q.
Zusätzlich eine Kodierungsmatrix D mit q Zeilen und n Spalten.
Und letztlich einen "Träger"-Vektor b der Länge n. (das entspricht im praktischen Fall der Anzahl aller LSBs der Pixel eines JPEG-Bildes)

Es werden nun sogenannte defekte Stellen (nicht änderbare Pixel) ermittelt und bestimmte Elemente aus b gestrichen. So z.B. b2 und b5.

Man nehme nun die Matrix D und streiche alle zu den aus Vektor b defekten Stellen korrespondierenden Spalten und erhält die Matrix H. Laut obigen Beispiel wird die 2. und 5. Spalte aus der Matrix D weggenommen und man erhält H.

Anschließend gilt es die folgende Gleichung nach dem Vektor v aufzulösen:

H*v = m - D * b

(Die Länge des Vektors v entspricht natürlich der Spaltenzahl der Matrix H, er gibt später zu ändernde LSB's der Pixel an).

Nun kann ich besser das Problem beschreiben, was passiert, wenn ich die Vektoren zu quadratischen Matrizen mache... Alles fängt bei der Nachrichtenmatrix m an, dementsprechend muss später b dieselbe Spaltenanzahl von m haben. Angenommen ich zerteile den Vektor einfach in Spalten und fülle den Rest auf, bis dahin ist alles kein Problem.
Aber wenn ich die defekten Stellen streiche, muss ich automatisch die ganze Zeile aus dem Vektor b streichen, da ja auch die ganze dazugehörige Spalte aus D gestrichen wird um H zu erzeugen. Im Endeffet dezimiert sich im praktischen Fall die Spaltenzahl von H mit steigender Spaltenanzahl von b, welche ja wiederum von der Spaltenzahl von m abhängt...
Am Schluss stehen zwar quadratische Matrizen aber leider eine viel zu "kleine" Matrix H. Wenn diese zu wenig Spalten hat, ist das Gleichungssystem unterbestimmt und nicht mehr lösbar.

Tut mir Leid, wenn es nicht ganz anschaulich beschrieben wurde, ich wollte damit nur sagen, dass quadratische Matrizen eine absolute Notlösung mit einem nicht vollständig zufriedenstellendem Ergebnis sind...
tigerbine Auf diesen Beitrag antworten »

Zitat:
Original von Bebbo
... bei den Bedingungen habe ich vergessen zu erwähnen, dass als Bedinung gilt:
  • m = n
    oder
  • m < n


m > n darf nicht gelten...



Aber das sind ganz entscheidende Bedingungen. "Mathe Klassik" wäre m=n, am besten noch regulär Big Laugh

Mit m > n, Rang (A)=n wären wir dann im Bereich lineare Ausgleichsprobleme.


Bei Dir liegt der Fall aber nun anders. Mit m < n haben wir mehr Unbekannte als
Bedingungen. Wir können die Matrix ohne großen Aufwand Quadratisch machen (Nullzeilen).

Es liegt also im Grunde der Fall einer Quadratischen singulären Matrix vor, denn selbst im Falle m=n muss der Rang ja nicht voll sein.


Was für Lösungen können wir erwarten?

Diese Fallunterscheidung überlasse ich einmal Bebbo als Übung. Hilfe findet sich sich hier.:


Welches Verfahren ist optimal?

Alle Verfahren die mir ad-hoc einfallen, zielen aber auf die beiden vorherigen Fälle (regulär oder überbestimmt) ab. Für singulär muss ich erst mal nachschlagen. Augenzwinkern


@Bebbo,

es ist mir nun zuspät mich in die "pixel" einzulesen. Vielleicht, da ja wohl meine Darstellung Ax=b von oben passt, schreibst Du gerade die Substitutionen hin, wie das mit H,v und so zusammenhängt.

Denn wie ich hier schrieb, ist dein System unterbestimmt, auch ohne dass man versucht, quadratische Matrizen zu machen.

@ swerbe:

Für positiv definit würde man wohl (wenn man der Literatur Glauben schenken darf) mit dem Cholesky Algorithmus (Durchführbarkeit) testen.

Wohl meint, dass ich nicht aus der praktischen Informatik komme und direkt am Puls des Geschehens sitze Augenzwinkern


Gute Nacht, vielleicht bis morgen Schläfer
Bebbo Auf diesen Beitrag antworten »

Guten Morgen smile

Ich versuche gleich einmal das ganze mathematisch nochmal am Beispiel darzustellen:

Es gibt einen Vektor m, z.B.

  • mit q Zeilen (3)


Und eine Matrix D...

  • mit q Zeilen (3)
  • und n Spalten (5)


Und einen Vektor b, z.B.

  • mit n Zeilen (5)


Aus b werden x Elemente ( x > 0 ) gesucht, die "weggestrichen werden". Dabei wird der Vektor b nie kürzer werden als der Vektor m. (sonst: Abbruchbedinung erfüllt)

Angenommen die Stelle b3 soll später einmal weggestrichen werden.
Der Vektor b' sähe nun so aus:



(vom Vektor b' wird hier mathematisch kein Gebrauch gemacht, er dient nur zur Veranschaulichung)

Man nehme nun D und streiche alle korrespondierenden Spalten heraus und man erhält die Matrix H. Es werden also aus D alle Spalten gestrichen, die bei einer Multiplikation mit der defekten Stelle aus b' in Berührung kommen würden. In dem Fall sieht die neue Matrix H so aus:


  • mit q Zeilen (3)
  • und p Spalten (4), wobei p < n (p = n - x)


Anschließend wird folgendes Gleichungssystem aufgestellt:

H * v = m - D * b

Davon ist v ein unbekannter Vektor mit p Zeilen. Im Beispiel sieht die Gleichung so aus:



Natürlich wird ersteinmal die rechte Seite zusammengefasst:



Bei der Rechnung ist zu beachten, dass nach jeder Operation modulo 2 gerechnet wird und der Betrag genommen wird. Also gilt z.B. 1 + 1 = 0 und 0 - 1 = 1
Ich glaub sowas kann man auch in Form von mathematischen Körpern definieren, davon habe ich aber eher weniger Ahnung. Jedenfalls gibt es hier kein multiplikatives Inverses zum Element 0, deswegen kann man ja nicht teilen und somit keine besonderen Verfahren anwenden.

Das Gleichungssystem hat nun die Form: Ax = b
Wenn ich mich nicht ganz irre, ist das Gleichungssystem jetzt unterbestimmt, da ja der Vektor b auf der rechten Seite zu kurz ist (Das wolltest du mir ja klar machen, jetzt hab ichs begriffen smile ) . Das Problem sei mal damit gelöst, dass man b beliebig auffüllen kann, bis b genau p Zeilen hat:



Damit existiert entweder genau eine Lösung oder mehrere Lösungen richtig? Im Prinzip ist die Zahl der Lösungen egal, sofern überhaupt welche existieren, da dann einfach irgendeine günstige ausgewählt wird.
tigerbine Auf diesen Beitrag antworten »

Bevor ich das nun alles Lese, etwas zur Modulo Rechnung. 2 ist eine Primzahl, daher ist ein (Restklassen)körper.

http://de.wikipedia.org/wiki/Restklassenk%C3%B6rper

Was ist denn ein endlicher Körper? Hier findest du auch den gesuchten.

http://de.wikipedia.org/wiki/Endlicher_K%C3%B6rper


Zitat:



Das geht nicht. Die Rechte Seite ist zu "lang"


Zitat:



Das ist ok. Das Problem mit der Eindeutigkeit ist die "Höhe" der Matrix H. Oder besser gesagt, die Anzahl lin. unabhängiger Zeilen, d.h. auch durch auffüllen mit 0 Zeilen ändern wir an dem Problem nichts.

Es können für (m < n) 2 Fälle auftreten: Keine Lösung, unendlich viele Lösungen.

"Irgendeine günstige", was soll das bedeuten?
Bebbo Auf diesen Beitrag antworten »

Ah, danke für schnelle Auskunft über die Körper!

Mir ist da ein Fehler passiert. Es soll nämlich gleich am Anfang "aufgefüllt" werden, beim Vektor m. Das heißt ich besetze den Vektor m mit p Zeilen, sodass die Matrix H später auch p Zeilen besitzt. Das Gleichungssystem sieht dann am Schluss so aus:



Dann wäre es doch eindeutig lösbar, oder?

Die günstige Lösung bezieht sich wiederum auf die Praxis. Es wird die Lösung für v ausgewählt, für die der Vektor die wenigsten Einsen besitzt. Das hat den Hintergrund, das der Vektor angibt, welche Stellen in dem Bild geändert werden müssen, damit die Nachricht m eingebettet werden kann.
tigerbine Auf diesen Beitrag antworten »

Günstigste Lösung. Ok, ich wollte nur wissen, ob da ein Kriterium vorhanden ist.

So ganz hast Du das aber mit den LGS nicht verstanden, oder? Auch wenn wir nun eine quadratische Matrix haben, ist diese i.A: nicht regulär (besitzt vollen Rang). Nur in diesem Fall besitzt das LGS für jeden Vektor b eine eindeutige Lösung.

Bei singulär kann es passieren, dass wir unendlich viele oder eben keine Lösung haben.

Da deine Matrix zufällig ist, wissen wir nicht ob sie regulär oder singulär ist. Von irgendwelchen Symmetrien oder positiv Definit wollen wir gar nicht reden.

auch können wir so nicht annehmen, dass die Matrix dünnbesetzt ist, was uns aber auch nur bei einer Bandgestalt einen Vorteil bringen würde.


Von Hand kann man diese LGS aber auch mit dem Gauss Algorithmus Lösen. man führt ihn bis zum Abbruch durch. Dann sollte der obere Teil der Matrix Treppengestalt haben und dann nur noch Nullzeilen Folgen. Befindet sich im Vektor b im unteren Block ien von 0 verschiedener Eintrag, so ist das LGS nicht lösbar. Ansonsten können diese Eintrage von x Frei gewählt werden, Du wolltest einen Lösungsvektor mit möglichst viel Nullen, also wähle sie alle Null? verwirrt

So müßten wir doch zumindest einmal einen Lauffähigen Algorithmus bekommen. Des weiteren treten in der Matrix nur ganze Zahlen auf. Man müßte sich nun einmal schlau machen, wie man Rechnung in Primkörpen programmiert. Worin schriebst Du das Programm denn?
Bebbo Auf diesen Beitrag antworten »

Achso, ich hatte nicht bedacht, dass es ja auch bei vielen gegebenen Gleichungen möglich ist, dass keine eindeutige Lösung bestimmbar ist. Manche Zeilen können ja aus anderen durch Vervielfachung auseinander hervorgehen.

Ich schreibe das Programm in C als Erweiterung für Entwicklungsumgebung R. Die Programmierung an sich ist weniger das Problem, nur wollte ich erst wissen ob es noch etwas schnelleres als die Gaus-Elimination gibt...
tigerbine Auf diesen Beitrag antworten »

Da die Matrix wohl singulär sein wird, weiß ich es nicht, ob es was schnelleres gibt. Man könnte jetzt erstmal, im Pseudocode das Verfahren mit Gauss aufschreiben.

Dann eine "Laufzeitanalyse" bzgl. Des Rangs von H verwirrt zumindest hätte man dann ein Verfahren, welches läuft und eine Zahl die es zu "schlagen" gilt.

Leider habe ich in meinen Unterlage nichts zum Thema "Algorithmen zur Lösung singulärer LGS".

Gruß Wink
Bebbo Auf diesen Beitrag antworten »

Nagut ich werde einfach mal ein bisschen was dazu versuchen. Ich melde mich einfach falls ich was erreicht habe und/oder mir nochmal neue Fragen begegnen!
tigerbine Auf diesen Beitrag antworten »

Ja, meld Dich einfach wieder. Oder schau vorbei. Vielleicht weiß ja jemand anderes noch etwas mehr Wink
bebbo Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Ja, meld Dich einfach wieder. Oder schau vorbei. Vielleicht weiß ja jemand anderes noch etwas mehr Wink


Apropos, weil du gerade von dem Rang der Matrix geschrieben hast...
Ich habe nochmal in der Aufzeichnung nachgelesen, ich zitiere mal:

[quote]Original von Wet Paper Codes
H*v = m - D*b
[...]
Diese Gleichung hat nur dann eine Lösung, wenn die Matrix H mindestens den Rang q (die Nachrichtenlänge) hat. Die Wahrscheinlichkeit, dass eine zufällige binäre q*k Matrix den Rang q hat nähert sich für große k (Die Anzahl der änderbaren Pixel) sehr schnell 1 je kleiner q wird. Deswegen ist es sehr unwahrscheinlich, dass die Gleichung keine Lösung hat. [...]

Deswegen hatte ich wohl auch unbewusst vorrausgesetzt, dass das Gleichungssystem lösbar ist, wenn die Matrix H diese Maße annimmt.

Jedenfalls vielen vielen Dank bis dahin, du hast mir unglaublich geholfen!
tigerbine Auf diesen Beitrag antworten »

Mir ist da gerade noch etwas eingefallen. Muss mich nochmal in dein H %Co einlesen. Schreibe heute Nacht vielleicht noch was. Wink
tigerbine Auf diesen Beitrag antworten »

Zitat:
Original von Bebbo

Es gibt einen sogenannten Nachrichtenvektor m der Länge q.




Zusätzlich eine Kodierungsmatrix D mit q Zeilen und n Spalten.



Und letztlich einen "Träger"-Vektor b der Länge n. (das entspricht im praktischen Fall der Anzahl aller LSBs der Pixel eines JPEG-Bildes)





Beispiel von Bebbo:






Zitat:
Bebbo
Es werden nun sogenannte defekte Stellen (nicht änderbare Pixel) ermittelt und bestimmte Elemente aus b gestrichen. So z.B.

Man nehme nun die Matrix D und streiche alle zu den aus Vektor b defekten Stellen korrespondierenden Spalten und erhält die Matrix H. .





Zitat:
Bebbo

Anschließend gilt es die folgende Gleichung nach dem Vektor v aufzulösen:



(Die Länge des Vektors v entspricht natürlich der Spaltenzahl der Matrix H, er gibt später zu ändernde LSB's der Pixel an).




Zitat:

Beim Streichen von s Spalten in D soll gelten: . so liegt nie ein überbestimmtes System vor. aufgrund der "Zufälligkeit" der Matrix gilt für mit hoher Wahrscheinlichkeit Rang(H) = q


Jedoch wissen wir nicht, welche Spalten linear unabhängig sind. In welchen Größenordnungen bewegen sich denn q und (n-s) ? Da die Matrix nicht quadratisch ist, müssen auch nicht (n-s), sondern maximal q Durchläufe beim Gaußalgorithmus gemacht werden.






die Matrix H hat also den Rang 3. Es ergibt sich als Lösung:











Da gilt t=0 oder t=1

Bebbo Auf diesen Beitrag antworten »

Danke, du hast das ganze nochmal perfekt dargestellt!

Zitat:
Original von tigerbine

Jedoch wissen wir nicht, welche Spalten linear unabhängig sind. In welchen Größenordnungen bewegen sich denn q und (n-s) ? Da die Matrix nicht quadratisch ist, müssen auch nicht (n-s), sondern maximal q Durchläufe beim Gaußalgorithmus gemacht werden.


Linear unabhängig bedeutet dann wohl, dass in der Spalte nur Nullen sind?
In dem Text steht, dass ein durchschnittliches Coverbild mit Pixeln rund änderbare Pixel hat. Das bedeutet, dass (n-s) also sich in der Größenordnung bewegt, q hingegen ist ja je nach Nachrichtenlänge unterschiedlich, deswegen sollte man auch alle Fälle annehmen (von kleinen Werten, z.b. 100 bis 10^4).

In einem schon existierendem Programm, welches dieses Gleichungssystem löst wird erwartet, dass die Matrix A quadratisch ist, also q = (n-s) gilt. Das hat aber einen anderen Hintergrund: In dem Text wird ausgesagt, dass es effizienter ist, das Bild in y kleinere Teile zu zerlegen und für jeden Teil das Gleichungssystem einzeln zu lösen. Wenn man von Anfang an nur vom Vektor b' mit (n-s) Pixeln ausgeht, dann versucht man pro Teil natürlich so viel wie möglich Nachrichtenbits unterzubringen. Also legt man genau (n-s) Nachrichtenbits auf (n-s) Pixel in dem Teil, sodass die Matrix A quadratisch wird...
tigerbine Auf diesen Beitrag antworten »

Nein, linear unabhängig bedeutet etwas anderes Augenzwinkern Ich wollte damit nur klarmachen, dass wir, wenn quadratisch, auf (n-s) x (n-s) gehen müßten und nicht auf q x q . "Grob" gesagt, weil wir sonst die vielzahr, die uns die WS, dass der Rang q ist, verlieren.

Zitat:
Wenn man von Anfang an nur vom Vektor b' mit (n-s) Pixeln ausgeht, dann versucht man pro Teil natürlich so viel wie möglich Nachrichtenbits unterzubringen. Also legt man genau (n-s) Nachrichtenbits auf (n-s) Pixel in dem Teil, sodass die Matrix A quadratisch wird...


??? Kannst du das mal an unserem Beispiel aufschreiben?
Bebbo Auf diesen Beitrag antworten »

Ich glaube, ich muss mir nochmal genauer ansehen, wie das im Beispiel umgesetzt wird, dass es auch später Sinn macht... habe es probiert aufzuschreiben, aber das klappt noch nicht ganz, ich füge es später hinzu!

Fest steht nur, dass die Gleichung immernoch gilt, nur das n nicht mehr der Anzahl der Gesamtpixel und q nichtmehr der gesamten Nachrichtenbitzahl entspricht (es ändert sich nur die Aufbereitung und die praktische Bedeutung der Variablen). Am Ende gilt jedoch: (n-s) = q
Neue Frage »
Antworten »



Verwandte Themen

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