definitheit und extremwertproblem

08.05.2007, 17:42

miss t'cafer

definitheit und extremwertproblem

hallo zusammen,

sei A € R^(n,n), A=A^t (also orthogonal); A > 0 (also positiv definit!), b€R^n

dann sind äquivalent:

(i) das LGS: Ax = b

(ii) das Minimierungsproblem: Minimiere f: R^n -> R
f(x) := 1/2 <Ax.x> - <x.b>

und <a.b> bezeichne das Skalarprodukt

ich sehe ja dass man Ax=b umformen kann zu <Ax.x> - <x.b> = 0 aber wie kommt man auf den faktor 1/2 vor dem ersten skp?

danke im voraus, miss t'cafer

08.05.2007, 18:04

tigerbine

Auf diesen Beitrag antworten »

RE: definitheit und extremwertproblem
Könntest Du nicht den Editor benutzen? Wink

Das ganze müsste man am Anfang des Beweises des Gradienten Verfahrens finden. Hier haben wir da mal drüber geredet.

08.05.2007, 18:31

miss t'cafer

Auf diesen Beitrag antworten »

$\begin{eqnarray*} A \in \mathbb R^{n}, A=A^{t}, A>0,b \in \mathbb R^{n} \end{eqnarray*}$

dann sind äquivalent

(i) das LGS $\begin{eqnarray*} Ax = b \end{eqnarray*}$

(ii) das minimierungsproblem: minimiere $\begin{eqnarray*} f:\mathbb R^{n} \to \mathbb R \end{eqnarray*}$

$\begin{eqnarray*} f(x) := \frac{1}{2} <Ax,b> - <x,b>; \end{eqnarray*}$

08.05.2007, 18:37

miss t'cafer

Auf diesen Beitrag antworten »

was bei dem link steht versteh ich nicht wirklich... warum stimmt das überein... woher hat man die funktion f?

08.05.2007, 18:43

tigerbine

Auf diesen Beitrag antworten »

Wie woher hat man f? verwirrt

Die Funktion ist doch definiert

$\begin{eqnarray*} f(x) := \frac{1}{2} <Ax,b> - <x,b>= \frac{1}{2}x^TA^Tb-x^Tb \end{eqnarray*}$

Nun sollst du die Äquivalenz zeigen:

$\begin{eqnarray*} x^* \text{ löst } Ax=b \Leftrightarrow x^* \text{ minimiert } f \end{eqnarray*}$

Den Tipp habe ich Dir mit dem Link gegeben. Die Hauptidee ist die Hilfsfunktion g und die kennst Du jetzt schon.

08.05.2007, 19:43

miss t'cafer

Auf diesen Beitrag antworten »

also gut ich geh mal so ran und will beweien dass aus (i) folgt (ii):

$\begin{eqnarray*} Ax = b \Rightarrow x = A ^{-1} \end{eqnarray*}$

dieses x nennen wir mal x*;

aus (ii) wissen wir (übrigens heißt es so in meinem skript, wirklich)

$\begin{eqnarray*} Ax = b \Rightarrow x = A ^{-1} \end{eqnarray*}$

dann x* eingesetzt in f(x) ergibt:

$\begin{eqnarray*} f(x*)=f(A^{-1}b)=...=-\frac{1}{2} b^{t}A^{-1}b \end{eqnarray*}$

aber inwiefern hilt mir das weiter und wie nutze ich aus dass A symmetrisch und positiv definit is

08.05.2007, 19:45

miss t'cafer

Auf diesen Beitrag antworten »

übrigens die zweite formel soll so lauten und nich wie die erste sein

08.05.2007, 19:48

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von miss t'cafer
$\begin{eqnarray*} Ax = b \Rightarrow x = A ^{-1} \end{eqnarray*}$

Ist schon falsch. $\begin{eqnarray*} Ax = b \Leftrightarrow x = A ^{-1}b \end{eqnarray*}$ Unser A ist natürlich regulär. Augenzwinkern

Was gibt's jetzt bei f für ein Problem verwirrt

<,> bezeichnet üblicherweise ein Skalarprodukt. Ich hab eben das IdealStandard genommen.

Du hattest Oben gesagt, dass du mit (.) auch ein Skalarprodukt meinst, oder? Also was passt nicht?

Wink

08.05.2007, 20:21

miss t'cafer

Auf diesen Beitrag antworten »

sorry echt wenn ich mich so dämlich anstelle und du bist so nett, danke dafür, dass du deine zeit für mich opferst, also ich bin mal anders ran gegangen:

$\begin{eqnarray*} f(x) := \frac{1}{2} <Ax,x> - <x,b> \end{eqnarray*}$

$\begin{eqnarray*} f'(x) = Ax - b \end{eqnarray*}$ bzw. $\begin{eqnarray*} f'(x) = 0 \Rightarrow Ax = b \end{eqnarray*}$

und das x ist eindeutig bestimmt wegen A invertierbar.

allerdings, wo nutze ich aus dass A symmetrisch und pos. definit ist?

auf der anderen seite stimmt ja eigentlich schon dass gilt $\begin{eqnarray*} Ax = b \Leftrightarrow x = A ^{-1}b \end{eqnarray*}$

und damit $\begin{eqnarray*} f(x*) = \frac{1}{2} b^{t} A^{-t}AA^{-1}b-b^{t}A^{-t}b = \frac{1}{2} b^{t} A^{-1}b - b^{t}A^{-1}b = - \frac{1}{2} b^{t} A^{-1}b; \end{eqnarray*}$

aber was sagt mir das jetzt? sorry echt wenn ich nerve

08.05.2007, 20:38

tigerbine

Auf diesen Beitrag antworten »

Zitat:

allerdings, wo nutze ich aus dass A symmetrisch und pos. definit ist?

Warum ist A wohl invertierbar? Augenzwinkern

Und wo kommt jetzt diese Ableitung her? verwirrt

Wir haben eine Funktion:

$\begin{eqnarray*} f:~\mathbb R^n \to \mathbb R \end{eqnarray*}$

Ableit
ungen

08.05.2007, 20:53

miss t'cafer

Auf diesen Beitrag antworten »

ok cool

zum letzten problem: ich bekomme ja für die minimalstelle von $\begin{eqnarray*} f(x) \end{eqnarray*}$ raus:

$\begin{eqnarray*} f(x*) = - \frac{1}{2} b^{t} A^{-1}b; \end{eqnarray*}$

im anderen thread benutzt du jetzt die hilfsfunktion $\begin{eqnarray*} g(x) = f(x) - f(x*) \end{eqnarray*}$

mit $\begin{eqnarray*} x \end{eqnarray*}$ minimiert $\begin{eqnarray*} f(x) \end{eqnarray*}$ genau dann wenn $\begin{eqnarray*} x \end{eqnarray*}$ die funktion $\begin{eqnarray*} g(x) \end{eqnarray*}$ minimiert, stimmts? und dann bekomm ich ja

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

weil A SPD ist muss $\begin{eqnarray*} Ax-b = 0 \end{eqnarray*}$ gelten, was sein kann, damit $\begin{eqnarray*} g(x) \end{eqnarray*}$ und damit $\begin{eqnarray*} f(x) \end{eqnarray*}$ minimal (sprich = 0 ) wird. kleiner als null kann es nicht werden weil:
$\begin{eqnarray*} Ax = b \Leftrightarrow x^{t}Ax = x^{t}b \end{eqnarray*}$ beides größer null wegen A SPD

kann man so argumentieren?

08.05.2007, 20:57

tigerbine

Auf diesen Beitrag antworten »

Zitat:

mit $\begin{eqnarray*} x \end{eqnarray*}$ minimiert $\begin{eqnarray*} f(x) \end{eqnarray*}$ genau dann wenn $\begin{eqnarray*} x \end{eqnarray*}$ die funktion $\begin{eqnarray*} g(x) \end{eqnarray*}$ minimiert, stimmts?

Ja, so ist es...

Der Rest sieht nach dem Überfliegen gut aus.

08.05.2007, 21:05

miss t'cafer

Auf diesen Beitrag antworten »

ich glaub meine arguemntation dass $\begin{eqnarray*} Ax - b > 0 \end{eqnarray*}$ für A SPD stimmt nicht, mein gott ich hab zu viel mathe gemacht heute, irgendwie spricht doch da nichts dagegen, wär doch möglich... mann mann mann, sorry echt, du bist echt ein schatz

08.05.2007, 21:07

miss t'cafer

Auf diesen Beitrag antworten »

achso ja Ax - b kann schon < 0 werden aber wegen dem A dazwischen wirds ja nciht < 0

08.05.2007, 22:04

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Jede quadratische Matrix beschreibt eine Bilinearform auf $\begin{eqnarray*} \mathbb R^n \end{eqnarray*}$ oder eine Sesquilinearform $\begin{eqnarray*} \mathbb C^n \end{eqnarray*}$ . Man nennt die quadratische Matrix deshalb positiv definit, wenn diese Eigenschaft auf die durch die Matrix definierte Bilinearform oder Sesquilinearform zutrifft. Dies ist gleichbedeutend mit der Forderung, dass für alle von Null verschiedenen Vektoren x die folgende Ungleichung erfüllt ist:

$\begin{eqnarray*} x^TAx > 0 \end{eqnarray*}$

Somit haben wir bei $\begin{eqnarray*} x*:=A^{-1}b \end{eqnarray*}$ das Minimum der Funktion g gefunden. Und die Lösung des LGS Ax=b. Damit ist die Äquivalenz gezeigt.

Neue Frage »

Antworten »

definitheit und extremwertproblem

Verwandte Themen