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 =========================================================================
