Discussion :

[Alexis.M]

Bonjour,

Je cherche à résoudre efficacement le problème suivant:

(a * I_n + QQ^T) x = y

Où a est un scalaire positif, I_n est la matrice identité de taille n x n, et Q une matrice n x m telle que m << n. x et y sont des vecteurs de taille n.

L'inverse de la matrice est a priori calculable par:

(a * I_n + QQ^T)^(-1) = 1/a * ( I_n + Q (a * I_m + Q^TQ)^(-1)Q^T))

Ce qui permet de beaucoup réduire les temps de calcul puisque la matrice à inverser est de taille m x m au lieu de n x n. Cependant, j'imagine que, comme pour la solution de Ax = y, le calcul de l'inverse n'est pas la méthode la plus adaptée pour des problèmes de précision numérique et de temps de calcul.

Quelle est donc la meilleure façon de résoudre ce type de système ?

D'avance merci,

Alexis

[bertry]

Salut,

le calcul de l'inverse n'est pas la méthode la plus adaptée pour des problèmes de précision numérique et de temps de calcul.

Habituellement, une décomposition LU ou une décomposition de Cholesky est utilisée pour résoudre les systêmes linéaires.

[Alexis.M]

Habituellement, une décomposition LU ou une décomposition de Cholesky est utilisée pour résoudre les systêmes linéaires.

Oui mais mon cas a une structure très particulière. Il n'y a pas d'intérêt à calculer naïvement la décomposition de Cholesky de (a*I_n + QQ^T), à moins de disposer d'une méthode spécialisée pour la structure du problème, faute de quoi on se retrouve avec la complexité O(n^3) habituelle. Alors que la formule de l'inverse montre qu'il doit être possible de calculer le tout en O(m^3 + n^2m). Avec m << n, le gain en temps de calcul est considérable.

[souviron34]

Si je comprend bien, tu as un système sur-dimensionné, c'est ça ?

N équations à m inconnues ?

[acx01b]

A x = b

où A a plus de colonnes que de lignes (donc x plus grand que b)

supposons que A est de rang plein (pas de lignes dépendantes)
x = x1 + x2
où x1 = A^T y est une combinaison linéaire des lignes de A,
et A x2 = 0 (donc x2 appartient à ker(A))

tu résous pour y (A A^T est inversible) :
A A^T y = b

puis si tu veux tu cherches une base de ker(A) pour trouver l'ensemble des x2 possibles

si A n'est pas de rang plein c'est pareil mais A A^T n'est pas inversible donc il peut ne pas y avoir de solution pour y

pour trouver ker(A) je pense à Gram-Schmidt

concernant la régularisation, c'est A A^T y = b qu'il faut régulariser

[souviron34]

ben moi je pensais au Simplex, si effectivement il ya plus d"équations que d'inconnues