[obm-l] Re: [obm-l] Inversão de Matriz Simétrica

["Domingos Jr." <dopikas@xxxxxxxxxx>]

com LU a idéia é a mesma, resolva o sistema (LU)x_i = e_i para i = 1...n e
monte a matriz cujas colunas são x_i's.

você pode conseguir ganhar alguma coisa aproveitando o fato que e_i tem
quase todas as componentes nulas na hora de resolver o sistema linear, mas
isso não vai afetar a complexidade do algoritmo.

também dá pra conseguir uma inversa através de fatoração QR... estou um
pouco enferrujado então eu não estou vendo uma maneira de aproveitar a
simetria da matriz no problema.

o que você falou, no entanto, está errado... não se diz que algo é O(n)^3 ou
O(n)^3/3...

dizer que f(n) = O(g(n)) é equivalente a dizer que
f(n) <= C*g(n) para uma constante C e todo n >= n_0 com algum n_0 fixado.

sendo assim, a complexidade das duas decomposições é a mesma, a saber,
O(n^3).
o que muda é a constante...

pra encerrar, vale notar que a multiplicação e inversão de matrizes pode ser
feita em
O(n^lg7), onde lg é o log na base 2 e lg 7 ~ 2,807.

http://www.library.cornell.edu/nr/bookcpdf/c2-11.pdf

-----

Esse é justamente um dos meus problemas, a minha matriz não é positiva.
Vou acabar usando fatoraçao LU.
Só a titulo de curiosidade para o Johan Peter... a inversão de matrizes
por fatoração LU tem complexidade O(n)³ e a fatoração de Cholesky O(n)³/3.
Se alguém souber de mais alguma coisa por favor me avisem.

[]'s

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================