Numéro de condition des formulations A'A et AA '

Il est montré (Yousef Saad, Méthodes itératives pour les systèmes linéaires clairsemés , p. 260) que$cond(A'A) \approx cond(A)^2$

Est-ce également vrai pour les ?$AA'$

Dans le cas où est avec , j'observe queN × M N ≪ M c o n d ( A ′ A ) ≫ c o n d ( A A ′$A$$N\times M$$N \ll M$$cond(A'A) \gg cond(AA')$

Cela signifie-t-il que la formulation en termes d' est préférable dans ce cas?$AA'$

Si avec N < M , alors r a n k ( A T A ) = r a n k ( A A T ) = r a n k ( A ) ≤ N < M pour que A T A ∈ R M × M ne peut pas être de rang complet, c'est-à-dire qu'il est singulier.$A\in\mathbb{R}^{N\times M}$$N<M$

Par conséquent, le numéro de condition est . En raison de l'arithmétique de précision finie, si vous calculez dans matlab, vous obtenez un grand nombre, non .$\kappa_2(A^TA)=\infty$cond(A'A)Inf

Eh bien, le regard let à pourquoi a approximativement le nombre au carré de l' état d' A . En utilisant la décomposition SVD de A = U S V T , avec U ∈ R N × N , S ∈ R N × M , V ∈ R M × M , nous pouvons exprimer A T A comme$A^TA$$A$$A=USV^T$$U \in \mathbb{R}^{N \times N}$$S \in \mathbb{R}^{N \times M}$$V \in \mathbb{R}^{M \times M}$$A^T A$

$A^T A=(USV^T)^T USV^T=VS^T U^T U S V^T=V S^T S V^T$

Ce que nous arrivons à en notant que est orthonormé, de sorte que U T U = I . De plus, nous notons que S est une matrice diagonale, de sorte que la décomposition finale de A T A peut être exprimée comme V S 2 V T , avec S 2 signifiant S T S , donnant une matrice diagonale avec les N premières valeurs singulières de S au carré dans la diagonale. Cela signifie que, puisque le numéro de condition est le rapport de la première et de la dernière valeur singulière, c o n d $U$$U^T U=I$$S$$A^TA$$V S^2 V^T$$S^2$$S^T S$$S$ pourA∈RN×M, $cond(A)=\frac{s_1}{s_N}$$A \in \mathbb{R}^{N \times M}$

$cond(A^T A)=\frac{s_1^2}{s_M^2}=(\frac{s_1}{s_M})^2=cond(A)^2$

Maintenant, nous pouvons effectuer le même exercice avec :$AA^T$

$AA^T=USV^T (USV^T)^T=USV^T V S^T U^T=U S^2 U^T$

Ce qui signifie que nous obtenons le résultat , puisqueS2signifie iciSST, une différence subtile par rapport à la notation ci-dessus.$cond(AA^T)=\frac{s_1^2}{s_N^2}$$S^2$$SS^T$

Mais notez cette subtile différence! Pour , le numéro de condition a la M'th valeur singulière dans le dénominateur, tandis que A A T a la N'th singularité. Cela explique pourquoi vous voyez des différences significatives dans le nombre de conditions - A A T sera en effet « meilleure condition » que A T A .$A^TA$$AA^T$$AA^T$$A^TA$

Pourtant, David Ketcheson avait raison - vous comparez les nombres de conditions entre deux matrices très différentes. En particulier, ce que vous pouvez accomplir avec ne sera pas la même chose que ce que vous pouvez accomplir avec A A T .$A^TA$$AA^T$

$\DeclareMathOperator{\cond}{cond} \cond A^2 \approx \cond A^T A$

$\cond A^T A = \bigO(\epsilon^{-4})$$\cond A^2 = \bigO(\epsilon^{-2})$

En arithmétique exacte cond (A ^ 2) = cond (A'A) = cond (AA '), voir par exemple. Golub et van Loan, 3e éd., P70. Ce n'est pas vrai en arithmétique à virgule flottante si A est presque déficient en rang. Le meilleur conseil est de suivre les recettes de livres ci-dessus lors de la résolution des problèmes des moindres carrés, l'approche la plus sûre étant SVD, p257. Utilisez \ varepsilon-rank à la place lors du calcul de SVD, où \ varepsilon est la résolution de vos données matricielles.