Householder-Tranformationen < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:45 So 09.10.2011 | | Autor: | MaRaQ |
| Aufgabe | Das lineare Ausgleichsproblem [mm]min||Ax - b||_2^2[/mm] mit [mm]A = \pmat{ 3 & 6 \\ 0 & 2 \\ 4 & 8 }[/mm] und [mm]b = \vektor{0\\1\\1}[/mm] soll gelöst werden.
a) Warum ist das Problem eindeutig?
b) Überführen Sie Die Matrix A durch Householder-Transformationen in eine obere Dreiecksmatrix. Transformieren Sie Vektor b analog, um dann die Lösung [mm]x^{*}[/mm] des Ausgleichsproblems zu bestimmen.
c) Geben Sie den Wert [mm]||r||_2[/mm] mit [mm]r:=Ax^{0} - b[/mm] und [mm]x^{0}[/mm] aus b an, ohne dabei Vektor r auszurechnen. |
Ich bin mir nicht sicher, ob ich das Verfahren korrekt anwende, daher würde ich mich über ein Gegenlesen freuen - und über einen evtl. Tipp zu einer alternativen Berechnung einer Zeile, siehe unten.
Zu (a): Eindeutig, da die Spalten von A linear unabhängig voneinander sind.
Zu (b): Betrachte zunächst die erste Spalte von A und bezeichne sie im Folgenden als Vektor x.
Da [mm]x_{1}\not=0[/mm], bestimme ich Hilfsvariable [mm]\lambda[/mm] durch [mm]\lambda = ||x||_2 * \bruch{x_1}{|x_1|} = 5[/mm].
Weiter: [mm]u_1 = x + \lambda e_1 = \vektor{3\\0\\4} + \vektor{5\\0\\0} = \vektor{8\\0\\4}[/mm].
Und [mm]k_1 = x{^T}x + ||x||_2 * |x_1| = 25 + 5 * 3 = 40[/mm].
Jetzt kann ich (endlich) [mm]T_1[/mm] bestimmen:
[mm]T_1 = I - \bruch{1}{k_1}u_1*u_1^{T} = \pmat{1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1} - \bruch{1}{40} \pmat{64 & 0 & 32 \\ 0 & 6 & 0 \\ 32 & 0 & 16} = \pmat{ -0,6 & 0 & -6,4 \\ 0 & 1 & 0 \\ -4,8 & 0 & 4,8}[/mm]
Damit transformiert sich die 2. Spalte zu [mm]T_1*\vektor{6//2//8} = \vektor{-10//2//0}[/mm] und ich habe ein neues A:
A' = [mm] \pmat{ -5 & -10 \\ 0 & 2 \\ 0 & 0}
[/mm]
Jetzt ist mein A bereits in der gewünschten rechten oberen Dreiecks-Form und ich könnte theoretisch aufhören. Damit habe ich Q = [mm] T_1 [/mm] und R = A', die einfache Probe geht auch auf:
Q*R = A.
Nun soll man aber in der Praxis T gar nicht direkt bestimmen, es gibt die Möglichkeit, hier die 2. Spalte von A' zu ermitteln, ohne T direkt zu bestimmen. Ich bin mir aber nicht zu 100% im Klaren, wie das exakt funktioniert (bzw. sich die Formel zusammensetzt, da ich nur (Zahlen-)Beispiele kenne).
Hier wäre das analog nach meinen Beispielen:
[mm]T_1 * \vektor{6\\2\\8} = \vektor{6\\2\\8} - \bruch{1}{40}*80*\vektor{8\\0\\4} = \vektor{-10\\2\\0}.[/mm].
Woher kommt hier die 80? Alle anderen Werte leiten sich für mich logisch her. Die Vektoren sind ja die zweite Spalte von A sowie [mm] u_1, [/mm] weiterhin steht im Nenner des Bruchs das berechnete [mm] k_1. [/mm]
Nur diese eine Zahl ist mir vollkommen schleierhaft in ihrem Ursprung...
Weiter im Takt, es will [mm] x^{0} [/mm] berechnet werden:
Das Ausgleichsproblem kann man schreiben als
[mm]||Qb - QAx||_2 = ||\vektor{c\\d} - \vektor{Rx\\0}||_2 \rightarrow min[/mm]
Wegen [mm]||\vektor{c\\d} - \vektor{Rx\\0}||_2^2 = ||c - Rx||_2^2 + ||d||_2^2[/mm] muss fürs Minimum gelten [mm]||c - Rx^{0}||_2^2 = 0 \gdw R*x^{0}=c[/mm]
Nun ist [mm]\vektor{c\\d} = Q^{T}*b = \pmat{ -0,6 & 0 & -4,8\\ 0 & 1 & 0 \\ -6,4 & 0 & 4,8}*\vektor{0\\1\\1} = \vektor{-4,8\\1\\4,8}[/mm].
Und damit [mm]c = \vektor{-4,8\\1}[/mm].
Rückwärtssubstitution liefert
[mm] x^{0} [/mm] = [mm] \vektor{-0,04 \\ 0,5}
[/mm]
Und das ist schon ein sehr schwaches Ergebnis (Fehler oder das Verfahren so ungenau? ).
c) die Norm des Residuums gerade die Norm von d ist, welche man aus der Transformation direkt erhält. Damit ist die Aufgabe (c) für mich gelöst, die Lösung ist 4,8 - was folgende Probe bestätigt:
[mm]r = \vektor{ 2,88 \\ 0 \\ 3,84 }[/mm] , [mm]||r||_2 = 4,8[/mm].
Ich wäre um zeitnahe Antworten/Tipps sehr dankbar, da ich übermorgen nachmittag eine Prüfung (evtl. u.a. zu diesem Thema) habe, die ich gerne einigermaßen überzeugt/selbstbewusst bestreiten würde. 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:25 Mo 10.10.2011 | | Autor: | meili |
Hallo,
> Das lineare Ausgleichsproblem [mm]min||Ax - b||_2^2[/mm] mit [mm]A = \pmat{ 3 & 6 \\ 0 & 2 \\ 4 & 8 }[/mm]
> und [mm]b = \vektor{0\\1\\1}[/mm] soll gelöst werden.
> a) Warum ist das Problem eindeutig?
> b) Überführen Sie Die Matrix A durch
> Householder-Transformationen in eine obere Dreiecksmatrix.
> Transformieren Sie Vektor b analog, um dann die Lösung
> [mm]x^{*}[/mm] des Ausgleichsproblems zu bestimmen.
> c) Geben Sie den Wert [mm]||r||_2[/mm] mit [mm]r:=Ax^{0} - b[/mm] und [mm]x^{0}[/mm]
> aus b an, ohne dabei Vektor r auszurechnen.
> Ich bin mir nicht sicher, ob ich das Verfahren korrekt
> anwende, daher würde ich mich über ein Gegenlesen freuen
> - und über einen evtl. Tipp zu einer alternativen
> Berechnung einer Zeile, siehe unten.
>
> Zu (a): Eindeutig, da die Spalten von A linear unabhängig
> voneinander sind.
>
> Zu (b): Betrachte zunächst die erste Spalte von A und
> bezeichne sie im Folgenden als Vektor x.
> Da [mm]x_{1}\not=0[/mm], bestimme ich Hilfsvariable [mm]\lambda[/mm] durch
> [mm]\lambda = ||x||_2 * \bruch{x_1}{|x_1|} = 5[/mm].
[mm]\lambda = ||x||_2 = 5[/mm] ist ok,
aber was [mm] $\bruch{x_1}{|x_1|}$ [/mm] sein soll, weis ich nicht.
Wenn Du damit aber das Vorzeichen von [mm] $x_1$ [/mm] auf [mm] $\lambda$ [/mm] übertragen
willst, ist es ok, und kommt bei dem Ablauf der Householder-Transformationen vor.
> Weiter: [mm]u_1 = x + \lambda e_1 = \vektor{3\\0\\4} + \vektor{5\\0\\0} = \vektor{8\\0\\4}[/mm].
>
> Und [mm]k_1 = x{^T}x + ||x||_2 * |x_1| = 25 + 5 * 3 = 40[/mm].
>
> Jetzt kann ich (endlich) [mm]T_1[/mm] bestimmen:
> [mm]T_1 = I - \bruch{1}{k_1}u_1*u_1^{T} = \pmat{1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1} - \bruch{1}{40} \pmat{64 & 0 & 32 \\ 0 & 6 & 0 \\ 32 & 0 & 16} = \pmat{ -0,6 & 0 & -6,4 \\ 0 & 1 & 0 \\ -4,8 & 0 & 4,8}[/mm]
Hier scheint mir, kommen einige Tipp- und Rechenfehler vor:
[mm]T_1 = I - \bruch{1}{k_1}u_1*u_1^{T} = \pmat{1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1} - \bruch{1}{40} \pmat{64 & 0 & 32 \\ 0 & 0 & 0 \\ 32 & 0 & 16} = \pmat{ -0,6 & 0 & -0,8\\ 0 & 1 & 0 \\ -0,8 & 0 & 0,6}[/mm]
>
> Damit transformiert sich die 2. Spalte zu
> [mm]T_1*\vektor{6//2//8} = \vektor{-10//2//0}[/mm] und ich habe ein
> neues A:
>
> A' = [mm]\pmat{ -5 & -10 \\ 0 & 2 \\ 0 & 0}[/mm]
>
> Jetzt ist mein A bereits in der gewünschten rechten oberen
> Dreiecks-Form und ich könnte theoretisch aufhören. Damit
> habe ich Q = [mm]T_1[/mm] und R = A', die einfache Probe geht auch
> auf:
> Q*R = A.
![[ok]](/images/smileys/ok.gif "[ok]")
>
> Nun soll man aber in der Praxis T gar nicht direkt
> bestimmen, es gibt die Möglichkeit, hier die 2. Spalte von
> A' zu ermitteln, ohne T direkt zu bestimmen. Ich bin mir
> aber nicht zu 100% im Klaren, wie das exakt funktioniert
> (bzw. sich die Formel zusammensetzt, da ich nur
> (Zahlen-)Beispiele kenne).
>
> Hier wäre das analog nach meinen Beispielen:
> [mm]T_1 * \vektor{6\\2\\8} = \vektor{6\\2\\8} - \bruch{1}{40}*80*\vektor{8\\0\\4} = \vektor{-10\\2\\0}.[/mm].
>
> Woher kommt hier die 80? Alle anderen Werte leiten sich
> für mich logisch her. Die Vektoren sind ja die zweite
> Spalte von A sowie [mm]u_1,[/mm] weiterhin steht im Nenner des
> Bruchs das berechnete [mm]k_1.[/mm]
> Nur diese eine Zahl ist mir vollkommen schleierhaft in
> ihrem Ursprung...
>
> Weiter im Takt, es will [mm]x^{0}[/mm] berechnet werden:
>
> Das Ausgleichsproblem kann man schreiben als
> [mm]||Qb - QAx||_2 = ||\vektor{c\\d} - \vektor{Rx\\0}||_2 \rightarrow min[/mm]
>
> Wegen [mm]||\vektor{c\\d} - \vektor{Rx\\0}||_2^2 = ||c - Rx||_2^2 + ||d||_2^2[/mm]
> muss fürs Minimum gelten [mm]||c - Rx^{0}||_2^2 = 0 \gdw R*x^{0}=c[/mm]
>
> Nun ist [mm]\vektor{c\\d} = Q^{T}*b = \pmat{ -0,6 & 0 & -4,8\\ 0 & 1 & 0 \\ -6,4 & 0 & 4,8}*\vektor{0\\1\\1} = \vektor{-4,8\\1\\4,8}[/mm].
[mm]\vektor{c\\d} = Q^{T}*b = \pmat{ -0,6 & 0 & -0,8\\ 0 & 1 & 0 \\ -0,8 & 0 & 0,6}*\vektor{0\\1\\1} = \vektor{-0,8\\1\\0,6}[/mm].
($ [mm] Q^{T} [/mm] = Q$)
>
> Und damit [mm]c = \vektor{-4,8\\1}[/mm].
Und damit [mm]c = \vektor{-0,8\\1}[/mm]
>
> Rückwärtssubstitution liefert
> [mm]x^{0}[/mm] = [mm]\vektor{-0,04 \\ 0,5}[/mm]
[mm]x^{0}[/mm] = [mm]\vektor{-0,84 \\ 0,5}[/mm]
>
> Und das ist schon ein sehr schwaches Ergebnis (Fehler oder
> das Verfahren so ungenau? ).
>
> c) die Norm des Residuums gerade die Norm von d ist,
> welche man aus der Transformation direkt erhält. Damit ist
> die Aufgabe (c) für mich gelöst,
> die Lösung ist 4,8 -
> was folgende Probe bestätigt:
> [mm]r = \vektor{ 2,88 \\ 0 \\ 3,84 }[/mm] , [mm]||r||_2 = 4,8[/mm].
[mm]r = \vektor{ 0,48 \\ 0 \\ -0,36 }[/mm] , [mm]||r||_2 = 0,6[/mm].
>
>
> Ich wäre um zeitnahe Antworten/Tipps sehr dankbar, da ich
> übermorgen nachmittag eine Prüfung (evtl. u.a. zu diesem
> Thema) habe, die ich gerne einigermaßen
> überzeugt/selbstbewusst bestreiten würde.
Alles Gute und viel Erfolg für die Prüfung.
Gruß
meili
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:13 Mo 10.10.2011 | | Autor: | Blech |
Hi,
> $ [mm] T_1 \cdot{} \vektor{6\\2\\8} [/mm] = [mm] \vektor{6\\2\\8} [/mm] - [mm] \bruch{1}{40}\cdot{}80\cdot{}\vektor{8\\0\\4} [/mm] = [mm] \vektor{-10\\2\\0}. [/mm] $.
> Woher kommt hier die 80?
[mm] (\, u_1 u_1^t\, )\,\vektor{6\\2\\8} [/mm] = [mm] u_1\, (\, u_1^t \vektor{6\\2\\8}\,)
[/mm]
oder komplett:
[mm] $T_1\vektor{6\\2\\8}= [/mm] (I - [mm] \frac 1{k_1} u_1 u_1^t )\vektor{6\\2\\8} [/mm] = [mm] \vektor{6\\2\\8} [/mm] - [mm] \frac 1{k_1}* \left( u_1^t* \vektor{6\\2\\8}\right) *u_1$
[/mm]
80, denn
[mm] $u_1^t \vektor{6\\2\\8} [/mm] = [mm] \vektor{8\\0\\4}^t [/mm] * [mm] \vektor{6\\2\\8} [/mm] = 80$
ciao
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:30 Di 11.10.2011 | | Autor: | MaRaQ |
Perfekt, ich danke euch beiden! Wird schon schiefgehen. :)
|
|
|
|
