Hilbert Matrix < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Wie nutzt mir eine Hilbert Matrix zum lösen eines linearen Gleichungssystems? |
Wie kann ich in Matlab eine Hilbert Matrix dazu benutzen ein Gleichungungsystem der Form Ax=b zu lösen.
wenn A quadratisch ist.
Ich habe mich auch schon belesen wie die Hilbert Matrix aussieht aber ich komme nicht dahinter wie ich das anstelle
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:21 Do 01.04.2010 | | Autor: | Blech |
Hi,
bist Du Dir wirklich sicher, daß Du ein LGS mit *Hilfe* der Hilbertmatrix lösen sollst.
Ich kenne die Hilbertmatrix nur als Testfall, den man von verschiedenen Verfahren lösen läßt, weil die Matrix so schön schrecklich konditioniert ist und die exakte Inverse einfach zu berechnen ist.
Sonst wäre es hilfreich, A zu kennen.
ciao
Stefan
|
|
|
| |
|
| Aufgabe | | Lösung des Richardson Verfahrens |
Also ich habe ein Gleichungssystem Ax=b mit dem Richardson Verfahren gelöst nur konvergiert es bei zuvielen Iterationen-->Laufzeit zu groß...
Ich war der Meinung das man das Problem mit Hilfe der Hilbert Matrix lösen kann...
gut möglich das ich mich geirrt habe. Fällt dir noch eine Möglichkeit ein die Lösung zu verbessern (das Gl ist Unterbestimmt). Ich versuche gerade die For schleife umzuwandel. Die meiste Zeit nimmt die umwandlung in Eigenwerte (zum berechnen des optimalen Relaxationsparameter und die Forschleife in Anspruch. Hast du eine Idee wie die Genauigkeit noch verbessert werden kann?
|
|
|
| |
|
Hallo melchior2K,
Bevor Du anfängst für die Bestimmung von Relaxationsparametern Eigenwerte zu berechnen würde ich mal einen anderen(bzw. einen direkten statt iterativen) Löser für Gleichungssysteme vorschlagen - z.B. Orthogonalisierung mittels Householder-Spiegelungen. Das sollte wohl effektiver sein als Eigenwerte zu bestimmen.
viele Grüße
mathemaduenn
|
|
|
| |
|
| Aufgabe | | Versuch der besten Lösung des Gl zu finden |
Ich habe es schon auf direktem Weg versucht...mit QR Zerlegung...das ist mir auch gelungen...mit Richardson hatte ich auch erfolg nur konvergiert das Verfahren erst bei einer großen Anzahl an Iterationen und es wird zu langsam...hat jemand ne Idee wie man das optimieren kann...Ich habe gelesen das Mehrgitterverfahren sehr gut sein sollen...ich habe auch Literatur dazu gelesen nur leider verstehe ich es nicht. könnte mir jemand einen Ansatz geben.
Man kann ein Iterationsverfahren verwenden und es auf mehreren Gitterebenen anwenden...ich hab nur keine Ahnung wie ich es umsetze...
|
|
|
| |
|
Hallo melchior2K,
> Versuch der besten Lösung des Gl zu finden
> Ich habe es schon auf direktem Weg versucht...mit QR
> Zerlegung...das ist mir auch gelungen...
Dies sollte eigentlich auch der beste Weg sein falls der Aufwand nicht zu hoch ist(große GS mit deutlich mehr als 1000 Unbekannten). Falls dies nicht genau genug ist sollte man eher überlegen, ob die Kondition der Problemstellung verbessert werden kann.
> mit Richardson
> hatte ich auch erfolg nur konvergiert das Verfahren erst
> bei einer großen Anzahl an Iterationen und es wird zu
> langsam...hat jemand ne Idee wie man das optimieren
> kann...
Das festlegen des optimalen Relaxationsparameters über die Eigenwerte ist eigentlich nur eine theoretische Überlegung die praktisch keinen Sinn macht(da zu langsam).
> Ich habe gelesen das Mehrgitterverfahren sehr gut
> sein sollen...ich habe auch Literatur dazu gelesen nur
> leider verstehe ich es nicht. könnte mir jemand einen
> Ansatz geben.
>
> Man kann ein Iterationsverfahren verwenden und es auf
> mehreren Gitterebenen anwenden...ich hab nur keine Ahnung
> wie ich es umsetze...
Mehrgitterverfahren sind, soweit ich mich erinnere nur im Zshg. mit numerischem Differentialgleichungslösen zu verwenden. Besser konvergente iterative Verfahren wären Gaus-Seidel oder Jacobiverfahren ggf. mit Äquilibrierung. Falls die Genauigkeit beim Lösen mittels QR-Zerlegung nicht ausreicht sollte man aber wie gesagt eher nochmal auf das Problem schauen.
viele Grüße
mathemaduenn
|
|
|
| |
|
| Aufgabe | | Warum konvergiert Gausseidel bei mir nicht und wie meinst du das mit QR zerlegung bei Gaussseidel |
A: hat die Dimensionen 2250*2250
b: hat die Dimensionen 2250:1
D = diag(diag(Atest));
[L,U]=lu(Atest);
xstart=zeros(2250,1);
Tg = -inv(D-L)*U;
cg = inv(D-L)*b;
for i=1:1:100
XX =( Tg*xstart + cg);
xstart=XX;
figure(3)
xdiff=abs(x-XX);
plot(xdiff);
end
In einem Buch habe ich diese Kösung für Gausseidel gefunden und umgesetzt...nur konvergiert das Verfahren überhaupt nicht...also die Lösung ist fürn A....bein dem richardson Verfahren habe ich einfach den Startvektor vom Ergebnis der Qr Zerlegung genommen und das Ergenis ist um 40% besser geworden nur reicht das immer noch nicht aus.
Könntest du mir bitte einen Tip für das Gausseidel Verfahren geben.
Vielleicht noch interessant ist das ich mit der transponierten von A multipliziert habe da das System unterbestimmt war-->um es quadratisch zu machen...
Mfg Sebastian....danke für deine mühen und die Zeit die du immer auf dich nimmst
|
|
|
| |
|
HAllo melchior2K,
> Warum konvergiert Gausseidel bei mir nicht und wie meinst
> du das mit QR zerlegung bei Gaussseidel
Wenn die Genauigkeit der QR Zerlegung nicht ausreicht nehme ich an, dass A [mm] \not= [/mm] Q*R gilt. Dann kann man ein iteratives Verfahren wie oben mit Tg=inv(Q*R)*(Q*R - A) und cg=inv(Q*R)b aufsetzen.
Das wäre dann ein Splitting-Verfahren wie auch Gauss-Seidel, hat aber sonst nichts damit zu tun.
> A: hat die Dimensionen 2250*2250
> b: hat die Dimensionen 2250:1
> D = diag(diag(Atest));
>
> [L,U]=lu(Atest);
Hier kommt bei ![[]](/images/popup.gif) matlab eine Faktorisierung raus Atest=L*U Du bräuchtest aber eine Zerlegung Atest =L+U
>
>
> xstart=zeros(2250,1);
> Tg = -inv(D-L)*U;
> cg = inv(D-L)*b;
> for i=1:1:100
>
> XX =( Tg*xstart + cg);
> xstart=XX;
> figure(3)
> xdiff=abs(x-XX);
> plot(xdiff);
> end
>
>
> In einem Buch habe ich diese Kösung für Gausseidel
> gefunden und umgesetzt...nur konvergiert das Verfahren
> überhaupt nicht...also die Lösung ist fürn A....bein dem
> richardson Verfahren habe ich einfach den Startvektor vom
> Ergebnis der Qr Zerlegung genommen und das Ergenis ist um
> 40% besser geworden nur reicht das immer noch nicht aus.
> Könntest du mir bitte einen Tip für das Gausseidel
> Verfahren geben.
> Vielleicht noch interessant ist das ich mit der
> transponierten von A multipliziert habe da das System
> unterbestimmt war-->um es quadratisch zu machen...
Unterbestimmt -> d.h. abhängige Lösungen oder doch überbestimmt?? Um die Genauigkeit zu erhöhen sollte man das mit dem multiplizieren in jedem Fall lassen, da man eine QR-Zerlegung mit Householder auch auf die nicht quadratische Matrix anwenden kann und beim multiplizieren Genauigkeit verloren geht.
Welches zugrundeliegende Problem soll denn eigentlich gelöst werden?
viele Grüße
mathemaduenn
P.S.: noch ein tipp wenn Du bei matlab cond(Atest) berechnen lässt und da kommen sehr hohe Zahlen raus, dann haben die meisten Lösungsverfahren Probleme.
|
|
|
| |
|
| Aufgabe | | Die Dimensionen stimmen nicht! |
Also es handelt sich um die Rekonstruktion von Tsunamiparametern...
eigentlich ist A (183,2250) groß aber wenn ich mit der Transponierten von A multipliziere komme ich auf (2250,2250)
und b=(183,1) mit A' =("2250,183)
dann kann ich auch die Splitting Verfahren anwenden aber sonst stimmen die Dimensionen nicht überein weil am Ende (2250,1) rauskommen muss...aber ich weis nicht wie ich effektiv das unterbestimmte System löse mittels Qr zerlegung habe ich schon eine gute Lösung bekommen.
A=L+U habe ich mittels tril(A) und triu(A) gemacht aber dann stimmen beim Anwenden die Dimension nicht mehr weil diagonalmatrix nur noch 183*183 ist...
ich habe auch mal Cond angewendet
A=240
A'*A=23e10 also eher nicht sogut wenn man multipliziert aber ich habe sonst keine idee du sagstest householder...aber da kann ich doch auch tril und triu nehmen...funktioniert jedenfalls...
Ich werde weiter dran bleiben...aber wenn du noch eine Idee hättest wäre ich dir sehr verbunden
Mfg Basti
|
|
|
| |
|
Hallo Basti,
Jetzt hab ich's glaub ich verstanden. Du hast versucht bei deinem unterbestimmten System alle x auszurechnen. Das geht nicht daher ist auch A^TA eigentlich singulär. Das Du trotzdem was rausbekommst liegt nur an der Rechenungenauigkeit bei der Berechnung von A^TA. Eigentlich kannst Du nur 183 [mm] x_i [/mm] in Abhängigkeit der anderen 2067 [mm] x_i [/mm] bestimmen. Jetzt wäre die Frage ob du [mm] x_i [/mm] kennst und festlegen kannst oder was Du genau auflösen willst. Alle [mm] x_i [/mm] zu bestimmen geht nicht.
viele Grüße
mathemaduenn
|
|
|
| |
|
| Aufgabe | | welche möglichkeiten hab ich noch |
Also ich kenne A und b und ich soll x bestimmen...mit dem Qr Verfahren und richardson stehe ich schon gut da...aber gut reicht ja bekanntlich nicht...besteht die Möglichkeit mit einem Glättungsverfahren mein Ergebniss zu glätten? weil ich 2 ausreißer drin habe die das Ergebnis ca. um 20% schlechter machen. Also ich erläutere dir das mal vielleicht hast du noch eine andere Idee also. auf dem Festland stehen 61 gps Sensoren die jeweils eine Verschiebung in x y und z messen also nicht die pos nur die Verschiebung. aus dem grund ist b 183,1 vor die Küste wurde ein gedachtes Raster mit 2250 Rechtecken gelegt. jedes Rechteck wirkt sich mit einem gewissen Wert auf die Sensoren aus.Das heist wenn ein Erdbeben im gange is findet eine verschiebung der rechtecke statt und ich soll den schlupf ausrechnen. Ich habe auch das Ergenis gegeben welches heraus kommen soll deswegen sehe ich ja wie nah ich dran bin.
Mein Gedanke ist: A ist ziemlich dünn besetzt hab mal Sparse(A) gemacht da sind meist pro Zeile nur 2-5 Werte ...hilft mir das nicht weiter kann man nicht ein Verfahren ansetzen das Zeilenweise schaut....wenn ich da nur ein A pro zeile habe müsste das doch die Sache vereinfachen...bzw. warum kommt bei Gausseidel nur Müll raus und bei richardson ein gutes Ergebnis?...ich werde mich nochmal an die LU zerlegung heranwagen und dann mittels splitting verfahren versuchen das was zu erreichen...ich habe mir auch gedacht wenn ich A nicht mit A transponiert multipliziere sondern mit einer zufälligen Matrix die sich besser eignet müssten doch auch bessere Ergenisse herauskommen...die Frage ist nur wie die aussehen muss...ich habe gelesen das Splitting verfahren auch mit iterativen methoden arbeiten nur auf mehreren Ebenen-->verstanden habe ich das ganze nur noch nicht....wie sollte xstart gewählt werden? ich finde das spielt auch eine große rolle ob ich zeros(2250,1) nehme oder das Ergeniss von der Qr zerlegung ist schon ein Unterschied... das eine konvergiert nach 100 iterationen zu einem guten Ergeniss das andere ist aber bei 10000 besser...warum ist das so?....bzw wie kann ich eine höhere Geschwindigkeit erreichen das 10000 iterationschritte keine 4mins dauern sondern nur 30 sec....die Berechnung der Eigenwerte nimmt viel Zeit in Ansruch...gibts da eine Möglichkeit der Optinierung?
Mfg Basti
|
|
|
| |
|
Hallo Basti,
Du bekommst unterschiedliche Ergebnisse, weil Deine Ergebnisse in gewisser Weise einen zufälligen Anteil haben, wenn Du mehr Unbekannte als Gleichungen hast und trotzdem alle Unbekannten ausrechnen willst.
Da kannst Du statt [mm] $A^T$ [/mm] eine andere Matrix nehmen oder einen Kopfstand machen das wird nicht besser 
Du brauchst mehr Gleichung oder weniger Variablen für dein System. Zum Beispiel könntest Du versuchen Abhängigkeiten zwischen den Rechtecken zu suchen bzw. zu modellieren oder eben weniger Rechtecke zu benutzen.
viele Grüße
mathemaduenn
|
|
|
| |
|
| Aufgabe | | Warum konvergiert das zyklische Richardson Verfahren nicht so gut? |
Ich habe versucht am zyklischen richardson Verfahren etwas herumzubasteln...aber wenn sich der relaxionsfaktor bei jedem Schritt ändert bekomme ich nicht so gute Werte als würde ich jedes mal den optimalen nehmen...aber eigentlich soll es besser konvergieren... es scheint auch einen Wendepunkt zu geben...bei dem sich das Verfahren von der guten Lösung wieder entfernt...wenn man da ansetzen würde und den relaxationsparameter an dem Punkt verändert könnte noch etwas drin sein...ich werde versuchen abhänigkeiten zwischen den rechtecken festzustellen und diese vielleicht zusammen zufassen das ich auf 183 komme oder so mal schaun...
|
|
|
| |
|
Hallo Basti,
> Warum konvergiert das zyklische Richardson Verfahren nicht
> so gut?
> Ich habe versucht am zyklischen richardson Verfahren etwas
> herumzubasteln...aber wenn sich der relaxionsfaktor bei
> jedem Schritt ändert bekomme ich nicht so gute Werte als
> würde ich jedes mal den optimalen nehmen...aber eigentlich
> soll es besser konvergieren... es scheint auch einen
> Wendepunkt zu geben...bei dem sich das Verfahren von der
> guten Lösung wieder entfernt...wenn man da ansetzen würde
> und den relaxationsparameter an dem Punkt verändert
> könnte noch etwas drin sein...
Wie gesagt ich denke das dies eine Sackgase ist. Du kannst eine singuläre Matrix nicht lösbar machen. Ein System sollte erstmal theoretisch lösbar sein bevor man eine numerische Lösung versucht.
> ich werde versuchen
> abhänigkeiten zwischen den rechtecken festzustellen und
> diese vielleicht zusammen zufassen das ich auf 183 komme
> oder so mal schaun...
So sollte es wohl weitergehen.
Grüße
mathemaduenn
|
|
|
| |
|
Hallo Basti,
> welche möglichkeiten hab ich noch
> Also ich kenne A und b und ich soll x bestimmen...mit dem
> Qr Verfahren und richardson stehe ich schon gut da...aber
> gut reicht ja bekanntlich nicht...besteht die Möglichkeit
> mit einem Glättungsverfahren mein Ergebniss zu glätten?
> weil ich 2 ausreißer drin habe die das Ergebnis ca. um 20%
> schlechter machen. Also ich erläutere dir das mal
> vielleicht hast du noch eine andere Idee also. auf dem
> Festland stehen 61 gps Sensoren die jeweils eine
> Verschiebung in x y und z messen also nicht die pos nur die
> Verschiebung. aus dem grund ist b 183,1 vor die Küste
> wurde ein gedachtes Raster mit 2250 Rechtecken gelegt.
> jedes Rechteck wirkt sich mit einem gewissen Wert auf die
> Sensoren aus.Das heist wenn ein Erdbeben im gange is findet
> eine verschiebung der rechtecke statt und ich soll den
> schlupf ausrechnen. Ich habe auch das Ergenis gegeben
> welches heraus kommen soll deswegen sehe ich ja wie nah ich
> dran bin.
>
> Mein Gedanke ist: A ist ziemlich dünn besetzt hab mal
> Sparse(A) gemacht da sind meist pro Zeile nur 2-5 Werte
Wenn die 183 Zeilen jeweils nur mit 2-5 Werten besetzt sind heißt das auch, das gar nicht alle Variablen einen Einfluß haben. Einige müssten ausschließlich mit Nullen multipliziert werden - Die könntest Du schonmal weglassen.
Grüße
mathemaduenn
|
|
|
| |
|
Vielen Dank für deine Hilfe ich denke den Rest schaffe ich alleine
ich habe nur noch ein paar allgemeine Fragen.
Ich werde jetzt ein paar Begriffe definieren könntest du mir bitte sagen ob das in etwa stimmt.
Eigenwerte: sind die Nullstellen einer Matrix
Relaxationsparamter: steigert die Konvergenz...ich verändere die Matrix aber nicht das Ergebnis...wie kann man das in einem Satz ausdrücken?
Wozu Splitting Verfahren: um nicht invertieren zu müssen und ein iteratives Verfahren zu kreiern. Umwandeln in ein Fixpunkt Problem
Vorteile direkte Verfahren: endliche Anzahl an berechnungsschritten
multiplizieren mit der Transponierten: Kondition der Matrix wird schlecht-->Ergebnis wird ungenauer...
Mit freundlichen Grüßen
Basti
|
|
|
| |
|
Hallo Basti,
> Vielen Dank für deine Hilfe ich denke den Rest schaffe ich
> alleine
Schön.
> ich habe nur noch ein paar allgemeine Fragen.
> Ich werde jetzt ein paar Begriffe definieren könntest du
> mir bitte sagen ob das in etwa stimmt.
>
> Eigenwerte: sind die Nullstellen einer Matrix
Nein. Dann wären sie ja Lösung der Gleichung Ax=0 und das sind sie nicht.
> Relaxationsparamter: steigert die Konvergenz...ich
> verändere die Matrix aber nicht das Ergebnis...wie kann
> man das in einem Satz ausdrücken?
Man verändert die Iterationsmatrix, aber nicht den Fixpunkt. ->anderes Verfahren(mit anderen Konvergenzeigenschaften) - gleiche Lösung.
> Wozu Splitting Verfahren: um nicht invertieren zu müssen
> und ein iteratives Verfahren zu kreiern. Umwandeln in ein
> Fixpunkt Problem
In etwa ja. Invertieren sollte man sowieso nie, da dabei Genauigkeit verloren geht und der Aufwand steigt. Lieber Faktorisieren und danach direkt lösen. Matlab macht meiner Meinung nach auch wenn Du x=A/b verwendest. Da kannst Du aber auch nochmal in derHilfe schauen.
> Vorteile direkte Verfahren: endliche Anzahl an
> berechnungsschritten
Ja. Konvergenzbetrachtungen fallen weg. Meist lohnen sich iterative Verfahren nur bei sehr großen und/oder dünn besetzten Matrizen.
> multiplizieren mit der Transponierten: Kondition der Matrix
> wird schlecht-->Ergebnis wird ungenauer...
Das stimmt formal immer. Im speziellen Fall hier wurde durch die Multiplikation eine singuläre Matrix (Die Kondition ist eigentlich unendlich) erzeugt, da A unterbestimmt ist.
viele Grüße
mathemaduenn
|
|
|
| |
|
Hallo,
Da man die Inverse der Hilbertmatrix herausfinden kann, könnte man diese im Rahmen eines Splitting-Verfahrens nutzen falls die zu Invertierende Matrix sehr ähnlich ist. Aber ich weiß nicht ob das wirklich sinnvoll wäre.
viele Grüße
mathemaduenn
|
|
|
|
