Gleichung nach Vektor lösen < Matrizen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:33 Di 08.11.2011 | | Autor: | Pille456 |
| Aufgabe | Berechne den Tiefpunkt folgender Funktion:
[mm] f(w)=(P*w-y)^T(P*w-y)
[/mm]
(P ist eine NxM-Matrix, y ein Nx1 Vektor und w ein Mx1 Vektor) |
Hi,
leider bin ich in lineare Algebra nicht mehr so fit, daher komme ich bei der Aufgabe gerade nicht weiter. (Die eigentliche Aufgabe ist in einen anderen Kontext eingebettet, bei deren Lösung ich die obrige Gleichung lösen muss, nur leider komme ich da nicht weiter)
Mein Plan war, nach den üblichen Bedingungen für ein Extremum vorzugehen, d.h. 1. Ableitung = 0 und 2. Ableitung [mm] \not= [/mm] 0 zu prüfen. Klar ist, dass die 1. Bedingung sich dann natürlich auf den 0 Vektor bezieht und bei der 2. Bedingung man wahrscheinlich mit der Hesse-Matrix argumentieren muss.
Nun aber erstmal ganz von vorne:
[mm] f(w)=(P*w-y)^T(P*w-y)
[/mm]
[mm] \bruch{d*f(w)}{w}=P^T(P*w-y)+(P*w-y)^T*P [/mm] (nach Kettenregel)
Nun darf man bei Summen das Transponiert reinziehen und natürlich gilt auch Distributivität:
[mm] 0=P^T(P*w-y)+(P*w-y)^T*P=P^T(P*w-y)+((P*w)^T-y^T)*P=P^T*P*w-P^T*y+(P*w)^T*P-y^T*P
[/mm]
Nun versuche ich das nach w aufzulösen. Dabei weiß ich von [mm] P^T*P [/mm] bzw. [mm] P*P^T, [/mm] dass diese an der Hauptdiagonalen gespiegelt sind. Problematisch ist momentan für mich eher der [mm] P^T*y [/mm] bzw. [mm] y^T*P [/mm] teil.
Wenn ich mal ein Beispiel durchrechne komme ich auf folgendes:
[mm] y^T*P=\vektor{y1 \\ y2}^T*\pmat{ a & b \\ c & d }=\vektor{y1*a+y2*b \\ y1*c+y2*d}^T
[/mm]
und
[mm] P^T*y=\pmat{ a & c \\ b & d }*\vektor{y1 \\ y2}=\vektor{y1*a+y2*c \\ y1*b+y2*d}
[/mm]
Hier stimmen dann die Dimensionen für die Addition schon gar nicht mehr, also muss irgendwo ein Fehler sein. Jemand eine Idee wo das Problem hier liegt?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:25 Mi 09.11.2011 | | Autor: | meili |
Hallo,
> Berechne den Tiefpunkt folgender Funktion:
> [mm]f(w)=(P*w-y)^T(P*w-y)[/mm]
>
> (P ist eine NxM-Matrix, y ein Nx1 Vektor und w ein Mx1
> Vektor)
> Hi,
>
> leider bin ich in lineare Algebra nicht mehr so fit, daher
> komme ich bei der Aufgabe gerade nicht weiter. (Die
> eigentliche Aufgabe ist in einen anderen Kontext
> eingebettet, bei deren Lösung ich die obrige Gleichung
> lösen muss, nur leider komme ich da nicht weiter)
>
> Mein Plan war, nach den üblichen Bedingungen für ein
> Extremum vorzugehen, d.h. 1. Ableitung = 0 und 2. Ableitung
> [mm]\not=[/mm] 0 zu prüfen. Klar ist, dass die 1. Bedingung sich
> dann natürlich auf den 0 Vektor bezieht und bei der 2.
> Bedingung man wahrscheinlich mit der Hesse-Matrix
> argumentieren muss.
![[ok]](/images/smileys/ok.gif "[ok]")
> Nun aber erstmal ganz von vorne:
> [mm]f(w)=(P*w-y)^T(P*w-y)[/mm]
Die Funktion f(w) würde ich schreiben mit:
$w = [mm] \vektor{w_1 \\ \vdots \\ w_m}$
[/mm]
P = [mm] \pmat{ p_{1 1} & \cdots & p_{1 m} \\ \vdots & \ddots & \vdots \\ p_{n 1} & \cdots & p_{n m}}$
[/mm]
$y= [mm] \vektor{y_1 \\ \vdots \\ y_n}$
[/mm]
ergibt ausmultipliziert
$f(w) = [mm] \summe_{k = 1}^n \left( \left(\summe_{j = 1}^m p_{k j}w_j\right) - y_k\right)^2$
[/mm]
Davon die partiellen Ableitungen bilden:
[mm] $\vektor{\bruch{\partial f }{\partial w_1} \\ \vdots \\ \bruch{\partial f }{\partial w_m}}$
[/mm]
> [mm]\bruch{d*f(w)}{w}=P^T(P*w-y)+(P*w-y)^T*P[/mm] (nach
> Kettenregel)
> Nun darf man bei Summen das Transponiert reinziehen und
> natürlich gilt auch Distributivität:
>
> [mm]0=P^T(P*w-y)+(P*w-y)^T*P=P^T(P*w-y)+((P*w)^T-y^T)*P=P^T*P*w-P^T*y+(P*w)^T*P-y^T*P[/mm]
>
> Nun versuche ich das nach w aufzulösen. Dabei weiß ich
> von [mm]P^T*P[/mm] bzw. [mm]P*P^T,[/mm] dass diese an der Hauptdiagonalen
> gespiegelt sind. Problematisch ist momentan für mich eher
> der [mm]P^T*y[/mm] bzw. [mm]y^T*P[/mm] teil.
> Wenn ich mal ein Beispiel durchrechne komme ich auf
> folgendes:
> [mm]y^T*P=\vektor{y1 \\ y2}^T*\pmat{ a & b \\ c & d }=\vektor{y1*a+y2*b \\ y1*c+y2*d}^T[/mm]
>
> und
> [mm]P^T*y=\pmat{ a & c \\ b & d }*\vektor{y1 \\ y2}=\vektor{y1*a+y2*c \\ y1*b+y2*d}[/mm]
>
> Hier stimmen dann die Dimensionen für die Addition schon
> gar nicht mehr, also muss irgendwo ein Fehler sein. Jemand
> eine Idee wo das Problem hier liegt?
Gruß
meili
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:00 Mi 09.11.2011 | | Autor: | Pille456 |
Hi,
danke für Deine Antwort. Ich hatten den Fall mal für m=n=2 durchgespielt und empfand das als einen extrem großen Aufwand, daher dachte ich, dass es vielleicht einfacher geht. Habe mal mit Deiner Formel weitergerechnet und komme dann auf folgendes:
[mm] \bruch{d}{dw_i}\summe_{k = 1}^n \left( \left(\summe_{j = 1}^m p_{k j}w_j\right) - y_k\right)^2 =2*\summe_{k = 1}^n \left(( \left(\summe_{j = 1}^m p_{k j}w_j\right) - y_k\right)p_{k i})=0 [/mm] (Not. Bed. für Extremstellen)
Nun habe ich ein wenig hin und her gerechnet und kam auf folgenden Ausdruck, der meiner Meinung etwas unhandlich ist...
[mm] w_i=\bruch{1}{\summe_{k=1}^{m}p_{k i}^2}*(\summe_{k=1}^{m}(y_k*p_{k i})-\summe_{j=1, j\not=i}^{n}[(\summe_{k=1, k\not=i}^{m}p_{i k}*w_k)*p_{ji}])
[/mm]
Ich hoffe zwar selten, dass ich einen Fehler gemacht habe, bei dem Ausdruck bin ich doch schon eher dazu bereit, wenn ich mir vorstelle, dass ich das alles in der Hesse-Matrix verarbeiten darf.
Gibt es da nicht irgendwlelche Tricks und Kniffe um das alles zu vereinfachen bzw. kann das überhaupt korrekt sein?^^
Mal ganz pragmatisch gedacht, hat doch kein Tutor lust sowas zu korrigieren
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:12 Do 10.11.2011 | | Autor: | meili |
Hallo,
> Hi,
>
> danke für Deine Antwort. Ich hatten den Fall mal für
> m=n=2 durchgespielt und empfand das als einen extrem
> großen Aufwand, daher dachte ich, dass es vielleicht
> einfacher geht. Habe mal mit Deiner Formel weitergerechnet
> und komme dann auf folgendes:
>
> [mm]\bruch{d}{dw_i}\summe_{k = 1}^n \left( \left(\summe_{j = 1}^m p_{k j}w_j\right) - y_k\right)^2 =2*\summe_{k = 1}^n \left(( \left(\summe_{j = 1}^m p_{k j}w_j\right) - y_k\right)p_{k i})=0[/mm]
> (Not. Bed. für Extremstellen)
> Nun habe ich ein wenig hin und her gerechnet und kam auf
> folgenden Ausdruck, der meiner Meinung etwas unhandlich
> ist...
> [mm]w_i=\bruch{1}{\summe_{k=1}^{m}p_{k i}^2}*(\summe_{k=1}^{m}(y_k*p_{k i})-\summe_{j=1, j\not=i}^{n}[(\summe_{k=1, k\not=i}^{m}p_{i k}*w_k)*p_{ji}])[/mm]
Das ist zwar nach der Komponente [mm] $w_i$ [/mm] aufgelöst,
aber es ist ein (oder mehrere) $w = [mm] \vektor{w_1 \\ \vdots \\ w_m}$ [/mm] gesucht für den (die) [mm] $\vektor{\bruch{\partial f}{\partial w_1} \\ \vdots \\ \bruch{\partial f}{\partial w_m}} [/mm] = [mm] \mathcal{O}$.
[/mm]
Das führt zu einem linearen Gleichungssystem
[mm] \pmat{ \summe_{k=1}^{n} p_{k 1}p_{k 1} & \cdots & \summe_{k=1}^{n} p_{k 1}p_{k m} \\ \vdots & \ddots & \vdots \\ \summe_{k=1}^{n} p_{k m}p_{k 1} & \cdots & \summe_{k=1}^{n} p_{k m}p_{k m}} \vektor{w_1 \\ \vdots \\ w_m} [/mm] = [mm] \vektor{\summe_{k=1}^{n} p_{k 1}y_k \\ \vdots \\ \summe_{k=1}^{n} p_{k m}y_k}
[/mm]
(Hoffentlich habe ich mich da nicht mit irgendeinem Index vertan)
>
> Ich hoffe zwar selten, dass ich einen Fehler gemacht habe,
> bei dem Ausdruck bin ich doch schon eher dazu bereit, wenn
> ich mir vorstelle, dass ich das alles in der Hesse-Matrix
> verarbeiten darf.
> Gibt es da nicht irgendwlelche Tricks und Kniffe um das
> alles zu vereinfachen bzw. kann das überhaupt korrekt
> sein?^^
> Mal ganz pragmatisch gedacht, hat doch kein Tutor lust
> sowas zu korrigieren
Gruß
meili
|
|
|
| |
|
Hi,
Danke für Deine Antwort! Das hilft mir weiter, auch wenn ich gestehen muss, dass ich da so nicht drauf gekommen wäre..
Wenn ich das richtig verstehe, ist die neue Matrix genau das, was ich ausgerechnet habe für ein [mm] w_i [/mm] nur etwas anders aufgeschrieben, oder? Anders gesagt, ich habe mich mit dem [mm] w_i [/mm] nicht unbedingt vertan, sondern hätte das nur etwas konsequenter durchziehen müssen..?
$ [mm] \pmat{ \summe_{k=1}^{n} p_{k 1}p_{k 1} & \cdots & \summe_{k=1}^{n} p_{k 1}p_{k m} \\ \vdots & \ddots & \vdots \\ \summe_{k=1}^{n} p_{k m}p_{k 1} & \cdots & \summe_{k=1}^{n} p_{k m}p_{k m}} [/mm] ist achsensymmetrisch und quadratisch ,d.h. aufjedenfall invertierbar.
Das heißt ich gehe hier jetzt mal davon aus, dass ich den Vektor w bestimmen kann.
Problematisch wird das eher momentan bei der Hesse-Matrix. Die Aufgabe gibt nicht explizit an, dass man Beweisen muss, dass es ein lokales Minimum ist, sondern gibt vor, dass wir dort ein Minimum erwarten a la "Zeigen sie, dass ... durch ... ein Minimum vorliegt".
Dennoch fände ich es mal interessant, das vollkommen durchzugehen. Die Ableitungen zu bilden ist relativ einfach: [mm] \bruch{d}{dw_i dw_j}=2*\summe_{k=1}^{n}p_{k i}*p_{k j} [/mm]
Damit hängen die Einträge der Hesse-Matrix schonmal nicht mehr vom Vektor w ab, also muss ich jetzt doch die Definitheit dieser Matrix bestimmen. Diese kann ich wahrscheinlich aber nicht mehr so einfach, ohne genauere Kentniss von den Einträgen [mm] p_{i j} [/mm] der Matrix bestimmen, d.h. ich müsste mir dann schon genauer ansehen wie diese Aufgebaut sind, oder?
Wikipedia sagt mir prinzipiell würden die Eigenwerte der Matrix eine Möglichkeit sein (Minimum vorhanden, falls alle Eigenwerten > 0), oder man müsste zeigen, dass [mm] x^T*A*x>0 [/mm] gilt für eine Matrix A und Vektor x.
Momentan muss ich leider jedoch annehmen, dass [mm] p_{i j}\in\IR [/mm] gilt, d.h. ich habe momentan keine Ahnung ob es sich tatsächlich um ein Minimum handelt.
Was klar ist, dass diese Matrix achsensymmetrisch ist und auf der Hauptdiagonalen nur positive Werte enthält. Ich habe mir mal wieder ein Beispiel mit einer 2x2 Matrix gemacht und diese untersucht, aber leider kann auch hier die Definitheit negativ werden.
Bezogen auf die Aufgaben könnte ich noch annehmen, dass für alle [mm] p_{i j}>0 [/mm] gilt, jedoch bringt mich das nicht wirklich weiter. Das macht mich im Bezug auf die Aufgaben auch gerade etwas stutzig, denn schließlich sollte doch hier (nach Aufgabe) aufjedenfall ein Minimum herauskommen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:20 Fr 11.11.2011 | | Autor: | meili |
Hallo,
Berechne den Tiefpunkt folgender Funktion:
$ [mm] f(w)=(P\cdot{}w-y)^T(P\cdot{}w-y) [/mm] $
(P ist eine NxM-Matrix, y ein Nx1 Vektor und w ein Mx1 Vektor)
bedeutet die beste Näherung des nichtquadratischen linearen Gleichungssystem [mm] $P\cdot{}w [/mm] = y$ zu finden.
Vergleiche ![[]](/images/popup.gif) Methode der kleinsten Quadrate, Lösung des Minimierungsproblem.
Da steht auch, wenn P vollen Rang hat, ist [mm] $P^T*P [/mm] = [mm] \pmat{ \summe_{k=1}^{n} p_{k 1}p_{k 1} & \cdots & \summe_{k=1}^{n} p_{k 1}p_{k m} \\ \vdots & \ddots & \vdots \\ \summe_{k=1}^{n} p_{k m}p_{k 1} & \cdots & \summe_{k=1}^{n} p_{k m}p_{k m}} [/mm] $ positiv definit.
Gruß
meili
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 So 13.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
