Algorithme le plus rapide pour calculer le numéro de condition d'une grande matrice dans Matlab / Octave

9

D'après la définition du numéro de condition, il semble qu'une inversion de matrice est nécessaire pour le calculer, je me demande si pour une matrice carrée générique (ou mieux si symétrique positive définie) est possible d'exploiter une décomposition de matrice pour calculer le numéro de condition dans un manière plus rapide.

linear-algebra matrix condition-number linello
la source

7

Le calcul du nombre de conditions (même en l'approximant dans un facteur 2) semble avoir la même complexité que le calcul d'une factorisation, bien qu'il n'y ait pas de théorèmes dans cette direction.

A partir d'un facteur de Cholesky clairsemé d'une matrice définie positive symétrique, ou d'une factorisation clairsemée (avec implicite ) d'une matrice carrée générale, on peut obtenir le nombre de conditions dans la norme Frobenius en calculant le sous-ensemble inverse clairsemé de , ce qui est beaucoup plus rapide que le calcul de l'inverse complet. (Lié à ceci est mon article: Normes et limites hybrides pour les systèmes linéaires surdéterminés, Linear Algebra Appl. 216 (1995), 257-266. Http://www.mat.univie.ac.at/~neum/scan/74 .pdf ) $R$ $QR$ $Q$ $(R^TR)^{-1}$

Edit: Si alors par rapport à tout norn unitairement invariant,Pour le calcul des factorisations QR éparses, voir, par exemple, http://dl.acm.org/citation.cfm?id=174408 . Pour le calcul de l'inverse clairsemé, voir, par exemple, mon article: Estimation du maximum de vraisemblance restreint des covariances dans les modèles linéaires clairsemés, Genetics Selection Evolution 30 (1998), 1-24. https://www.mat.univie.ac.at/~neum/ms/reml.pdf Le coût est environ 3 fois le coût de la factorisation. $A=QR$

c o n d (A) = c o n d (R) = \sqrt{c o n d (R^{T} R)} .

$cond(A)=cond(R)=\sqrt{cond(R^TR)}.$

Arnold Neumaier
la source

Vous proposez donc ce qui suit: Étant donné une matrice calculez son QR de la forme où est une matrice triangulaire supérieure et est une matrice orthogonale puis le numéro de condition est donné par Le point ici est de savoir comment trouver une méthode rapide pour calculer une factorisation QR. Ai-je raison?

A

$\mathbf{A}$

A = Q R

$\mathbf{A}=\mathbf{Q}\mathbf{R}$

R

$\mathbf{R}$

Q

$\mathbf{Q}$

cond (A) = | | A | | | | A^{- 1} | | (R^{T} R)^{- 1}

$\textrm{cond}(\mathbf{A})=||A|| ||A^{-1}|| (\mathbf{R}^T\mathbf{R})^{-1}$

linello

@linello: pas tout à fait; voir mon montage.

Arnold Neumaier

Merci! Je vais vérifier, btw quel est le coût de cette étape?

linello

@linello: Pour une matrice complète, ; pour une matrice clairsemée, cela dépend beaucoup de la structure clairsemée.

O (n^{3})

$O(n^3)$

Arnold Neumaier

4

Il est certainement facile d'utiliser la décomposition valeur propre / vecteur propre d'une matrice symétrique ou la SVD d'une matrice générale pour calculer le numéro de condition, mais ce ne sont pas des moyens particulièrement rapides de procéder.

$A^{-1}$ condest

Brian Borchers
la source

Mais l'estimation est parfois nettement trop petite. Le calcul du nombre de conditions (même en l'approximant dans un facteur 2) semble avoir la même complexité que le calcul d'une factorisation, bien qu'il n'y ait pas de théorèmes dans cette direction.

Arnold Neumaier

1

$H$ $H$ $H^TH$

Étant donné que les valeurs propres / valeurs singulières les plus grandes et les plus petites peuvent être trouvées très rapidement (bien avant la fin de la tridiagonalisation), la méthode de Lanczos est particulièrement utile pour calculer le nombre de conditions.

chaohuang
la source

Je me suis toujours demandé où trouver un code matlab lisible pour l'itération lanczos qui clarifie comment obtenir la valeur propre la plus petite ou la plus grande. Pouvez-vous m'en suggérer un?

linello

Je n'ai pas les codes MATLAB pour l'algorithme de Lanczos.

chaohuang

Algorithme le plus rapide pour calculer le numéro de condition d'une grande matrice dans Matlab / Octave

Réponses: