Faktorizimi QR

Në algjebër lineare, një **dekompozim QR**, i njohur gjithashtu si **faktorizimi QR** ose **zbërthimi QR**, është një zbërthim i një matrice *A* në një prodhim *A*&nbsp;=&nbsp;*QR* të një matrice ortonormale *Q* dhe të një matrice trekëndore të sipërme *R.* Zbërthimi QR përdoret shpesh për të zgjidhur problemin e katrorëve më të vegjël dhe është baza për një algoritëm të veçantë të vlerave vetjake, algoritmin QR .

## Rastet dhe përkufizimet 
### Matrica katrore 
Çdo matricë katrore reale *A* mund të zbërthehet si

:  A = QR, 

ku *Q* është një matricë ortogonale (kolonat e saj janë vektorë njësi ortogonalë që do të thotë {{Nowrap|Q^\textsf{T} = Q^{-1})}} dhe *R* është një matricë trekëndore e sipërme. Nëse *A* ka të anasjelltë, atëherë faktorizimi është unik nëse kërkojmë që elementet diagonale të *R* të jenë pozitive.

### Matricë drejtkëndore 
Në përgjithësi, ne mund të faktorizojmë një matricë komplekse *m* × *n* *A*, me , si prodhim i një matrice njësi *m* × *m* *Q* dhe një matrice trekëndore të sipërme, R, *m* × *n*  . Duke qenë se rreshtat e poshtëm ( *m* − *n* ) të një matrice trekëndore të sipërme *m* × *n* përbëhen tërësisht nga zero, shpesh është e dobishme ta ndash *R*, ose të dyja *R* dhe *Q* :

: 
 A = QR = Q \begin{bmatrix} R_1 \\ 0 \end{bmatrix}
 = \begin{bmatrix} Q_1 & Q_2 \end{bmatrix} \begin{bmatrix} R_1 \\ 0 \end{bmatrix}
 = Q_1 R_1,

ku *R* 1 është një matricë *n* × *n* trekëndore e sipërme, 0 është një matricë zero , *Q* 1 është *m* × *n*, *Q* 2 është  dhe *Q* 1 dhe *Q* 2 të dyja kanë shtylla ortogonale.

## Llogaritja e dekompozimit QR 
Ka disa metoda për llogaritjen reale të faktorizimit QR, të tilla si me anë të procesit Gram-Schmidt, shndërrimet Householder ose rrotullimet Givens . Secili ka një numër përparësish dhe mangësish.

### Duke përdorur procesin Gram-Schmidt 
Konsideroni procesin Gram-Schmidt të zbatuar mbi shtyllat e matricës me rank të plotë {{Nowrap|A = \begin{bmatrix}\mathbf{a}_1 & \cdots & \mathbf{a}_n\end{bmatrix},}} me prodhim të brendshëm \langle\mathbf{v}, \mathbf{w}\rangle = \mathbf{v}^\textsf{T} \mathbf{w} (ose \langle\mathbf{v}, \mathbf{w}\rangle = \mathbf{v}^\dagger \mathbf{w} për rastin kompleks).

Përcaktoni projeksionin :

: \operatorname{proj}_{\mathbf{u}}\mathbf{a} =
 \frac{\left\langle\mathbf{u}, \mathbf{a}\right\rangle}{\left\langle\mathbf{u}, \mathbf{u}\right\rangle}{\mathbf{u}}

pastaj:

: \begin{align}
 \mathbf{u}_1 &= \mathbf{a}_1, &
  \mathbf{e}_1 &= \frac{\mathbf{u}_1}{\|\mathbf{u}_1\|} \\
 \mathbf{u}_2 &= \mathbf{a}_2 - \operatorname{proj}_{\mathbf{u}_1} \mathbf{a}_2, &
  \mathbf{e}_2 &= \frac{\mathbf{u}_2}{\|\mathbf{u}_2\|} \\
 \mathbf{u}_3 &= \mathbf{a}_3 - \operatorname{proj}_{\mathbf{u}_1} \mathbf{a}_3 - \operatorname{proj}_{\mathbf{u}_2} \mathbf{a}_3, &
  \mathbf{e}_3 &= \frac{\mathbf{u}_3}{\|\mathbf{u}_3\|} \\
         & \;\; \vdots & & \;\; \vdots \\
 \mathbf{u}_k &= \mathbf{a}_k - \sum_{j=1}^{k-1}\operatorname{proj}_{\mathbf{u}_j} \mathbf{a}_k,&
  \mathbf{e}_k &= \frac{\mathbf{u}_k}{\|\mathbf{u}_k\|}
\end{align}

Tani mund të shprehim \mathbf{a}_i s mbi bazën tonë ortonormale të llogaritur rishtazi:

: \begin{align}
  \mathbf{a}_1 &= \left\langle\mathbf{e}_1, \mathbf{a}_1\right\rangle \mathbf{e}_1 \\
  \mathbf{a}_2 &= \left\langle\mathbf{e}_1, \mathbf{a}_2\right\rangle \mathbf{e}_1
         + \left\langle\mathbf{e}_2, \mathbf{a}_2\right\rangle \mathbf{e}_2 \\
  \mathbf{a}_3 &= \left\langle\mathbf{e}_1, \mathbf{a}_3\right\rangle \mathbf{e}_1
         + \left\langle\mathbf{e}_2, \mathbf{a}_3\right\rangle \mathbf{e}_2
         + \left\langle\mathbf{e}_3, \mathbf{a}_3\right\rangle \mathbf{e}_3 \\
        &\;\;\vdots \\
  \mathbf{a}_k &= \sum_{j=1}^k \left\langle \mathbf{e}_j, \mathbf{a}_k \right\rangle \mathbf{e}_j
\end{align}

ku \left\langle\mathbf{e}_i, \mathbf{a}_i\right\rangle = \left\|\mathbf{u}_i\right\|. Kjo mund të shkruhet në formën matricore si:

: A = QR

ku:

: Q = \begin{bmatrix}\mathbf{e}_1 & \cdots & \mathbf{e}_n\end{bmatrix}

dhe

: R = \begin{bmatrix}
 \langle\mathbf{e}_1, \mathbf{a}_1\rangle &
 \langle\mathbf{e}_1, \mathbf{a}_2\rangle &
 \langle\mathbf{e}_1, \mathbf{a}_3\rangle & 
                  \cdots &
 \langle\mathbf{e}_1, \mathbf{a}_n\rangle \\
                     0 &
 \langle\mathbf{e}_2, \mathbf{a}_2\rangle &
 \langle\mathbf{e}_2, \mathbf{a}_3\rangle & 
                  \cdots &
 \langle\mathbf{e}_2, \mathbf{a}_n\rangle \\
                     0 &
                     0 &
 \langle\mathbf{e}_3, \mathbf{a}_3\rangle & 
                  \cdots & 
 \langle\mathbf{e}_3, \mathbf{a}_n\rangle \\
                  \vdots &
                  \vdots &
                  \vdots &
                  \ddots &
                  \vdots \\
                     0 &
                     0 &
                     0 &
                  \cdots &
 \langle\mathbf{e}_n, \mathbf{a}_n\rangle \\
                  
\end{bmatrix}.

#### Shembull 
Merrni parasysh zbërthimin e

: A = \begin{bmatrix}
 12 & -51 &  4 \\
  6 & 167 & -68 \\
 -4 & 24 & -41
\end{bmatrix}.

Kujtojmë se një matricë ortonormale Q ka vetinë {{Nowrap|Q^\textsf{T} Q = I.}}

Atëherë mund të llogarisim Q me anë të procedurës Gram-Schmidt si më poshtë:

: \begin{align}
 U = \begin{bmatrix} \mathbf u_1 & \mathbf u_2 & \mathbf u_3 \end{bmatrix}
  &= \begin{bmatrix}
    12 & -69 & -58/5 \\
     6 & 158 &  6/5 \\
    -4 & 30 & -33
   \end{bmatrix}; \\
 Q = \begin{bmatrix}
    \frac{\mathbf u_1}{\|\mathbf u_1\|} &
    \frac{\mathbf u_2}{\|\mathbf u_2\|} &
    \frac{\mathbf u_3}{\|\mathbf u_3\|}
   \end{bmatrix} &=
   \begin{bmatrix}
     6/7 & -69/175 & -58/175 \\
     3/7 & 158/175 &  6/175 \\
    -2/7 &  6/35 & -33/35
   \end{bmatrix}.
\end{align}

Kështu, ne përftojmë

: \begin{align}
 Q^\textsf{T} A &= Q^\textsf{T}Q\,R = R; \\
        R &= Q^\textsf{T}A =
  \begin{bmatrix}
   14 & 21 & -14 \\
    0 & 175 & -70 \\
    0 &  0 & 35
  \end{bmatrix}.
\end{align}