Ueberbestimmtes GL-System < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 03:02 Di 04.02.2014 | | Autor: | cosPhi |
Ich habe ein ueberbestimmtes GL System N x Q mit N >> Q (viel mehr Zeilen als Spalten).
Dieses moechte ich mit Least Squares loesen, dabei aber nur eine Untermenge an M Zeilen verwenden (M << N, M > Q).
Wie gut dies funktioniert, zeigt mit die Konditionszahl der jeweiligen Sub-Matrix.
Die Konditionszahl ist aber ein Mass dafuer, wieweit die Zeilen/Spalten einer Matrix von der Orthogonalitaet entfernt sind (cond(A)=1: Vektoren sind orthogonal). Stimmt das so?
Gilt das nun fuer die Zeilen- oder die Spaltenvektoren?
Zurueck zur NxQ Matrix A: Sagen wir ich moechte die jenige MxQ Submatrix B finden (durch beliebige Auswahl an M Zeilen aus A) die am stabilsten ist (d.h. die niedrigste Konditionszahl hat). Ist dann (zumindest theoretisch) folgender Ansatz richtig?
* Fuer alle Zeilenkombinationen ("N ueber M") berechne das Innenprodukt der Spaltenvektoren. Fuer jede Kombination gibt es davon Q(Q-1)/2 Innenprodukte
* Waehle die Kombination, von denen das maximale Innenprodukt am minimalsten ist.
Oder muss ich bei der Auswahl auf die Orthogonalitaet der Zeilen achten?
Oder gar auf die der Zeilen und Spalten?
Danke!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 06:44 Fr 07.02.2014 | | Autor: | cosPhi |
Mal hoeflich nachgefragt: Weiss niemand was dazu, ist die Frage zu konfus oder hab ich irgendeine Regel nicht befolgt?
Ich versuche es jedenfalls nochmal vereinfacht:
Fuer ein ueberbestimmtes Gleichungssystem: Was sagen die Spalten- und die Zeilenvektoren (bzw. deren lineare Abhaengigkeit) ueber die Stabilitaet des Systems aus?
Hat ein stabiles System (=niedrige Konditionszahl) moeglichst orthogonale Spaltenvektoren, Zeilenvektoren oder gar beides? Wieso?
Wenn ichs mir aussuchen koennte: Wuerde ich lieber die Spaltenvektoren oder die Zeilenvektoren hinsichtlich "moeglichst orthogonal" optimieren?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:21 Sa 08.02.2014 | | Autor: | cosPhi |
Wirklich nicht? Sind im Forum allgemeine Fragen vielleicht nicht so erwuenscht? Sondern eher mehr vorgegebene Rechenaufgaben?
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:42 Sa 08.02.2014 | | Autor: | Diophant |
Hallo,
> Wirklich nicht? Sind im Forum allgemeine Fragen vielleicht
> nicht so erwuenscht? Sondern eher mehr vorgegebene
> Rechenaufgaben?
Doch, das ist vollkommen ok. Es hat sich eben nur noch niemand gefunden, der eine Antwort weiß.
Ich habe mal die ursprüngliche Frage auf unbeantwortet zurückgesetzt und die andere Frage zu einer Mitteilung gemacht. Durch deine Rückfrage wurde das ganze jetzt ja nochmals gepusht. Hoffen wir also, dass am Wochenende sich jemand finden wird, der dir weiterhelfen kann.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:20 Sa 08.02.2014 | | Autor: | DieAcht |
Hallo,
> Ich habe ein ueberbestimmtes GL System N x Q mit N >> Q
> (viel mehr Zeilen als Spalten).
> Dieses moechte ich mit Least Squares loesen, dabei aber
> nur eine Untermenge an M Zeilen verwenden (M << N, M > Q).
> Wie gut dies funktioniert, zeigt mit die Konditionszahl der
> jeweiligen Sub-Matrix.
>
> Die Konditionszahl ist aber ein Mass dafuer, wieweit die
> Zeilen/Spalten einer Matrix von der Orthogonalitaet
> entfernt sind (cond(A)=1: Vektoren sind orthogonal). Stimmt
> das so?
> Gilt das nun fuer die Zeilen- oder die Spaltenvektoren?
Das hängt von der Norm ab. Es soll $Ax=b$ gelöst werden.
$A$ ist bei dir übrigens in der Regel nicht quadratisch!
Sei aber dennoch $A$ nicht-singulär, dann gilt für eine
induzierte Matrixnorm [mm] \eta:
[/mm]
[mm] \kappa_{\eta}(A)=\|A\|_{\eta}*\|A^{-1}\|_{\eta}
[/mm]
Die Kondition [mm] \kappa(A) [/mm] beschreibt die Kondition des
linearen Gleichungssystems. Die Kondition ist aber eine
Eigenschaft des Problems und nicht des Algorithmus. Mit
anderen Worten: Für schlecht konditionierte Systeme kann man
auch den Ergebnissen eines numerisch stabilen Algorithmus
nicht trauen!
Bei Least Squares solltest du dir klar machen wieso man
die Quadrate überhaupt nimmt. Das Gleichungssystem $Ax=b$
ist im Allgemeinen nicht lösbar. Was man aber bei Least
Squares macht ist die [mm] \eta=2 [/mm] setzten, also die euklidische
Norm betrachten. Du kannst dir mal den Grund überlegen.
Die Konditionszahl beschreibt wie sich ein relativer Ein-
gabefehler in Vektor b auf das Resultat auswirkt.
Du kannst dir mal [mm] \kappa(A) [/mm] noch ausführlicher hinschreiben,
dann sollte sich deine Frage bezüglich des orthogonalen
Vektors in Luft auflösen.
Wenn $A$ eine orthogonale Matrix ist, dann gilt:
[mm] \|Ax\|^2_2=\|x\|^2_2
[/mm]
[mm] \Rightarrow \kappa_2(A)=1
[/mm]
Damit kann man natürlich auch sofort die QS-Zerlegung motivieren.
> Zurueck zur NxQ Matrix A: Sagen wir ich moechte die jenige
> MxQ Submatrix B finden (durch beliebige Auswahl an M Zeilen
> aus A) die am stabilsten ist (d.h. die niedrigste
> Konditionszahl hat). Ist dann (zumindest theoretisch)
> folgender Ansatz richtig?
>
> * Fuer alle Zeilenkombinationen ("N ueber M") berechne das
> Innenprodukt der Spaltenvektoren. Fuer jede Kombination
> gibt es davon Q(Q-1)/2 Innenprodukte
> * Waehle die Kombination, von denen das maximale
> Innenprodukt am minimalsten ist.
>
> Oder muss ich bei der Auswahl auf die Orthogonalitaet der
> Zeilen achten?
> Oder gar auf die der Zeilen und Spalten?
Durch geschickte Zeilenvertauschungen kann man
manchmal eine bessere "Gesamt"-Kondition erreichen.
Im Grunde formst du dein Problem äquivalent um.
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:25 Mi 12.02.2014 | | Autor: | cosPhi |
Hallo 8!
Danke fuer deine Antwort! Ich glaube deine Antwort hilft mir schon viel weiter, mir fehlt allerdings noch ein kleiner "Link".
> Das hängt von der Norm ab.
Richtig, bei mir soll es L2 sein ("Least Squares").
Also ein ganz klassisches LS System das ueber die Pseudo Inverse geloest wird.
> Es soll $ Ax=b $ gelöst werden.
> $ A $ ist bei dir übrigens in der Regel nicht quadratisch!
Richtig, A ist per Problemdefinition nicht quadratisch.
Vielleicht hilft es besser zu verstehen wo das herkommt: Ein physikalisches System wird modelliert. Das Modell hat Q Freiheitsgrade. Ich schicke nun ein "Signal" ins System (derzeit durch white Noise modelliert) um es zu identifizieren. Nach deiner obigen Beschreibung beschreibt "b" die Ausgabemessungen, "x" die Modellparameter und "A" wird aus dem bekannten Eingangssignal gebildet (ganz aehnlich wie bei eine Faltung).
Mit dem ersten Ansatz werden nun N >> Q Messungen (=Zeilen) genommen und das System per LS geloest.
Das eigentliche Problem ist aber dass ich die Zahl der Messungen M minimieren moechte (Q < M << N). Angenommen ich kann mir aussuchen welche M Messungen ich aus den N zu Verfuegung stehenden auswaehle, wie waehle ich die?
Experimentell sehe ich, dass eine zufaellige Auswahl gut ist. Ich moechte aber verstehen wieso und vielleicht sogar eine Auwahl finden, die nicht zufaellig ist.
Welche M Zeilen ich waehle stelle ich mir so vor: Ich suche die Untermatrix, die die kleinste Konditionszahl besitzt.
Allerdings ist das kein gutes Konzept um eine Regel fuer die Auswahl abzuleiten, denn ich kann schwer analytisch von den Eigenschaften des Eingangssignals auf $ [mm] \kappa [/mm] $ kommen.
Deshalb hab ich mir gedacht, ich kann es intuitiv besser verstehen wenn ich paarweise Vektoren anschaue und dann "sehe" unter welchen Umstaenden diese am meisten orthogonal oder linear unabhaengig sind.
So koennte ich dann - wenn ich annehme dass das Eingangssignal nicht weisses Rauschen ist, eine bessere Auswahl finden.
> Du kannst dir mal $ [mm] \kappa(A) [/mm] $ noch ausführlicher hinschreiben,
> dann sollte sich deine Frage bezüglich des orthogonalen
> Vektors in Luft auflösen.
Wie oben gesagt, befuerchte ich, dass das zu viel Entropie hat und wollte daher eher "intuitiv" auf die Eigenschaft von Zeilen-/Spaltenvektoren gehen.
Aber danke, ich versuch es nochmal auf diesem Wege, nach deiner obigen Formel (und nicht als Verhaeltnis von kleinstem und groessten Singulaerwert, wie ich es zuvor versuchte).
> Durch geschickte Zeilenvertauschungen kann man
> manchmal eine bessere "Gesamt"-Kondition erreichen.
> Im Grunde formst du dein Problem äquivalent um.
Ich glaube das ist ein aehnliches Setup, allerdings moechte ich nicht N Zeilen vertauschen, sondern M < N Zeilen auswaehlen die die beste Konditionierung haben.
Dann ist aber trotzdem die Frage was "geschickt" heisst. Wie urspruenglich vorgeschlagen wuerde ich z.B. die Innenprodukte zwischen den Zeilenvektoren anschauen und diejenigen Zeilen waehlen, deren Innenprodukte am naechsten bei 0 sind.
Alternativ koennte ich aber auch sagen ich suche diejenigen Zeilenvektoren, deren Spaltenvektoren der resultierenden Matrix am meisten linear unabhaengig sind.
Ich verstehe allerdings noch nicht was davon richtig und oder ob sie vielleicht sogar aequivalent sind.
Danke nochmal!
LG
|
|
|
| |
|
Vermutlich ist dir der folgende Hinweis bekannt und daher überflüssig, da du das Problem aus meiner Sicht in einer "höheren Sphäre" löst.
Allgemein: Wenn ein System zu viele Zeilen hat, ist es meist überbestimmt in dem Sinne, dass sich Gleichungen (evtl. wegen Messfehlern nur geringfügig) widersprechen, so dass es dann nicht mehr lösbar ist.
Multipliziert man nun die unlösbare Gleichung [mm] A\vec{x}=\vec{b} [/mm] mit der Transponierten [mm] A^T [/mm] von A, so erhält man das Gleichungssystem
[mm] (A^TA)\vec{x}=A^T\vec{b}. [/mm] Die Lösung, die man nun für [mm] \vec{x} [/mm] erhält, hat die Eigenschaft, dass bei diesem [mm] \vec{x} [/mm] der Vektor [mm] A\vec{x}-\vec{b} [/mm] minimale Länge hat (die Summe der Abstandsquadrate der Komponenten der errechneten Werte [mm] A\vec{x} [/mm] von den Messwerten [mm] \vec{b} [/mm] wird minimal).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:40 Sa 15.02.2014 | | Autor: | cosPhi |
Danke auch dir!
> Allgemein: Wenn ein System zu viele Zeilen hat, ist es meist überbestimmt
> in dem Sinne, dass sich Gleichungen (evtl. wegen Messfehlern nur
> geringfügig) widersprechen, so dass es dann nicht mehr lösbar ist.
In meinem Fall ist es sogar so dass sie sich allein durch numerische (Un)genauigkeit widersprechen! D.h. ich moechte verstehen welche Messungen am stabilsten sind. Was dabei vielleicht nicht klar ist: Ich kenne die Struktur der Matrix bzw. kann deren Elemente analytisch beschreiben.
Stell dir vor, du moechtest ein unbekanntes, zeitdiskretes LTI-FIR System identifizieren welches aus Q Parametern besteht.
Theoretisch beinhalten alle Q Messungen genuegend Informationen um die Parameter zu schaetzen.
Nun ist es aber so, dass jeses System einen gewissen Frequenzgang hat. Wenn ich z.B. Werte von der Stelle nehme, an dem der Frequenzgang steil abfaellt, dann geht es zwar theoretisch, praktisch das Gleichungssystem aber instabil. Hier ist es trivial. Aber es verhaelt sich aehnlich wenn ich sozusagen die ersten Werte im Frequenzbereich nehme.
Ich glaub ich hab einfach nur ein Brett vorm Hirn. Wenn du deine Antwort vielleicht etwas intuitiver ausdruecken koenntest wuerde sich das Brett vielleicht loesen 
Ich bin mir sicher man kann ein ueberbestimmtes Gleichungssystem irgendwie so interpretieren dass Zeilen- oder Spaltenvektoren einen Raum aufspannen, die Messungen sind Punkte und diese sollen sich nicht wiedersprechen ... oder so aehnlich.
Vielleicht ein Trivialbeispiel:
[mm] y_0 [/mm] = [mm] a_{00} c_0 [/mm] + [mm] a_{01} c_1
[/mm]
[mm] y_1 [/mm] = [mm] a_{10} c_0 [/mm] + [mm] a_{11} c_1
[/mm]
[mm] y_2 [/mm] = [mm] a_{20} c_0 [/mm] + [mm] a_{21} c_1
[/mm]
Angenommen ich moechte nur 2 Zeilen verwenden, welche wuerde ich nehmen (qualitativ)?
Ich bin wirklich verwirrt ob nun die Spaltenvektoren
[ [mm] a_{00} \quad a_{10} \quad a_{20} [/mm] ]
[ [mm] a_{01} \quad a_{11} \quad a_{21} [/mm] ]
oder die Zeilenvektoren
[ [mm] a_{00} \quad a_{01} [/mm] ]
[ [mm] a_{10} \quad a_{11} [/mm] ]
[ [mm] a_{20} \quad a_{21} [/mm] ]
von Bedeutung sind ...
|
|
|
| |
|
> Danke auch dir!
>
> > Allgemein: Wenn ein System zu viele Zeilen hat, ist es
> meist überbestimmt
> > in dem Sinne, dass sich Gleichungen (evtl. wegen
> Messfehlern nur
> > geringfügig) widersprechen, so dass es dann nicht mehr
> lösbar ist.
>
> In meinem Fall ist es sogar so dass sie sich allein durch
> numerische (Un)genauigkeit widersprechen! D.h. ich moechte
> verstehen welche Messungen am stabilsten sind. Was dabei
> vielleicht nicht klar ist: Ich kenne die Struktur der
> Matrix bzw. kann deren Elemente analytisch beschreiben.
>
> Stell dir vor, du moechtest ein unbekanntes, zeitdiskretes
> LTI-FIR System identifizieren welches aus Q Parametern
> besteht.
> Theoretisch beinhalten alle Q Messungen genuegend
> Informationen um die Parameter zu schaetzen.
> Nun ist es aber so, dass jeses System einen gewissen
> Frequenzgang hat. Wenn ich z.B. Werte von der Stelle nehme,
> an dem der Frequenzgang steil abfaellt, dann geht es zwar
> theoretisch, praktisch das Gleichungssystem aber instabil.
> Hier ist es trivial. Aber es verhaelt sich aehnlich wenn
> ich sozusagen die ersten Werte im Frequenzbereich nehme.
>
> Ich glaub ich hab einfach nur ein Brett vorm Hirn. Wenn du
> deine Antwort vielleicht etwas intuitiver ausdruecken
> koenntest wuerde sich das Brett vielleicht loesen
>
> Ich bin mir sicher man kann ein ueberbestimmtes
> Gleichungssystem irgendwie so interpretieren dass Zeilen-
> oder Spaltenvektoren einen Raum aufspannen, die Messungen
> sind Punkte und diese sollen sich nicht wiedersprechen ...
> oder so aehnlich.
>
> Vielleicht ein Trivialbeispiel:
>
> [mm]y_0[/mm] = [mm]a_{00} c_0[/mm] + [mm]a_{01} c_1[/mm]
> [mm]y_1[/mm] = [mm]a_{10} c_0[/mm] + [mm]a_{11} c_1[/mm]
>
> [mm]y_2[/mm] = [mm]a_{20} c_0[/mm] + [mm]a_{21} c_1[/mm]
>
> Angenommen ich moechte nur 2 Zeilen verwenden, welche
> wuerde ich nehmen (qualitativ)?
Grundsätzlich:
Wenn du weißt, welche deiner Daten unzuverlässiger/instabiler sind als andere, lässt du diese Zeile(n) einfach weg, wenn du ansonsten genügend messwerte hast. Mathematisch wäre das dort der Fall, wo eine geringe Variation der c-Werte (=gesuchte Lösung) eine große Änderung der y-Werte zur Folge hat, wo also die Ableitung betragsmäßig groß ist. Das hast du aber auch schon selber erkannt.
Andererseits kannst du aber auch alle Varianten durchspielen, wobei du immer eine Zeile weglässt. Darauf gehe ich unten noch mal ein.
>
> Ich bin wirklich verwirrt ob nun die Spaltenvektoren
>
> [ [mm]a_{00} \quad a_{10} \quad a_{20}[/mm] ]
> [ [mm]a_{01} \quad a_{11} \quad a_{21}[/mm] ]
>
> oder die Zeilenvektoren
>
> [ [mm]a_{00} \quad a_{01}[/mm] ]
> [ [mm]a_{10} \quad a_{11}[/mm] ]
> [ [mm]a_{20} \quad a_{21}[/mm] ]
>
> von Bedeutung sind ...
A = [mm] \pmat{ a_{00} & a_{01} \\ a_{10} & a_{11} \\ a_{20} & a_{21} }
[/mm]
[mm] \vec{c}=\vektor{c_0 \\ c_1} [/mm]
[mm] \vec{y}=\vektor{y_0 \\ y_1 \\ y_2} [/mm]
Gesucht: Lösung von [mm] A*\vec{c}=\vec{y}, [/mm]
[mm] \vec{c} [/mm] gesucht.
Die 3 Gleichungen werden sich i.a. widersprechen.
Nun multiplizierst du A von links mit [mm] A^T=\pmat{ a_{00} & a_{10} & a_{20} \\ a_{01} & a_{11} & a_{21} } [/mm] und ebenso [mm] \vec{y}.
[/mm]
Du erhältst das neue Gleichungssystem
[mm] (A^T*A)*\vec{c}=A^T*\vec{y}
[/mm]
Das ist ein 2-mal-2-Gleichungssystem und im allgemeinen eindeutig lösbar. Du bekommst die "beste" Lösung für [mm] \vec{c} [/mm] in folgendem Sinne:
Wenn du für irgend einen Vektor [mm] \vec{c} [/mm] die Ausgangsgleichung
[mm] A*\vec{c} [/mm] ausrechnest, bekommst du nie [mm] \vec{y} [/mm] heraus, weil das GLST. ja nicht eindeutig lösbar ist. Der Differenzvektor [mm] A*\vec{c}-\vec{c} [/mm] hat dann - je nach dem, wie "gut" [mm] \vec{c} [/mm] passt - eine bestimmte Länge. Und diese ist bei der nach obigem Verfahren gefundenen Lösung minimal!
Jetzt kannst du noch folgendes machen, wenn du der Meinung bist, dass irgendeiner der Messwerte besonders schlecht ist, du aber nicht weiß, welcher:
Du lässt immer eine Gleichung weg, bestimmst mit den restlichen Gleichungen die "beste" Lösung nach obigem Verfahren und bestimmst für all diese Berechnungen immer die Länge des "Fehler"-Vektors [mm] A*\vec{c}-\vec{c}. [/mm] Wenn du feststellst, dass einer davon besonders kurz im Verhältnis zu den anderen ist, hast du diejenige Messung weggelassen, die am wenigsten zu den anderen Messdaten passt.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 05:39 So 16.02.2014 | | Autor: | cosPhi |
Ich danke dir fuer deine Geduld!!
Und Entschuldigung dass ich nochmal nachfrage ...
> Wenn du weißt, welche deiner Daten unzuverlässiger/instabiler sind als andere, lässt du diese Zeile(n) einfach weg, wenn du ansonsten genügend messwerte hast. Mathematisch wäre das dort der Fall, wo eine geringe Variation der c-Werte (=gesuchte Lösung) eine große Änderung der y-Werte zur Folge hat, wo also die Ableitung betragsmäßig groß ist. Das hast du aber auch schon selber erkannt.
Genau auf das will ich hinaus, aber ich glaub ich habs noch nicht erkannt
Der fundamentale Unterschied ist, dass ich es eben nicht weiss sondern verstehen anhand der Struktur bzw. einem Bildungsgesetz verstehen moechte.
Vielleicht wird es klarer wenn ich sage: Ich kenne nicht die genauen Werte der Matrix A, allerdings kenne ich die Struktur [mm] (a_{ij} [/mm] ist i-te Zeile und j-te Spalte der Matrix A):
[mm] a_{ij} [/mm] = [mm] f(i,j,x,y,\dots)
[/mm]
Einfaches Beispiel (bereits aehnlich meinem Setup, allerdings stark vereinfacht):
[mm] a_{ij} [/mm] = [mm] x_i e^{-j\frac{2\pi}{N} i j} \qquad x_i \sim \mathcal{N}(\sigma^2,0)
[/mm]
Fuer diesen Fall scheint mein Vorschlag mit dem Inprodukt der Spaltenvektoren bereits zu funktionieren: Die optimale Auswahl ist hier jede Zeile gleichverteilt. Das klingt logisch, da hier der Einheitskreis abgetastet wird und z.B. 1 und -1 genau orthogonal sind.
> [mm] $A\cdot{}\vec{c}$ [/mm] ausrechnest, bekommst du nie [mm] $\vec{y}$ [/mm] heraus, weil das GLST. ja nicht eindeutig lösbar ist. Der Differenzvektor [mm] $A\cdot{}\vec{c}-\vec{c}$
[/mm]
> hat dann - je nach dem, wie "gut" [mm] $\vec{c}$ [/mm] passt - eine bestimmte Länge. Und diese ist bei der nach obigem Verfahren gefundenen Lösung minimal!
Hier meinst du [mm] $A\cdot{}\vec{c}-\vec{y}$ [/mm] oder?
> Du lässt immer eine Gleichung weg, bestimmst mit den restlichen Gleichungen die "beste" Lösung nach obigem Verfahren und bestimmst für all diese Berechnungen immer die Länge des "Fehler"-Vektors $ [mm] A\cdot{}\vec{c}-\vec{c}. [/mm] $
Auch hier [mm] $A\cdot{}\vec{c}-\vec{y}$ [/mm] ?
> Wenn du feststellst, dass einer davon besonders kurz im Verhältnis zu den anderen ist, hast du diejenige Messung weggelassen, die am wenigsten zu den anderen Messdaten passt.
besonders kurz oder besonders lang?
Am wenigsten oder am meisten?
Sollte [mm] $A\cdot{}\vec{c}-\vec{y}$ [/mm] nicht minimiert werden? Hier wuerde ich meinen dass derjeniger, der besonders lange ist, am wenigsten passt (=groesster Fehler).
Ich habe jedenfalls versucht ein formales Ergebnis mit oben beschriebener Struktur zu bekommen, aber es ist einfach zu viel Entropie:
[mm]
\min_{A_{sub}} \| A_{sub} c - y \|
[/mm]
Das Problem ist, dass ich mit Ableiten nicht weiterkomme, selbst wenn ich y und c als konstant annehme. Denn was ich minimieren moechte ist keine Variable sondern ein bestimmtes Subset an Zeilen ...
Ich fange uebrigens inzwischen selbst an der Zeilen-/Spaltengeschichte zu zweifeln. Ich hab das simple 3x2 System in MATLAB implementiert.
Ich habe den Code + Ergebnis auf pastebin gepostet: http://pastebin.com/NKFQPQdG
Das erlaubt es immer nur 2 Vektoren zu vergleichen. Meistens stimmt meine Vermutung und die Submatrix mit der geringsten Konditionszahl hat auch den kleinsten absoluten Winkel (=Vektoren am meisten "orthogonal"). Allerdings deckt sich das auch mit den Zeilenvektoren.
Problematisch: Manchmal stimmt es nicht. Fuer das im Link angegebene Beispiel hat die dritte Spalte (die erste ist die komplette 2x3 Matrix) die geringste Konditionszahl und auch den kleinsten Fehler. Allerdings ist der Winkel in der zweiten Spalte (grosserer Fehler) kleiner - sowohl Spalten- als auch Zeilenvektor. Laesst sich das irgendwie erklaeren?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:20 Do 20.02.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:40 So 16.02.2014 | | Autor: | DieAcht |
Hallo,
Wenn ich dich richtig verstanden habe willst du wissen weshalb
das Entfernen bestimmter Spalten und Zeilen dein Ergebnis
nicht verändern.
Das liegt daran, dass deine Matrix, nennen wir sie $A$, stabil ist.
Ich schätze, dass sie sogar exponentiell stabil ist.
Für stabile Matrizen ist
[mm] \sup\limits_{x\ge 0}\|e^{Ax}\|=:\alpha
[/mm]
[mm] \alpha [/mm] eine reelle Zahl.
Mit anderen Worten: Solange diese Eigenschaft gilt kannst du
an deiner Matrix machen und tun was du willst. Natürlich nur
in einem speziellem Rahmen. Das heißt speziell, dass der
Fehler des Ergebnisses nicht signifikant vergrößert wird.
Falls dich das genauer interessiert kann du mal nach
"Stabilität von Matrizen" googeln.
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 07:15 Mo 17.02.2014 | | Autor: | cosPhi |
Hallo 8,
Danke auch dir nochmal fuer deine Geduld.
> Wenn ich dich richtig verstanden habe willst du wissen weshalb
> das Entfernen bestimmter Spalten und Zeilen dein Ergebnis
> nicht verändern.
Eigentlich nicht. Das Entfernen von Zeilen aendert das Ergebnis fundamental (macht Konditionierung schlechter).
Eigentlich bin ich nachwievor mit ein paar einfachen "Interpretationen" verwirrt. Ich google seit Tagen und finde nix zu ueberbestimmten Systemen - deprimierend :-( Das meiste findet sich zu zu nxn Systemen.
Ich finde tonnenweise was ich weiss, z.B. "Wenn Zeilen und Spalten linear unabhaengig sind existiert eine Loesung".
Kann man sowas aehnliches nicht auch fuer MxN, M>N Matrizen sagen?
Ich habe z.B. eine Stelle gefunden da heisst es "Die Konditionszahl ist ein Mass dafuer wie stark die Zeilenvektoren vom Idealfall Orthogonalitaet abweichen".
Ich verstehe das aber aus mehreren Gruenden nicht: Sind es wirklich die Spalten- oder die Zeilenvektoren?
In der Wikipedia finde ich dazu eine gute graphische Interpretation http://en.wikipedia.org/wiki/Overdetermined_system mit dem traurigen Text "The informal discussion of constraints and degrees of freedom above relates directly to these more formal concepts.".
Im Wikipedia Beispiel z.B. ist "#5" das erstrebenswerteste - alle Vektoren treffen sich moeglichst in einem Punkt. Was wiederum heisst die Vektoren (Zeilenvektoren??) sollten moeglichst linear unabhaengig zueinander sein. Ist das die richtige Interpretation?
Allerdings verstehe ich nicht wieso das genug sein soll - in "#1" sind die Vektoren auch sehr linear unabhaengig und trotzdem ist der Fehler tendentiell gross, da sie sich nicht im gleichen Punkt treffen. Was konkret sagen mir also [2 ; -3 ; -1] bzw. [1;1;1] und [2,1] bzw. [-3,1] bzw. [-1,1] ? Es muss doch irgendwie moeglich sein aufgrund der Eigenschaften (lineare Abhaengkeit etc) der Spalten und/oder Zeilenvektoren etwas ueber die Stabilitaet des Systems auszusagen, oder?
LG
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 03:44 Di 18.02.2014 | | Autor: | cosPhi |
Ich probiere meine Frage anders zu stellen: Angenommen ich stelle die folgende Aufgabe:
"Erstelle mir eine 10x3 Matrix die optimal mit Least Squares loesbar ist".
Eine Antwort koennte lauten: "Ich werfe MATLAB an, erstelle in einer Endlosschleife 10x3 Zufallsmatrizen und bestimmte mit cond(.) die Konditionszahl. Ist eine gute Konditionszahl dabei breche ich ab."
Aber das ist natuerlich nicht gut. Gibt es nicht eine Antwort wie die folgende?
"Ich waehle die ersten 2 Spalten sodass diese orthogonal sind. Dann waehle ich die dritte Spalte so, dass diese ebenfalls orthogonal zu den ersten sind."
Oder: "Ich versuche die 10 Zeilenvektoren so zu waehlen, dass diese moeglichst linear unabhaengig sind. Bildlich koennte das wie Naegel aussehen, die gleichverteilt aus einer Viertelkugel rausragen."
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:20 Mi 19.02.2014 | | Autor: | DieAcht |
Hallo,
> Ich probiere meine Frage anders zu stellen: Angenommen ich
> stelle die folgende Aufgabe:
>
> "Erstelle mir eine 10x3 Matrix die optimal mit Least
> Squares loesbar ist".
>
> Eine Antwort koennte lauten: "Ich werfe MATLAB an, erstelle
> in einer Endlosschleife 10x3 Zufallsmatrizen und bestimmte
> mit cond(.) die Konditionszahl. Ist eine gute
> Konditionszahl dabei breche ich ab."
Gegenfrage: Was ist eine "gute" Konditionszahl?
Willst du warten bis du als Ergebnis die Eins bekommst? 
> Aber das ist natuerlich nicht gut. Gibt es nicht eine
> Antwort wie die folgende?
>
> "Ich waehle die ersten 2 Spalten sodass diese orthogonal
> sind. Dann waehle ich die dritte Spalte so, dass diese
> ebenfalls orthogonal zu den ersten sind."
>
> Oder: "Ich versuche die 10 Zeilenvektoren so zu waehlen,
> dass diese moeglichst linear unabhaengig sind. Bildlich
> koennte das wie Naegel aussehen, die gleichverteilt aus
> einer Viertelkugel rausragen."
Wenn ich das richtig verstanden habe, dann kann ich nicht
nachvollziehen, weshalb das rechnerisch schneller sein sollte.
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:56 Mi 19.02.2014 | | Autor: | DieAcht |
Hallo cosPhi,
> Hallo 8,
>
> Danke auch dir nochmal fuer deine Geduld.
>
> > Wenn ich dich richtig verstanden habe willst du wissen
> weshalb
> > das Entfernen bestimmter Spalten und Zeilen dein
> Ergebnis
> > nicht verändern.
>
> Eigentlich nicht. Das Entfernen von Zeilen aendert das
> Ergebnis fundamental (macht Konditionierung schlechter).
Ja, eindeutig. Es geht doch darum, dass du dich gefragt hast
weshalb dir eine bestimmte Anzahl von Messwerten ausreichen
um eine möglichst genauer Lösung zu erhalten, oder habe ich
deine Frage falsch interpretiert?
Ich habe dir bereits folgendes geschrieben:
Für stabile Matrizen ist
[mm] \sup\limits_{x\ge 0}\|e^{Ax}\|=:\alpha [/mm]
[mm] \alpha [/mm] eine reelle Zahl.
> Eigentlich bin ich nachwievor mit ein paar einfachen
> "Interpretationen" verwirrt. Ich google seit Tagen und
> finde nix zu ueberbestimmten Systemen - deprimierend :-(
> Das meiste findet sich zu zu nxn Systemen.
Ja, denn das wird sofort mit bekannten Sätzen der Linearen
Algebra motiviert. Die Beweise dazu erspart man sich dann.
> Ich finde tonnenweise was ich weiss, z.B. "Wenn Zeilen und
> Spalten linear unabhaengig sind existiert eine Loesung".
Ja.
> Kann man sowas aehnliches nicht auch fuer MxN, M>N Matrizen
> sagen?
> Ich habe z.B. eine Stelle gefunden da heisst es "Die
> Konditionszahl ist ein Mass dafuer wie stark die
> Zeilenvektoren vom Idealfall Orthogonalitaet abweichen".
> Ich verstehe das aber aus mehreren Gruenden nicht: Sind es
> wirklich die Spalten- oder die Zeilenvektoren?
Zeilenvektoren.
> In der Wikipedia finde ich dazu eine gute graphische
> Interpretation
> http://en.wikipedia.org/wiki/Overdetermined_system mit dem
> traurigen Text "The informal discussion of constraints and
> degrees of freedom above relates directly to these more
> formal concepts.".
>
> Im Wikipedia Beispiel z.B. ist "#5" das erstrebenswerteste
> - alle Vektoren treffen sich moeglichst in einem Punkt. Was
> wiederum heisst die Vektoren (Zeilenvektoren??) sollten
> moeglichst linear unabhaengig zueinander sein. Ist das die
> richtige Interpretation?
Ja. Dabei existiert eine Lösung, falls die Anzahl der un-
abhängige Zeilenvektoren größer ist als die Anzahl der Un-
bekannten.
> Allerdings verstehe ich nicht wieso das genug sein soll -
> in "#1" sind die Vektoren auch sehr linear unabhaengig und
> trotzdem ist der Fehler tendentiell gross, da sie sich
> nicht im gleichen Punkt treffen. Was konkret sagen mir also
> [2 ; -3 ; -1] bzw. [1;1;1] und [2,1] bzw. [-3,1] bzw.
> [-1,1] ?
Du hast bei diesem Beispiel drei Lösungen und zwei Unbekannte.
Ist nun die Anzahl der unabhängigen Zeilenvektoren kleiner als 2?
> Es muss doch irgendwie moeglich sein aufgrund der
> Eigenschaften (lineare Abhaengkeit etc) der Spalten
> und/oder Zeilenvektoren etwas ueber die Stabilitaet des
> Systems auszusagen, oder?
Eine Aussage darüber kann man i.A. nur bei quadratischen
Matrizen machen. Ansonsten muss man immer unterscheiden.
Du betrachtest eine [mm] $n\times [/mm] m$ Matrix mit [mm] $n\ge [/mm] m$. Du
müsstest dir nun genau anhand der Anzahl der Unbekannten
überlegen was gilt.
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:25 Mi 26.02.2014 | | Autor: | cosPhi |
Ich moechte mich nochmal bei dir/euch fuer eure Geduld bedanken.
Nach mehreren Wochen hab ich nun ENDLICH gefunden nach was ich gesucht habe: Das ganze scheint worum auch immer kein klares mathematisches Gebiet zu sein sondern eher Systemtheorie. Das Problem wird "optimal sensor placement" gennant und ist 1:1 (!) das von dem ich gesprochen habe. Ein weiteres nuetzliches Zauberwort ist "Frame Theory". Hier geht es ja eben nicht um eine orthogonales Basis sondern um ein orthogonales Set mit Redundanz - ein Frame.
Die richtige Antwort ist fast gleich wie von mir vermutet: Die Zeilenvektoren muessen moeglichst orthogonal sein (und eben nicht die Spaltenvektoren).
Die Ansaetze zur Loesung sind relativ aehnlich wie von mir vorgeschlagen/vermutet: z.B. Minimierung der Summe der Innenprodukte fuer alle moeglichen Kombinationen. Da dies aber exponentieller Arbeitsaufwand ist, gibt es dazu polynomielle Algorithmen (konvexe Optimierung, Greedy Algorithmen und heuristische Algorithmen).
Wie gesagt, wir ging es ohnehin nie um die eigentliche Loesung sondern nur um zu verstehen was ich "minimieren" soll, da ich die Struktur der Matrix ja kenne.
|
|
|
|
