Householder-Transformation < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:17 Fr 23.01.2009 | | Autor: | Pacapear |
Hallo.
Ich verstehe in meinem Skript die Herleitung der Berechnungsformel nicht.
Ich habe hier folgendes stehen:
1) [mm] Q=I-2*\bruch{vv^T}{v^Tv} [/mm] heißt Householder-Reflexion.
2) Wendet man Q auf einen Vektor y an, so gilt: [mm] y\mapsto Qy=(I-2*\bruch{vv^T}{v^Tv})y=y-2*\bruch{}{}v
[/mm]
3) Soll y auf ein Vielfaches [mm] \alpha e_1 [/mm] des ersten Einheitsvektors [mm] e_1 [/mm] ebgebildet werden, so gilt: [mm] \alpha e_1=y-2*\bruch{}{}v\in span(e_1)
[/mm]
4) Daraus folgt: [mm] |\alpha|=||y||_2 [/mm] und [mm] v\in span(y-\alpha e_1)
[/mm]
5) Daher kann man Q bestimmen durch [mm] v:=y-\alpha e_1 [/mm] mit [mm] \alpha=\pm ||y||_2
[/mm]
6) Um Auslöschung bei der Berechnung von [mm] v=(y_1-\alpha,y_2,...,y_n)^T [/mm] zu vermeiden, wählt man [mm] \alpha:=-sgn(y_1)*||y||_2
[/mm]
7) Es gilt [mm] ==||y||_2^2-2\alpha+\alpha^2=-2\alpha(y_1-\alpha)
[/mm]
8) Daher lässt sich [mm]\ Qx[/mm] für beliebige [mm] x\in\IR^n [/mm] am einfachsten berechnen durch [mm] Qx=x-2*\bruch{}{}v=x+\bruch{}{\alpha(y_1-\alpha)}v
[/mm]
So, jetzt meine Fragen:
1) Hingenommen, ok.
2) Ok, Multiplikation einfach ausgerechnet.
3) Das ich jetzt den Term [mm] y-2*\bruch{}{}v [/mm] mit [mm] \alpha e_1 [/mm] gleichsetze ist mir auch noch klar, ich will ja halt, dass es darauf abgebildet wird. Warum das ganze jetzt aber in der linearen Hülle von [mm] e_1 [/mm] liegt, versteh ich nicht. Weiß jemand, warum?
4) Ich verstehe weder die erste Folgerung, noch die zweite ![[nixweiss]](/images/smileys/nixweiss.gif "[nixweiss]")
5) auch hier verstehe ich die erste Folgerung nicht. In der zweiten Folgerung lös ich nur den betrag auf, oder?
6) Hingenommen, ok.
7) Skalarprodukt berechnen, bin ich nicht wirklich fit drin. Kann die Formel nicht ganz nachvollziehen. Kann mir jemand einen nach dem zweiten Gleichheitszeichen die Umformung erklären?
8) Einfach alle Ergebnisse und Folgerungen auf 2) anwenden. Das ist wieder klar.
Bin für jede Hilfe sehr dankbar.
LG, Nadine
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:58 Fr 23.01.2009 | | Autor: | Blech |
Hallo.
>
> Ich verstehe in meinem Skript die Herleitung der
> Berechnungsformel nicht.
> Ich habe hier folgendes stehen:
>
>
>
> 1) [mm]Q=I-2*\bruch{vv^T}{v^Tv}[/mm] heißt Householder-Reflexion.
>
> 2) Wendet man Q auf einen Vektor y an, so gilt: [mm]y\mapsto Qy=(I-2*\bruch{vv^T}{v^Tv})y=y-2*\bruch{}{}v[/mm]
>
> 3) Soll y auf ein Vielfaches [mm]\alpha e_1[/mm] des ersten
> Einheitsvektors [mm]e_1[/mm] ebgebildet werden, so gilt: [mm]\alpha e_1=y-2*\bruch{}{}v\in span(e_1)[/mm]
Ein Vielfaches des 1. Einheitsvektors [mm] ($\alpha$ [/mm] ist ein Skalar) liegt im Spann desselben.
>
> 4) Daraus folgt: [mm]|\alpha|=||y||_2[/mm] und [mm]v\in span(y-\alpha e_1)[/mm]
Eine Spiegelung verändert die Länge eines Vektors nicht. Wir spiegeln y auf [mm] $\alpha e_1$, [/mm] der Einheitsvektor hat Länge 1, also ist [mm] $\alpha$ [/mm] die Länge des Vektors.
Zum zweiten;
formal: [mm] $Qy=\alpha e_1 [/mm] = [mm] y-\underbrace{2\cdot{}\bruch{}{}}_{=:\beta, \text{ ein Skalar}} [/mm] v $
[mm] $\Rightarrow v=\frac{1}{\beta} (y-\alpha e_1)$
[/mm]
Und das ist im Spann von [mm] $y-\alpha e_1$.
[/mm]
die anschauliche, aber leider schwer zu formulierende Variante: Wir bewegen uns ja im Moment rein im 2-dimensionalen (wir können ja eine Ebene durch 2 beliebige Vektoren zeichnen). Also mal Dir mal 2 gleich lange Vektoren auf, der eine ist y, der andere [mm] $\alpha e_1$. [/mm] Jetzt gilt für Spiegelungen Einfallswinkel gleich Ausfallswinkel, also muß die Spiegelungsebene genau durch die Winkelhalbierende von den beiden Vektoren gehen. Und die Winkelhalbierende von 2 *gleich langen* Vektoren ist [mm] $y+\alpha e_1$ [/mm] und [mm] $y-\alpha e_1$ [/mm] steht senkrecht drauf (wiederum: die Vektoren sind gleich lang), also ist es die Normale auf die Spiegelungsebene.
> 5) Daher kann man Q bestimmen durch [mm]v:=y-\alpha e_1[/mm] mit
> [mm]\alpha=\pm ||y||_2[/mm]
Die Länge von v ist wurscht, weil wir die in der Definition von Q rausdividieren. Wir brauchen den Faktor [mm] $\beta$ [/mm] also nicht.
> 7) Es gilt [mm]==||y||_2^2-2\alpha+\alpha^2=-2\alpha(y_1-\alpha)[/mm]
Das Skalarprodukt ist eine symmetrische Bilinearform, Du kannst es statt mit spitzen Klammern auch schreiben als
[mm] $(y^t-\alpha e_1^t)( y-\alpha e_1)$
[/mm]
und dann die binomische Formel anwenden.
ciao
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:35 So 25.01.2009 | | Autor: | Pacapear |
Hi Stefan!
Danke für deine Antwort.
Ich habe noch ein paar Fragen dazu:
> > 3) Soll y auf ein Vielfaches [mm]\alpha e_1[/mm] des ersten
> > Einheitsvektors [mm]e_1[/mm] ebgebildet werden, so gilt: [mm]\alpha e_1=y-2*\bruch{}{}v\in span(e_1)[/mm]
>
> Ein Vielfaches des 1. Einheitsvektors ([mm]\alpha[/mm] ist ein
> Skalar) liegt im Spann desselben.
Liegt das Vielfache deshalb drin, weil die Hülle von [mm] e_1 [/mm] ja die Menge aller Linearkombinationen von [mm] e_1 [/mm] ist, und [mm] \alpha e_1 [/mm] ist eine Linearkombination von [mm] e_1?
[/mm]
> > 4) Daraus folgt: [mm]|\alpha|=||y||_2[/mm] und [mm]v\in span(y-\alpha e_1)[/mm]
>
> Eine Spiegelung verändert die Länge eines Vektors nicht.
> Wir spiegeln y auf [mm]\alpha e_1[/mm], der Einheitsvektor hat Länge
> 1, also ist [mm]\alpha[/mm] die Länge des Vektors.
Also [mm] ||y||_2 [/mm] ist die Länge meines zu spiegelnden Vektors y, richtig?
Und da ich ich y auf [mm]\alpha e_1[/mm] spiegel, und das spiegeln die Länge von y nicht verändert, muss [mm] ||y||_2 [/mm] gleich [mm] \alpha [/mm] sein?
Warum der Betrag um das [mm] \alpha?
[/mm]
Weil eine Länge immer positiv ist?
> Zum zweiten;
>
> formal: [mm]Qy=\alpha e_1 = y-\underbrace{2\cdot{}\bruch{}{}}_{=:\beta, \text{ ein Skalar}} v[/mm]
>
> [mm]\Rightarrow v=\frac{1}{\beta} (y-\alpha e_1)[/mm]
> Und das ist
> im Spann von [mm]y-\alpha e_1[/mm].
Ist das mit dem Spann wieder das gleiche Argument wie oben?
[mm] \frac{1}{\beta} (y-\alpha e_1) [/mm] ist ein Vielfaches von [mm] y-\alpha e_1 [/mm] (weil [mm] \beta [/mm] Skalar) und damit im Spann von [mm] y-\alpha e_1?
[/mm]
> > 5) Daher kann man Q bestimmen durch [mm]v:=y-\alpha e_1[/mm] mit
> > [mm]\alpha=\pm ||y||_2[/mm]
>
> Die Länge von v ist wurscht, weil wir die in der Definition
> von Q rausdividieren. Wir brauchen den Faktor [mm]\beta[/mm] also
> nicht.
Das verstehe ich nicht.
Warum ist die Länge von v wurscht?
Wo dividieren wir sie raus?
Zu [mm]\alpha=\pm ||y||_2[/mm]: Kommt das vom Betrag auflösen?
> > 7) Es gilt [mm]==||y||_2^2-2\alpha+\alpha^2=-2\alpha(y_1-\alpha)[/mm]
>
> Das Skalarprodukt ist eine symmetrische Bilinearform, Du
> kannst es statt mit spitzen Klammern auch schreiben als
> [mm](y^t-\alpha e_1^t)( y-\alpha e_1)[/mm]
> und dann die binomische
> Formel anwenden.
Da komm ich irgendwie nicht mit zurecht.
Ich hab jetzt folgendes:
[mm]\ [/mm][mm] ==(y^T-\alpha e_1^T)*( y-\alpha e_1)=y*y-y^T\alpha e_1-\alpha e_1^Ty+\alpha^2e_1*e_1=y*y-y^T\alpha e_1-\alpha e_1^Ty+\alpha^2e_1
[/mm]
Hier komme ich nicht mehr weiter
Kannst du mir nochmal weiter helfen?
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:27 So 25.01.2009 | | Autor: | Blech |
Hallo,
> Liegt das Vielfache deshalb drin, weil die Hülle von [mm]e_1[/mm] ja
> die Menge aller Linearkombinationen von [mm]e_1[/mm] ist, und [mm]\alpha e_1[/mm]
> ist eine Linearkombination von [mm]e_1?[/mm]
Ja.
> Warum der Betrag um das [mm]\alpha?[/mm]
> Weil eine Länge immer positiv ist?
Hier hab ich bei Deiner Begründung ein Problem mit Ursache und Wirkung.
Wir wissen noch nichts über [mm] $\alpha$, [/mm] es ist nur unser Platzhalter für den Faktor, den wir vor dem [mm] $e_1$ [/mm] brauchen. Und jetzt schauen wir, welche Bedingungen [mm] $\alpha$ [/mm] erfüllen muß. Und eine ist, daß [mm] $\| y\|_2=\|\alpha e_1\|_2=|\alpha|\cdot\| e_1 \|_2 [/mm] = [mm] |\alpha|$ [/mm] gelten muß.
Das Vorzeichen von [mm] $\alpha$ [/mm] wird dabei nicht eingeschränkt (es gibt auch zwei verschiedene Vektoren, auf die wir v spiegeln können) und wir nutzen die Freiheit ja auch nachher, um durch die geeignete Wahl des Vorzeichens von [mm] $\alpha$ [/mm] die Stabilität zu verbessern.
> Ist das mit dem Spann wieder das gleiche Argument wie
> oben?
Es ist nicht wirklich ein "Argument". Es ist die Definition des Spanns. =P
> Das verstehe ich nicht.
> Warum ist die Länge von v wurscht?
> Wo dividieren wir sie raus?
$ [mm] Q=I-2\cdot{}\bruch{vv^T}{v^Tv} [/mm] = I - [mm] 2\frac{v}{\| v \|_2}\frac{v^t}{\| v \|_2}$
[/mm]
[mm] $v^tv=\| v\|^2_2$. [/mm] Das wirst Du noch häufig brauchen, u.a. bei 7).
Es sollte direkt aus einer Definition folgen. Aus welcher hängt davon ab, wie Ihr die verschiedenen Sachen definiert habt. =)
> $ [mm] ==(y^T-\alpha e_1^T)\cdot{}( y-\alpha e_1)=$
[/mm]
> [mm] $y\cdot{}y-y^T\alpha e_1-\alpha e_1^Ty+\alpha^2e_1\cdot{}e_1$
[/mm]
Es ist [mm] $y^t [/mm] y$ und [mm] $e_1^t e_1$. [/mm] Wenn Du nicht transponierst, was soll dann [mm] $y\cdot [/mm] y$ auch sein? Die Operation ist nicht definiert. Du kannst Matrizen (und damit auch Vektoren) nur miteinander multiplizieren, wenn die Zahl der Spalten des ersten Faktors mit der Zahl der Zeilen des zweiten übereinstimmt.
Wie oben erwähnt:
[mm] $v^tv=\| v\|^2_2$
[/mm]
> [mm] $-y^T\alpha e_1-\alpha e_1^Ty$
[/mm]
[mm] $y^t e_1=e_1^t [/mm] y$. Wie gesagt, ein Skalarprodukt ist symmetrisch. Du kannst Dir aber auch anschauen, wie Du [mm] $y^t e_1$ [/mm] berechnen würdest, und es dann sehen.
> $ [mm] \alpha^2e_1 [/mm] $
[mm] $e_1^t e_1=1$, [/mm] definitiv, absolut und ganz sicher nicht [mm] $e_1$. [/mm] Streich Dir das ganz fett rot an, weil bei einem Skalarprodukt niemals ein Vektor rauskommen wird. =)
ciao
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:25 So 25.01.2009 | | Autor: | Pacapear |
Hallo Stefan!
> > Warum der Betrag um das [mm] \alpha?
[/mm]
> > Weil eine Länge immer positiv ist?
> Hier hab ich bei Deiner Begründung ein Problem mit Ursache und Wirkung.
> Wir wissen noch nichts über $ [mm] \alpha [/mm] $, es ist nur unser Platzhalter
> für den Faktor, den wir vor dem $ [mm] e_1 [/mm] $ brauchen.
Hmm, aber [mm] \alpha [/mm] ist doch genau die Länge von unserem Vektor y, also [mm] \alpha=||y||_2^2, [/mm] oder nicht?
Und Längen müssen doch immer positiv sein, oder nicht , deshalb doch ein Betrag, dachte ich ![[haee]](/images/smileys/haee.gif "[haee]")
> > Das verstehe ich nicht.
> > Warum ist die Länge von v wurscht?
> > Wo dividieren wir sie raus?
> [mm]Q=I-2\cdot{}\bruch{vv^T}{v^Tv} = I - 2\frac{v}{\| v \|_2}\frac{v^t}{\| v \|_2}[/mm]
Hmm, irgendwie sehe ich da kein rausdividieren.
Du teilst die Länge/Norm doch einfach nur auf, aber sie ist doch immer noch da
> Es ist [mm]y^t y[/mm] und [mm]e_1^t e_1[/mm]. Wenn Du nicht transponierst,
> was soll dann [mm]y\cdot y[/mm] auch sein? Die Operation ist nicht
> definiert. Du kannst Matrizen (und damit auch Vektoren) nur
> miteinander multiplizieren, wenn die Zahl der Spalten des
> ersten Faktors mit der Zahl der Zeilen des zweiten
> übereinstimmt.
In der Vorlesung hat unser Prof immer einen Mal-Punkt (einen dicken Mal-Punkt) für Skalarprodukt benutzt.
Wenn er keinen Punkt gemacht hat, dann wars (wohl) auch kein Skalarprodukt.
Etwas verwirrend, weil er manchmal Punkte gemacht hat, und manchmal auch nicht...
> [mm]e_1^t e_1=1[/mm], definitiv, absolut und ganz sicher nicht [mm]e_1[/mm].
> Streich Dir das ganz fett rot an, weil bei einem
> Skalarprodukt niemals ein Vektor rauskommen wird. =)
Ja, stimmt, das hab ich irgendwie völlig übersehen 
So, ich hab jetzt nochmal gerechnet, so weit bin ich jetzt:
[mm] ==+<-\alpha e_1,y-\alpha e_1>=++<-\alpha e_1,y>+<-\alpha e_1,-\alpha e_1>
[/mm]
[mm] =||y||_2^2++<-\alpha e_1,y>+||-\alpha e_1||_2^2=||y||_2^2++<-\alpha e_1,y>+(|-\alpha|*||e_1||_2)^2
[/mm]
[mm] =||y||_2^2++<-\alpha e_1,y>+(|\alpha|*1)^2=||y||_2^2++<-\alpha e_1,y>+|\alpha|^2
[/mm]
So, jetzt komme ich nicht mehr weiter.
Ich weiß nicht, wie ich die beiden Skalarprodukte in der Mitte lösen soll.
Könntest du mir nochmal helfen?
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:51 Mo 26.01.2009 | | Autor: | Blech |
> Hallo Stefan!
>
>
>
> > > Warum der Betrag um das [mm]\alpha?[/mm]
> > > Weil eine Länge immer positiv ist?
>
> > Hier hab ich bei Deiner Begründung ein Problem mit Ursache
> und Wirkung.
> > Wir wissen noch nichts über [mm]\alpha [/mm], es ist nur unser
> Platzhalter
> > für den Faktor, den wir vor dem [mm]e_1[/mm] brauchen.
>
> Hmm, aber [mm]\alpha[/mm] ist doch genau die Länge von unserem
[mm] $|\alpha|$ [/mm] ist die Länge von [mm] $\alpha e_1$, [/mm] nicht [mm] $\alpha$. $\alpha$ [/mm] enthält auch noch die Richtung.
> > > Das verstehe ich nicht.
> > > Warum ist die Länge von v wurscht?
> > > Wo dividieren wir sie raus?
>
> > [mm]Q=I-2\cdot{}\bruch{vv^T}{v^Tv} = I - 2\frac{v}{\| v \|_2}\frac{v^t}{\| v \|_2}[/mm]
>
>
> Hmm, irgendwie sehe ich da kein rausdividieren.
[mm] $\frac{v}{\| v \|_2}$
[/mm]
Sieht für mich sehr nach einer Division aus. Ich teile den Vektor v durch seine Länge. =)
> In der Vorlesung hat unser Prof immer einen Mal-Punkt
> (einen dicken Mal-Punkt) für Skalarprodukt benutzt.
Wieso hat er dann hier immer [mm] $<\cdot,\cdot>$ [/mm] hergenommen?
Nimm auf jeden Fall was anderes her, als einen normalen Punkt, wenn Du ein Skalarprodukt meinst. [mm] $\circ$ [/mm] zum Beispiel, aber es ist meist einfacher, die Vektoren/Matrizen zu transponieren.
> [mm]==+<-\alpha e_1,y-\alpha e_1>=++<-\alpha e_1,y>+<-\alpha e_1,-\alpha e_1>[/mm]
>
> [mm]=||y||_2^2++<-\alpha e_1,y>+||-\alpha e_1||_2^2=||y||_2^2++<-\alpha e_1,y>+(|-\alpha|*||e_1||_2)^2[/mm]
>
> [mm]=||y||_2^2++<-\alpha e_1,y>+(|\alpha|*1)^2=||y||_2^2++<-\alpha e_1,y>+|\alpha|^2[/mm]
>
Wie in der letzten Antwort geschrieben:
$ [mm] y^t e_1=e_1^t [/mm] y $
[mm] $-y^t\alpha e_1 [/mm] - [mm] \alpha e_1^t [/mm] y= [mm] -\alpha y^t e_1 [/mm] - [mm] \alpha y^t e_1 [/mm] = [mm] -2\alpha y^t e_1 [/mm] = -2 [mm] \alpha $
[/mm]
> So, jetzt komme ich nicht mehr weiter.
> Ich weiß nicht, wie ich die beiden Skalarprodukte in der
> Mitte lösen soll.
![[]](/images/popup.gif) Das und das solltest Du in linearer Algebra und/oder am Anfang von Numerik gehört haben.
ciao
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:16 Di 07.04.2009 | | Autor: | Blech |
Hi,
Wir hatten doch:
$ [mm] \Rightarrow v=\frac{1}{\beta} (y-\alpha e_1) [/mm] $
[mm] $\frac{1}{\beta}$ [/mm] ist ein skalierender Faktor, weil [mm] $\beta$ [/mm] ein Skalar ist, sonst könnten wir auch nicht durch [mm] $\beta$ [/mm] teilen.
(Es ist nicht unbedingt die Länge von v, weil ich nicht weiß, ob [mm] $y-\alpha e_1$ [/mm] Länge 1 hat, und ich im Moment keinen Bock hab, es mir zu überlegen)
Nun können wir v aber skalieren, wie wir lustig, weil wir nachher v eh normieren mit [mm] $\frac{v}{\| v\|_2}\frac{v^t}{\| v\|_2}$. [/mm] Egal, was [mm] $\beta$ [/mm] ist, der Vektor wird auf Länge 1 gebracht. Also gibt es keinen Grund ihn vorher irgendwie zu skalieren, weil die Länge von v unerheblich ist.
[mm] $\| v\|_2 [/mm] = [mm] \| \frac{1}{\beta} (y-\alpha e_1) \|_2 [/mm] = [mm] \frac{1}{|\beta|}\|y-\alpha e_1\|_2$
[/mm]
[mm] $\Rightarrow \frac{v}{\| v\|_2} [/mm] = [mm] \underbrace{\frac{|\beta|}{\beta}}_{=\pm 1}\frac{y-\alpha e_1}{\|y-\alpha e_1\|_2}$
[/mm]
[mm] $\Rightarrow\frac{v}{\| v\|_2}\frac{v^t}{\| v\|_2}=\left(\frac{|\beta|}{\beta}\right)^2\frac{y-\alpha e_1}{\|y-\alpha e_1\|_2}\frac{y^t-\alpha e_1^t}{\|y-\alpha e_1\|_2}$
[/mm]
ciao
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:11 Mo 06.04.2009 | | Autor: | Pacapear |
Hallo!
> > 7) Es gilt [mm]==||y||_2^2-2\alpha+\alpha^2=-2\alpha(y_1-\alpha)[/mm]
Ich verstehe das letzte Gleichheitszeichen nicht.
Ich habe wie folgt gerechnet:
[mm] ||y||_2^2-2\alpha+\alpha^2
[/mm]
[mm] =||y||_2^2-2\alpha+(-sgn(y_1)*||y||_2)^2
[/mm]
[mm] =||y||_2^2-2\alpha+(-sgn(y_1))^2*||y||_2^2
[/mm]
[mm] =||y||_2^2-2\alpha+(+1)*||y||_2^2
[/mm]
[mm] =||y||_2^2-2\alpha+||y||_2^2
[/mm]
[mm] =2||y||_2^2-2\alpha
[/mm]
Aber wie komme ich von hier auf [mm] -2\alpha(y_1-\alpha)?
[/mm]
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:20 Di 07.04.2009 | | Autor: | Blech |
Zum zweiten:
> Aber wie komme ich von hier auf [mm]-2\alpha(y_1-\alpha)?[/mm]
Ersetz das [mm] $\|y\|_2^2$ [/mm] durch [mm] $\alpha^2$, [/mm] nicht andersrum. =)
ciao
Stefan
|
|
|
|
