Normas de Vetores e Matrizes

Prévia do material em texto

MS211 - Cálculo Numérico
Aula 5 – Normas de Vetores e Matrizes.
Condicionamento de uma Matriz.
Marcos Eduardo Valle
Na aula anterior, falamos sobre os erros de arredondamento na
representação de ponto flutuante e suas operações aritméticas.
Em termos gerais, erros sempre existirão quando resolvemos um
problema contínuo (e.g. em R) num computador.
Consequentemente, um método numérico raramente produz a
solução exata de um problema matemático contínuo.
Na aula de hoje, veremos quando o arredondamento em ponto
flutuante e suas operações aritméticas influenciam na
credibilidade do resultado produzido por um método numérico.
Iniciaremos apresentando a definição de norma, conceito
matemático utilizado para medir tamanho ou distância.
Definição 1 (Norma)
Uma norma é uma função } ¨ }, de um espaço vetorial V no
conjunto dos reais R, que satisfaz as seguintes propriedades para
quaisquer u, v P V e α P R:
1. }v} ě 0 com }v} “ 0 se e somente se v “ 0.
2. }αv} “ |α|}v}.
3. }u ` v} ď }u} ` }v}. (desigualdade triangular)
Não entraremos nos detalhes do que é um espaço vetorial. Por
ora, basta saber que os conjuntos Rn e Rnˆn dos vetores com n
componentes e as matrizes n ˆ n são ambos espaços vetoriais
com a soma e multiplicação por escalar.
Uma norma } ¨ } : Rn Ñ R, que associa à um vetor de Rn um
número real, será chamada norma vetorial. Similarmente, uma
função } ¨ } : Rnˆn Ñ R é uma norma matricial.
Norma Vetorial
Muitas normas vetoriais são dadas pela equação
}x}p “ p
gffe nÿ
i“1
|xi |p “ p
a|x1|p ` |x2|p ` . . .` |xn|p, 1 ď p ă `8.
Exemplos de normas para x “ rx1, x2, . . . , xnsT incluem:
‚ }x}1 “
nÿ
i“1
|xi | “ |x1| ` |x2| ` . . .` |xn|.
‚ }x}2 “
gffe nÿ
i“1
x2i “
b
x21 ` x22 ` . . .` x2n . (norma Euclidiana)
‚ }x}8 “ max
i“1:n |xi | “ maxt|x1|, |x2|, |xn|u.
Exemplo 2
Para o vetor x “ r3´ 4sT , temos:
}x}1 “ |3| ` | ´ 4| “ 7,
}x}2 “
b
32 ` p´4q2 “ 5,
}x}8 “ maxt|3|, | ´ 4|u “ 4.
No GNU Octave, podemos calcular as normas } ¨ }1, } ¨ }2 e } ¨ }8
de um vetor x usando respectivamente os comandos:
» norm(x,1)
» norm(x) ou » norm(x,2)
» norm(x,inf)
Interpretação Geométrica
O conjunto
B1 “ tx “ px , yq P R2 : }x}1 ď 1u,
corresponde à figura geométrica
Interpretação Geométrica
O conjunto
B2 “ tx “ px , yq P R2 : }x}2 ď 1u,
corresponde à figura geométrica
Interpretação Geométrica
O conjunto
B8 “ tx “ px , yq P R2 : }x}8 ď 1u,
corresponde à figura geométrica
Normas Matriciais Subordinadas
Podemos identificar uma matriz A com uma transformação linear
x ÞÑ Ax.
Uma norma matricial subordinada }A} mede a maior distorção
efetuada pela transformação linear x ÞÑ Ax. Formalmente, temos
}A} “ max
xPRn
}Ax}
}x} .
Equivalentemente, escrevendo v “ x{}x}, concluímos que
}A} “ maxt}Av} : }v} “ 1u,
ou seja, }A} é a maior distorção que A faz em tv : }v} “ 1u.
Observe que a norma matricial acima está subordinada ou é
induzida pela norma vetorial!
Exemplo da } ¨ }1
Considere a matriz A “
„
1 2
0 2

. Geometricamente, temos
A //
}A}1 “ maxt}Av}1 : }v}1 “ 1u “ 4.
A Norma Subordinada } ¨ }1
Pode-se mostrar que tAv : }v}1 “ 1u é um politopo
(generalização de um polígono) e o valor máximo de }Av}1, para
}v}1 “ 1, é obtido num dos vértices.
Os vértices do politopo t}Av : }v}1 “ 1u são ˘a1,˘a2, . . . ,˘an,
em que a1, . . . ,an são as colunas de A, i.e., A “ ra1, . . . ,ans.
Portanto, }A}1 é o valor máximo da soma dos valores absolutos
das colunas de A, ou seja,
}A}1 “ maxt}a1}1, . . . , }an}1u “ max
j“1:n
#
nÿ
i“1
|aij |
+
.
Exemplo da } ¨ }8
Considere a matriz A “
„
1 2
0 2

. Geometricamente, temos
A //
}A}8 “ maxt}Av}8 : }v}8 “ 1u “ 3.
A Norma Subordinada } ¨ }8
De um modo similar, pode-se mostrar que tAv : }v}8 “ 1u é um
politopo e o valor máximo de }Av}8 é obtido num dos vértices.
Contudo, os vértices do politopo t}Av : }v}8 “ 1u são obtidos
pelo produto Av, em que v “ r˘1,˘1, . . . ,˘1sT .
Usando esse fato, podemos concluir que }A}8 é o valor máximo
da soma dos valores absolutos das linhas de A, ou seja,
}A}8 “ maxt}aT1 }1, . . . , }aTn }1u “ maxi“1:n
$&% nÿ
j“1
|aij |
,.- ,
em que aTi denota a i-ésima linha de A.
Exemplo da } ¨ }2
Considere a matriz A “
„
1 2
0 2

. Geometricamente, temos
A //
}A}2 “ maxt}Av}2 : }v}2 “ 1u “ 2.92081.
A Norma Subordinada } ¨ }2
Pode-se mostrar que tAv : }v}2 “ 1u é um hiper-elipse
(generalização de uma elipse) e o valor máximo de }Av}2, para
}v}1 “ 2, é a metade do maior eixo.
Formalmente, }A}2 é o maior valor singular de matriz A.
No GNU Octave, podemos calcular as normas } ¨ }1, } ¨ }2 e } ¨ }8
de uma matriz A usando respectivamente os comandos:
» norm(A,1)
» norm(A) ou » norm(A,2)
» norm(A,inf)
Norma Consistente
Dizemos que uma norma matricial } ¨ } é consistente se
}AB} ď }A}}B},
para quaisquer matrizes A e B.
Todas as normas subordinadas são consistentes!
As normas subordinadas também satisfazem a desigualdade
}Ax} ď }A}}x},
para quaisquer matriz A e vetor x.
Erro Absoluto e Erro Relativo
Suponha que resolvemos um sistema linear Ax “ b, em que
A P Rnˆn é uma matriz não-singular e b P Rn, usando um método
numérico como, por exemplo, o método da eliminação de Gauss.
Vamos denotar por x˜ a solução encontrada pelo método numérico
e x˚ “ A´1b a solução exata.
Para avaliar a qualidade da solução produzida pelo método
numérico, comparamos a solução numérica x˜ com a solução
exata x˚ usando uma norma vetorial. Especificamente,
calculamos o erro absoluto Ea ou o erro relativo Er dados por:
Ea “ }x˚ ´ x˜} e Er “ }x
˚ ´ x˜}
}x˚} .
Resíduo
Uma desvantagem da análise que descrevemos anteriormente é
que, na prática, não conhecemos a solução exata x˚ do sistema
linear Ax “ b. Portanto, não podemos calcular o erro.
Como alternativa, calculamos o chamado resíduo absoluto Ra
ou o resíduo relativo Rr definidos por
Ra “ }b´ Ax˜} e Rr “ }b´ Ax˜}}b} .
Em algumas situações, é conveniente definir os vetores
e “ x˚ ´ x˜ e r “ b´ Ax˜,
chamados respectivamente erro e resíduo.
Matriz Gerada Aleatoriamente
Para valiar a qualidade da solução de um sistema linear Ax “ b
produzida pelo método da eliminação de Gauss, geramos uma
matriz A P R100ˆ100 cujos elementos aij possuem distribuição
normal padrão.
Além disso, definimos x˚ “ r1, . . . ,1sT e b “ Ax˚.
Determinamos a solução numérica x˜ usando o método da
eliminação de Gauss e calculamos o erro e o resíduo relativo.
Repetimos o processo 1000 vezes. A média dos erros e resíduos
relativos foram 1.3ˆ 10´12 e 6.0ˆ 10´14, respectivamente.
Note que o resíduo forneceu uma boa estimativa para o erro!
Comandos do GNU Octave
» for i=1:1000
A = randn(100,100); xs=ones(100,1);
b=A*xs; xt=Azb;
E_r(i)=norm(xs-xt,inf);
R_r(i)=norm(b-A*xt,inf)/norm(b,inf);
end
» [mean(E_r),mean(R_r)];
ans =
1.6535e-13 2.2155e-15
Matriz de Hilbert
Considere a matriz A P R100ˆ100 cujos elementos são
aij “ 1i ` j ´ 1 .
Definimos x˚ “ r1, . . . ,1sT , b “ Ax˚ e determinamos a solução
numérica x˜ usando o método da eliminação de Gauss.
O erro relativo e o resíduo relativo foram
Er “ }x
˚ ´ x˜}8
}x˚}8 “ 1.38 e Rr “
}b´ Ax˜}8
}b}8 “ 1.46ˆ 10
´15.
Ao contrário do exemplo anterior, temos resíduo relativo muito
pequeno mas um erro relativo grande.
Comandos do GNU Octave
» A = hilb(100); xs=ones(100,1);
» b=A*xs; xt=Azb;
warning: matrix singular to machine precision,
rcond = 1.14558e-21
» R_r=norm(b-A*xt,inf)/norm(b,inf)
R_r = 1.4554e-15
» E_r=norm(xs-xt,inf)
E_r = 1.3774
Sistemas Lineares Mal-Condicionados
Em termos gerais, um sistema linear Ax “ b é mal-condicionado
se pequenas perturbações na matriz A ou no vetor b causam
grandes variações na solução.
Nesse caso, devido aos errosna representação e operações de
pontos flutuantes, não devemos esperar uma solução precisa de
um método numérico!
Além disso, num sistema linear mal-condicionado, o resíduo pode
não revelar a natureza do erro!
O condicionamento de uma matriz A é definido em termos de sua
norma e a norma de sua inversa.
Sabemos que os vetores e (erro) e r (resíduo) satisfazem:
r “ Ae e e “ A´1r.
Sendo } ¨ } uma norma subordinada, tem-se:
}r} ď }A}}e} e }e} ď }A´1}}r} ùñ }r}}A} ď }e} ď }A
´1}}r}.
Analogamente, das equações b “ Ax˚ e x˚ “ A´1b, obtemos
}b} ď }A}}x˚} e }x˚} ď }A´1}}b} ùñ 1}A´1}}b} ď
1
}x˚} ď
}A}
}b} .
Combinamos as inequações, obtemos:
1
}A}}A´1}
}r}
}b} ď
}e}
}x˚} ď }A}}A
´1} }r}}b} .
Número de Condição de uma Matriz
O número de condição de uma matriz A, também chamado
condicionamento de A, é definido por
condpAq “ }A}}A´1}.
Vale a seguinte relação entre o erro relativo e o resíduo relativo:
Rr
condpAq ď Er ď condpAqRr .
‚ Se condpAq é próximo de 1, o erro relativo Er e o resíduo
relativo Rr são próximos.
‚ Se condpAq é grande, o erro relativo pode ser muito maior que
o resíduo relativo.
O número de condição de uma matriz A pode ser calculada no
GNU Octave usando o comando:
» cond(A)
O comando
» rcond(A)
fornece o recíproco 1{ condpAq, obtido usando a norma-1.
Note que A é mal-condicionada se rcond(A) é próximo de zero.
Calculamos o condicionamento da matriz de Hilbert como segue:
» cond(hilb(100))
ans = 5.9832e+19
Com base nos números do exemplo anterior, temos
1.38loomoon
Er
ď 5.98ˆ 1019loooooomoooooon
condpAq
1.46ˆ 10´15looooooomooooooon
Rr
“ 8.71ˆ 104.
Considerações Finais
Na aula de hoje apresentamos os conceitos de norma vetorial e
norma matricial subordinada.
Vimos como esses conceitos podem ser usados para determinar
o erro relativo de um sistema linear.
Vimos também o conceito de resíduo relativo e mostramos que
ele representa o erro relativo se o condicionamento de A for
próximo de 1.
Se condpAq é grande, dizemos que a matriz é mal-condicionada.
Nesse caso, não podemos confiar na solução fornecida por um
método numérico.
Muito grato pela atenção!