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

9

Il est montré (Yousef Saad, Méthodes itératives pour les systèmes linéaires clairsemés , p. 260) quecond(AA)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 )AN×MNMcond(AA)cond(AA)

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

Alexandre
la source
2
Vous comparez les nombres de conditions de deux matrices avec des tailles très différentes. Sans expliquer pourquoi, il semble que cette comparaison ne soit probablement pas significative. Certes, si vous pouvez accomplir ce dont vous avez besoin en utilisant la matrice beaucoup plus petite, vous devriez (même si le conditionnement était similaire).
David Ketcheson
1
La nouvelle réponse de Stefano M ci-dessous est correcte. Veuillez le lire et voter.
David Ketcheson

Réponses:

6

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.ARN×MN<M

rank(ATA)=rank(AAT)=rank(A)N<M
ATARM×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 .κ2(ATA)=cond(A'A)Inf

Stefano M
la source
@OscarB: les valeurs singulières de sont que N , la M ème valeur singulière n'existe pas ! Votre dérivation est correcte, mais veuillez noter que si σ i , i = 1 N sont les sv de A , alors S S T = d i a g ( σ 2 1 , , σ 2 n ) , tandis que S T S = d i a g ( σ 2ANMσii=1NASST=diag(σ12,,σn2)avecM-Nzéros de fin. STS=diag(σ12,,σn2,0,,0)MN
Stefano M
8

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 commeATAAA=USVTURN×NSRN×MVRM×MATA

ATA=(USVT)TUSVT=VSTUTUSVT=VSTSVT

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 (UUTU=ISATAVS2VTS2STSS pourARN×M, cond(A)=s1sNARN×M

cond(ATA)=s12sM2=(s1sM)2=cond(A)2

Maintenant, nous pouvons effectuer le même exercice avec :AAT

AAT=USVT(USVT)T=USVTVSTUT=US2UT

Ce qui signifie que nous obtenons le résultat , puisqueS2signifie iciSST, une différence subtile par rapport à la notation ci-dessus.cond(AAT)=s12sN2S2SST

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 .ATAAATAATATA

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 .ATAAAT

OscarB
la source
Voilà une excellente explication! Je vois clairement la différence maintenant. La matrice A est utilisé pour construire des équations normales et avec de légères modifications , vous pouvez aussi le formuler comme , et non classique A ' A . Pouvez-vous également dire s'il est avantageux d'utiliser un solveur comme LSQR au lieu de résoudre des équations normales? Depuis LSQR ne nécessite pas du tout de construire ce produit. AAAA
Alexander
Heureux que cela ait du sens. En général, vous devez considérer le conditionnement du problème. Mais, si ce n'est pas un problème, vous pouvez utiliser soit des équations normales / QR-factorisation (de A) / LSQR, en fonction de la taille du problème (entre autres). À moins que votre problème soit important ou mal conditionné, j'appliquerais probablement la factorisation QR, mais sans plus de connaissances sur le problème que vous essayez de résoudre, c'est difficile à dire. Je suis sûr que d'autres ayant plus d'expérience pourraient fournir des conseils plus détaillés.
OscarB
107cond(A)<cond(AAT)<cond(ATA)N<M), alors l'utilisation de LSQR semble toujours préférable, car vous n'avez pas du tout besoin de former un produit. La question est de savoir si les solutions obtenues avec des équations normales et LSQR sont identiques?
Alexander
Eh bien, si je comprends bien, LSQR fournira une solution identique aux équations normales après "infiniment" d'itérations avec une précision exacte. Cependant, pour les problèmes mal posés, la solution d'équations normales n'est pas celle que vous souhaitez. Au lieu de cela, vous souhaitez utiliser LSQR pour itérer jusqu'à ce que la semi-convergence soit atteinte. Cependant, contrôler les algorithmes itératifs dans les problèmes mal posés est un tout autre jeu de balle. En outre, selon le coût de votre produit matriciel-vecteur et le nombre d'itérations (et donc de matvecs) nécessaires, une solution tikhonov directe avec bidiagonalisation pourrait être meilleure.
OscarB
Super explication. +1 pour vous monsieur!
meawoppl
2

condA2condATA

A=(ϵ10ϵ),ϵ1

condATA=O(ϵ4)condA2=O(ϵ2)

Jed Brown
la source
A2ATA[cond(A)]2
@StefanoM Merci, il semble que j'ai mal lu, bien que la discussion n'ait pas été la seule.
Jed Brown
1

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.

Artan
la source
Je suis désolé, j'ai regardé Golub et Van Loan 3e éd p. 70, et n'a rien trouvé pour sauvegarder l'instruction cond (A ^ 2) = cond (A ^ TA) = cond (AA ^ T). Pourriez-vous être plus précis avec votre référence?
OscarB
Il n'y a pas de déclaration ici, mais vous pouvez déduire du théorème 2.5.2 et du pseudoinverse, section 5.5.4 que cond (AA ') = cond (A'A). La raison pour laquelle je prends pseudoinverse est que c'est ce qui compte pour le problème des moindres carrés en main. L'égalité après cond (A ^ 2) devrait être \ approx, désolé pour la faute de frappe.
Artan
Non, cette réponse est totalement incorrecte. Voir mon contre-exemple.
Jed Brown
Saad doit avoir fait une telle remarque par rapport à un contexte spécifique. Ce qui est pertinent pour la question à l'examen, c'est l'argument de la procédure.
Artan