Algoritmo mais rápido para calcular o número de condição de uma matriz grande no Matlab / Octave

9

A partir da definição do número da condição, parece que é necessária uma inversão da matriz para calculá-la. Será que para uma matriz quadrada genérica (ou melhor, se a definição positiva simétrica positiva) é possível explorar alguma decomposição da matriz para calcular o número da condição em um maneira mais rápida.

linello
fonte

Respostas:

7

Computar o número da condição (mesmo aproximando-o dentro de um fator de 2) parece ter a mesma complexidade que calcular uma fatoração, embora não haja teoremas nessa direção.

A partir de um fator Cholesky esparso de uma matriz definida positiva simétrica ou de uma fatoração Q R esparsa (com Q implícito ) de uma matriz quadrada geral, é possível obter o número da condição na norma Frobenius calculando o subconjunto inverso esparso de ( R T R ) - 1 , que é muito mais rápido do que computar o inverso completo. (Relacionado a este é o meu artigo: Normas e limites híbridos para sistemas lineares sobredeterminados, Linear Algebra Appl. 216 (1995), 257-266. Http://www.mat.univie.ac.at/~neum/scan/74 .pdf )RQRQ(RTR)1

Editar: Se , em seguida, no que diz respeito a qualquer norn unitariamente invariante, c o n d ( A ) = c o n d ( R ) = A=QRPara o cálculo de fatorações QR esparsas, consulte, por exemplo,http://dl.acm.org/citation.cfm?id=174408. Para o cálculo do inverso esparso, veja, por exemplo, meu artigo: Estimativa de verossimilhança máxima restrita de covariâncias em modelos lineares esparsos, Genetics Selection Evolution 30 (1998), 1-24. https://www.mat.univie.ac.at/~neum/ms/reml.pdf O custo é cerca de 3 vezes o custo da fatoração.

cond(A)=cond(R)=cond(RTR).



Arnold Neumaier
fonte
Então você está sugerindo o seguinte: Dada uma matriz calcule seu QR da forma A = Q R em que R é uma matriz triangular superior e Q é uma matriz ortogonal e, em seguida, o número da condição é dado por cond ( A ) = | | Um | | | | A - 1 | | ( R T R ) - 1 O ponto aqui é como encontrar um método rápido para calcular uma fatoração QR. Estou certo? AA=QRRQcond(A)=||A||||A1||(RTR)1
linello
@linello: não exatamente; veja minha edição.
Arnold Neumaier 22/10/12
Obrigado! Vou verificar, mas qual é o custo dessa etapa?
Linux 22/10/12
@linello: Para uma matriz completa, ; para uma matriz esparsa, isso depende muito da estrutura de esparsidade. O(n3)
Arnold Neumaier 22/10/12
4

Certamente é fácil usar a decomposição de valor próprio / vetor próprio de uma matriz simétrica ou o SVD de uma matriz geral para calcular o número da condição, mas essas não são formas particularmente rápidas de proceder.

A1condest

Brian Borchers
fonte
Mas a estimativa às vezes é significativamente pequena demais. Computar o número da condição (mesmo aproximando-o dentro de um fator de 2) parece ter a mesma complexidade que calcular uma fatoração, embora não haja teoremas nessa direção.
Arnold Neumaier 22/10/12
1

HHHTH

Como os maiores e menores valores próprios / valores singulares podem ser encontrados muito rapidamente (muito antes da conclusão da tridiagonalização), o método Lanczos é particularmente útil para calcular o número da condição.

chaohuang
fonte
Sempre me perguntei onde encontrar um código leglab legível para a iteração de lanczos, que esclarece como obter o menor ou maior valor próprio. Você pode me sugerir uma?
Linux 23/10/12
Eu não tenho os códigos MATLAB para o algoritmo de Lanczos.
chaohuang