Resolver sistemas como $A \vec{x} = \vec{b}$ pode ser computacionalmente intensivo, especialmente para sistemas grandes.

A decomposição de matrizes simplifica esse processo ao dividir a matriz $A$ em partes mais simples – que podem ser resolvidas em etapas.

LU vs QR

Decompomos a matriz $A$ em outras matrizes estruturadas.

Decomposição LU

Divide $A$ em uma matriz triangular inferior e uma superior:

• Construída usando eliminação de Gauss;
• Funciona melhor para matrizes quadradas.

$$A = LU$$

Decomposição QR

Divide $A$ em uma matriz ortogonal e uma superior:

• Frequentemente usada para matrizes não quadradas;
• Ideal para problemas de mínimos quadrados ou quando a LU falha.

$$A = QR$$

Decomposição LU

Comece com uma matriz quadrada:

$$A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}$$

O objetivo é escrever isso como:

$$A = LU$$

Onde:

$$L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}$$

Essa decomposição é possível se A for quadrada e invertível.

Pontos importantes:

• Matrizes triangulares inferiores possuem todos os elementos acima da diagonal iguais a zero, facilitando a substituição direta;
• Matrizes triangulares superiores possuem zeros abaixo da diagonal, tornando a substituição retroativa simples;
• Uma matriz ortogonal possui colunas que são vetores ortonormais (vetores de comprimento 1 e perpendiculares entre si);
• Essa propriedade preserva o comprimento e os ângulos dos vetores, o que é útil na resolução de mínimos quadrados e na melhoria da estabilidade numérica.

Eliminação de Gauss

Aplicar a eliminação de Gauss para eliminar o elemento abaixo do pivô no canto superior esquerdo:

$$R_2 \rarr R_2 - \frac{6}{4}R_1$$

Isso nos dá:

$$R'_2 = [0, -1.5]$$

Assim, as matrizes atualizadas tornam-se:

$$U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}$$

E a partir da nossa operação de linha, sabemos:

$$L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}$$

Pontos Importantes:

• A eliminação de Gauss elimina sistematicamente os elementos abaixo do pivô em cada coluna subtraindo versões escaladas da linha do pivô das linhas abaixo;
• Esse processo transforma A em uma matriz triangular superior U;
• Os multiplicadores usados para eliminar esses elementos são armazenados em L, permitindo representar A como o produto LU.

Resultado da Decomposição LU

Verificamos:

$$A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}$$

Agora o sistema $A \vec{x} = \vec{b}$ pode ser resolvido em dois passos:

1. Resolver $L \vec{y} = \vec{b}$ por substituição direta;
2. Resolver $U \vec{x} = \vec{y}$ por substituição retroativa.

Decomposição QR

Deseja-se expressar uma matriz $A$ como o produto de duas matrizes:

$$A = QR$$

Onde:

• $A$ é a matriz de entrada (por exemplo, dados, coeficientes, etc.);
• $Q$ é uma matriz ortogonal (suas colunas são vetores ortonormais);
• $R$ é uma matriz triangular superior.

Exemplo de decomposição de formato:

$$A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}$$

Essa decomposição é frequentemente utilizada quando:

• A matriz A não é quadrada;
• Resolução de problemas de mínimos quadrados;
• A decomposição LU não é estável.

O que são vetores ortonormais?

Vetores ortogonais

Dois vetores $u, v$ são ortogonais se seu produto escalar é zero:

$$u \cdot v = 0$$

Vetor normalizado

Um vetor $u$ está normalizado quando $|u| = 1$.

Conjunto ortonormal

Um conjunto de vetores $\{q_1, q_2, ..., q_k\}$ é ortonormal se cada vetor tem comprimento unitário e são mutuamente ortogonais:

$$q_i \cdot q_j = \begin{cases} 1,\ \text{se}\ \ i = j,\\ 0,\ \text{se}\ \ i \neq j. \end{cases}$$

Importância: colunas ortonormais em $Q$ preservam a geometria, simplificam projeções e melhoram a estabilidade numérica.

Definição da matriz A

Vamos começar com este exemplo:

$$A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}$$

Utilizaremos o processo de Gram-Schmidt para encontrar as matrizes $Q$ e $R$ tais que $A=QR$. O processo de Gram-Schmidt cria um conjunto ortonormal de vetores a partir das colunas de $A$.

Isso significa que os vetores em $Q$ são todos perpendiculares (ortogonais) entre si e têm comprimento unitário (normalizados). Essa propriedade simplifica muitos cálculos e melhora a estabilidade numérica na resolução de sistemas.

Portanto, o objetivo aqui é:

• Tornar as colunas de $Q$ ortonormais;
• Criar a matriz $R$ que irá codificar as projeções.

Cálculo do primeiro vetor base

Extraímos a primeira coluna de $A$:

$$a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}$$

Para normalizar, calculamos a norma:

$$|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}$$

Então:

$$q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}$$

Este é o primeiro vetor ortonormal para $Q$.

Como normalizar um vetor

Dado um vetor:

$$v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}$$

Calculamos sua norma:

$$|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}$$

Depois normalizamos:

$$\hat{v} = \frac{1}{|v|}v$$

Exemplo:

$$v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5$$

Portanto, o vetor normalizado é:

$$\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}$$

Uma vez que sabemos como normalizar e ortogonalizar vetores, podemos aplicar o processo de Gram-Schmidt para formar a matriz $Q$ e utilizá-la para calcular $R$ na decomposição QR.

Calcular q₂ Usando Gram-Schmidt

Para calcular $q_2$, começamos com a segunda coluna de $A$:

$$a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}$$

Em seguida, projeta-se $a_2$ em $q_1$:

$$r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30$$

Remove-se a projeção de $a_2$:

$$u_2 = a_2 - r_{12}q_1$$

Depois, normaliza-se (como mostrado acima):

$$q_2 = \frac{u_2}{|u_2|}$$

Agora, tanto $q_1$ quanto $q_2$ formam a base ortonormal para $Q$. Em seguida, monta-se o resultado final:

$$Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}$$

Essas matrizes satisfazem:

$$A = QR$$