Gradient, Hessematrix < mehrere Veränderl. < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:44 Mi 25.10.2006 | | Autor: | Riley |
| Aufgabe | Es sei A [mm] \in R^{n,n} [/mm] eine quadratische Matrix und b [mm] \in R^{n}, \lambda>0. [/mm] Wir definieren die Funktion:
F(x) = F [mm] (x_1,...,x_n) [/mm] := [mm] \|b [/mm] - [mm] Ax\|_2^2 [/mm] + [mm] \lambda \|x\|_2^2.
[/mm]
(i) Berechnen Sie den Gradienten [mm] \DeltaF(x) [/mm] und die Hessematrix [mm] \Delta^2F(x).
[/mm]
(ii) Begründen Sie, warum [mm] \Delta^2F [/mm] positiv definit ist. |
Hallo!
Ich komm bei dieser Aufgabe nicht weiter, mir ist schon ganz schwindelig vor lauter indizes *help*
also ich hab mir folgendes überlegt:
F(x) = [mm] \summe_{i=1}^{n}(b_i [/mm] - [mm] \summe_{j=1}^{n}a_{ij} x_j)^2 [/mm] - [mm] \lambda \summe_{i=1}^{n}(x_i)^2 [/mm] , also wenn man das ganze komponentenweise aufschreibt. stimmt das?
dann müsste
[mm] \frac{dF}{dx_1} [/mm] = [mm] \summe_{i=1}^{n}2 (b_i [/mm] - [mm] \summe_{j=1}^{n}a_{ij}x_j) (-a_{i1}) [/mm] + 2 [mm] \lambda x_1 [/mm] sein
und
[mm] \frac{dF}{dx_k} [/mm] = - 2 [mm] \summe_{i=1}^{n}a_{ik} (b_i [/mm] - [mm] \summe_{j=1}^{n}a_{ij}x_j) [/mm] + 2 [mm] \lambda x_k.
[/mm]
dann hab ich versucht die zweiten ableitungen zu bilden:
[mm] \frac{d^2F}{dx_ldx_k} [/mm] = 2 [mm] \summe_{i=1}^{n}a_{ik}a_{il} [/mm] für l [mm] \not=k.
[/mm]
für k=l:
[mm] \frac{d^2F}{(dx_k)^2} [/mm] = 2 [mm] \summe_{i=1}^{n}a_{ik}a_{ik} [/mm] + 2 [mm] \lambda
[/mm]
... ich weiß nur nicht, wie ich damit die pos.definitheit der hessematrix zeigen kann??
oder gibt es einen besseren weg, der nicht über diese ganzen indizes führt?
viele grüße
riley
|
|
| |
|
> Es sei A [mm]\in R^{n,n}[/mm] eine quadratische Matrix und b [mm]\in R^{n}, \lambda>0.[/mm]
> Wir definieren die Funktion:
> F(x) = F [mm](x_1,...,x_n)[/mm] := [mm]\|b[/mm] - [mm]Ax\|_2^2[/mm] + [mm]\lambda \|x\|_2^2.[/mm]
>
> (i) Berechnen Sie den Gradienten [mm]\DeltaF(x)[/mm] und die
> Hessematrix [mm]\Delta^2F(x).[/mm]
> (ii) Begründen Sie, warum [mm]\Delta^2F[/mm] positiv definit ist.
> Hallo!
> Ich komm bei dieser Aufgabe nicht weiter, mir ist schon
> ganz schwindelig vor lauter indizes *help*
Mir auch 
Einfacher wirds wohl wenn du Dir folgende Rechenregeln für die Ableitung überlegst(oder nachschaust)
Linearität (klar oder?)
[mm] D(x^t*x)=2x
[/mm]
D(Ax)=A für eine Konstante Matrix A.
Dann kannst du ganz ohne Indizees ableiten.
Die positive Definitheit dessen was dann rauskommt kannst Du vllt. eher erkennen. Falls Dir das zu kompliziert ist kannst du auch das was Du raus hast mit [mm] A^T*A [/mm] vergleichen.
viele Grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:26 Mi 25.10.2006 | | Autor: | Riley |
HI Mathemaduenn,
danke für den tipp, das is natürlich viel besser! :)
hmm, was bedeutet das "D" genau, ist es so ähnlich wie der gradient ?
d.h. bei [mm] x^t [/mm] x = [mm] x_1^2+ x_2^2 [/mm] + ... + [mm] x_n^2 [/mm] und wenn ich das als F(x) betrachte, dann ist Gradient(F(x)) = [mm] (2x_1,...,2x_n) [/mm] = 2x ?
sorry, dumme frage, aber wo kann ich solche regeln nachschlagen, bzw unter was? in den büchern die ich hab sind keine ableitungsregeln für matrizen oder vektoren...
und bei dieser Regel D(Ax) = A, kann ich mir das so überlegen:
Ax= [mm] \vektor{a_{11} x_1+ ... + a_{1n}x_{nn} \\ ... \\ a_{n1}x_1 + ... + a_{nn} x_n } [/mm] = [mm] \vektor{ F_1 \\ ... \\ F_n}
[/mm]
und dann bildet man so was wie eine hessematrix mit den ersten ableitungen...?
[mm] \pmat{ \frac{dF_1}{dx_1} & .... & \frac{dF_1}{dx_n} \\ ... & ... \\ & ... \\ \frac{dF_n}{dx_1} & .... & \frac{dF_n}{dx_n} } [/mm] = A
hmm, jetzt fehlt mir aber noch etwas, hab das mal alles umgeformt, aber nun muss ich [mm] x^T A^T [/mm] Ax ableiten - was das ist hab ich noch nicht hinbekommen, gibt es dafür eine art produktregel? denn ich hab versucht das komponentenweise aufzuschreiben, gibt aber auch nur indizeesalat *traurig*
und [mm] D(\lambda x^T [/mm] x) = 2 [mm] \lambda [/mm] x, oder?
viele grüße
riley
|
|
|
| |
|
Hallo Riley,
> hmm, jetzt fehlt mir aber noch etwas, hab das mal alles
> umgeformt, aber nun muss ich [mm]x^T A^T[/mm] Ax ableiten - was das
> ist hab ich noch nicht hinbekommen, gibt es dafür eine art
> produktregel? denn ich hab versucht das komponentenweise
> aufzuschreiben, gibt aber auch nur indizeesalat *traurig*
Ja gibt es aber wohl nur für die partielle Ableitung(oder mir ist das gerade zu kompliziert) Vergleiche auch das ![[]](/images/popup.gif) erste Google Ergebnis zu Produktregel Bücher hab ich gerade keine zur Hand kann aber sein das solche Informationen manchen Autoren zu trivial scheinen. ![[grummel]](/images/smileys/grummel.gif "[grummel]")
Also sei mal ' die partielle Ableitung nach einer Veränderlichen. Dann gilt mit Produktregel sowas
[mm](x^TA^TAx)'=(x^T)'A^TAx+x^T(A^T)'Ax+x^TA^T(A)'x+x^TA^TA(x)'[/mm]
Die Ableitung von A und [mm] A^T [/mm] ist 0. Da die einzelnen Summanden einfach Zahlen sind darf man zum weiteren zusammenfassen zum transponierten übergehen und erhält.
[mm](x^TA^TAx)'=2*(x^T)'A^TAx[/mm]
> und [mm]D(\lambda x^T[/mm] x) = 2 [mm]\lambda[/mm] x, oder?
Ja. Stichwort: Linearität! (OK?)
viele Grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:30 Do 26.10.2006 | | Autor: | Riley |
Hi Mathemaduenn!
ah okay,... ja so trivial find ich das nicht...
also ich hab für die erste ableitung nun folgendes:
F'(x) = -2b^tA + 2 [mm] (x^t)' A^t [/mm] A x + 2 [mm] \lambda [/mm] x
es gilt dann auch [mm] (x')^t [/mm] = [mm] (x^t)' [/mm] , oder?
und kann man das [mm] (x^t)' [/mm] noch anders schreiben / vereinfachen? weil für die 2.ableitung bekomm ich nun:
F'' (x)= 2 [mm] (x^t)'' A^t [/mm] A x + 2 [mm] (x^t)' A^t [/mm] A x ... ?
viele grüße
riley
|
|
|
| |
|
Hallo Riley,
> ah okay,... ja so trivial find ich das nicht...
> also ich hab für die erste ableitung nun folgendes:
> F'(x) = -2b^tA + 2 [mm](x^t)' A^t[/mm] A x + 2 [mm]\lambda[/mm] x
>
> es gilt dann auch [mm](x')^t[/mm] = [mm](x^t)'[/mm] , oder?
Ja.
> und kann man das [mm](x^t)'[/mm] noch anders schreiben /
> vereinfachen?
Das Strich war ja erstmal eine partielle Ableitung also z. die nach [mm] x_k. [/mm]
x' ist dann der k-te Einheitsvektor (klar?) Wenn man nun einen Vektor mit dem k-ten Einheitsvektor multipliziert bekommt man das raus was in der k-ten Spalte des Vektors steht. Also steht in der k-ten Spalte von 2*A^TAx die partielle Ableitung von x^TA^TAx nach [mm] x_k [/mm] Also kannst Du zunächst den Gradienten hinschreiben oder?
viele Grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:56 Do 26.10.2006 | | Autor: | Riley |
Hi Mathemaduenn!
hm, vielen dank für deine erklärung...
ich hab mir das mal "aufgemalt" - schaust du ob ich das so richtig verstanden hab *please* =?
die ableitung nach [mm] x_k: \vektor{x_1 \\ ... \\ x_k \\ ... \\ x_n }' [/mm] = [mm] \vektor{0\\ ... \\1 \\ ... \\0 } [/mm]
(0,...,0,1,0...0) [mm] \underbrace{A^T A x}_{Vektor} [/mm] = k.te Komponente des Vektors
okay, dann steht an der k.ten stelle von 2 [mm] A^T [/mm] Ax die partielle Abl von [mm] x^T A^T [/mm] Ax nach [mm] x_k:
[/mm]
[mm] (x^T A^T [/mm] A x)' = 2 [mm] (x^T)' A^T [/mm] A x und dann muss man jeweils den k.ten einheitsvektor einsetzen und erhält:
Gradient [mm] \nabla(x^T A^T [/mm] Ax) = 2 [mm] A^T [/mm] A x ?? das wär ja cool... =)
und die hessematrix müsste dann sein:
[mm] \nabla^2 [/mm] F(x) = 2 [mm] A^T [/mm] A
und diese Matrix [mm] A^t [/mm] A ist ja symmetrisch (braucht man eigentlich nicht, oder?) und pos definit weil gilt [mm] \|Ax\|_2^2 [/mm] > 0 , oder?
viele grüße
riley =)
|
|
|
| |
|
Hallo Riley,
> die ableitung nach [mm]x_k: \vektor{x_1 \\ ... \\ x_k \\ ... \\ x_n }'[/mm]
> = [mm]\vektor{0\\ ... \\1 \\ ... \\0 }[/mm]
>
> (0,...,0,1,0...0) [mm]\underbrace{A^T A x}_{Vektor}[/mm] = k.te
> Komponente des Vektors
>
> okay, dann steht an der k.ten stelle von 2 [mm]A^T[/mm] Ax die
> partielle Abl von [mm]x^T A^T[/mm] Ax nach [mm]x_k:[/mm]
> [mm](x^T A^T[/mm] A x)' = 2 [mm](x^T)' A^T[/mm] A x und dann muss man
> jeweils den k.ten einheitsvektor einsetzen und erhält:
> Gradient [mm]\nabla(x^T A^T[/mm] Ax) = 2 [mm]A^T[/mm] A x ?? das wär ja
> cool... =)
>
> und die hessematrix müsste dann sein:
> [mm]\nabla^2[/mm] F(x) = 2 [mm]A^T[/mm] A
![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
> und diese Matrix [mm]A^t[/mm] A ist ja symmetrisch (braucht man
> eigentlich nicht, oder?) und pos definit weil gilt
> [mm]\|Ax\|_2^2[/mm] > 0 , oder?
Es gilt zunächst mal [mm]\|Ax\|_2^2 \ge 0[/mm] für die positive Definitheit brauchst Du noch das mit dem [mm] \lambda
[/mm]
viele Grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:03 Do 26.10.2006 | | Autor: | Riley |
Hi Mathemaduenn!
hm das mit dem [mm] \lambda [/mm] ?
bin etwas verwirrt, da das [mm] \lambda [/mm] in der hessematrix nicht mehr vorkommt?
die def. der pos.defh ist doch:
B pos def. falls [mm] x^T [/mm] B x > 0 für alle x aus [mm] R^n [/mm] und x [mm] \not=0.
[/mm]
und es gilt doch x [mm] A^T [/mm] A x = [mm] \|Ax\|_2^2 [/mm] > 0 für alle x, [mm] x\not=0 [/mm] oder ? langt dieses argument nicht?
viele grüße
riley
|
|
|
| |
|
Hallo Riley,
> hm das mit dem [mm]\lambda[/mm] ?
> bin etwas verwirrt, da das [mm]\lambda[/mm] in der hessematrix
> nicht mehr vorkommt?
Am Anfang(mit den Indizees) stand noch eins das war auch richtig mußt Du nochmal schauen wo das verlorengegangen ist.
> die def. der pos.defh ist doch:
> B pos def. falls [mm]x^T[/mm] B x > 0 für alle x aus [mm]R^n[/mm] und x
> [mm]\not=0.[/mm]
> und es gilt doch x [mm]A^T[/mm] A x = [mm]\|Ax\|_2^2[/mm] > 0 für alle x,
> [mm]x\not=0[/mm] oder ? langt dieses argument nicht?
A muß nicht regulär sein. D.h. auch das Ax=0 sein darf auch wenn [mm] x\not=0 [/mm] gilt.
viele Grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:50 Do 26.10.2006 | | Autor: | Riley |
Hi Mathemaduenn!
ops stimmt, danke, ich nehm alles zurüch, die hessematrix muss so aussehen:
[mm] \nabla^2 [/mm] F(x) = 2 [mm] A^T [/mm] A + 2 [mm] \lambda [/mm] I.
hm, die [mm] \lambda [/mm] > 0 war gegeben. darf ich die pos. def. dann so begründen, dass [mm] A^T [/mm] A symmetrisch ist, also nur positive EW hat und deshalb mit dem hauptminorenkrit. die pos. def. folgt?
ich bin mir da nicht sicher, ist die determinante invariant unter einer solchen transformation?
viele grüße
riley
|
|
|
| |
|
Hallo Riley,
B symmetrisch -> alle Eigenwerte sind reell .
A^TA ist aber schonmal positiv semidefinit.
Über die Eigenwerte zu gehen scheint mir trotzdem sinnvoll.
viele Grüße
mathemaduenn
ein paar Definitheitskriterien
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:17 Fr 27.10.2006 | | Autor: | Riley |
Hi Mathemaduenn!
Danke für dein tipps samt link.
d.h aus der pos.semi.defh. folgt, dass die EW [mm] \geq [/mm] 0 sind.
aber wie kanni ch zeigen, dass die EW nicht null werden?
hm, [mm] 2\lambda [/mm] I kann man ja so sehen, dass diese matrix pos.def. sein muss, weil die [mm] \lambda's [/mm] ja alle >0 sind und damit die EW = [mm] 2\lambda>0, [/mm] oder?
nur mit dem [mm] A^T [/mm] A ist mir noch nichts eingefallen - nach dem einen krit ist eine matrix B pos def., wenn es B + [mm] B^T [/mm] ist.
aber [mm] A^t [/mm] A + [mm] A^T [/mm] A = 2 [mm] A^T [/mm] A bringt einen ja auch nicht weiter... ;(
macht es überhaupt sinn sich das einzeln zu überlegen, oder muss man die matrix [mm] (A^T [/mm] A + 2 [mm] \lambda [/mm] I) "ganz" betrachten?
oder darf ich sagen, dass wenn ich zu einer semi-pos.def. matrix eine pos.definite addiere, sie dann pos.def. sein muss ... ?
viele grüße
riley
|
|
|
| |
|
Hallo Riley,
Man muß das als Ganzes betrachten da ja [mm] A^T*A [/mm] nur positiv semidefinit.
Die 2 Ansätze sowohl
1. direkt: B pos. definit und C pos. semidefinit [mm] \Rightarrow [/mm] B+C pos. definit
als auch
2. die Eigenwerte von B sind größer gleich null [mm] \Rightarrow [/mm] die Eigenwerte von $B+2 [mm] \lambda [/mm] I $ sind größer gleich [mm] 2\lambda
[/mm]
scheinen mir erfolgversprechend. Kannst Dir einen raussuchen
viele grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:25 Fr 27.10.2006 | | Autor: | Riley |
Hi Mathemaduenn!
ahh *lichtaufgeh* =)) ... also 1.möglichkeit:
sei B pos definit, d.h. [mm] x^T [/mm] B x > 0 und sei A pos.semi.def.,
d.h. [mm] x^T [/mm] A x [mm] \geq [/mm] 0.
[mm] \Rightarrow [/mm] 0 < [mm] x^T [/mm] A x + [mm] x^T [/mm] B x = [mm] x^T [/mm] (A + B) x
[mm] \Rightarrow [/mm] Beh.
2.möglichkeit:
seien die EW von B gleich [mm] 2\lambda [/mm] > 0, die EW von A seien x [mm] \geq [/mm] 0.
[mm] \Rightarrow \pmat{ 2\lambda & 0 & ... \\ ... & ... & ... \\ ... & 0 & 2\lambda } [/mm] + [mm] \pmat{ x_1 & 0 & ... \\ ... & ... & ... \\ ... & 0 & x_n } [/mm] = [mm] \pmat{ 2\lambda + x_1 & 0 & ... \\ ... & ... & ... \\ ... & 0 & 2\lambda + x_n }
[/mm]
mit 2 [mm] \lambda [/mm] + [mm] x_i \geq [/mm] 2 [mm] \lambda [/mm] > 0.
sind beide wege so ok?
viele grüße
riley
ps: hab noch eine frage. du hast ganz am anfang diese schreibweise benutzt:
D (A x) = A. für was steht das D ? wie nennt man das?
|
|
|
| |
|
Hallo Riley,
> ahh *lichtaufgeh* =)) ... also 1.möglichkeit:
> sei B pos definit, d.h. [mm]x^T[/mm] B x > 0 und sei A
> pos.semi.def.,
> d.h. [mm]x^T[/mm] A x [mm]\geq[/mm] 0.
> [mm]\Rightarrow[/mm] 0 < [mm]x^T[/mm] A x + [mm]x^T[/mm] B x = [mm]x^T[/mm] (A + B) x
> [mm]\Rightarrow[/mm] Beh.
DAs sieht richtig aus.
> 2.möglichkeit:
> seien die EW von B gleich [mm]2\lambda[/mm] > 0, die EW von A seien
> x [mm]\geq[/mm] 0.
>
> [mm]\Rightarrow \pmat{ 2\lambda & 0 & ... \\ ... & ... & ... \\ ... & 0 & 2\lambda }[/mm]
> + [mm]\pmat{ x_1 & 0 & ... \\ ... & ... & ... \\ ... & 0 & x_n }[/mm]
> = [mm]\pmat{ 2\lambda + x_1 & 0 & ... \\ ... & ... & ... \\ ... & 0 & 2\lambda + x_n }[/mm]
>
> mit 2 [mm]\lambda[/mm] + [mm]x_i \geq[/mm] 2 [mm]\lambda[/mm] > 0.
DAs scheint mr nicht den Kern zu treffen, wenn es so eine spezielle Matrizensumme ist wie hier kann man sagen. a Eigenwert von A [mm] \Rightarrow [/mm] a+ [mm] \lambße
[/mm]
da ist Eigenwert von [mm] $A+\lambda [/mm] I$
Aber eins reicht ja
viele Grüße
mathemaduenn
>
> ps: hab noch eine frage. du hast ganz am anfang diese
> schreibweise benutzt:
> D (A x) = A. für was steht das D ? wie nennt man das?
>
Die Jacobi Matrix. Man hätte auch J(Ax) schreiben können.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:08 Sa 28.10.2006 | | Autor: | Riley |
Hi Mathemaduenn!
vielen vielen dank - hast mir mal wieder viel geholfen!! 
... auch wenn der andere weg reicht - würd es trotzdem gerne wissen, wie man das richtig begründet...
die EW von [mm] A^T [/mm] A + [mm] 2\lambda [/mm] I sind also a + 2 [mm] \lambda, [/mm] wenn a EW von [mm] A^T [/mm] A, oder? und [mm] a\geq [/mm] 0, 2 [mm] \lambda [/mm] > 0 [mm] \Rightarrow [/mm] a+ 2 [mm] \lambda [/mm] > 0
[mm] \Rightarrow A^T [/mm] A pos.definit.
würde es so stimmen?
viele grüße
riley
|
|
|
|
