Decomposição QR e Gram-Schmidt

Construir uma base ortonormal

Colunas ortonormais são as mais bem-comportadas que uma matriz pode ter: $Q^{T}Q=I$ , então $Q$ preserva comprimentos e ângulos e nunca amplifica erros. Gram-Schmidt transforma quaisquer colunas independentes $\mathbf{a}_1,\dots,\mathbf{a}_n$ em colunas ortonormais: tome $\mathbf{q}_1=\mathbf{a}_1/\|\mathbf{a}_1\|$ e, para cada coluna seguinte, subtraia suas projeções sobre os $\mathbf{q}$ já encontrados e normalize o que sobra.

A=QR,\qquad R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j\ (i\le j),\qquad \mathbf{q}_j=\frac{\mathbf{a}_j-\sum_{i<j}R_{ij}\mathbf{q}_i}{R_{jj}}

(1)

Registrar os números usados dá a decomposição QR: $Q$ tem as colunas ortonormais e $R$ é triangular superior, com $R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j$ e os comprimentos $R_{jj}$ na diagonal. Para mínimos quadrados, $\|A\mathbf{x}-\mathbf{b}\|=\|QR\mathbf{x}-\mathbf{b}\|$ é minimizada por $R\hat{\mathbf{x}}=Q^{T}\mathbf{b}$ , um sistema triangular resolvido por substituição regressiva, sem nunca formar $A^{T}A$ . Por isso $\kappa(R)=\kappa(A)$ em vez de $\kappa(A)^2$ .

Gram-Schmidt em duas colunasSeja

A=\begin{pmatrix}3&1\\4&2\end{pmatrix}

, com colunas

\mathbf{a}_1=(3,4)

\mathbf{a}_2=(1,2)

. Então

R_{11}=\|\mathbf{a}_1\|=5

\mathbf{q}_1=(0{,}6;\ 0{,}8)

. Depois

R_{12}=\mathbf{q}_1\cdot\mathbf{a}_2=2{,}2

, e

\mathbf{a}_2-2{,}2\,\mathbf{q}_1=(-0{,}32;\ 0{,}24)

tem comprimento

R_{22}=0{,}4

, então

\mathbf{q}_2=(-0{,}8;\ 0{,}6)

. Assim

Q=\begin{pmatrix}0{,}6&-0{,}8\\0{,}8&0{,}6\end{pmatrix}

R=\begin{pmatrix}5&2{,}2\\0&0{,}4\end{pmatrix}

. Conferência:

\det A=2=\det R

Q: colunas ortonormais, $Q^{T}Q=I$ , sem amplificação de erros.
R: triangular superior; sua diagonal guarda os comprimentos restantes depois de remover as direções anteriores.
Gram-Schmidt modificado (ou reflexões de Householder nas bibliotecas) mantém $Q$ ortogonal em ponto flutuante; a versão clássica perde ortogonalidade em colunas quase dependentes.

Por que as bibliotecas usam QR na regressãoOs regressores em finanças costumam ser quase colineares (muitos fatores correlacionados, termos polinomiais). As equações normais elevariam ao quadrado esse número de condição e devolveriam lixo em silêncio, enquanto o QR (ou a SVD) dá conta. É o algoritmo por trás das rotinas de mínimos quadrados do NumPy e do statsmodels, e o que você construirá no projeto final.

Lab: o que é avaliado

A primeira entrada diagonal10 pts
A matriz Q20 pts
A matriz R20 pts
Um determinante a partir de R15 pts
Mínimos quadrados com QR15 pts
Por que o QR é mais preciso20 pts

Construir uma base ortonormal

A=QR,\qquad R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j\ (i\le j),\qquad \mathbf{q}_j=\frac{\mathbf{a}_j-\sum_{i<j}R_{ij}\mathbf{q}_i}{R_{jj}}

(1)

Gram-Schmidt em duas colunasSeja

A=\begin{pmatrix}3&1\\4&2\end{pmatrix}

, com colunas

\mathbf{a}_1=(3,4)

\mathbf{a}_2=(1,2)

. Então

R_{11}=\|\mathbf{a}_1\|=5

\mathbf{q}_1=(0{,}6;\ 0{,}8)

. Depois

R_{12}=\mathbf{q}_1\cdot\mathbf{a}_2=2{,}2

, e

\mathbf{a}_2-2{,}2\,\mathbf{q}_1=(-0{,}32;\ 0{,}24)

tem comprimento

R_{22}=0{,}4

, então

\mathbf{q}_2=(-0{,}8;\ 0{,}6)

. Assim

Q=\begin{pmatrix}0{,}6&-0{,}8\\0{,}8&0{,}6\end{pmatrix}

R=\begin{pmatrix}5&2{,}2\\0&0{,}4\end{pmatrix}

. Conferência:

\det A=2=\det R

Q: colunas ortonormais, $Q^{T}Q=I$ , sem amplificação de erros.
R: triangular superior; sua diagonal guarda os comprimentos restantes depois de remover as direções anteriores.
Gram-Schmidt modificado (ou reflexões de Householder nas bibliotecas) mantém $Q$ ortogonal em ponto flutuante; a versão clássica perde ortogonalidade em colunas quase dependentes.

Lab: o que é avaliado

A primeira entrada diagonal10 pts
A matriz Q20 pts
A matriz R20 pts
Um determinante a partir de R15 pts
Mínimos quadrados com QR15 pts
Por que o QR é mais preciso20 pts

Decomposição QR e Gram-Schmidt

Construir uma base ortonormal

Lab: o que é avaliado

Entre para executar o seu código.

Decomposição QR e Gram-Schmidt

Construir uma base ortonormal

Lab: o que é avaliado

Entre para executar o seu código.