QR faktorizazio

Aljebra linealean, matrize baten QR deskonposizioa edo faktorizazioa haren deskonposizioa da matrize ortogonal baten produktu gisa matrize goi triangeluar baten bidez. QR faktorizazioa matrize baten autobalio eta autobektoreak kalkulatzeko QR algoritmoaren oinarria da.

Householder-en islapenen bidez

Householderren islapenak matrize-transformazioak dira, eta zenbakizko algoritmo moldagarri eta eraginkorrenetariko batzuen oinarria da.

Demagun $A\in {ℝ}^{n\times n}$ matrize ez-singularra dugula; orduan, n-1 Householderren matrizeak eraiki ditzakegu hurrengoa bete dadin:

$H_{n-1}...H_2{H}_{1}A=R,$

non $R\in {ℝ}^{n\times n}$ matrize goi-triangeluarra den.

Faktorizazioaren prozesuko lehenengo urratsa $H_1$ matrizea eraikitzea da, A-ren lehenengo zutabe, $a_1,e_1$ -en multiplo bihurtzeko ($e_1$ oinarri kanonikoaren lehenengo bektorea izanik), zutabearen norma euklidearra gordez. Alegia, 2. gaitik n.-ra dauden gaiak zero bihurtuz; hurrengoa lortzen da:

$H_1{a}_1=(\mathrm{I}-{\rho }_1{u}_1{u}_1^T)a_1=-{\sigma }_1{e}_1=\left[\begin{array}{c}r11\\ 0\\ ...\\ 0\end{array}\right],$

non $r_{11}=-{\sigma }_1$ eta ${\sigma }_1=zeinu(a_{11})\Vert a_1{\Vert }_2$. Bestalde, $u_1=a_1+{\sigma }_1{e}_1$ hartu behar dugu. Beraz, Householderren lehenengo bektorea hau izango da:

$u_1=\left[\begin{array}{c}{a}_{11}+{\sigma }_1\\ a_{21}\\ ...\\ a_{n1}\end{array}\right].$

Bektore horrekin, A matrizean $H_1$ aplikatuz lortzen duguna da:

$A^{(2)}=H_{1}A=\left[\begin{array}{cccc}r11& a_{12}^{(2)}& ...& a_{1n}^{(2)}\\ 0& a_{22}^{(2)}& ...& a_{2n}^{(2)}\\ ...& ...& ...& ...\\ 0& a_{n2}^{(2)}& ...& a_{nn}^{(2)}\end{array}\right]$.

Bigarren Householderren transformaziorako $A^{(2)}$ matrizea txikituko dugu lehen zutabea eta lehen lerroa kendurik, $\widetilde{A_2}$ matrizea izenekoa. Hori lortzeko, nahikoa da $u_2$-ren lehenengo gaia zero hartzea.

A ez bada singularra, Householderren ezabapenaren n-1 urrats egin ditzakegu, eta hurrengoa lortuko dugu:

$H_{n-1}...H_{1}A=R,$

non $R\in {ℝ}^{n\times n}$ matrize goi triangeluarra den. Hartu dezagun $Q^T\in {ℝ}^{n\times n}$ matrize ortogonal hau:

$Q^T=H_{n-1}...H_1.$

Beraz, $Q=H_1...H_{n-1}.$

Beraz A-ren QR faktorizazio hurrengoari deritzogu:

$Q^{T}A=R$ edo $A=QR.$