Normas de Matrizes e Condicionamento

Para além do problema de instabilidade numérica que decorre da propagação dos erros de arredondamento, podem também ocorrer problemas de mau condicionamento. Para podermos analisar convenientemente o problema do condicionamento, é necessário introduzirmos a noção de normas vectoriais e matriciais.

Definição: Seja ||.|| uma norma vectorial em Rn.
A norma da matriz A induzida pela norma vectorial é:
 

|| A || = max||x||=1 || A x || = maxx¹0  ||A x ||
  ||x||

Propriedades :
Para quaisquer matrizes A, B quadradas e qualquer vector x, temos:

i) || A x || < || A || || x ||
ii) || A B || < || A || || B ||

dem:
i) É imediato. Caso x ¹0, temos  || A ||  >|| A x || / ||x||<=>|| A x || < || A || || x ||, e se x = 0 temos 0 < 0.
ii) É semelhante, basta ver que de i), para qualquer x ¹0,
|| A B x || / ||x|| < || A || || B x || / ||x||
e portanto
|| A B || = max || A B x || / ||x|| <  || A || max || B x || / ||x|| = || A || || B || .

Exemplos de Normas :

1) Norma do Máximo (linhas):
 
Norma vectorial, || x ||¥ =    max
i =1,...,n		 | xi |
Norma matricial induzida, || A ||¥ =    max
i =1,...,n		   N
S
j = 1		 | aij |

Corresponde ao máximo dos somatórios dos módulos dos elementos das linhas.

2) Norma da Soma (colunas):
 
Norma vectorial, || x ||1 =    N
S
i = 1		 | xi |
Norma matricial induzida, || A ||1 =    max
j =1,...,n		   N
S
i = 1		 | aij |

Corresponde ao máximo dos somatórios dos módulos dos elementos das colunas.

3) Norma Euclidiana:
 
Norma vectorial, || x ||2 =  (   N
S
i = 1		 | xi | 2 ) 1/2
Norma matricial induzida, || A ||2 = r(ATA)1/2

onde r(A) designa o raio espectral da matriz A.


Definição:
Designamos por raio espectral de uma matriz A o valor :
 
r(A)=    max
i =1,...,n		 | l i |
onde l 1, ..., ln são os valores próprios de A.

Observação: Se a matriz A for simétrica então || A ||2 = r(A). 


Teorema: Seja A uma matriz quadrada.
  • Para qualquer norma matricial ||.|| , temos
    • r(A) < || A ||
  • Para qualquer e > 0 existe sempre uma norma induzida ||.|| tal que:
    • || A || < r(A) + e

    Ou seja, o raio espectral é o ínfimo do conjunto das normas induzidas de uma matriz.


    Número de Condição de uma Matriz

    Ao resolver um sistema

    A x = b
    podemos ter problemas de condicionamento e de estabilidade numérica. Os problemas de estabilidade numérica estão relacionados com o algoritmo que utilizamos para resolver o sistema. Por exemplo, para evitar os problemas de instabilidade numérica, é habitual considerar o método de eliminação de Gauss com pesquisa de pivot.
    No entanto, se o problema fôr mal condicionado, essas técnicas de pesquisa de pivot deixam de ser úteis, já que um problema mal condicionado será sempre numericamente instável. Interessa-nos, portanto, identificar quais os sistemas que nos podem trazer problemas de condicionamento.

    Supondo que nos era dado, não o vector b exacto, mas apenas uma aproximação b~, vamos analisar a influência desse erro nos resultados obtidos, já que em vez do valor exacto, obtemos um valor aproximado x~, solução do sistema:

    A x~ = b~

    As normas que acabámos de estudar, permitem-nos estabelecer uma medida de comparação entre os erros vectoriais, definindo-se, de forma semelhante ao caso escalar:

  • Erro Absoluto de x~ : || ex || = || x - x~ ||
  • Erro Relativo de x~ : ||dx || = || x - x~ || / || x ||

    • relativamente a uma certa norma || . || .

    Para estabelecermos a relação entre os erros relativos dos dados e os erros relativos dos resultados vai ser importante estabelecer uma noção que envolve a norma de matrizes :

    Definição: Designa-se por número de condição de uma matriz A relativamente à norma || . ||, o valor :

    cond (A) = || A || || A-1||

    Teorema: Temos as seguintes desigualdades, para o erro absoluto:

    a) || eb || || A || -1< || ex || < || A-1 || || eb ||

    e para o erro relativo :
    b) || db || cond( A )-1< || dx || < cond( A ) || db ||

    dem:
    Usando os dois sistemas, retiramos
    A ( x - x~) = b - b~
    portanto:
    || A || || x - x~ || > || b - b~ ||
    e
    || x - x~ || < || A-1|| || b - b~ ||
    logo a alínea a) fica provada, pois :
    || A||-1 || b - b~ || < || x - x~|| < || A-1|| || b - b~ ||

    Por outro lado, de A x = b, retiramos, de forma análoga :

    || A||-1 || b || < || x || < || A-1|| || b ||

    dividindo o resultado de a) por este resultado, obtemos b).

    Observações:
    1) Podemos concretizar estes resultados para qualquer uma das normas.
    Por exemplo, podemos retirar a majoração :

    || dx ||1 < cond1( A ) || db ||1
    onde cond1( A ) designa o número de condição relativamente à norma da soma, ou seja :
    cond1( A ) = || A ||1 || A-1||1

    2) Se || I || = 1 (o que acontece para as normas estudadas), como || I || = || A A-1 || < || A || || A-1 || ,
    obtemos cond( A ) > 1.

    3) No caso de existirem erros na matriz, definimos || dA || = || A - A~ || / || A ||
    e no caso de || dA || < 1/cond (A), obtemos A~ invertível e verifica-se

    || dx || < cond( A )   || dA || + || db || 
    1 - cond( A )|| dA || 


     
  • Destes resultados podemos concluir que um número de condição elevado não nos permite estabelecer boas majorações para o erro relativo. Quanto maior fôr o número de condição, pior será a majoração de erro relativo obtida.
  • Consequentemente, para matrizes cujo número de condição seja elevado, um pequeno erro relativo no vector b, pode provocar um grande erro relativo na solução do sistema.

    •  

     

  • Terminamos este parágrafo observando que podemos também definir um número de condição associado ao raio espectral :
    • condr ( A ) =  r( A ) r( A-1 )

    que verifica a propriedade (resultante do raio espectral ser o ínfimo das normas) :

    condr ( A ) < cond ( A )
    para qualquer norma.

    Atendendo a que os valores próprios de A-1 são os inversos de A, temos :
     

    condr( A ) =  maxk=1,...,n | lk (A) | 
    mink=1,...,n  | l k (A) |