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 )=\left[\begin{array}{ccccccc}1& \cdots & 0& \cdots & 0& \cdots & 0\\ ⋮& \ddots & ⋮& & ⋮& & ⋮\\ 0& \cdots & c& \cdots & -s& \cdots & 0\\ ⋮& & ⋮& \ddots & ⋮& & ⋮\\ 0& \cdots & s& \cdots & c& \cdots & 0\\ ⋮& & ⋮& & ⋮& \ddots & ⋮\\ 0& \cdots & 0& \cdots & 0& \cdots & 1\end{array}\right]$

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{array}{cc}\cos \theta & \text{ ha }j=i,l=i\text{ vagy }j=k,l=k\\ \sin \theta & \text{ ha }j=i,l=k\\ -\sin \theta & \text{ ha }j=k,l=i\\ 1& \text{ ha }j=l,j\ne i,j\ne k\\ 0& \text{ különben. }\end{array}$

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 $𝒪(mn)$. 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 $𝒪(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 =\mathrm{sgn}(a_{jj})\sqrt{a_{jj}^2+a_{ij}^2}$.

Példa

Legyen

$G_{2,4}\cdot G_{1,4}\cdot \left[\begin{array}{cc}3& 5\\ 0& 2\\ 0& 0\\ 4& 5\end{array}\right]=G_{2,4}\cdot \left[\begin{array}{cc}5& 7\\ 0& 2\\ 0& 0\\ 0& -1\end{array}\right]=\left[\begin{array}{cc}5& 7\\ 0& \sqrt{5}\\ 0& 0\\ 0& 0\end{array}\right]$

ahol

$G_{1,4}=\left[\begin{array}{cccc}\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{array}\right]$, $G_{2,4}=\left[\begin{array}{cccc}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{array}\right]$

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)=\left[\begin{array}{cccc}\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{array}\right],R=\left[\begin{array}{cc}5& 7\\ 0& \sqrt{5}\\ 0& 0\\ 0& 0\end{array}\right],Q\cdot R=\left[\begin{array}{cc}3& 5\\ 0& 2\\ 0& 0\\ 4& 5\end{array}\right]$

Algoritmus

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

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

$G_{1,m}A=\left[\begin{array}{cccc}*& \cdots & \cdots & *\\ ⋮& \ddots & \ddots & ⋮\\ *& \cdots & \cdots & *\\ 0& *& \cdots & *\end{array}\right]$

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

$\rho =\mathrm{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,\dots ,m$-re eltároljuk a $G_1$ mátrixban:

$\begin{array}{cc}{G}_{1}A=& \left[\begin{array}{cccc}*& \cdots & \cdots & *\\ 0& *& \ddots & ⋮\\ ⋮& ⋮& \ddots & ⋮\\ 0& *& \cdots & *\end{array}\right]\\ \text{ahol}{G}_1:=& G_{1,2}\cdot \dots \cdot G_{1,m}.\end{array}$

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 \dots \cdot G_{1,m}A$.

Hasonlóan kell feldolgozni a következő oszlopot, és így kapjuk a $G_i,i=2,\dots ,n$ mátrixokat, így a $G_{i-1}\cdot \dots \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 )=\left(\begin{array}{ccc}1& 0& 0\\ 0& \cos \theta & -\sin \theta \\ 0& \sin \theta & \cos \theta \end{array}\right)$

$R_Y(\theta )=\left(\begin{array}{ccc}\cos \theta & 0& -\sin \theta \\ 0& 1& 0\\ \sin \theta & 0& \cos \theta \end{array}\right)$

$R_Z(\theta )=\left(\begin{array}{ccc}\cos \theta & -\sin \theta & 0\\ \sin \theta & \cos \theta & 0\\ 0& 0& 1\end{array}\right)$

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 )=\left[\begin{array}{ccc}\cos \theta & 0& \sin \theta \\ 0& 1& 0\\ -\sin \theta & 0& \cos \theta \end{array}\right]$

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, Sablon:ISBN.
• W. Dahmen, A. Reusken: Numerik für Ingenieure und Naturwissenschaftler. Springer-Verlag Berlin Heidelberg, 2006, Sablon:ISBN