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.

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

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

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

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

Faktorizazioaren prozesuko lehenengo urratsa ${\displaystyle H_{1}}$ matrizea eraikitzea da, A-ren lehenengo zutabe, ${\displaystyle a_{1},e_{1}}$ -en multiplo bihurtzeko (${\displaystyle e_{1}}$ oinarri kanonikoaren lehenengo bektorea izanik), zutabearen norma euklidearra gordez. Alegia, 2. gaitik n.-ra dauden gaiak zero bihurtuz; hurrengoa lortzen da:

${\displaystyle H_{1}a_{1}=(\mathrm {I} -\rho _{1}u_{1}u_{1}^{T})a_{1}=-\sigma _{1}e_{1}={\begin{bmatrix}r11\\0\\...\\0\end{bmatrix}},}$

non ${\displaystyle r_{11}=-\sigma _{1}}$ eta ${\displaystyle \sigma _{1}=zeinu(a_{11})\lVert a_{1}\rVert _{2}}$. Bestalde, ${\displaystyle u_{1}=a_{1}+\sigma _{1}e_{1}}$ hartu behar dugu. Beraz, Householderren lehenengo bektorea hau izango da:

${\displaystyle u_{1}={\begin{bmatrix}a_{11}+\sigma _{1}\\a_{21}\\...\\a_{n1}\end{bmatrix}}.}$

Bektore horrekin, A matrizean ${\displaystyle H_{1}}$ aplikatuz lortzen duguna da:

${\displaystyle A^{(2)}=H_{1}A={\begin{bmatrix}r11&a_{12}^{(2)}&...&a_{1n}^{(2)}\\0&a_{22}^{(2)}&...&a_{2n}^{(2)}\\...&...&...&...\\0&a_{n2}^{(2)}&...&a_{nn}^{(2)}\end{bmatrix}}}$.

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

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

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

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

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

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

Beraz A-ren QR faktorizazio hurrengoari deritzogu:

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

• Datuak: Q653242