Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Uma matriz singular deve ter autovalores iguais a 0, mas uma matriz quase singular tem autovalores "pequenos"?

0 votos
26 visitas
perguntada Out 15 em Programação Computacional por Thiago Trafane (36 pontos)  

Exercício 4.10 do capítulo 4 do livro "Scientific Computing: An Introductory Survey" de Michael T. Heath. O enunciado completo segue abaixo:

Uma matriz singular deve ter autovalores iguais a zero, mas uma matriz quase singular tem autovalores "pequenos"? Considere uma matriz da forma
\begin{bmatrix}
1 & -1 & -1 & -1 & -1 \\
0 & 1 & -1 & -1 & -1 \\
0 & 0 & 1 & -1 & -1 \\
0 & 0 & 0 & 1 & -1 \\
0 & 0 & 0 & 0 & 1
\end{bmatrix}
cujos autovalores são obviamente todos iguais a 1. Use uma rotina de uma biblioteca para calcular os valores singulares de matrizes dessa forma para várias dimensões. Como a razão \( \sigma_{max}/\sigma_{min} \) se comporta à medida que a dimensão da matriz aumenta? Que conclusões você pode tirar?

Compartilhe

1 Resposta

0 votos
respondida Out 15 por Thiago Trafane (36 pontos)  
editado Out 15 por Thiago Trafane

Seja \(A\) uma matriz qualquer. Então, os valores singulares de \(A\) são as raízes quadradas não negativas dos autovalores de \(A'A\). Uma propriedade interessante dos valores singulares, apresentada na seção 3.6.1 do livro "Scientific Computing: An Introductory Survey" de Michael T. Heath, é que a razão entre o maior e o menor valor singular de \(A\) (\( \sigma_{max} \) e \( \sigma_{min} \), respectivamente) é igual ao número de condicionamento dessa matriz na norma Euclidiana ( \(Cond_2(A)\)), isto é, \( Cond_2(A) = \sigma_{max}/\sigma_{min} \). Assim, quanto maior for \( \sigma_{max}/\sigma_{min} \), mais próxima da singularidade estará a matriz \(A\).

A partir desses conceitos, podemos resolver o exercício proposto. Para isso, eu construí uma função que, inicialmente, gera a matriz \(M\) da forma apresentada no enunciado para uma dimensão \(n\) qualquer e calcula os seus valores singulares usando a biblioteca scipy.linalg. Então, a função obtém \( \sigma_{max} \) e \( \sigma_{min} \) e, finalmente, \( Cond_2(M) = \sigma_{max}/ \sigma_{min} \). O código dessa função é bastante simples, como se vê abaixo.

# 0) Importando pacotes
import numpy as np
from scipy.linalg import svd
import matplotlib.pyplot as plt

# 1) Definindo a função que calcula a razão pedida
def sigma_ratio(n):

    # Construindo a matriz de dimensão n do enunciado
    M = np.zeros((n,n))
    for i in range(n):
        for j in range(n):
            if i==j:
                M[i,j] = 1
            elif j>i:
                M[i,j] = -1

    # Obtendo os valores singulares
    _, sigma, _ = svd(M)

    # Calculando o valor singular máximo e mínimo e obtendo a razão entre eles
    sigma_max = max(sigma)
    sigma_min = min(sigma)
    cond2 = sigma_max/sigma_min

    # Definindo o output da função
    return cond2

Com base nessa função, eu gerei a medida de condicionamento na norma Euclidiana para \(n=2,3,...,39\). Para facilitar a visualização, eu plotei em um gráfico esses valores contra a dimensão da matriz. O código que gera tal gráfico é apresentado abaixo.

# 2) Resolvendo o exercício proposto
if __name__ == '__main__':

    # Definindo listas a serem preenchidas
    n_grid = []
    ratio_grid = []

    # Preenchendo listas considerando n de 2 a 39
    for n in range(2,40):
        n_grid.append(n)
        ratio_grid.append(sigma_ratio(n))        

    # Plotando gráfico com os valores de n e da razão
    plt.plot(n_grid,ratio_grid)                    
    plt.title('Número de condicionamento')
    plt.xlabel('Dimensão da matriz')
    plt.ylabel('Número de condicionamento')
    plt.savefig('g_ratio')
    plt.show()

O gráfico gerado é mostrado abaixo. Como se vê, o número de condicionamento aumenta à medida que a dimensão da matriz se eleva, indicando uma matriz mais próxima da singularidade. De fato, vemos que \( Cond_2(M) \rightarrow \infty \) se \( n \rightarrow \infty \). Em outras palavras, podemos construir uma matriz arbitrariamente próxima da singularidade se escolhermos uma dimensão suficientemente elevada. Contudo, para qualquer dimensão \(n\), os autovalores da matriz \(M\) são todos iguais a 1. Logo, é falsa a afirmação de que uma matriz quase singular deve ter autovalores "pequenos", o que encerra a resolução do exercício.

A imagem será apresentada aqui.

comentou Nov 2 por Alan Antunes Rosendo (41 pontos)  
Parabéns pela solução, os gráficos ajudam muito no entendimento de como as variáveis estão se comportando.
Segue algumas sugestões de modificações no código
Por uma questão de clareza do código, eu faria a função que gera a matriz fora da função sigma_ratio e chamaria ela.
Não sei qual motivo, mas quando a dimensão aumenta muito, o número de condicionamento calculado começou a reduzir, pode ser uma questão de erro de aproximação.
comentou Nov 6 por Thiago Trafane (36 pontos)  
Alan, obrigado pelos comentários! Acabei construindo a matriz dentro da função sigma_ratio mesmo por entender que é um código relativamente simples, mas, naturalmente, seria possível também fazer da forma que você sugeriu. Quanto ao seu segundo comentário, imagino que deva ser algum problema numérico mesmo.
...