Jacobiho rotace - Jacobi rotation

v numerická lineární algebra, a Jacobiho rotace je otáčení, Q_kℓ, dvourozměrného lineárního podprostoru an n-dimenzionální vnitřní produktový prostor, zvoleno k vynulování symetrické dvojice off-úhlopříčka položky an n×n nemovitý symetrická matice, A, pokud se použije jako transformace podobnosti:

${ displaystyle A mapsto Q_ {k ell} ^ {T} AQ_ {k ell} = A '. , !}$

${ displaystyle { begin {bmatrix} {*} &&& cdots &&& * & ddots &&&& && a_ {kk} & cdots & a_ {k ell} && vdots && vdots & ddots & vdots && vdots && a _ { ell k} & cdots & a _ { ell ell} && &&&&& ddots & {*} &&& cdots &&& * end {bmatrix}} to { začít {bmatrix} {*} &&& cdots &&& * & ddots &&&&& && a '_ {kk} & cdots & 0 && vdots && vdots & ddots & vdots && vdots && 0 & cdots & a '_ { ell ell} && &&&&& ddots & {*} &&& cdots &&& * end {bmatrix}}.}$

Jedná se o hlavní činnost v EU Algoritmus vlastní hodnoty Jacobiho, který je numericky stabilní a je vhodný pro implementaci na paralelní procesory^{[Citace je zapotřebí ]}.

Pouze řádky k a ℓ a sloupce k a ℓ z A bude ovlivněn, a to A′ Zůstane symetrický. Také explicitní matice pro Q_kℓ je zřídka počítán; místo toho se počítají pomocné hodnoty a A je aktualizován efektivním a číselně stabilním způsobem. Pro referenci však můžeme matici zapsat jako

${ displaystyle Q_ {k ell} = { begin {bmatrix} 1 &&&&&& & ddots &&&& 0 & && c & cdots & -s && && vdots & ddots & vdots && && s & cdots & c && & 0 &&&& ddots & &&&&&& 1 1 end {bmatrix}}.}$

To znamená, Q_kℓ je matice identity s výjimkou čtyř vstupů, dvou na úhlopříčce (q_kk a q_ℓℓ, obě rovna C) a dva symetricky umístěné mimo úhlopříčku (q_kℓ a q_ℓk, rovná s a -s). Tady C = cos ϑ a s = sin ϑ pro nějaký úhel ϑ; ale k použití rotace není nutný samotný úhel. Použitím Kroneckerova delta zápis, lze zápisy matice

${ displaystyle q_ {ij} = delta _ {ij} + ( delta _ {ik} delta _ {jk} + delta _ {i ell} delta _ {j ell}) (c-1 ) + ( delta _ {ik} delta _ {j ell} - delta _ {i ell} delta _ {jk}) s. , !}$

Předpokládat h je index jiný než k nebo ℓ (které musí být samy o sobě odlišné). Aktualizace podobnosti pak algebraicky vytvoří

${ displaystyle a '_ {hk} = a' _ {kh} = ca_ {hk} -sa_ {h ell} , !}$

${ displaystyle a '_ {h ell} = a' _ { ell h} = ca_ {h ell} + sa_ {hk} , !}$

${ displaystyle a '_ {k ell} = a' _ { ell k} = (c ^ {2} -s ^ {2}) a_ {k ell} + sc (a_ {kk} -a_ { ell ell}) = 0 , !}$

${ displaystyle a '_ {kk} = c ^ {2} a_ {kk} + s ^ {2} a _ { ell ell} -2sca_ {k ell} , !}$

${ displaystyle a '_ { ell ell} = s ^ {2} a_ {kk} + c ^ {2} a _ { ell ell} + 2sca_ {k ell}. , !}$

Numericky stabilní výpočet

Abychom určili množství potřebná pro aktualizaci, musíme vyřešit off-diagonální rovnici pro nulu (Golub & Van Loan 1996, §8.4). To z toho vyplývá

${ displaystyle { frac {c ^ {2} -s ^ {2}} {sc}} = { frac {a _ { ell ell} -a_ {kk}} {a_ {k ell}}} .}$

Nastavte β na polovinu tohoto množství,

${ displaystyle beta = { frac {a _ { ell ell} -a_ {kk}} {2a_ {k ell}}}.}$

Li A_kℓ je nula, můžeme se zastavit bez provedení aktualizace, takže ji nikdy nedělíme nulou. Nechat t být opálený Potom s několika trigonometrickými identitami redukujeme rovnici na

${ displaystyle t ^ {2} +2 beta t-1 = 0. , !}$

Pro stabilitu zvolíme řešení

${ displaystyle t = { frac { operatorname {sgn} ( beta)} {| beta | + { sqrt { beta ^ {2} +1}}}}.}$

Z toho můžeme získat C a s tak jako

${ displaystyle c = { frac {1} { sqrt {t ^ {2} +1}}} , !}$

${ displaystyle s = ct , !}$

Ačkoli bychom nyní mohli použít dříve uvedené algebraické aktualizační rovnice, může být vhodnější je přepsat. Nechat

${ displaystyle rho = { frac {s} {1 + c}},}$

takže ρ = opálení (ϑ / 2). Pak jsou revidované aktualizační rovnice

${ displaystyle a '_ {hk} = a' _ {kh} = a_ {hk} -s (a_ {h ell} + rho a_ {hk}) , !}$

${ displaystyle a '_ {h ell} = a' _ { ell h} = a_ {h ell} + s (a_ {hk} - rho a_ {h ell}) , !}$

${ displaystyle a '_ {k ell} = a' _ { ell k} = 0 , !}$

${ displaystyle a '_ {kk} = a_ {kk} -ta_ {k ell} , !}$

${ displaystyle a '_ { ell ell} = a _ { ell ell} + ta_ {k ell} , !}$

Jak již bylo uvedeno výše, nikdy nemusíme explicitně počítat úhel otočení ϑ. Ve skutečnosti můžeme reprodukovat symetrickou aktualizaci určenou pomocí Q_kℓ zachováním pouze tří hodnot k, ℓ a t, s t nastaven na nulu pro nulovou rotaci.

Viz také

• Dává rotaci

Reference

• Golub, Gene H.; Van Loan, Charles F. (1996), Maticové výpočty (3. vyd.), Baltimore: Johns Hopkins University Press, ISBN  978-0-8018-5414-9