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 = 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ë $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 m ≥ n, 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 ₁ është një matricë n × n trekëndore e sipërme, 0 është një matricë zero (m − n)×n, Q ₁ është m × n, Q ₂ është m×(m − n) dhe Q ₁ dhe Q ₂ 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ë $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{aligned}\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{aligned}}$

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

${\begin{aligned}\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{aligned}}$

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ë $Q^{\textsf {T}}Q=I$.

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

${\begin{aligned}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{aligned}}$

Kështu, ne përftojmë

${\begin{aligned}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{aligned}}$