Blatt7

Bachelor Algorithmik kontinuierlicher Systeme
1

Jacobi-Rotation

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Blatt7
Habe hier mal ne Frage: im Skript steht Givens-Rotation (c -s)
(s c)

In Wikipedia steht aber (c s)
(-s c)

Und wie funktioniert das ganze für nicht quadratische Matrizen???

3

  1. Das eine ist eine Rotation um links und das andere eine um rechts (oder umgekehrt)! Das ist voellig Wurst, was man fuer eine nimmt. Hauptsache man leitet sich die Formel, wie sie im Hinweis steht richtig her.

  2. Beachte das Beispiel auf der deutschen Wikipedia Seite:
    http://de.wikipedia.org/wiki/Givens-Rotation

Also konkret zur Aufgabe:

  1. 3x3 Givens Rotationmatrix von links an B ran multiplizieren
  2. das Ergebnis wieder von links mit einer 3x3 Givens Matrix multiplizieren
  3. usw.
  4. bis man eine Matrix bekommt, die eine rechte obere Dreiecksmatrix ist.
  5. Aus den Givens Rotationsmatrizen bekommt man dann Q.

Bei so “langen” Matrizen (also mehr Zeilen n als Spalten m), befindet sich das Dreieck in den ersten m Zeilen und aber der m+1-ten Zeile sind nur noch 0 Eintraege, mkay?

4

Supi, danke!!!

5

hiho :slight_smile:
gibts sone anleitung evtl auch für HouseholderSpiegelungen ? Aus der Formel die in den Folien steht werd ich nicht so richtig schlau…
danke :wink:

6

Mithilfe einer Householder-Spiegelung kannst du z.B. einen Vektor
[m]a := (a1, a2, a3, …)^T[/m]
auf einen mit der euklidischen Norm von a multiplizierten Einheitsvektor, also
[m]x := (||a||, 0, 0, …)^T[/m],
abbilden.

Das ny in den Folien ist dabei der normierte Vektor w, d.h.
[m]ny = w / ||w||[/m], mit
[m]w := a - x[/m]

Hilft das weiter? ^^

7

denke schon… danke :slight_smile:

8

müsste es nicht w:= a+x sein???

9

…?
habs jetzt denk ich mal…
aber wie bekomme ich jetzt die matrizen Q und R ? R ist die Restmatrix, die nach den zwei Spiegelungen übrig bleibt oder ? aber wie bekomme ich Q ?
ein Beispiel wäre irgendwie nicht verkehrt :slight_smile:

ciao :wink:

10

Fuer Givens:



       /x x x\
A_0 =  |x x x|
       \x x x/

                   /x x x\
Q_1 * A_0 = A_1 =  |0 x x |
                   \x x x/


                   /x x x\
Q_2 * A_1 = A_2 =  |0 x x |
                   \0 x x/


                   /x x x\
Q_3 * A_2 = A_3 =  |0 x x | = R
                   \0 0 x/



Q_3 * A_2    = R;
Q_3 * Q_2 * A_1 = R;
Q_3 * Q_2 * Q_1 * A_0 = R;
Q^T             * A_0 = R

Q * Q^T  = Id, weil Q orthogonal. Also die Gleichung von links mit Q multiplizieren:

Q * Q^T * A_0 = Q * R
Id     *  A_0 = Q * R
A_0 = Q * R
---------------------------
Fuer Householder


       /x x x\
A_0 =  |x x x|
       \x x x/

                   /x x x\
Q_1 * A_0 = A_1 =  |0 x x |
                   \0 x x/


                   /x x x\
Q_2 * A_1 = A_2 =  |0 x x |
                   \0 0 x/
                   
Fertig

Rest siehe oben!

Gibts hier so was wie ne tex umgebung? wo man so basismaesig formeln eingeben kann?

11

gibts bei der zwei irgend einen ansatz, nach dem man da vorgehen koennte ?
oder schau ich mir einfach schritt fuer schritt an und zaehle mit ?

12

So viel ich es verstanden habe, du sollst die spezielle Struktur von w und S ausnutzen, d.h. die Zeilen, die Nullen enthalten kannst du dir aussparen und somit kommste auf weniger Multiplikationen.

13

Dazu frage ich mich in Aufgabe 1(a) gerade auch warum das so sein soll. Also warum ich 2 HH Schritte anwenden muss um die Nullen unter dem Dreiecksmatrixblock zu erzeugen. Eigentlich interessieren mich diese Zeilen für das lösen eines Gleichungssystems doch garnicht mehr, oder?

Nach einem HH-Schritt hätte ich ja etwas der Form:
Q1 * A = R

        * *
        0 *

mit R = 0 *
0 *

Die obere Blockmatrix (2x2) ist ja damit schon auf Dreiecksform und ich kann mithilfe dieser beiden Zeilen und den ersten beiden Einträgen eines ebenfalls gespiegelten Ergebnisvektors b das Gleichungssystem lösen.

also
R[2,2] x2 = b2 => x2
R[1,1] x1 + R[1,2] x2 = b1 => x1

Warum also muss ich mich also noch um die Matrixeinträge R[3,2] und R[4,2] mit einer weiteren Spiegelung kümmern?

14

Die sache ist: derartige Gleichungssysteme kann man, i.A., gar nicht loesen: sie sind ueberbestimmt (mehr gleichungen als unbekannte)!

Man kann sich aber eine Naeherungsloesung verschaffen. Und dazu muss man weiternullen bis man unten eine Nullmatrix stehen hat. Man kann sich damit eine Loesung x_0 verschaffen, die ||Ax - b|| minimiert!

Mehr zum Thema ueberbestimmte und unterbestimme Gleichungssyteme demnaechst in der Vorlesung AlgoKS.

15

Achso… ist klar. Danke. :slight_smile:

[EDIT] quirin zuliebe hier ein SOILER-ALERT: folgende Zeilen könnten unter Umständen den Spannungsbogen der dramaturgisch ausgetüftelten Vorlesung beeinflussen.[/EDIT]

Den Fehler kann man dann glaub ich mit dem unteren Teil des transformierten Ergebnisvektors in 2er-Norm bestimmen, richtig?

16

Ruhig Blut! Kommt alles noch!

Und nimm gefaelligst nicht die ganze Spannung vorweg!

Das ist das retadierenden Moment in der Vorlesung!

:slight_smile:

17

Ich hatte ja keine Ahnung wie viele dramaturgische Überlegungen in so einer Vorlesung stecken…
Sind die Filmrechte denn schon vermarktet? An einem Buch im AlgoKS-Franchise wird ja schon gearbeitet hab ich mir sagen lassen. (Script!) :wink:

Ich möchte das ganze Konzept natürlich nicht über den haufen werfen, und habe meinen Beitrag mit einem entsprechenden Spoiler-Alert versehen. :wink: