Givens Rotation < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:38 Fr 18.09.2009 | | Autor: | tynia |
Hallo. Ich habe nur eine kurze Frage. Hoffe einer von euch hier kann mir dabei helfen. Danke schonmal.
Wenn ich jetzt eine Matrix A= [mm] \begin{pmatrix}
-1 & 1 & 0 \\ 0 & 1 & 0 \\
1 & -1 & \wurzel{2}
\end{pmatrix} [/mm] , woher weiß ich da, welche Elemente ich da zuerst eliminieren soll?
LG
|
|
| |
|
> Hallo. Ich habe nur eine kurze Frage. Hoffe einer von euch
> hier kann mir dabei helfen. Danke schonmal.
>
> Wenn ich jetzt eine Matrix A= [mm]\begin{pmatrix}
-1 & 1 & 0 \\ 0 & 1 & 0 \\
1 & -1 & \wurzel{2}
\end{pmatrix}[/mm]
> habe, woher weiß ich da, welche Elemente ich da zuerst
> eliminieren soll?
Es kommt wohl darauf an, was du mit der Transformation
überhaupt beabsichtigst. Was ist das Ziel ?
LG
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:44 Fr 18.09.2009 | | Autor: | tynia |
Ich soll den QR algorithmus mittels Givens Rötation durchführen.
Eine Idee??
|
|
|
| |
|
> Ich soll den QR algorithmus mittels Givens Rötation
> durchführen.
>
> Eine Idee??
Hallo,
bei http://de.wikipedia.org/wiki/Givens-Rotation
lese ich:
Die Idee besteht darin, sukzessiv die Elemente unterhalb der Hauptdiagonalen auf Null zu setzen, indem man die Matrix von links mit Givens-Rotationen multipliziert. Zunächst bearbeitet man die erste Spalte von oben nach unten und dann nacheinander die anderen Spalten ebenfalls von oben nach unten.
Damit sollte die Reihenfolge klar sein.
![[gutenacht]](/images/smileys/gutenacht.gif "[gutenacht]")
Al
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:11 Sa 19.09.2009 | | Autor: | tynia |
Ok. ich habe hier jetzt eine Aufgabe versucht zu rechnen und dazu habe ich jetzt eine Frage. Ich poste mal das, was ich habe.
Erstmal ein bißchen Theorie, damit man versteht, wie ich vorgegangen bin:
Die Matrix A wird mit Givensrotationen auf obere Dreiecksform gebracht.
Das Grundprinzip sieht so aus:
Man formt den Vektor [mm] (x,y)^{T} [/mm] in den Vektor [mm] (r,0)^{T} [/mm] um, wozu man die Matrix [mm] G=\begin{pmatrix}c & s \\-s & c\end{pmatrix} [/mm] verwendet. Es ist [mm] c=\bruch{x}{r},s=\bruch{y}{r},r=\wurzel{x^{2}+y^{2}}
[/mm]
Damit gilt: [mm] G\begin{pmatrix} x \\ y \end{pmatrix}=\begin{pmatrix} cx+sy \\ -sx+cy \end{pmatrix}=\begin{pmatrix} r \\ 0 \end{pmatrix}
[/mm]
Wenn A größer als 2×2 ist, wird die obige Matrix in den anderen Richtungen durch die Identität fortgesetzt.
Also ich habe jetzt folgende Matrix:
[mm] A=\begin{pmatrix}1 & 5 & 4 \\-2 & 1 & 3 \\2 & 0 & -2\end{pmatrix}
[/mm]
Als erstes muss ich ja [mm] a_{31} [/mm] eliminieren:
[mm] x=a_{11}=1
[/mm]
[mm] y=a_{21}=-2 [/mm]
[mm] r=\wurzel{1^{2}+(-2)^{2}}=\wurzel{5}
[/mm]
[mm] c=\bruch{x}{r}=\bruch{1}{\wurzel{5}} ,s=\bruch{y}{r}=-\bruch{2}{\wurzel{5}}
[/mm]
Daraus folgt: [mm] G_{21}=\begin{pmatrix}c & s & 0 \\-s & c & 0 \\0 & 0 & 1\end{pmatrix}=\begin{pmatrix}\bruch{1}{\wurzel{5}} & -\bruch{2}{\wurzel{5}} & 0 \\-\bruch{2}{\wurzel{5}} & \bruch{1}{\wurzel{5}} & 0 \\0 & 0 & 1\end{pmatrix}
[/mm]
[mm] A_{1}=G_{21}A=\begin{pmatrix}\wurzel{5} & \bruch{3}{\wurzel{5}} & -\bruch{2}{\wurzel{5}} \\0 & \bruch{11}{\wurzel{5}} & \bruch{11}{\wurzel{5}} \\2 & 0 & -2\end{pmatrix}
[/mm]
usw.
Meine Frage ist nun, woher weiß ich welche [mm] a_{ij} [/mm] mein x und y sind?
Ich verstehe das irgendwie nicht so ganz. Gibt es da irgendein Schema?
Wenn ich jetzt ne allgemeine 3x3-Matrix habe:
[mm] A=\begin{pmatrix}a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} & a_{23} \\a_{31} & a_{32} & a_{33}\end{pmatrix}
[/mm]
Wenn ich jetzt [mm] a_{21} [/mm] eliminieren möchte, ist mein x= [mm] a_{11} [/mm] und [mm] y=a_{21}. [/mm]
Wenn ich [mm] a_{31} [/mm] eliminieren möchte, ist mein x= [mm] a_{11} [/mm] und [mm] y=a_{31}.
[/mm]
Wenn ich [mm] a_{32} [/mm] eliminieren möchte, ist mein x= [mm] a_{?} [/mm] und [mm] y=a_{?}. [/mm]
Vielleicht kann mir das ja jemand erklären.
Danke schonmal. LG
|
|
|
| |
|
du wilst immer einen eintrag der Matrix "nullen".
betrachte dazu den Spaltenvektor, der diesen Eintrag enthält!!
in diesem Spaltenvektor finde dein x und y, wobei y der zu nullende eintrag ist und x derjenige, der die länge kompensieren soll (sprich zu r wird).
in dem beispiel deiner frage also: wenn du a32 nullen willst, betrachte den mittleren Spaltenvektor der matrix. der zu nullende ist wie gesagt a32, der eintrag der die länge kompensieren soll ist der erste eintrag des mittleren spaltenvektors, also a12
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:21 Sa 19.09.2009 | | Autor: | tynia |
danke
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:41 Sa 19.09.2009 | | Autor: | tynia |
Hab doch noch ne Frage. Also ich habe jetzt im Internet ein durchgerechnetes Beispiel zur Givens Rotation gefunden, und da passt das mit deiner Aussage nicht überein.
> in dem beispiel deiner frage also: wenn du a32 nullen
> willst, betrachte den mittleren Spaltenvektor der matrix.
> der zu nullende ist wie gesagt a32, der eintrag der die
> länge kompensieren soll ist der erste eintrag des
> mittleren spaltenvektors, also a12
>
![[]](/images/popup.gif) HIER ist der [mm] a_{32} [/mm] zu nullen und der Eintrag, der die Länge kompensieren soll ist da aber [mm] a_{22}. [/mm] Oder habe ich das falsch verstanden?
|
|
|
| |
|
Hm, also in dem Beispiel dort ist eine komplette Zerlegung angestrebt, während ich bei meiner Antwort nur das Ziel hatte a32 zu nullen...
Ich werde die ganze Sache jetzt eifnach mal ausführlich durchgehen, um die Verwirrung die ich mit meiner vorschnellen, nicht wirklich falschen, aber im Kontext einer QR-Zerlegung wohl eher unbrauchbaren Wahl des r-Eintrags verursacht habe =D
Also von Anfang an:
Dir liegt eine Matrix A vor.
Diese Matrix soll in Q*R zerlegt werden, also Q*R=A.
Q ergibt sich am Ende durch das Produkt der einzelnen Rotationsmatrizen, also [mm] Q=Q_{1}*Q_{2}*Q_{3}...*Q_{n}
[/mm]
Diese einzelnen Rotationsmatrizen [mm] Q_{1} [/mm] bis [mm] Q_{n} [/mm] sind diejenigen, die du mithilfe der "Schablone"
[mm] \pmat{ c & s \\ -s & c } [/mm] in jedem Schritt ermittelst, jede dieser Rotationsmatrizen sorgt dafür, dass ein Eintrag der Matrix genullt wird.
Bekanntlich ermittelst du die einzelnen Rotationsmatrizen anhand eines Spaltenvektors. In diesem Spaltenvektor ändert die Rotationsmatrix zwei Einträge: einen macht sie zu Null, einen zu r.
Geometrisch betrachtet passiert folgendes: dieser spaltenvektor "rotiert", dreht sich also.
Insbesondere wird seine Länge nicht verändert!
Wenn du also den einen Eintrag zu Null machst, dann ist der Vektor kürzer geworden, damit er jedoch gleich lang bleibt, wird dieses kompensiert, indem ein anderer Eintrag zu r wird.
Es ist dabei egal, in welchem der anderen Einträge die Länge kompensiert wird!! Das heisst theoretisch kannst du als dein x jede andere Koordinate wählen.
Im Kontext einer QR-Zerlegung bist du aber nicht so frei!
Denn:
Du ermittelst die Rotationsmatrix zwar anhand des einen betrachteten Spaltenvektors.
Aber die "fertige" Rotationsmatrix multiplizierst du dann mit der gesamten Matrix, nicht nur mit dem einen Spaltenvektor!
Die Rotationsmatrix verändert also nicht nur den Spaltenvektor anhand dessen du sie konstruiert hast, sondern sie verändert auch die übrigen Spaltenvektoren der Matrix!
Dabei kann es passieren, dass ein Eintrag in einer anderen Spalte, den du vorher schon zu null gemacht hast, sich nun wieder verändert und nicht mehr null ist.
Da du aber eine rechte obere Dreiecksmatrix anstrebst (QR-Zerlegung), willst du dass einmal genullte Einträge auch null bleiben.
Erstmal muss man also entscheiden, in welcher Reihenfolge man welchen Eintrag nullt.
Dabei ist es üblich so vorzugehen:
[mm] \pmat{ * & * & * \\ * & * & * \\ * & * & * \\ * & * & *} [/mm] -> [mm] \pmat{ * & * & * \\ 0 & * & * \\ * & * & * \\ * & * & *} [/mm] -> [mm] \pmat{ * & * & * \\ 0 & * & * \\ 0 & * & * \\ * & * & *} [/mm] -> [mm] \pmat{ * & * & * \\ 0 & * & * \\ 0 & 0 & * \\ * & * & *} [/mm] -> [mm] \pmat{ * & * & * \\ 0 & * & * \\ 0 & 0 & * \\ 0 & * & *} [/mm] -> [mm] \pmat{ * & * & * \\ 0 & * & * \\ 0 & 0 & * \\ 0 & 0 & *} [/mm] -> [mm] \pmat{ * & * & * \\ 0 & * & * \\ 0 & 0 & * \\ 0 & 0 & 0}
[/mm]
Bleibt jetzt also die Frage zu klären, um die es eigentlich geht: was ist dein x in jedem Zwischenschritt?
Betrachten wir mal die "Schablone" der Rotationsmatrix um diese Frage zu klären:
[mm] \pmat{ c & s \\ -s & c }
[/mm]
Diese Matrix kannst du in eine Einheitsmatrix einbetten! D.h es ist auch möglich:
[mm] \pmat{ 1&0&0&0 \\ 0&c&s&0 \\ 0&-s&c&0 \\ 0&0&0&1}
[/mm]
oder sogar:
[mm] \pmat{ 1&0&0&0&0&0 \\ 0&c&0&0&s&0 \\ 0&0&1&0&0&0 \\ 0&0&0&1&0&0 \\ 0&-s&0&0&c&0 \\ 0&0&0&0&0&1}
[/mm]
Du kannst die Matrix also beliebig groß machen und was noch toller ist: du kannst bestimmen, in welcher Zeile und Spalte sich die Einträge c und s bzw. c und -s befinden sollen!
Nennen wir diese Zeilen/Spalten mal Spalte x und Spalte y.
Zeile x ist im letzten Beispiel oben also die 2te Zeile,
Zeile y ist die 5te Zeile.
Spalte x ist die 2te Spalte,
Spalte y ist die 5te Spalte.
Das tolle: wenn du diese Rotationsmatrix mit einer Matrix A multiplizierst, dann werden in der Matrix A nur diejenigen Einträge des jeweiligen Spaltenvektors verändert, die sich in Spalte/Zeile x und y befinden! Alle anderen werden nicht angepackt.
Kommen wir also zum Beispiel dort auf der Seite:
Es soll dort im dritten Schritt der Eintrag [mm] a_{23} [/mm] genullt werden.
Und: die Einträge der Spalte 1 und Zeile 1 der Matrix sollen jedoch nicht verändert werden, diese sind schon "fertig"!
Also wird die Rotationsmatrix nach folgendem Schema kreiert:
[mm] \pmat{ 1&0&0 \\ 0&c&s \\ 0&-s&c }
[/mm]
Zeile x ist hier die 2te Zeile,
Zeile y ist hier die 3te Zeile.
Spalte x ist hier die 2te Spalte,
Spalte y ist hier die 3te Spalte.
Wenn man diese Rotationsmatrix mit der Matrix A multipliziert, werden in der Matrix A alle Einträge in der Zeile und Spalte 1 NICHT VERÄNDERT, genau dies ist der QR-Zerlegung dienlich.
Natürlich haben wir Zeile/Spalte x und y nicht einfach so x und y genannt - diese Zeilen bestimmen was nun DEIN x und y beim Ermitteln der Rotationsmatrix ist!
Aus diesem Grund wurde dort im Beispiel als x der Eintrag [mm] a_{22} [/mm] gewählt, denn Spalte x in der Schablone entspricht in diesem Fall Spalte 2, aus dem Grund dass Zeile 1 und Spalte 1 der Matrix A nicht angepackt werden sollen, aus dem Grund dass schon genullte Einträge nicht wieder verändert werden sollen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:25 Sa 19.09.2009 | | Autor: | awakening |
hoffentlich beantwortet =D
Anmerkung: hatte diese Mitteilung (ursprünglich Antwort^^) erstellt weil der Status nach meiner anderen Antwort immernoch offen war...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:22 Sa 19.09.2009 | | Autor: | tynia |
Auf jeden Fall. Nochmal danke.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:37 Sa 19.09.2009 | | Autor: | tynia |
Noch eine Frage:
> Die Idee besteht darin, sukzessiv die Elemente unterhalb
> der Hauptdiagonalen auf Null zu setzen, indem man die
> Matrix von links mit Givens-Rotationen multipliziert.
Was ist denn, wenn die Matrix so aussieht A= [mm] \begin{pmatrix}
1 & 3 \\2 & 1 \\4 & 0\end{pmatrix}
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:40 Sa 19.09.2009 | | Autor: | tynia |
Die Frage hat sich erledigt. Habe die Antwort schon selbst gefunden 
|
|
|
|
