Householder-Reflexion < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:19 Di 28.07.2015 | | Autor: | just |
| Aufgabe | A=[...], b=[...]
Ausgleichproblem: min{||b-Ax||}
Bestimmen Sie mittels Householder-Verfahren eine QR-Zerlegung von A. Berechnen Sie dabei weder die Housolder-Transformation H = I - [mm] 2vv^T [/mm] noch Q explizit, sondern führen Sie alle Operationen als Matrix-Vektor- und Vektor-Vektor-Multiplikation bzw. als Skalarprodukt und Multiplikation eines Vektors mit einem Skalar durch. Geben Sie Q als Produkt von Householder-Transformationen an. |
Was ist damit denn gemeint?
Oder was bedeutet Q explizit zu berechnen?
Ich hätte jetzt zunächst Q1 berechnet.
Q1=I-2*(v1*v1')/(v1'*v1)
dafür muss erst v1 berechnet werden.
Das ist, was hier gefordert war oder?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Do 30.07.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:47 Mi 10.02.2016 | | Autor: | just |
Ein Semester später beschäftige ich mich erneut mit dieser Thematik. Kann sich niemand vorstellen, was mein Professor damit meint?
Also dass ich Q=Q1*...*Qn am Ende nicht berechnen soll ist OK, aber wie soll ich denn hinkommmen ohne Qn=I-2vn*vn'/vn'*vn zu berechnen?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:05 Mi 10.02.2016 | | Autor: | sissile |
Hallo
Es geht vorallem um die Realisierung am PC. Eine Matrix*Maxtrix Multiplikation PA mit einer Householder-Transformation P kostet O(m^2n) Multiplikationen für A [mm] \in K^{m\times n}.
[/mm]
Ich kann dir nur wärmsten empfehlen: Grundlagen der Numerischen Mathematik und des Wissenschftlichen Rechnens von Martin Hanke-Bourgeois.
Sei A [mm] \in K^{m \times n} [/mm] mit vollen Rang.
Erste Schritt des Algorithmus:
Nachdem du den Vektor v für die Householder-Transformation bestimmt hast. Möchtest du die HHT [mm] P_{v} [/mm] auf A anwenden um so unter den ersten Eintrag von A in der ersten Spalte 0en zu erzeugen. Aber wir multiplizieren nicht direkt die HHT mit A sondern berechnen stattdessen:
[mm] \beta:=\frac{2}{v^{\*}v}
[/mm]
[mm] w:=A^{\*} [/mm] v
[mm] P_{v} [/mm] A= A- [mm] \frac{2}{v^{\*}v} [/mm] v v* A = A [mm] -\beta [/mm] v w*
[mm] \beta [/mm] ist eine Zahl, v ist ein Spaltenvektor und [mm] w^{\*} [/mm] ein Zeilenvektor. Du bist die Matrix*Matrix-Multiplikation also umgangen.
und dann geht´s wieder von vorne los für [mm] A_2 [/mm] ( der Teil von A ohne der ersten Zeile und Spalte von A)
In dem Buch findest du auch einen Algorithmus wie man effizient das lineare Ausgleichsproblem löst ohne auf die Matrix Q zurückgreifen zu müssen.
Hast du die Umformung im Kopf, dass die Lösung des linearen Ausgleichsproblem durch x= [mm] R_1^{-1} c_1 [/mm] wobei [mm] R_1 [/mm] der quadratische Teil in der Matrix [mm] R:=\vektor{R_1 \\ 0} [/mm] und [mm] c:=Q^{\*} b=\vektor{c_1 \\ c_2}gegeben [/mm] ist?
Um c auszurechnen braucht man Q nicht unbedingt.
[mm] c=Q^{\*} [/mm] b = [mm] P_{v_n}*..*P_{v_1}*b [/mm]
Hier rechnest du analog zuerst [mm] P_{v_1} [/mm] *b mit der Methode von oben, dann wendest du auf dein gerade berechneten vektor [mm] P_{v_2} [/mm] an usw.
Du musst hier nur auf die Dimesion von [mm] v_i [/mm] achtgeben.
Am besten du rechnest das einmal für ein Bsp durch.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:16 Mi 10.02.2016 | | Autor: | just |
Wow, vielen vielen Dank.
Nun kann ich loslegen und das auf meine Beispiele anwenden, denn das verstehe ich alles.
Danke auch für die Literaturempfehlung. Ich habe Glück, das gibt es in unserer Uni-Bibliothek als E-Book.
Danke :)
|
|
|
|
