Givens-forgatás

A lineáris algebrában egy Givens-forgatás (Wallace Givens után) adott két koordináta által kifeszített síkban végzett forgatás. Néha Jacobi-forgatásnak is nevezik (Carl Gustav Jacobi).

A numerikus algebrában például QR-felbontás előállítására és sajátértékek meghatározására használják. Ezeket az alkalmazásokat az 1950-es években vezették be, amikor Givens az Oak Ridge National Laboratory munkatársa volt. Ezeket a forgatásokat a régebbi Jacobi-eljárásban (1846) is használták, de gyakorlati alkalmazásuk a számítógépekkel terjedt el.

Leírás

A transzformáció alakja egy ortogonális mátrix:

$G(i,k,\theta )={\begin{bmatrix}1&\cdots &0&\cdots &0&\cdots &0\\\vdots &\ddots &\vdots &&\vdots &&\vdots \\0&\cdots &c&\cdots &-s&\cdots &0\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\0&\cdots &s&\cdots &c&\cdots &0\\\vdots &&\vdots &&\vdots &\ddots &\vdots \\0&\cdots &0&\cdots &0&\cdots &1\end{bmatrix}}$

ahol $c=\cos(\theta )$, $s=\sin(\theta )$ az $i$-edik és a $k$-adik sorban és oszlopban helyezkedik el. Formálisan,

$G(i,k,\theta )_{j,l}={\begin{cases}\cos \theta &{\mbox{ ha }}j=i,l=i{\mbox{ vagy }}j=k,l=k\\\sin \theta &{\mbox{ ha }}j=i,l=k\\-\sin \theta &{\mbox{ ha }}j=k,l=i\\1&{\mbox{ ha }}j=l,j\neq i,j\neq k\\0&{\mbox{ különben. }}\end{cases}}$

A $G^{T}(i,k,\theta )x$ mátrix-vektor szorzat az $x$ vektor $\theta$ szögű forgatását ábrázolja az $(i,k)$ síkban, ezt Givens-forgatásnak nevezik.

A Givens-forgatás fő alkalmazási területe a numerikus lineáris algebrában vektorok és mátrixok koordinátáinak kinullázása. Ez felhasználható mátrixok QR-felbontásának elkészítéséhez és Jacobi-eljárással sajátértékek megtalálásához.

QR-felbontás Givens-forgatásokkal

• Az eljárás stabil. Pivot kiválasztásra nincs szükség.
• Rugalmasan figyelembe veszi a strukturált mátrixok nulla koordinátáit. Ez különösen a ritka mátrixok esetén fontos a feltöltődés elkerülésére.
• A főátló alatti elemeket sorra kinullázza azzal, hogy a mátrixot balról szorozza Givens-mátrixokkal. A sorrend oszloponként felülről lefelé halad.
• A szükséges mátrixszorzások száma ${\mathcal {O}}(m\,n)$. Mivel szorzásonként legfeljebb 2n érték változik, azért egy telt m×n-es mátrix felbontásának teljes költsége ${\mathcal {O}}(m\,n^{2})$. A mátrixban már eleve meglevő nullák esetén nem kell transzformációt végezni, így ritka mátrixok esetén az algoritmus gyorsabb.
• Ha egy $(i,j)$ pozíció koordinátát akarunk kinullázni, akkor $c=a_{jj}/\rho$, $s=a_{ij}/\rho$, ahol $\rho =\operatorname {sgn}(a_{jj}){\sqrt {a_{jj}^{2}+a_{ij}^{2}}}$.

Példa

Legyen

$G_{2,4}\cdot G_{1,4}\cdot {\begin{bmatrix}3&5\\0&2\\0&0\\4&5\end{bmatrix}}=G_{2,4}\cdot {\begin{bmatrix}5&7\\0&2\\0&0\\0&-1\end{bmatrix}}={\begin{bmatrix}5&7\\0&{\sqrt {5}}\\0&0\\0&0\end{bmatrix}}$

ahol

$G_{1,4}={\begin{bmatrix}{\frac {3}{5}}&0&0&{\frac {4}{5}}\\0&1&0&0\\0&0&1&0\\{\frac {-4}{5}}&0&0&{\frac {3}{5}}\end{bmatrix}}$, $G_{2,4}={\begin{bmatrix}1&0&0&0\\0&{\frac {2}{\sqrt {5}}}&0&-{\frac {1}{\sqrt {5}}}\\0&0&1&0\\0&{\frac {1}{\sqrt {5}}}&0&{\frac {2}{\sqrt {5}}}\\\end{bmatrix}}$

Végül megkapjuk a QR-felbontást:

$Q=(G_{2,4}\cdot G_{1,4})^{T}=(G_{1,4}^{T}\cdot G_{2,4}^{T})={\begin{bmatrix}{\frac {3}{5}}&{\frac {4}{5{\sqrt {5}}}}&0&-{\frac {8}{5{\sqrt {5}}}}\\0&{\frac {2}{\sqrt {5}}}&0&{\frac {1}{\sqrt {5}}}\\0&0&1&0\\{\frac {4}{5}}&-{\frac {3}{5{\sqrt {5}}}}&0&{\frac {6}{5{\sqrt {5}}}}\end{bmatrix}},\quad R={\begin{bmatrix}5&7\\0&{\sqrt {5}}\\0&0\\0&0\end{bmatrix}},\quad Q\cdot R={\begin{bmatrix}3&5\\0&2\\0&0\\4&5\end{bmatrix}}$

Algoritmus

Egy $A=\left(a_{i,j}\right)_{i,j}\in \mathbb {R} ^{m\times n},m\geq n$ mátrix QR-felbontása:

Forgassuk meg az $A$ mátrix $a_{-,1}$ első oszlopát:

$G_{1,m}A={\begin{bmatrix}*&\cdots &\cdots &*\\\vdots &\ddots &\ddots &\vdots \\*&\cdots &\cdots &*\\0&*&\cdots &*\end{bmatrix}}$

ahol $G_{1,m}$-hoz $c,s,\rho$ választása:

$\rho =\operatorname {sgn}(a_{1,1}){\sqrt {a_{1,1}^{2}+a_{m,1}^{2}}},\;c={\frac {a_{1,1}}{\rho }},\;s={\frac {a_{m,1}}{\rho }}.$

Hasonlóan járunk el a következő elemmel, és $G_{1,i},i=2,\ldots ,m$-re eltároljuk a $G_{1}$ mátrixban:

${\begin{aligned}G_{1}A=&{\begin{bmatrix}*&\cdots &\cdots &*\\0&*&\ddots &\vdots \\\vdots &\vdots &\ddots &\vdots \\0&*&\cdots &*\end{bmatrix}}\\{\text{ahol}}\quad G_{1}:=&G_{1,2}\cdot \ldots \cdot G_{1,m}.\end{aligned}}$

Figyelembe kell vennünk, hogy az újabb átalakítás nem az eredeti, hanem az addig átalakított mátrixra vonatkozik: $G_{1,i+1}\cdot \ldots \cdot G_{1,m}A$.

Hasonlóan kell feldolgozni a következő oszlopot, és így kapjuk a $G_{i},i=2,\ldots ,n$ mátrixokat, így a $G_{i-1}\cdot \ldots \cdot G_{1}A$ mátrix $i$-edik oszlopa nulla értékeket tartalmaz az $i$-edik érték alatt.

Speciális eset

Háromdimenziós térben háromféle Givens-mátrix létezik:

$R_{X}(\theta )={\begin{pmatrix}1&0&0\\0&\cos \theta &-\sin \theta \\0&\sin \theta &\cos \theta \end{pmatrix}}$

$R_{Y}(\theta )={\begin{pmatrix}\cos \theta &0&-\sin \theta \\0&1&0\\\sin \theta &0&\cos \theta \end{pmatrix}}$

$R_{Z}(\theta )={\begin{pmatrix}\cos \theta &-\sin \theta &0\\\sin \theta &\cos \theta &0\\0&0&1\end{pmatrix}}$

Ezekkel a mátrixokkal a Davenport's chained rotation theorem (Davenport láncolt forgatási tétele) szerint minden forgatómátrix előállítható három dimenzióban. Ez azt jelenti, hogy a vektortér standard bázisa a tér bármely ortogonális bázisába beforgatható.

Ez a mátrix nem a $\theta$ szöghöz, hanem a -$\theta$ szöghöz tartozó Givens-mátrix, amit a komputergrafikában használnak a jobbkézszabály miatt:

$R_{Y}(\theta )={\begin{bmatrix}\cos \theta &0&\sin \theta \\0&1&0\\-\sin \theta &0&\cos \theta \end{bmatrix}}$

Források

• Gene H. Golub, Charles F. van Loan: Matrix Computations. 2nd Edition. The Johns Hopkins University Press, 1989.
• Martin Hermann: Numerische Mathematik, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage, Walter de Gruyter Verlag, Berlin und Boston 2020, ISBN 978-3-11-065665-7.
• W. Dahmen, A. Reusken: Numerik für Ingenieure und Naturwissenschaftler. Springer-Verlag Berlin Heidelberg, 2006, ISBN 3-540-25544-3

Fordítás

Ez a szócikk részben vagy egészben a Givens-Rotation című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.