Transformations QR

La deuxième étape de la mise sous forme SVD consiste à appliquer un certain nombre de fois la décomposition $QR$ sur une matrice bidiagonale. Concrètement :

U = Id; V = Id; S = BD;
For i from 0 to NMax
    (Q1, R1) = decomp_qr(matrix_transpose(S))
    (Q2, R2) = decomp_qr(matrix_transpose(R1))
    S = R2;
    U = U * Q2;
    V = matrix_transpose(Q1) * V
    End for
Return (U,S,V)

Dans cet algorithme, la matrice $S$ converge vers une matrice diagonale, et les matrices ($U$,$S$,$V$) correspondent aux matrices de la décomposition SVD.

Implémentation

  • Question : Écrire une version préliminaire de cet algorithme en utilisant la fonction numpy.linalg.qr.

Etude de convergence

  • Question : Tester et dessiner la convergence de la matrice $S$ vers une matrice diagonale, et s’assurer que l’invariant $U\times S\times V = BD$ est toujours vérifié.

Les appels à la fonction de décomposition $QR$ dans cet algorithme sont en fait disproportionnés : les matrices sur lesquelles on applique cet algorithme sont beaucoup plus simples que des matrices pleines.

Analyse

  • Question : Montrer l’invariant suivant du calcul : les matrices $S$, $R1$ et $R2$ sont toujours bidiagonales.

Optimisation pour une matrice bidiagonale

  • Questions :
    1. Réécrire une version simplifiée de la décomposition $QR$ en utilisant l’algorithme vu en cours et l’invariant précédent,
    2. puis utiliser cette optimisation pour votre algorithme de décomposition SVD.
    3. Quelles sontles complexités des deux algorithmes obtenus ?

Mise en forme

Usuellement, la décomposition SVD demande à ce que les éléments de la matrice $S$ soient positifs, ordonnés de manière décroissante.

  • Question : Modifier les matrices $U$ et $S$ de manière à assurer cette propriété.