Decomposição QR
A melhor maneira de resolver um sistema sobredeterminado.
Vamos lá?
Nesta aula retomamos o assunto de sistemas sobredeterminados e como resolvê-los, no sentido de quadrados mínimos.
- 1
- 2
- 3
O que é um decomposição matricial?
Se é uma matriz ortogonal, então...
A solução de quadrados mínimos para um sistema sobredeterminado pode ser encontrada...
Na aula passada vimos que o problema de ajuste de curvas recai em encontrar o vetor
Com essa constatação, um sistema linear
Nesta aula vamos ver outra forma de determinar esse vetor
Teorema: Toda matriz
Mas o que é uma matriz ortogonal? Um matriz
Mas como isso nos ajuda no problema de quadrados mínimos? Se
Como a matriz
Repartindo o vetor
Logo
Para que isto funcione basta que
O caminho para encontrar a solução de quadrados mínimos de um sistema linear sobredeterminado está sumarizado nos passos a seguir.
- Computar a decomposição QR de
- Computar o vetor
- Resolver o sistema linear triangular superior
Nesta aula não vimos como computar a decomposição QR, mas tão somente como utilizá-la. Foge ao escopo desse curso a discussão de métodos para a obtenção da decomposição QR. Para quem se interessar, recomendo os livros Greenbaum e Chartier (2012) e Steweart (1998).
No Octave, o comando[Q,R] = qr(A)
, retorna as matrizes \
, quando aplicado a um sistema sobredeterminado, realiza os três passos acima e retorna a solução no sentido de quadrados mínimos. Sendo assim, se tiver acesso ao Octave, pode usar diretamente o \
para resolver sistemas sobredeterminados, sabendo agora o que ele faz por debaixo dos bits. Para finalizar, vejamos um exemplo no Octave.
A = [1 1; 1 2; 2 3]; b = [ 2; 3; 4]; [Q,R] = qr(A) Q = -4.0825e-01 7.0711e-01 -5.7735e-01 -4.0825e-01 -7.0711e-01 -5.7735e-01 -8.1650e-01 5.5511e-16 5.7735e-01 R = -2.44949 -3.67423 0.00000 -0.70711 0.00000 0.00000 z = Q'*b z = -5.30723 -0.70711 -0.57735 RR = R(1:2,1:2); zz = z(1:2,1); x = RR\zz x = 0.66667 1.00000 A\b ans = 0.66667 1.00000 norm(A*x-b) ans = 0.57735
Como exercício, repita o bloco acima no Octave, exibindo as saídas intermediárias (retirando os ;
do final de cada linha), para verificar se ficou claro o propósito de cada linha executada.
Referência
Anne Greenbaum e Timothy P. Chartier. Numerical Methods: Design, Analysis, and Computer Implementation of Algorithm. Princeton University Press, 2012.
Gilbert W. Steweart. Afternotes goes to Graduate School: Lectures on Advanced Numerical Analysis. SIAM, 1998.
1. Verique que matrizes abaixo são ortogonais.
, onde é a matriz identidade e é um vetor tal que .
2. Seja
- Verifique que
onde é o elemento na linha e coluna da matriz representa a coluna da matriz e representa a coluna da matriz - Se
é uma matriz ortogonal, usando o item anterior, verifique que suas colunas são ortogonais entre si e que cada coluna tem norma euclidiana unitária.
Para esse exercício, lembre que o produto interno usual entre dois vetores do
3. Considere os sistemas lineares a seguir. Para cada um deles, encontre a solução de quadrados mínimos usando a decomposição QR e depois verifique seu resultado comparando-o com o encontrado diretamente pelo \
. Compute o resíduo em cada caso, sem calcular o produto