Gradientenverfahren < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:27 So 22.02.2009 | | Autor: | Pacapear |
Hallo zusammen!
So, nach einer langen Diskussion zum Thema Gradient habe ich jetzt doch noch Fragen zum Gradientenverfahren.
Also meine Iterationsvorschrift lautet ja [mm] x^{k+1}=x^k+\lambda(x^k,r^k) [/mm] mit [mm] r^k=b-Ax^k.
[/mm]
So, nun ist [mm] r^k [/mm] grade mein Gradient beim zu minimierenden Standard-Funktional [mm] F(x)=\bruch{1}{2}*-.
[/mm]
So, ich würd gerne nochmal bei dem Beispiel mit der Gebirgslandschaft bleiben, also im [mm] \IR^3.
[/mm]
Ich wähle jetzt einen Startvektor [mm] x=(x_0,y_0). [/mm] Der liegt ja jetzt in der x-y-Ebene.
Wie finde ich nun mein neues x geometrisch betrachtet?
Ist folgender Algorithmus richtig?
1) Ich wähle den Startpunkt [mm] x=(x_0,y_0).
[/mm]
2) Ich berechne zu diesem Punkt den Gradienten [mm] r^0, [/mm] der auch in der x-y-Ebene liegt.
3) Ich multiplizieren den Gradienten mit den [mm] \lambda, [/mm] also verkürze oder verlängere ihn.
4) Ich zeichne eine Vektoraddition aus [mm] x^0 [/mm] und dem modifizierten Gradienten. Alles in der x-y-Ebene
5) Der Ergebnispunkt der Vektoraddition ist mein neuer Punkt [mm] x^{1}.
[/mm]
Und diesen ganzen Kram wiederhole ich jetzt so lange, bis ich im Minimum (auch in der x-y-Ebene, nicht in der Landschaft, weil ich ja noch keine Höhe, also keinen Funktionswert berechnet habe) angekommen bin?
Habe ich das jetzt richtig verstanden?
LG, Nadine
|
|
| |
|
Dein Verfahren ist absolut korrekt. Der Gradient zeigt dir dabei die Richtung (in x-y-Ebene) des größten z-Anstiegs, du gelangst normaler Weise zum Maximum und musst daher gegen der Gradienten laufen.
Teste das Ganze doch mal mit [mm] f(x|y)=(x-1)^2+(y-2)^2. [/mm] Da die Quadrate immer positiv oder 0 sind, liegt das Minimum bei (1|2).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:36 So 22.02.2009 | | Autor: | Pacapear |
Hallo!
> Dein Verfahren ist absolut korrekt. Der Gradient zeigt dir
> dabei die Richtung (in x-y-Ebene) des größten z-Anstiegs,
> du gelangst normaler Weise zum Maximum und musst daher
> gegen der Gradienten laufen.
Ja, wir haben hier auch den negativen Gradienten genommen.
> Teste das Ganze doch mal mit [mm]f(x|y)=(x-1)^2+(y-2)^2.[/mm] Da die
> Quadrate immer positiv oder 0 sind, liegt das Minimum bei
> (1|2).
Das werd ich morgen mal ausprobieren.
Vorher hab ich aber noch eine Frage:
Weil in unserem Skript rechen wir nur für das erste r mit [mm] r^k=b-Ax^k, [/mm] danach mit [mm] r^{k+1}=r^k-\lambda(x^k,r^k)Ar^k.
[/mm]
Was ist das?
Warum rechne ich nicht mit dem vorherigen Gradienten auch?
Meine Richtung, in die ich weiter marschieren muss, hat sich doch nicht verändert, weil ich ja bereits in die richtige Richtung gelaufen bin.
Das verstehe ich nicht ![[nixweiss]](/images/smileys/nixweiss.gif "[nixweiss]")
LG, Nadine
|
|
|
| |
|
> Warum rechne ich nicht mit dem vorherigen Gradienten auch?
Hallo,
wenn Du am neuen Punkt angekommen bist, mußt Du Dich doch wieder umschauen, wie der steilste Abstieg ist.
Wieso sollte das unbedingt die Richtung von zuvor sein?
>
> Meine Richtung, in die ich weiter marschieren muss, hat
> sich doch nicht verändert, weil ich ja bereits in die
> richtige Richtung gelaufen bin.
Wenn ich 10m gen Norden steil abwärts gehe, heißt das doch nicht, daß es ab jetzt immer so weitergeht. Nach 10m hatlte ich inne und gucke, wo es jetzt am steilsten runter geht. Vielleicht ja in Richtung Nordosten.
> Das verstehe ich nicht
Der Gradient ändert sich i.a. von Punkt zu Punkt. Genau wie die Tangentensteigung der Graphen von Funktionene über [mm] \IR, [/mm] welche Dir geläufig sind.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:53 Di 24.02.2009 | | Autor: | Pacapear |
Hallo Angela.
Ok, ich denke, ich habe das verstanden.
Dann nur noch eine Frage zu den beiden Formel für [mm]\ r [/mm]:
Auch wenn ich in jedem Schritt einen neuen Gradienten suche, warum rechne ich dann nicht immer mit der Formel [mm] r^k=b-Ax^k [/mm] ?
Ich laufe ja immer noch auf der Funktion [mm] F(x)=\bruch{1}{2}\cdot{}- [/mm] , auch wenn ich in einem neuen Punkt angekommen bin.
Und von der dieser Funktion ist der Gradient doch weiterhin [mm] r^k=b-Ax^k [/mm] , nur halt mit einem anderen x als vorher.
Woher kommt dann die Formel [mm] r^{k+1}=r^k-\lambda(x^k,r^k)Ar^k [/mm] und warum rechne ich nach dem ersten Schritt damit weiter?
Das verstehe ich nicht.
Dann noch zwei allgemeine Fragen zum Thema:
1) Wenn ich mich in jedem neu erreichten Punkt nach dem steilsten Weg umsehe, heißt dass, das ich so am schnellsten im Minimum ankomme? Ist das Gradientenverfahren damit ein recht flottes Verfahren?
> Der Gradient ändert sich i.a. von Punkt zu Punkt. Genau wie
> die Tangentensteigung der Graphen von Funktionene über [mm]\IR,[/mm]
2) Hmm, aber im [mm] \IR [/mm] gibt es eigentlich in jedem Punkt nur eine steilste Richtung, oder nicht? Zum Beispiel bei einer Parabel [mm] x^2. [/mm] Wenn ich im Nullpunkt loslaufe, wird der Gradient doch immer nach "Osten" zeigen, egal in welchen Punkt, bis ich da bin. Wieso ändert er sich da?
Ich bin jetzt grad wieder etwas verwirrt, im Moment hab ich mir gemerkt: Gradient zeigt in die Richtung, wo es am steilsten bergauf/bergab geht , ist also doch eigentlich keine Steigung, oder?
Vielen Dank schonmal für eure Hilfe.
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:13 Fr 27.02.2009 | | Autor: | leduart |
Hallo
> Auch wenn ich in jedem Schritt einen neuen Gradienten
> suche, warum rechne ich dann nicht immer mit der Formel
> [mm]r^k=b-Ax^k[/mm] ?
> Ich laufe ja immer noch auf der Funktion
> [mm]F(x)=\bruch{1}{2}\cdot{}-[/mm] , auch wenn ich in
> einem neuen Punkt angekommen bin.
> Und von der dieser Funktion ist der Gradient doch
> weiterhin [mm]r^k=b-Ax^k[/mm] , nur halt mit einem anderen x als
> vorher.
> Woher kommt dann die Formel
> [mm]r^{k+1}=r^k-\lambda(x^k,r^k)Ar^k[/mm] und warum rechne ich nach
> dem ersten Schritt damit weiter?
> Das verstehe ich nicht.
Was ist denn dein [mm] \lambda(x^k,r^k)?
[/mm]
>
> Dann noch zwei allgemeine Fragen zum Thema:
>
> 1) Wenn ich mich in jedem neu erreichten Punkt nach dem
> steilsten Weg umsehe, heißt dass, das ich so am schnellsten
> im Minimum ankomme? Ist das Gradientenverfahren damit ein
> recht flottes Verfahren?
Ja, steh mal auf nem Berg, du willst ins Tal: 1. Moeglichkeit, du gehst einen langen sanften Weg, der fuehrt dich wahrscheinlich 10 mal um den berg rum bist du vielleicht unten ankommst.
2. Moeglichkeit, du gehst den steilsten Weg runter!
>
> > Der Gradient ändert sich i.a. von Punkt zu Punkt. Genau wie
> > die Tangentensteigung der Graphen von Funktionene über [mm]\IR,[/mm]
>
> 2) Hmm, aber im [mm]\IR[/mm] gibt es eigentlich in jedem Punkt nur
> eine steilste Richtung, oder nicht? Zum Beispiel bei einer
> Parabel [mm]x^2.[/mm] Wenn ich im Nullpunkt loslaufe, wird der
> Gradient doch immer nach "Osten" zeigen, egal in welchen
> Punkt, bis ich da bin. Wieso ändert er sich da?
der Vergleich mit R sollte nur zeigen, das sich was aendert. im R nur die groesse der Steigung, im [mm] R^3 [/mm] auch die Richtung.
Stell dir doch wirklich mal einen Berg vor: an jeder Stelle aendert sich die Landschaft, mal ist es nach rechts steiler, mal nach links und die Groesse der Steigung aendert sich auch laufend. Wenn du auf nem Kegel bist laeufst du einfach ne grade Linie runter, der grad ist ueberall gleich. Wenns ein bissel komplizierter als ein Kegel ist wird eben auch der Weg immer anders sein.
> Ich bin jetzt grad wieder etwas verwirrt, im Moment hab ich
> mir gemerkt: Gradient zeigt in die Richtung, wo es am
> steilsten bergauf/bergab geht , ist also doch eigentlich
> keine Steigung, oder?
Wieso ist das keine Steigung? du laeufst ja immer ein Stueckchen einer Kurve, (die du durch ein Geradenstueck annaeherst) die hat ne Steigung!
Gruss leduart
>
>
> Vielen Dank schonmal für eure Hilfe.
> LG, Nadine
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:16 Fr 27.02.2009 | | Autor: | Pacapear |
Hallo leduart,
danke für deine Antwort.
> > Auch wenn ich in jedem Schritt einen neuen Gradienten
> > suche, warum rechne ich dann nicht immer mit der Formel
> > [mm]r^k=b-Ax^k[/mm] ?
> > Ich laufe ja immer noch auf der Funktion
> > [mm]F(x)=\bruch{1}{2}\cdot{}-[/mm] , auch wenn ich in
> > einem neuen Punkt angekommen bin.
> > Und von der dieser Funktion ist der Gradient doch
> > weiterhin [mm]r^k=b-Ax^k[/mm] , nur halt mit einem anderen x als
> > vorher.
> > Woher kommt dann die Formel
> > [mm]r^{k+1}=r^k-\lambda(x^k,r^k)Ar^k[/mm] und warum rechne ich nach
> > dem ersten Schritt damit weiter?
> > Das verstehe ich nicht.
> Was ist denn dein [mm]\lambda(x^k,r^k)?[/mm]
Wie haben in unserer Vorlesung nicht wirklich gesagt, was [mm] \lambda(x^k,r^k) [/mm] ist.
Wir haben es irgendwie mit einer Funktion f eingeführt, die u.a. das Funktional F als Argument hat.
[mm] \lambda [/mm] war dann von diesem f das Minimum oder so.
Mehr haben wir aber nicht gesagt.
Durch Recherche im Internet vermute ich, dass es sich dabei um eine Art Schrittweite handelt.
Formel haben wir dafür folgende:
[mm] \lambda(x^k,r^k)=\bruch{r^k*r^k}{Ar^k*r^k}
[/mm]
Kennst du nun vielleicht eine Antwort auf meine Frage?
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:23 Sa 07.03.2009 | | Autor: | Infinit |
Hallo Nadine,
das [mm] \lambda [/mm] ist wirklich die Schrittweite für den aktuellen Iterationsschritt. Nachdem man den Gradienten kennt, stellt sich natürlich die Frage, wie lange man auf ihm "reiten" kann, um in ein Minimum zu kommen. In jedem Iterationsschritt muss deshalb die optimale Länge des Gradienten bestimmt werden. Für die quadratischen Zielfunktionen führt diesd auf eine "Unteroptimierungsaufgabe", deren Ergebnis derjenige Ausdruck ist, den Du über die Recherche gefunden hast.
Viele Grüße,
Infinit
|
|
|
|
