jeg trenger å få en Givens-rotasjon, som nuller en matriseoppføring når den multipliseres fra høyre side. Jeg så allerede på dette emnet https://math.stackexchange.com/questions/945736/givens-rotation-from-right-side , men jeg kunne ikke forstå prosessen med å komme dit.
Noen flere detaljer: Jeg må matrise, A og B, og jeg trenger å få Eigenvalues ved hjelp av QZ-algoritmen. Jeg får B til trekantet form ved å bruke Givens-rotasjoner fra venstre. Disse transformasjonene blir også brukt på A fra venstre side. Etter at B er i trekantform, vil jeg også få A i trekantform. Derfor trenger jeg Givens-rotasjoner fra høyre slik at den ikke ødelegger nullene til Matrix B (eller er det en annen mulighet til å gjøre dette?)
Som en ligning:
$$ \ begin {bmatrix} a & b \\ c & d \ end {bmatrix} \ cdot \ begin {bmatrix} e & f \\ g & h \ end {bmatrix} = \ begin {bmatrix} ae + bg & af + bh \\ ce + dg & cf + dh \ end {bmatrix} $$
med
$$ ce + dg = 0 $$
Hvordan finner jeg passende e, f, g, h?
Kan noen gi meg noen tips om hvordan jeg kan oppnå dette?
Tusen takk på forhånd!
EDIT: Jeg er ganske sikker på at det fungerer slik: $$ \ begin {bmatrix} a & b \ end {bmatrix } \ cdot \ begin {bmatrix} c & -s \\ s & c \ end {bmatrix} = \ begin {bmatrix} 0 & r \ end {bmatrix} $$
med
$$ r = \ sqrt {a ^ 2 + b ^ 2 } $$ $$ c = \ frac {b} {r} $$ $$ s = \ frac {-a} {r} $$
Kan er det noen som godkjenner dette?
EDIT2: Tenk på en enkel 3×3-matrise som jeg prøver å triangulere ved hjelp av Disse gir-rotasjon fra høyre.
Jeg kan nullstille ut elementer (3,1 ) og (2,1) ved å bruke den samme rotasjonsmatrisen $ G $ med forskjellige parametere $ c $ og $ s $. Så jeg kan opprette et null som dette
$ \ begin {bmatrix} * & * & * \\ * & * & * \\ a & b & * \ end {bmatrix} \ cdot \ begin {bmatrix} c & -s & 0 \\ s & c & 0 \\ 0 & 0 & 1 \ end {bmatrix} = \ begin {bmatrix} * & * & * \\ * & * & * \\ 0 & * & * \ end {bmatrix} $ MEN også slik at $ \ begin {bmatrix} * & * & * \\ a & b & * \\ * & * & * \ end {bmatrix} \ cdot \ begin {bmatrix} c & -s & 0 \\ s & c & 0 \\ 0 & 0 & 1 \ end {bmatrix} = \ begin {bmatrix} * & * & * \\ 0 & * & * \\ * & * & * \ end {bmatrix} $ for samme rotasjonsmatrise $ G $. Dette gjør det umulig for meg å nullstille elementene iterativt, da den andre rotasjonen vil ødelegge null opprettet i den første.
Det er ikke noe problem å nullstille alle elementene i den siste raden bortsett fra den ene i høyre nederste kant (da hver null er opprettet av en annen rotasjonsmatrise $ G $).
Men hvordan kan jeg oppnå å nullstille elementene som er nevnt i eksemplet mitt, når jeg bruker den samme rotasjonsmatrisen $ G $ som ødelegger allerede opprettet null-elementer?
Vær så snill, noe hjelp er høyt verdsatt!
Kommentarer
- For fremtidig referanse , en redigering som » EDIT2 » er sannsynligvis bedre posisjonert som et andre spørsmål. Slik det er for tiden, bør det være i fred fordi spørsmålet har et akseptert svar.
- WOW! Tusen takk for detaljert svar! Endelig fikk jeg hintet som trengs for å nullstille element (2,1) 🙂
- Bare sjekket prosedyren din. Det fungerer virkelig! Tusen takk!
Svar
Du har rett. Med valget $$ \ begin {eqnarray *} r & = & \ sqrt {a ^ 2 + b ^ 2} \\ [.6em] c & = & \ frac {b} {r} \\ [.6em] s & = & \ frac {-a} {r} \ end {eqnarray *} $$ a Givens rotasjon fra høyre gir $$ \ begin {pmatrix} a & b \ end {pmatrix} \ begin {pmatrix} c & -s \\ s & c \ end {pmatrix} = \ begin {pmatrix} ac + bs & -as + bc \ end {pmatrix} = \ begin {pmatrix} 0 & r \ end {pmatrix} \ ,, $$ fordi $$ ac + bs = a \ frac {b} {r} + b \ frac { -a} {r} = \ frac {ab} {r} – \ frac {ab} {r} = 0 $$ og $$ – som + bc = -a \ frac {-a} {r} + b \ frac {b} {r} = \ frac {a ^ 2 + b ^ 2} {r} = \ frac {r ^ 2} {r} = r \,. $$ Bare pass på at $ r \ neq0 $.
Når det gjelder EDIT2:
Du kan bare nullstille begge elementene $ ( 3,1) $ og $ (2,1) $ i eksemplet ditt med samme Givens-rotasjonsmatrise hvis matrisen ser slik ut: $$ \ begin {pmatrix} * & * & * \\ a & b & * \\ a & b * \ end {pmatrix} $$ Og i så fall gir multiplikasjon av Givens-rotasjonsmatrisen din fra høyre $$ \ begin {pmatrix} * & * & * \\ a & b & * \\ a & b & * \ end {pmatrix} \ begin {pmatrix} c & -s & 0 \\ s & c & 0 \\ 0 & 0 & 1 \ end {pmatrix} = \ begin {pmatrix} * & * & * \\ 0 & r & * \\ 0 & r & * \ end {pmatrix} \ ,, $$ og du har brakt begge elementene til null samtidig. Hvis rad 2 og 3 ikke begge er $ \ begin {pmatrix} a & b & * \ end {pmatrix} $, vil du trenger forskjellige rotasjoner, dvs. forskjellige $ c $, $ s $ og $ r $ verdier.
Det du gjør i praksis for å få en matrise i øvre trekantform, er å starte med den nederste raden og bringe alle elementene, men de siste, til null: $$ \ begin {pmatrix} * & * & * \\ * & * & * \\ a_1 & b_1 & * \ end {pmatrix} \ begin {pmatrix} c_1 & -s_1 & 0 \\ s_1 & c_1 & 0 \\ 0 & 0 & 1 \ end { pmatrix} = \ begin {pmatrix} * & * & * \\ * & * & * \\ 0 & r_1 & * \ end {pmatrix} = \ begynn {pmatrix} *
* & * \\ * & * & * \\ 0 & a_2 & b_2 \ end {pmatrix} $$ og $$ \ begin {pmatrix} * & * & * \\ * & * & * \\ 0 & a_2 & b_2 \ end {pmatrix} \ begin {pmatrix} 1 & 0 & 0 \\ 0 & c_2 & -s_2 \ \ 0 & s_2 & c_2 \ end {pmatrix} = \ begynn {pmatrix} * & * & * \\ * & * & * \\ 0 & 0 & r_2 \ end {pmatrix} \,. $$
Nå skal vi se at en radvektor $ \ begin {pmatrix} 0 & 0 & * \ end {pmatrix} $ er uforanderlig under Givens-rotasjoner fra høyre som retter seg mot den første kolonnen: $$ \ begin {pmatrix} 0 & 0 & * \ end {pmatrix} \ begin { pmatrix} c & -s & 0 \\ s & c & 0 \\ 0 & 0 & 1 \ end {pmatrix} = \ begin {pmatrix} 0 \ cdot (c + s) & 0 \ cdot (cs) & 1 \ cdot * \ end {pmatrix} \ ,.$$
Dette lar oss bringe elementet $ (2,1) $ til null uten å endre den siste raden: $$ \ begin {pmatrix} * & * & * \\ a_3 & b_3 & * \\ 0 & 0 & r_2 \ end {pmatrix} \ begin {pmatrix} c_3 & -s_3 & 0 \\ s_3 & c_3 & 0 \\ 0 & 0 & 1 \ end {pmatrix} = \ begin {pmatrix} * & * & * \\ 0 & r_3 & * \\ 0 & 0 & r_2 \ end {pmatrix} \ ,, $$ og vi har nådd den øvre trekantformen ved å bruke tre (forskjellige) Givens-rotasjoner fra høyre.
Kommentarer
- Vær så snill og ta en titt på den andre redigeringen min. Tusen takk på forhånd.