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

Quociente de Iteração de Rayleigh

0 votos
8 visitas
perguntada 3 dias atrás em Matemática por Luiz Filippe (6 pontos)  
editado 1 dia atrás por Luiz Filippe

Implemente o quociente de iteração de Rayleigh para computar o eigenvalue e o correspondente eigenvector de uma matriz. Teste seu programa na matriz do exercício anterior (4.3) usando um vetor inicial aleatório. (Livro, página 211, questão 4.4)

REFERÊNCIA DA QUESTÃO: HEATH, M. T. "Scientific Computing: An Introductory Survey". 2ª edição, ed.: McGraw-Hill. Nova York, 2002. Disponível em: < http://www-e6.ijs.si/~roman/files/tmp/M.Heath-SComputing/scientific-computing-michael-t-heath.pdf >

Compartilhe

1 Resposta

0 votos
respondida 3 dias atrás por Luiz Filippe (6 pontos)  
editado 1 dia atrás por Luiz Filippe

Antes de adentrar na questão, é válido relembrar os conceitos de eigenvector e eigenvalue. O eigenvector (ou vetor característico) é um vetor "\(u\)" que, ao ser aplicado em um transformação linear \(T\) (ou seja, ao multiplicar pela direita uma matriz \(T\): \(Tu\)) retorna o próprio vetor "u" escalonado por um escalar c (tal escalar é o eigenvalue). Uma questão de interesse é investigar quem são os eigenvectors e eigenvalues de uma determinada matriz. Uma forma de conduzir tal investigação é a partir do uso do quociente de Rayleigh.

O quociente de Rayleigh é usado no teorema do min-max e em outros algoritmos com o intuito de encontrar os valores dos eigenvalues (exatos ou aproximados) de uma determinada matriz. Ele associa uma quantidade escalar a um vetor "\(u\)" (complexo ou real). Este quociente pode tanto ser empregado para uma dada matriz complexa Hermitiana (uma matriz quadrada de entradas complexas que é igual a sua própria matriz transposta conjugada) como para uma matriz real (esta, neste caso, deverá ser simétrica). De todas as formas, é válido apontar que ambas as matrizes são diagonalizáveis apenas com valores reais.

O método iterativo do quociente de Rayleigh entrega uma sequência de soluções aproximadas que, no limite, convergem para a solução verdadeira. Este algoritmo de iteração converge cubicamente para a matriz sob análise (Hermitiana ou real simétrica) desde que o vetor inicial usado para fazer tal iteração seja suficientemente próximo ao eigenvector de dita matriz. Primeiramente escolhemos algum valor inicial para "\(mu\)" ("chute" do eigenvalue inicial da matriz hermitiana) e algum valor inicial para o eigenvector "\(v\)". Nosso objetivo é chegar à convergência de ambos os valores "\(mu\)" e "\(v\)".

REFERÊNCIA: PARLETT, B. N. "The Rayleigh Quotient Iteration and Some Generalizations for Nonnormal Matrices". Mathematics of Computation, v. 28, n. 127, p. 679–693, jul. 1974. Disponível em: < https://www.ams.org/journals/mcom/1974-28-127/S0025-5718-1974-0405823-3/S0025-5718-1974-0405823-3.pdf >

A implementação em Python:

# Importar pylab é o mesmo que importar "numpy" e "pyplot" juntos  
from pylab import *

# A matriz do exercício anterior (4.3) é: 
A = array([[6,2,1],[2,3,1],[1,1,1]])

# Com este comando apenas mostro a matriz A que defini acima
print ("\nA = ")
print (A)

# Vou agora encontrar os eigenvectors da matriz A e mostrá-los
lam,X = eig(A)
eigenvalues = lam
print ("\nEigenvalues: ",lam)

# A questão pede para eu escolher um vetor aleatório como vetor inicial do algoritmo de 
iteração. Tomemos 
# alguns aleatórios para ver o que ocorre:
vetor_inicial = randn(3)
v = vetor_inicial
print ("\nVetor inicial v: ",v)
print (" ")

#"Chute" para valor inicial do eigenvalue da matriz Hermitiana 
mu = 1. + 1j
print ("k = %s, mu = %21.16f + %21.16fj" %  (0,mu.real,mu.imag))

# A iteração de Rayleigh
# A função "eye(3)" retorna a matriz identidade de dimensão 3
# A função solve vai resolver o sistema linear Bw=v
for k in range(1,10):
B = A - mu*eye(3)
try:
    w = solve(B,v)
except:
    print ("A matriz é singular e a solução convergiu")
    break

# Atualizamos o valor de mu    
v = w / norm(w,2)
mu = dot(conj(v.T), dot(A,v))
print ("k = %s, mu = %21.16f + %21.16fj" %  (k,mu.real,mu.imag))

Ao definirmos o vetorinicial=randn(3) acima, não há convergência; porém, ao colocarmos vetorinicial=eigenvalues, a convergência é imediata.

comentou 27 minutos atrás por Arthur Quintão (1 ponto)  
republicada 3 minutos atrás por Arthur Quintão
Excelente resposta, Luiz.
Se me permite, gostaria de trazer 2 contribuições a fim de melhor entender seu código.

A primeira trata-se da parte matemática do problema.
Como explorado em seu código, especificamente no função solve(), é interessante lembrar que os autovalores podem ser interpretados como a raiz do polinômio característico, isto é,

\( p(\lambda)=det(A-\lambda I)=0 \)

onde \[ \lambda \] é o autovalor.
...