Newtonverfahren (mehrdim.) < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:20 Mi 25.01.2012 | | Autor: | T65 |
Hallo,
ich möchte für eine Funktion, die von 4 Variablen abhängt, maximieren. Dazu muss ich den Gradienten der Funktion =0 setzen. Da in allen partiellen Ableitungen noch alle 4 Variablen (nichtlinear) miteinander verknüpft sind, kann ich dies nur mithilfe des Newtonverfahrens lösen.
Dazu habe ich die Jacobi-Matrix aufgestellt.
Das zu lösende Gleichungssystem ist dann:
Die Jacobimatrix * VektorX = - Gradient
Setze ich den Anfangsvektor ein, bekomme ich einen VektorX. Damit rechne ich die nächsten Werte aus: Anfangsvektor + VektorX = neuer Vektor.
Die Werte des neuen Vektors setze ich dann wieder in das Gleichungssystem ein und bekomme einen neuen VektorX usw.
Damit müsste ich mich doch eigentlich an die Werte, für die ich eine Nullstelle des Gradienten bekomme, annähren. Der Betrag des VektorsX müsste ja immer kleiner werden.
Bei mir wird er immer größer, auch wenn ich für die neuen Werte den Vektor von den Anfangswerten abziehe.
Was mache ich falsch?
Vielen Dank für die Hilfe!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
T65
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:52 Mi 25.01.2012 | | Autor: | Marcel |
Hallo,
> Hallo,
> ich möchte für eine Funktion, die von 4 Variablen
> abhängt, maximieren. Dazu muss ich den Gradienten der
> Funktion =0 setzen. Da in allen partiellen Ableitungen noch
> alle 4 Variablen (nichtlinear) miteinander verknüpft sind,
> kann ich dies nur mithilfe des Newtonverfahrens lösen.
>
> Dazu habe ich die Jacobi-Matrix aufgestellt.
> Das zu lösende Gleichungssystem ist dann:
> Die Jacobimatrix * VektorX = - Gradient
> Setze ich den Anfangsvektor ein, bekomme ich einen
> VektorX. Damit rechne ich die nächsten Werte aus:
> Anfangsvektor + VektorX = neuer Vektor.
> Die Werte des neuen Vektors setze ich dann wieder in das
> Gleichungssystem ein und bekomme einen neuen VektorX usw.
>
> Damit müsste ich mich doch eigentlich an die Werte, für
> die ich eine Nullstelle des Gradienten bekomme, annähren.
> Der Betrag des VektorsX müsste ja immer kleiner werden.
> Bei mir wird er immer größer, auch wenn ich für die
> neuen Werte den Vektor von den Anfangswerten abziehe.
>
> Was mache ich falsch?
ich kapier' zum einen nicht, wieso Du so vorgehen dürfen solltest, wie Du es tust. Schreib' das ganze doch mal mit der rekursiven Newtonfolge auf, und unterlasse dabei Wörter wie "müsste, sollte, eigentlich" - das zeigt nur, dass Dir selbst noch nicht klar ist, ob Deine Vorgehensweise funktioniert oder warum sie funktionieren sollte.
Und zum anderen: In Heusers Analysis II findest Du z.B. in Satz 189.2 mögliche Voraussetzungen zur Anwendung des Newtonverfahrens im mehrdimensionalen. Sicher kann man die abschwächen. Mit Deiner obigen Beschreibung bleibt man aber völlig im Unklaren drüber, ob Du überhaupt das Newton-Verfahren anwenden kannst/darfst:
Schreib' doch mal bitte, wie die Funktion aussieht, also inklusive Definitions- und Zielbereich und alle Voraussetzungen/Eigenschaften der Funktion, die Du kennst bzw. derer Du Dir sicher bist!
Da man dort mit der Invertierbarkeit der - dort - quadratischen Jacobimatrix bei der Newtonfolge arbeitet, bringt Dir der Satz natürlich nicht wirklich was. Aber vielleicht schaust Du mal rein, warum man dort sowas wie dieser Invertierbarkeit der Jacobimatrix hat, warum das "dort" also was bringt. Und vielleicht erkennst Du dann, dass Dein Verfahren nix taugt, oder kannst wenigstens begründen, warum Du vermutest, dass es was taugt...
Ich kapier' jedenfalls nicht, wie Du auf Deinen "Algorithmus" gekommen bist und wieso der was bringen sollte...
P.S.:
Wenn $f: [mm] \IR^4 \to \IR$ [/mm] ist, dann ist doch die Jacobimatrix [mm] $J_f$ [/mm] keine $4 [mm] \times [/mm] 4$-Matrix, sondern wieder ein Vektor... je nach Definition des Gradienten ist [mm] $J_f$ [/mm] gerade selbst der Gradient oder "Gradient transponiert". Also: Was machst Du da oben eigentlich wirklich? Rechnest Du etwa mit der Hesse-Matrix?
Edit: Mittlerweile hab' ich's kapiert: Man hat eine Funktion [mm] $\IR^4 \to \IR\,,$ [/mm] von dieser sucht man Extremstellen (in meinem verwirrten Kopf dachte ich, dass man von dieser Nullstellen suche... daher der Quatsch von mir da oben). Die "Gradientenfunktion" (Ableitung(sfunktion)) ist dann eine Funktion [mm] $\IR^4 \to \IR^4\,,$ [/mm] und deren Nullstellen sind natürlich Kandidaten für Extremstellen der Ausgangsfunktion. D.h. man wendet das Newtonverfahren nun "auf die Ableitung" an. Das macht so auf jeden Fall alles erstmal Sinn!! Sorry, falls ich jemanden mitverwirrt habe ^^
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 22:38 Mi 25.01.2012 | | Autor: | T65 |
Danke für deine Mühe erstmal. Ich hoffe folgende Informationen können dir helfen, besser zu verstehen, was ich mache.
Meine Funktion ist:
f(De, Di, h0, t)= [mm] (A*t^{4}/(K*De^{2})*s/t*((h0/t-s/t)*(h0/t-s/(2*t))+1) [/mm] - [mm] B)^{2}. [/mm]
Dabei gilt: De, Di, h0, t > 0
A, B, K und s sind Konstant und > 0 und bekannt.
Diese will ich minimieren
also:
[mm] g1=\partial f/\partial [/mm] De = 0;
[mm] g2=\partial f/\partial [/mm] Di =0;
[mm] g3=\partial f/\partial [/mm] h0 =0;
[mm] g4=\partial f/\partial [/mm] t =0;
Jetzt wende ich das Newtonverfahren für vektorwertige Funktionen an, das laut Meyberg-vachenauer (18.4.3) folgendermaßen aussieht:
(Vektoren sind fett):
Jg ( [mm] x_{k} [/mm] [mm] )\Delta [/mm] [mm] x_{k} [/mm] = - g ( [mm] x_{k} [/mm] )
[mm] x_{k+1} [/mm] = [mm] x_{k} [/mm] + [mm] \Delta x_{k}.
[/mm]
Hierbei sieht die Jacobimatrix folgendermaßen aus:
[mm] \pmat{ \partial g1/\partial De & \partial g1/\partial Di & \partial g1/\partial h0 & \partial g1/\partial t \\ \partial g2/\partial De & \partial g2/\partial Di & \partial g2/\partial h0 & \partial g2/\partial t \\ \partial g3/\partial De & \partial g3/\partial Di & \partial g3/\partial h0 & \partial g3/\partial t \\ \partial g4/\partial De & \partial g4/\partial Di & \partial g4/\partial h0 & \partial g4/\partial t }
[/mm]
Sie ist symmetrisch und damit invertierbar.
Ich sehe nicht, wo ich eine Vorraussetzung nicht erfüllt haben sollte, und warum [mm] \Delta x_{k} [/mm] immer größer wird, anstatt sich an die Lösung anzunähern.
Die Frage mit der Hesse- und Jacobimatrix haben mich ehrlich gesgat ein bisschen verwirrt. Aber ist in diesem Falle nicht die Jacobimatrix von g die Hessematrix von f?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:32 Mi 25.01.2012 | | Autor: | Marcel |
Hallo,
> Danke für deine Mühe erstmal. Ich hoffe folgende
> Informationen können dir helfen, besser zu verstehen, was
> ich mache.
das wird - ehrlich gesagt - eine Weile dauern, bis ich das mal vollständig überdacht habe.
> Meine Funktion ist:
> f(De, Di, h0, t)=
> [mm](A*t^{4}/(K*De^{2})*s/t*((h0/t-s/t)*(h0/t-s/(2*t))+1)[/mm] -
> [mm]B)^{2}.[/mm]
> Dabei gilt: De, Di, h0, t > 0
> A, B, K und s sind Konstant und > 0 und bekannt.
>
> Diese will ich minimieren
> also:
> [mm]g1=\partial f/\partial[/mm] De = 0;
> [mm]g2=\partial f/\partial[/mm] Di =0;
> [mm]g3=\partial f/\partial[/mm] h0 =0;
> [mm]g4=\partial f/\partial[/mm] t =0;
Ah, ich hatte da was falsch verstanden. Jetzt sehe ich klarer, was Du vorhin meintest - eigentlich hätte ich das auch aus Deinem Text entnehmen können. Aber okay: Jetzt sehe ich wenigstens, dass man Nullstellen einer Funktion [mm] $\IR^4 \to \IR^4$ [/mm] sucht (man sucht quasi "Nullstellen der Ableitungsfunktion", also "der Gradientenfunktion") - und wie das mit dem Newtonverfahren zusammenhängen könnte.
> Jetzt wende ich das Newtonverfahren für vektorwertige
> Funktionen an, das laut Meyberg-vachenauer (18.4.3)
> folgendermaßen aussieht:
> (Vektoren sind fett):
>
> Jg ( [mm]x_{k}[/mm] [mm])\Delta[/mm] [mm]x_{k}[/mm] = - g ( [mm]x_{k}[/mm] )
>
> [mm]x_{k+1}[/mm] = [mm]x_{k}[/mm] + [mm]\Delta x_{k}.[/mm]
>
>
> Hierbei sieht die Jacobimatrix folgendermaßen aus:
> [mm]\pmat{ \partial g1/\partial De & \partial g1/\partial Di & \partial g1/\partial h0 & \partial g1/\partial t \\ \partial g2/\partial De & \partial g2/\partial Di & \partial g2/\partial h0 & \partial g2/\partial t \\ \partial g3/\partial De & \partial g3/\partial Di & \partial g3/\partial h0 & \partial g3/\partial t \\ \partial g4/\partial De & \partial g4/\partial Di & \partial g4/\partial h0 & \partial g4/\partial t }[/mm]
>
> Sie ist symmetrisch und damit invertierbar.
>
>
> Ich sehe nicht, wo ich eine Vorraussetzung nicht erfüllt
> haben sollte, und warum [mm]\Delta x_{k}[/mm] immer größer wird,
> anstatt sich an die Lösung anzunähern.
>
>
> Die Frage mit der Hesse- und Jacobimatrix haben mich
> ehrlich gesgat ein bisschen verwirrt. Aber ist in diesem
> Falle nicht die Jacobimatrix von g die Hessematrix von f?
Kann sein, dass ich jetzt Unsinn antworte, aber momentan sieht's für mich erstmal danach aus. Ja, hab' ich kapiert, man will ja sozusagen "von der Gradientenfunktion" die Stellen finden, deren Funktionswert der Nullvektor des [mm] $\IR^4$ [/mm] ist. (Du hattest es übrigens, glaube ich, korrekt beschrieben, aber ich hatte irgendwie im Kopf dran gedacht, dass Du $f: [mm] \IR^4 \to \IR$ [/mm] mit dem Newtonverfahren behandeln willst... Aber von der suchst Du ja Extremstellen. Okay, das war einfach nur Verwirrung in meinem Kopf. Sorry!!)
Was mir oben nicht bekommt, ist der Satz, dass die Jacobimatrix(funktion), die bzgl. der Gradienten(funktion), also die Hessematrix(funktion) von [mm] $f\,,$ [/mm] alleine schon (an allen Stellen, "wo man sie braucht") invertierbar sein soll, nur weil sie symmetrisch ist. Symmetrie alleine reicht sicher nicht für die Invertierbarkeit einer Matrix (Du brauchst die Invertierbarkeit der obigen Jacobimatrix ja eigentlich auch nur an der Nullstelle - aber die willst Du ja gerade finden - vielleicht kann man sich dennoch mal Gedanken dazu machen, ob die obige Invertierbarkeit gewährleistet ist).
Dir wird ja sicher klar sein, dass jede quadratische Matrix, die nur Einträge auf der Diagonalen hat, schon dann nicht mehr invertierbar sein wird, wenn dort nur ein Diagonaleintrag den Wert Null hat. Symmetrisch sind solche dennoch stets - insbesondere ist die Nullmatrix eine wunderschöne und einfache, aber nicht invertierbare Matrix.
P.S.:
Im Heuser arbeitet man beim Newton-Verfahren mit der Inversen "Jacobimatrix, ausgewertet an der Stelle des vorangegangenen Iterationsschritts". Das machst Du ja auch, wenn Du [mm] $J_g(x_k)\Delta x_k=-g(x_k)$ [/mm] löst [mm] ($g\,$ [/mm] steht für Gradient? Sowas wie [mm] $g=\nabla$?)
[/mm]
Irgendwie wirst Du da doch die Invertierbarkeit von [mm] $J_g(x_k)$ [/mm] prüfen/benutzen?
P.P.S.:
Heuser hat in Satz 189.2 gewisse hinreichende Bedingungen für die Konvergenz der Newtonfolge stehen - sowas wie "stetige, beschränkte partielle Ableitungen zweiter Ordnung" (diese Voraussetzung wäre hier an die "Gradientenfunktion" zu überprüfen). Außerdem ist zu beachten, dass der Startwert "auch nahe genug" an der Nullstelle liegen muss. Wie das genau nun zu verifizieren ist bzw. wie Du das bei Dir testen kannst - dazu musst Du vielleicht mal in den Beweis reingucken. Vielleicht ist das auch schon die Lösung Deines Problems.... Das weiß ich nicht. Aber es sind auf jeden Fall Bedingungen, die man prüfen bzw. zu denen man sich Gedanken machen sollte.
P.P.(P.)S.: Ich lasse die Frage mal weiterhin "halboffen".
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:07 Do 26.01.2012 | | Autor: | chrisno |
Mir ist nicht klar, an welcher Stelle Du die Konvergenz des Newton-Verfahrens sicherstellst. Da ich mich aber im Mehrdimensionalen da nicht mit den Details beschäftigt habe, merke ich das nur sicherheitshalber an.
Musst oder willst Du das selbst schreiben? Es gibt da fertige Routinen, eine ist auch in Gnuplot eingebaut.Ich habe gerne auch mal in die numerical Recepies geschaut. Nach Möglichkeit habe ich aber Bibliotheken, die das Rechenzentrum bereitstellte, genommen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:13 Do 26.01.2012 | | Autor: | Marcel |
Hallo,
> Mir ist nicht klar, an welcher Stelle Du die Konvergenz des
> Newton-Verfahrens sicherstellst. Da ich mich aber im
> Mehrdimensionalen da nicht mit den Details beschäftigt
> habe, merke ich das nur sicherheitshalber an.
eben das war und ist mir auch nicht klar - ich sehe nicht, dass die Voraussetzungen zur Anwendung geprüft worden, noch, dass der "Startwert nahe genug an einer Nullstelle liegt".
> Musst oder willst Du das selbst schreiben? Es gibt da
> fertige Routinen, eine ist auch in Gnuplot eingebaut.Ich
> habe gerne auch mal in die numerical Recepies geschaut.
Ein Standardbuch für sowas 
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:18 Do 26.01.2012 | | Autor: | leduart |
Hallo
wenn du deine Terme geschickter zusammenfasst, statt der De, [mm] h_o [/mm] nur x,y,t verwendest sieht es gleich viel einfacher aus.
a) for De=x gegen 0 wächst die fkt gegen unendlich, wenn der Rest nicht verschwindet. also wähl das kleinst x des Def. Bereichs
also hast du nur noch ne fkt von 2 Variablen [mm] h_0 [/mm] und t, die man erst mal plotten kann, um das max zu suchen.
b) du kannst den Extremwert ohne das Quadrat bilden.
Gruss leduart
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:51 Do 26.01.2012 | | Autor: | ullim |
Hi,
die Funktion hängt aber nicht von [mm] D_i [/mm] ab. Also hat man nur eine Funktion mit drei Variablen zu minimieren. Du solltest auch noch die Werte der Parameter
A, B, K und s angeben.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:52 Fr 27.01.2012 | | Autor: | T65 |
das ganze ist ein bisschen komplizierter als hier dargestellt.
Aber das würde den Rahmen sprengen und dürfte uach nicht relevant sein.
K ist jedoch von De und Di abhängig, das habe ich bei meiner Funktion aber berücksichtigt.
Wie ich die Konvergenz überprüfen kann, ist mir aus den Sätzen in den Büchern nicht ganz klar geworden. Die Jacobi-matrix ist aber invertierbar.
Gibt es noch andere Verfahren, die ich hier anwenden könnte?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:22 Fr 27.01.2012 | | Autor: | leduart |
Hallo
oben K,.. sind Konstanten,
Unten K hängt von De und Di ab.
Wir sollen hier über was nachdenken, wozu wir die alschen informationen haben. wenn man schon ne funktion hinschreibt, dann bitte die richtige um die es geht.
Da dein Verfahren ja nicht funktioniert muss es am anfangswert oder der jakobimatrix liegen.
gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:23 Sa 28.01.2012 | | Autor: | ullim |
Hi,
und wie sieht die Abhängigkeit aus? Leduart vollkommen recht, wenn die Informationen nur teilweise gegeben werden kann man auch nicht richtig helfen.
|
|
|
|
