méthode de Gréville

Imaginez une matrice dont les colonnes arrivent une à une. Au lieu de reprendre tout le calcul à chaque arrivée, la méthode de Gréville met à jour le résultat déjà obtenu. Elle mesure d'abord ce que la nouvelle colonne apporte réellement par rapport aux précédentes.

Si la colonne apporte une direction nouvelle, l'algorithme l'intègre. Si elle répète une combinaison des autres, il emploie une autre mise à jour. Le résultat est le pseudo-inverse, même lorsque la matrice est rectangulaire ou singulière et ne possède donc pas d'inverse ordinaire.

La méthode de Gréville construit le pseudo-inverse de Moore-Penrose d'une matrice en ajoutant ses colonnes successivement. Pour une matrice réelle A de m lignes et n colonnes, ce pseudo-inverse, noté $A^{+}A^+$, possède n lignes et m colonnes. Si A est carrée et inversible, il coïncide avec l'inverse ordinaire. Il reste défini lorsque A est rectangulaire ou singulière.

À chaque étape, l'algorithme compare la nouvelle colonne à l'espace engendré par celles déjà traitées. Le résidu est nul lorsque cette colonne en dépend, et non nul lorsqu'elle ajoute une direction. Chacun de ces deux cas possède sa propre formule de mise à jour. Bien que les colonnes soient ajoutées, le pseudo-inverse gagne une ligne à chaque étape.

Le résultat est l'unique matrice qui satisfait les quatre relations de Moore-Penrose, où la lettre T indique la transposition : Pour des matrices complexes, la transposée est remplacée par la transposée conjuguée.

On commence par la première colonne a₁. Si elle est non nulle, $A_1^{+}=a_1^T\mathrm{/}(a_1^T{a}_1)A\_1^+=a\_1^T/(a\_1^Ta\_1)$ ; si elle est nulle, son pseudo-inverse est une ligne de m zéros, où m est le nombre de lignes de A.

Soit A_k la matrice formée des k premières colonnes, et a_k la colonne ajoutée à A_k−1. À partir du pseudo-inverse de A_k−1, on calcule le vecteur de coefficients d_k, puis le résidu c_k :

Si c_k n'est pas nul, la ligne b_k^T vaut $c_k^T\mathrm{/}(c_k^T{c}_k)c\_k^T/(c\_k^Tc\_k)$. S'il est nul, elle vaut $(1+d_k^T{d}_k{)}^{-1}{d}_k^T{A}_{k-1}^{+}(1+d\_k^Td\_k)^\{-1\}d\_k^TA\_\{k-1\}^+$. La mise à jour est alors : Après la dernière colonne, A_n⁺ est le pseudo-inverse recherché.

La méthode s'applique à toute matrice réelle finie, carrée ou rectangulaire, de rang plein ou non. Il faut connaître ses colonnes dans un ordre fixé et disposer du produit scalaire usuel. Pour une matrice complexe, chaque transposée des formules doit être comprise comme une transposée conjuguée.

À chaque ajout, deux contrôles sont indispensables. Le résidu c_k doit être calculé avant de choisir la formule de b_k^T. Le dénominateur c_k^Tc_k ne peut être utilisé que si ce résidu est non nul.

Une colonne qui est une combinaison exacte des précédentes donne c_k = 0. La formule du cas indépendant provoquerait alors une division par zéro ; il faut employer la branche dépendante fondée sur d_k. C'est précisément ce qui permet de poursuivre avec une matrice singulière.

On traite la matrice réelle A et le vecteur de données y. Les deux colonnes de A sont a₁ = (1, 0)^T et a₂ = (2, 0)^T ; la seconde vaut exactement deux fois la première.

1. Pour la première colonne non nulle, son pseudo-inverse est la ligne .

2. Pour la seconde colonne, le coefficient et le résidu sont : Le résidu nul impose la branche des colonnes dépendantes.

3. La nouvelle ligne vaut :

4. La mise à jour donne exactement :

Le contrôle est refaisable : $A^{+}y=(1,2{)}^{T}A^+y=(1,2)^T$, puis $A{A}^{+}y=(5,0{)}^{T}AA^+y=(5,0)^T$. Le second vecteur est la projection de y sur les colonnes de A, et (1, 2)^T est la solution de norme minimale parmi celles qui produisent cette projection.

Pour résoudre un système qui n'a pas de solution exacte, on multiplie les données par le pseudo-inverse. On obtient une solution de moindres carrés ; parmi les solutions ex æquo, celle-ci a la plus petite norme.

Lorsque des variables sont ajoutées une à une, la mise à jour de Gréville réutilise le pseudo-inverse courant. Elle est naturelle si l'on veut suivre cette construction incrémentale, plutôt que recalculer conceptuellement le problème depuis le début.

Pour une matrice carrée dont l'inversibilité est établie, une méthode directe de résolution peut suffire. Gréville devient surtout utile lorsque la forme rectangulaire, la dépendance des colonnes ou la recherche explicite du pseudo-inverse fait partie du problème.

Inverse ordinaire. Une matrice A possède un inverse ordinaire lorsque A est carrée et inversible, avec AA⁻¹ = A⁻¹A = I. La matrice de l'exemple est singulière : elle n'a pas d'inverse ordinaire, mais elle possède un pseudo-inverse.

Inverse généralisé quelconque. Une matrice G peut seulement vérifier AGA = A sans être unique. Le pseudo-inverse de Moore-Penrose impose quatre relations, dont deux symétries, qui le rendent unique. Ainsi, vérifier une seule identité ne suffit pas à identifier le résultat de Gréville.

Résidu nul ou presque nul. En calcul exact, c_k = 0 est le cas charnière entre les deux formules. En virgule flottante, tester une égalité stricte peut choisir la mauvaise branche. Il faut comparer la norme du résidu à une tolérance liée à la précision machine et aux normes des données, sans seuil universel.

Construction « ligne par ligne ». Les données de A sont incorporées colonne par colonne ; c'est le pseudo-inverse qui reçoit une nouvelle ligne à chaque mise à jour. Intervertir ces deux rôles conduit à des dimensions incompatibles.

Transposition dans le cas complexe. Les formules écrites avec T valent pour des matrices réelles. Avec des coefficients complexes, utiliser la transposée simple détruit en général les propriétés de Moore-Penrose ; il faut prendre la transposée conjuguée.

Les quatre relations de Moore-Penrose offrent un prolongement naturel : elles permettent de contrôler indépendamment le résultat d'une construction de Gréville. Elles relient aussi le pseudo-inverse aux projections orthogonales AA⁺ et A⁺A, puis aux solutions de moindres carrés et de norme minimale.