Extremaberechnung wie ich sie noch nie machen musste |
22.11.2006, 15:14 | Paul_H | Auf diesen Beitrag antworten » | ||||
Extremaberechnung wie ich sie noch nie machen musste ich soll ein (globales) Extremum der Funktion bestimmen so, dass für und positiv definit und symmetrisch. Hab echt keine Ahnung, wie ich da an die Sache rangehen soll. Tipps? |
||||||
22.11.2006, 15:53 | InfoStudent | Auf diesen Beitrag antworten » | ||||
Hm, ich hab die Aufgabe etwas anders verstanden, und zwar sollte du grade zeigen, das x* mit Ax*= b das einzige Extremum von f ist. Allerdings bin ich dann auch nicht weiter als du, denn ich weiß absolut nicht, wie man diese Gleichung nach x differenziert. |
||||||
23.11.2006, 16:31 | Paul_H | Auf diesen Beitrag antworten » | ||||
Vielleicht wäre ein Ansatz, den Teil als eine Bilinearform zu betrachten. Da A positiv definit und symmetrisch, wäre so eine Bilinearform auf jeden Fall gegeben. Aber ich wüßte dann immer noch nicht weiter, denn der Vektor x wäre dann ein Koordinatenvektor und müsste für unsere Bilinerform noch durch einen nicht gegebenen Isomorphismus gejagt werden. Oder irre ich mich da? Der Rest der Funktion wäre dann jedenfalls ohne Probleme differenzierbar. |
||||||
23.11.2006, 17:48 | kingskid | Auf diesen Beitrag antworten » | ||||
Hi, ich glaub das ganze hat was mit dem Abstiegsverfahren (Gradientenverfahren) zu tun, oder? also am besten du schreibst dir deine Funktion mal als Summe auf: wenn diese funktion nun in x* ein lokales extremum haben soll, muss weiter gelten, dass der Gradient d.h. du könntest mal die Ableitung betrachten. (wenn dir das zu viel Indizes-gewurschtel ist, kannst du den gradienten auch mit folgenden regeln bilden: und . ) dann musst du natürlich noch überprüfen, ob die Hessematrix positiv definit ist, um zu zeigen, dass wirklich ein Minimum vorliegt. Das coole was dabei rauskommt, ist, dass also die Lösung des LGS Ax=b mit der Minimalstelle der Fuktion übereinstimmt! viele grüße |
||||||
23.11.2006, 18:03 | tigerbine | Auf diesen Beitrag antworten » | ||||
Würde auch sagen, dass das der erste Schritt zum CG-Verfahren ist Hier steht auch ein bischen was http://de.wikipedia.org/wiki/CG-Verfahren Beim Beweis der Äquivalenz der Probleme Min! f <=> Löse Ax=b! gibt es einen Trick: Hilfsfunktion .... Da A als SPD-Matrix regülar ist, existiert die eindeutige Lösung x* von Ax-b =0 Noch folgern dass, minimierung von g und f äquivalent sind fertig |
||||||
24.11.2006, 19:22 | InfoStudent | Auf diesen Beitrag antworten » | ||||
@Kingskid: Danke, Rechenfehler in meiner Summeinschreibweise gefunden. ^^ @Tigerbine: Wie genau soll mir g(x) weiterhelfen, um g zu minimieren müsste ich es ja auch noch ableiten oder meinst du: "Noch folgern dass, minimierung von f und Nullstellen von g äquivalent sind."? Schonmal thx an für die Antworten! |
||||||
Anzeige | ||||||
|
||||||
25.11.2006, 09:28 | tigerbine | Auf diesen Beitrag antworten » | ||||
f und g unterscheiden sich nur durch einen konstanten Term A,b sind bekannt Ich habe dir dann g schon so umgeformt hingeschrieben, wie du es brauchst. Bedenke mit A ist auch die Inverse eine SPD Matrix. dann steht doch da so was in Klannern ()^T A^{-1} ()... Geht jetzt das Licht auf? Kann das denn negativ werden? Wann kann das Null werden Genau dann, wenn x das LGS Ax = b löst. SPD heist Symmetrisch positiv definit und gibt nicht meine politische Orientierung wieder Gruß tigerbine Die Ableitungen kommen erst später, wenn man die Frage beantworten will, wie man das Minimum (dessen Existenz und Eindeutigkeit wir eben gezeigt haben, denn SPD Matrizen sind regülar) bestimmt. Da kommt dann der Gradient ins Spiel, wie oben schon gepostet. Nur müsst Ihr Euch noch entscheiden, was jetzt eigentlich die Aufgabe st. Da wiedersprecht ihr Euch ja ein bischen. Wenn man dann x* bestimmen will, läuft das auf das GRadienten Verfahren und schließlich das Conjugate Gradient Verfahren raus. Könnt ja mal danach googlen. Im Grunde sind diese Beweise geprägt von stänigen umformulieren des Problems und deren Lösungen. x* löse! Ax=b <=> x* min! f(x) ... Wahl der Abstiegsrichtungen (orthogonal)... Probelm der Langsamen Konvergenz (siehe Satz von Kantorowitsch) ... Wahl von A-orthogonalen Richtungen ... Krylow-Räume ...Konstruktion eines Polynoms... Die Bestimmung von x* ist in m <= n Schritten möglich, wobei m die verschiedenen Eigenwerte der nxn Matrix A sind. Sorry, heute ohne latex, bin in Eile . Gruß |
||||||
25.11.2006, 17:23 | kingskid | Auf diesen Beitrag antworten » | ||||
...also ich find dass es ohne hilfsfunktion einfacher & schneller geht... oder was ist der vorteil davon? |
||||||
26.11.2006, 20:08 | tigerbine | Auf diesen Beitrag antworten » | ||||
Die Hilfsfunktion liefert mir ohne Ableitungen zu berechen das gewünschte ERgebnis: Existenz und Eindeutigkeit des Minimums x* von f (bzw. g) ist äquivalent zur Existenz und Eindeutigkeit der Lösungs x* des LGS Ax = b. Da ich über die Matrix weiss, das sie als SPD MAtrix regular ist, ist die Existenz und eindeutigkeit der Lösung x* im LGS gesichert, also auch in den Funktionen f und g. Also brauche ich
nicht. Desweiteren hasst Du
Dieser Ansatz dient eher der Konstruktiven Berechnung der Lösung x*, nicht dem Beweis ihrer Existenz. |
||||||
27.11.2006, 11:29 | kingskid | Auf diesen Beitrag antworten » | ||||
hi tigerbine, danke für deine erklärung... hm schade eigentlich... aber wenn ich gezeigt hab, dass die Funktion bei Ax-b= 0 minimal wird, dann ist das doch äquivalent zur Lösung des LGS Ax=b, oder? mit der existenz und eindeutigkeit versteh ich das noch nicht so ganz. ein minimum ist doch so definiert: gradient = 0, hessematrix pos.def. wenn ich das durch die "rechnung" gezeigt hab, wieso kann es dann trotzdem sein, dass gar kein minimum existiert oder dass es nicht eindeutig ist? *etwasverwirrtbin* viele grüße kingskid |
||||||
27.11.2006, 18:34 | tigerbine | Auf diesen Beitrag antworten » | ||||
Erstmal eine kurze Antwort...war ein langer Tag heute. Also ob nun x* löst Ax-b = 0 oder Ax=b ist egal. Es geht nur aus deinem Post nicht hervor dass du bewiesen hast: x* löst Ax = b <=> x* minimiert f(x), mit f wie gepostet. Vielleicht habt ihr das (also deb Weg zum GV oder CGV) ja anders aufgeschrieben als wir. Unser Arbeitsplan war so: - I Gesucht Lösung x* von Ax = b mit A = SPD-Matrix -> Lösung x* existiert und ist eindeutig, da A regulär ist - Lösung von Problem I ist äquivalent zur Lösung von Problem II: x* minimiert die Funktion g -> x* minimiert die Funktion f Problem I <=> Probelm II Ich habe eben die Existenz und eindeutigkeit der Lösung x* mittels Probelm I geziegt, Du willst es mit II zeigen. Geht beides. Nur fehlt bei dir eben noch der beweis, dass die beiden Probleme äquivalent sind. dass hast Du nur als Bemerkung hingeschrieben - siehe letzes Zitat. Gruß |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|