Comment la SVD d'une matrice est-elle calculée en pratique

Comment MATLAB, par exemple, calcule-t-il la SVD d'une matrice donnée? Je suppose que la réponse implique probablement de calculer les vecteurs propres et les valeurs propres de A*A'. Si tel est le cas, j'aimerais également savoir comment calcule-t-on ces informations?

$AA^{T}$

Voir

GH Golub et C. Reinsch. Solutions de décomposition en valeurs singulières et moindres carrés. Numerische Mathematik 14: 403-420, 1970.

Ce matériel est discuté dans de nombreux manuels sur l'algèbre linéaire numérique.

Outre le papier (désormais classique) de Golub-Reinsch que Brian note dans sa réponse (je l'ai lié à la version du manuel du document), ainsi que le papier prédécesseur (également maintenant classique) de Golub-Kahan , il y a eu un certain nombre des développements importants dans le calcul de la SVD depuis lors. Je dois d'abord résumer le fonctionnement de la méthode habituelle.

L'idée dans le calcul de la SVD d'une matrice est qualitativement similaire à la méthode utilisée pour calculer la composition à l'échelle d'une matrice symétrique (et, comme indiqué dans le PO, il existe une relation intime entre elles). En particulier, on procède en deux étapes: la transformation en matrice bidiagonale , puis la recherche de la SVD d'une matrice bidiagonale. Ceci est tout à fait analogue à la procédure consistant à réduire d'abord une matrice symétrique en forme tridiagonale, puis à calculer la composition en octets de la tridiagonale résultante.

Pour calculer la SVD d'une matrice bidiagonale, une percée particulièrement intéressante a été l' article de Jim Demmel et Velvel Kahan , qui a démontré que l'on peut calculer même les minuscules valeurs singulières d'une matrice bidiagonale avec une bonne précision, en modifiant convenablement la méthode initialement proposée dans Golub-Reinsch. Cela a ensuite été suivi par la (re?) Découverte de l' algorithme dqd , qui est un descendant de l'ancien algorithme de différence de quotient de Rutishauser. (Beresford Parlett donne une belle discussion ici.) Si la mémoire est bonne, c'est maintenant la méthode préférée utilisée en interne par LAPACK. En dehors de cela, il a toujours été possible de dériver des versions SVD de développements dans la solution de problèmes propres symétriques; par exemple, il existe une version SVD de diviser pour mieux régner, ainsi qu'une version SVD de l'ancien algorithme Jacobi (qui peut être plus précis dans certaines circonstances).

En ce qui concerne la bidiagonalisation, une méthode améliorée a été décrite dans l'article de Barlow , qui nécessite un peu plus de travail que la procédure originale de Golub et Reincsh, mais donne des matrices bidiagonales plus précises.