Extremaberechnung wie ich sie noch nie machen musste

22.11.2006, 15:14

Paul_H

Extremaberechnung wie ich sie noch nie machen musste

Tach an alle,

ich soll ein (globales) Extremum $\begin{eqnarray*} x^* \in \mathbb R^n \end{eqnarray*}$ der Funktion

$\begin{eqnarray*} f(x) = \frac{1}{2} x^T Ax - b^Tx \end{eqnarray*}$

bestimmen so, dass

$\begin{eqnarray*} Ax^* = b \end{eqnarray*}$

für $\begin{eqnarray*} b \in \mathbb R^n \end{eqnarray*}$ und $\begin{eqnarray*} A \in \mathbb R^{nxn} \end{eqnarray*}$ 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. unglücklich

23.11.2006, 16:31

Paul_H

Auf diesen Beitrag antworten »

Vielleicht wäre ein Ansatz, den Teil

$\begin{eqnarray*} x^T A x \end{eqnarray*}$

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:

$\begin{eqnarray*} F(x) =\frac{1}{2} x^TAx - b^T x = \frac{1}{2}\sum_{i=1}^n~ \sum_{j=1}^n~ a_{ij} x_i x_j - \sum_{i=1}^n~ b_i x_i \end{eqnarray*}$

wenn diese funktion nun in x* ein lokales extremum haben soll, muss weiter gelten, dass der Gradient
$\begin{eqnarray*} \nabla F(x*) = \begin{pmatrix} \frac{df}{dx_1} \\ ... \\ \frac{df}{dx_n} \end{pmatrix} (x*) =0 \end{eqnarray*}$

d.h. du könntest mal die Ableitung $\begin{eqnarray*} \frac{df}{dx_l} \end{eqnarray*}$ betrachten. (wenn dir das zu viel Indizes-gewurschtel ist, kannst du den gradienten auch mit folgenden regeln bilden:
$\begin{eqnarray*} \nabla (b^Tx) = b \end{eqnarray*}$ und $\begin{eqnarray*} \nabla (x^TAx) = 2Ax \end{eqnarray*}$ . )

dann musst du natürlich noch überprüfen, ob die Hessematrix $\begin{eqnarray*} \nabla^2 F(x) \end{eqnarray*}$ 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 $\begin{eqnarray*} F(x) = 1/2 x^T A x- b^T \end{eqnarray*}$ übereinstimmt! smile

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 Wink

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

$\begin{eqnarray*} g(x):=f(x)+\frac{1}{2}b^TA^{-1}b \end{eqnarray*}$

....

$\begin{eqnarray*} g(x)= \frac{1}{2}(Ax-b)^TA^{-1}(Ax-b) \end{eqnarray*}$

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 Wink

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! smile

25.11.2006, 09:28

tigerbine

Auf diesen Beitrag antworten »

f und g unterscheiden sich nur durch einen konstanten Term A,b sind bekannt Augenzwinkern

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 Augenzwinkern

Genau dann, wenn x das LGS Ax = b löst.

SPD heist Symmetrisch positiv definit und gibt nicht meine politische Orientierung wieder Augenzwinkern

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ß Wink

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

Zitat:

enn diese funktion nun in x* ein lokales extremum haben soll, muss weiter gelten, dass der Gradient
$\begin{eqnarray*} \nabla F(x*) = \begin{pmatrix} \frac{df}{dx_1} \\ ... \\ \frac{df}{dx_n} \end{pmatrix} (x*) =0 \end{eqnarray*}$

d.h. du könntest mal die Ableitung $\begin{eqnarray*} \frac{df}{dx_l} \end{eqnarray*}$ betrachten. (wenn dir das zu viel Indizes-gewurschtel ist, kannst du den gradienten auch mit folgenden regeln bilden:
$\begin{eqnarray*} \nabla (b^Tx) = b \end{eqnarray*}$ und $\begin{eqnarray*} \nabla (x^TAx) = 2Ax \end{eqnarray*}$ . )

dann musst du natürlich noch überprüfen, ob die Hessematrix $\begin{eqnarray*} \nabla^2 F(x) \end{eqnarray*}$ positiv definit ist, um zu zeigen, dass wirklich ein Minimum vorliegt.

nicht.

Desweiteren hasst Du

Zitat:

Das coole was dabei rauskommt, ist, dass also die Lösung des LGS Ax=b mit der Minimalstelle der Fuktion $\begin{eqnarray*} F(x) = 1/2 x^T A x- b^T \end{eqnarray*}$ übereinstimmt! smile

noch nicht bewiesen! Augenzwinkern

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. Augenzwinkern

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ß Wink

Neue Frage »

Antworten »

Extremaberechnung wie ich sie noch nie machen musste

Verwandte Themen