Überbestimmtes lineares Gleichungssystem

Neue Frage »

matrixman Auf diesen Beitrag antworten »
Überbestimmtes lineares Gleichungssystem
Das folgende numerische Problem beschäftigt mich schon sehr lange verwirrt . Und mittlerweile glaube ich, daß ich den Wald vor lauter Bäumen nicht mehr sehen kann. Ich wäre daher sehr froh, wenn jemand von Euch mir auf die Sprünge helfen könnte. Laßt mich noch ein paar Grundlagen wiederholen, bevor ich zum eigentlichen Problem komme:

Gegeben sei ein überbestimmtes lineares Gleichungssystem
,
wobei eine m x n Matrix ist mit m>>n. Da es meistens keine exakte Lösung für b gibt, sucht man diejenige Lösung, die dem kleineste-Quadrate-Kriterium genügt. Hierzu kann man die pseudo-inverse Matrix u.a. durch

ermitteln und damit dann leicht die Lösung berechnen:
.
Eine effiziente Methode zur Berechnung von ist die Singular Value Decomposition, bei der in drei Matrizzen zerlegt wird:
,
wobei eine numerisch leicht zu invertierende Matrix ist, da sie nur entlang der Diagonalen Werte größer 0 hat. Die pseudo-inverse Matrix läßt sich dann folgendermaßen berechnen:
.

Nun das Problem: Gegeben sei ein ganz spezielles überbestimmtes Gleichungssystem, das nur aus zwei Vektoren


und


wie folgt konstruiert wurde:



Frage: Gibt es für diesen Spezialfall eine numerisch noch effizientere Methode als die beiden oben angedeuteten? (Ein möglicher Lösungsansatz könnte sein, die oben genannten Methoden entsprechend der Eigenschaften dieser speziellen Matrix zu vereinfachen.)

Zwei Zusatzfragen: Gibt es einen speziellen Namen für diese Matrix ? Kann man dieses Gleichungssystem weniger umständlich schreiben?

Dies ist übrigens keine Prüfung, sondern eine Herausforderung Augenzwinkern und für jeden Hinweis und jeden weiteren Denkansatz wäre ich sehr dankbar.
matrixman Auf diesen Beitrag antworten »
RE: Überbestimmtes lineares Gleichungssystem
Habe ich eine wichtige Information vergessen oder war die Frage für Euch zu schwierig, zu exotisch, nicht relevant, unverständlich oder zu langweilig, oder warum hat keiner geantwortet? verwirrt
JochenX Auf diesen Beitrag antworten »

das zauberwort heißt geduld. sobald dir jemand antworten kann (ich kann's nicht) und das tun möchte, wird er (sie) es schon tun.
aber auch andere wollen fragen beantwortet haben und pushposts sind nicht gern gesehen! zumal noch nicht mal 24h rum sind....
lies mal bitte im userguide nach!
gut gestellte fragen werden selten ganz übergangen, aber du brauchst halt die geduld und kannst nicht erwarten, das wir uns alle sofort auf diese aufgabe stürzen.

mfg jochen
AD Auf diesen Beitrag antworten »

Ich hatte mir deinen Beitrag bereits gestern durchgelesen. Als Statistiker ist mir von der Regression her natürlich auch die MKQ-Methode wohlvertraut. Aber da mir zu deiner speziellen Matrix nichts besseres bekannt ist, bzw. nach kurzem Nachdenken auch nichts besseres eingefallen ist, wollte ich eigentlich nach dem bekannten Motto verfahren:

Wenn man keine Ahnung hat, einfach mal Fresse halten.

Das ich das jetzt verletzt habe, liegt an deiner Drängelei. Das oben ist schon eine sehr spezielle Frage - vielleicht kennt ja jemand einen Dreh, aber ich würde mich an deiner Stelle da nicht drauf verlassen. Auf jeden Fall solltest du etwas mehr Geduld aufbringen.


P.S.: Ich stell demnächst mal die Goldbachsche Vermutung hier ins Forum und meckere dann nach einem Tag rum, warum die noch keiner gelöst hat. Augenzwinkern
matrixman Auf diesen Beitrag antworten »

Zitat:
Original von LOED
pushposts sind nicht gern gesehen! zumal noch nicht mal 24h rum sind....
lies mal bitte im userguide nach!


Tut mir wirklich leid. Habe gerade nachgelesen. Ich wollte nicht wirklich eine pushpost fabrizieren, sondern hatte tatsächlich Zweifel, daß ich alle wichtigen Informationen mathematisch korrekt formuliert hatte. Es war immerhin meine erste Mail hier und ich habe auch zum ersten Mal mit dem Formeleditor gearbeitet (Ich finde es übrigens sehr gelungen, daß man Formeln hier mit einem LaTeX ähnlichen Konzept formatiert).

Da ich selbst an dem Problem schon lange grüble, sollte ich anderen eine vergleichbare Zeit einräumen. Also nochmal Entschuldigung und ein versöhnliches Wink
Bier17 Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent


P.S.: Ich stell demnächst mal die Goldbachsche Vermutung hier ins Forum und meckere dann nach einem Tag rum, warum die noch keiner gelöst hat. Augenzwinkern


"Nachdem der britische Verlag Faber & Faber im Jahr 2000 ein Preisgeld von 1.000.000 Dollar auf die Lösung dieses Problems ausgelobt hatte, war auch das öffentliche Interesse an dieser Frage gewachsen. Dieses Preisgeld sollte für einen Beweis der Vermutung vor dem April 2002 vergeben werden. Es wurde jedoch bis zu diesem Zeitpunkt kein Beweis gefunden."

Da heb ich meine Lösung lieber so lange auf bis es wieder ein sattes Preisgeld gibt.
 
 
matrixman Auf diesen Beitrag antworten »
RE: Überbestimmtes lineares Gleichungssystem
Wenn man mit der Methode

beginnt, kann man zumindest zeigen, daß zu einer quadratischen und symmetrischen p+1 x p+1 Matrix führt:





Diese müßte nun invertiert werden und genau da verlassen sie mich. Das einzige, was ich weiß ist, daß die invertierte Matrix auch symmetrisch ist. Kann mir jemand helfen? Hilfe
matrixman Auf diesen Beitrag antworten »
RE: Überbestimmtes lineares Gleichungssystem
Ich bin nun wieder einen Schritt weitergekommen, denke ich:

In der vorigen Mail wurde begonnen, die pseudo-inverse Matrix zu ermitteln, um zu lösen, was aber bereits vor der Invertierung der Matrix scheiterte. Das Gleichungssystem läßt sich aber auch ohne Invertieren lösen, denn immerhin wurde berechnet und damit die rechte Seite der folgenden Gleichung bearbeitet:

Zusammen mit der ebenfalls um erweiterten linken Seite ergibt sich folgendes lineares Gleichungssystem mit nur noch Zeilen:



Dies läßt sich zwar mittels Eliminationsverfahren schon lösen, aber vielleicht gibt es ein äquivalentes einfacheres Gleichungssystem, so daß man nicht erst so mühsam alle Elemente berechnen muß? Sieht jemand von Euch, ob und wie sich dieses Gleichungssystem weiter vereinfachen läßt?

Sicher kann man alle n entfernen, wenn man akzeptiert, daß die ersten Komponenten der Vektoren x und y mit dem Index 0 beginnen. Dann sieht es etwas schöner aus:



Aber wie geht es nun weiter???
Tobias Auf diesen Beitrag antworten »

Das zuletzt von dir beschriebene Verfahren ist das Verfahren der Normalengleichung.

Anstatt das überbestimmte System zu lösen, löst man das eindeutig bestimmte System . Diese Methode ist in gewisser Hinsicht auch die Formalisierung der Methode der kleinsten Fehlerquadrate von Gauß und wird für Ausgleichsprobleme verwendet.

Das Verfahren ist zwar geschickt, aber meistens numerisch instabil und nicht gut konditioniert. Es gibt Wege, mit mehr Aufwand die Kondition zu verbessern: QR-Zerlegung (Householder-Spiegelungen).
matrixman Auf diesen Beitrag antworten »

Wenn sich die Matrix also nicht mehr weiter vereinfachen läßt, so kann man doch immerhin sagen, daß sie symmetrisch ist, daß alle Werte der Hauptdiagonalen positiv sind und daß alle anderen Werte kleiner als die "meisten" Werte der Hauptdiagonale sein müssen. Ist die Matrix damit positiv definit?

Das würde heißen, daß man sie mit der Cholesky-Faktorisierung am effizientesten löst. Anderenfalls scheint wohl die LU-Zerlegung die Methode der Wahl zu sein. Oder?
Neue Frage »
Antworten »



Verwandte Themen

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