Discussion :

[PiRick]

Bonjour, j'ai un problème avec une matrice A 3x3 mal conditionnée. J'ai donc des erreurs lorsque je résous l'équation :
Ax=b.
Comme, dans mon problème particulier, la somme des valeurs de x est toujours égale à 1, je me permets d'effectuer une translation d'un vecteur t en utilisant une matrice T telle que les colonnes de T sont composées de t:
T=(t,t,t)
Ainsi, quel que soit x (pourvu que la somme de ses composantes soit égale à 1) on aura toujours :
Tx=t.
Et donc j’espère trouver t tel que la matrice (A+T) soit mieux conditionnée. Et ensuite je résous:
(A+T)x=b+t
Existe-t-il des méthodes pour trouver le meilleurs t?
Merci par avance

[dev_ggy]

Bonjour,

Je pense qu'il n'y a pas de solution à ton problème.

Y= AX n'implique pas qu'il existe T et t différent de 0 tel que Y+t = (A+T)x.

Pour l'explication mathématique. Cela doit se basé sur le fait que tu transforme un produit en somme, dans un espace vectoriel.

Pour résoudre Y = AX dans le cas ou A n'ai pas inversible. Tu as la pseudo-inverse.

Cordialement.

[Aleph69]

Bonjour,

Bonjour, j'ai un problème avec une matrice A 3x3 mal conditionnée. J'ai donc des erreurs lorsque je résous l'équation :
Ax=b.

Quel est le conditionnement de A? Quelle est la méthode de résolution?

Comme, dans mon problème particulier, la somme des valeurs de x est toujours égale à 1, je me permets d'effectuer une translation d'un vecteur t en utilisant une matrice T telle que les colonnes de T sont composées de t:
T=(t,t,t)
Ainsi, quel que soit x (pourvu que la somme de ses composantes soit égale à 1) on aura toujours :
Tx=t.

Ne serait-ce pas plutôt Tx=3t?

Et donc j’espère trouver t tel que la matrice (A+T) soit mieux conditionnée. Et ensuite je résous:
(A+T)x=b+t
Existe-t-il des méthodes pour trouver le meilleurs t?
Merci par avance

Ce n'est pas une bonne approche car tu imposes que T soit constante par ligne; par conséquent, le meilleur conditionnement possible est l'infinimum (dans l'espace des matrices T constantes par ligne) des conditionnements des matrices s'écrivant A+T. Or, il est possible que cette quantité soit très éloignée de 1.

Le plus simple serait de fournir A et b pour qu'on voit concrètement le problème.

[FR119492]

Salut!

dans mon problème particulier, la somme des valeurs de x est toujours égale à 1

Tu as donc:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
A11.x1 + A12.x2 + A13.x3 = b1
A21.x1 + A22.x2 + A23.x3 = b2
A31.x1 + A32.x2 + A33.x3 = b3
    x1 +     x2 +     x3 = 1

Il s'agit donc d'un système de 4 équations à 3 inconnues. Il n'est donc pas certain qu'il y ait une solution.
Jean-Marc Blanc

[PiRick]

Merci pour toutes vos réponses en très peu de temps!
Je suis nouveau sur le forum et je ne m'attendais pas à des réponses si rapides.
@ Jean-Marc :
"Il s'agit donc d'un système de 4 équations à 3 inconnues. Il n'est donc pas certain qu'il y ait une solution."

Exact, en fait si somme x1+x2+x3 n'est pas égale à 1, elle est rejetée.

@Aleph69 :
"Quel est le conditionnement de A? Quelle est la méthode de résolution? "

le déterminant de A est de l'ordre de 10^-5 et je soupçonne des erreurs numériques lorsque je fait l'opération
x1=det(B)/det(A)
ou les colonnes de B sont les mêmes que celles de A, exeptée la première colonne qui est égale à x1.
(idem pour x2 et x3 qui sont les deux autres inconnues)

"Ne serait-ce pas plutôt Tx=3t?"
x1,x2,x3 des scalaires (1,1), t le vecteur colonne de translation (3,1)
Tx=(t,t,t)*(x1,x2,x3)=t*x1+t*x2+t*x3=t*(x1+x2+x3)=t

"Le plus simple serait de fournir A et b pour qu'on voit concrètement le problème. "
Voici une matrice A :
-0.6959372 -0.6959372 -0.6959372
0.2578587 0.2655661 0.2588886
7.7605575E-02 8.1588157E-02 8.4874995E-02
et un vecteur b
-0.6957698
0.2540355
9.0615302E-02

@dev_ggy
malheureusement j'ai besoin d'une solution...
Je ne sonnais pas la pseudo-inverse, existe-t-il des publications ou de la documentation sur ce sujet?
je vais commencer par Wikipedia.

Sinon pour expliquer ma démarche :
Si on considère les 3 vecteurs de A=(a1,a2,a3) comme des coordonnées dans l'espace de trois points, le centre de ces trois points est :
o=(a1+a2+a3)/3
en prenant t=-o, on ramène ces trois points/vecteurs dans un même plan et alors det(A+T)=0
Comme il existe une matrice T de translation qui peut annuler le déterminant je me disais qu'il en existait peut-être une qui permettrait d'améliorer le conditionnement.
Encore une fois merci à tous.

[Aleph69]

Bonjour,

ta matrice est très bien conditionnée (cond(A)=265.6296 sous matlab). La résolution directe de Ax=b donne x=[-0.4376 -0.7849 2.2223] avec une erreur rétrograde nulle à la précision machine (norm(b-A*x)/norm(b)=0). L'erreur relative sur la solution est donc également nulle à la précision machine. Ton problème admet une solution unique dont la somme des composantes ne vaut pas 1.

[FR119492]

Salut!

la somme des valeurs de x est toujours égale à 1

Ne vaudrait-il pas mieux écrire

la somme des valeurs de x est toujours voisine de 1

Jean-Marc Blanc

[PiRick]

Salut,
effectivement Jean-Marc, la somme n'est pas forcément égale à 1 mais elle en est voisine

[PiRick]

Bonjour à tous,
En fait lors de la résolution je dois diviser par le déterminant de A et je n'aime pas trop ça quand il est proche de 0. J'avais trouvé une matrice translation par "intuition" sans avoir de réelle justification et je voulais savoir s'il existait un moyen de trouver la meilleure possible. Par exemple, pour la matrice A suivante:
-0.873563826084 -1.043226718903 -0.390902876854
-0.906283318996 -1.088057875633 -0.392626821995
-0.899949908257 -1.059592962265 -0.443507432938
Le déterminant est de
-0.000034332275
En utilisant la matrice T :
0.101300843060 1.633167028427 0.629045546055
0.101300843060 1.633167028427 0.629045546055
0.101300843060 1.633167028427 0.629045546055
On obtient la matrice A+T :
-0.772262871265 0.589940488338 0.238142654300
-0.804982364178 0.545109212399 0.236418694258
-0.798649072647 0.573573946953 0.185538113117
Dont le déterminant est :
-0.002942211926
Ce qui est préférable

[Aleph69]

En fait lors de la résolution je dois diviser par le déterminant de A

Tu utilises les formules de Cramer?

[PiRick]

Tu utilises les formules de Cramer?

Oui j'utilise la formule de Cramer.

[Aleph69]

Peux-tu envoyer ton code? Quelle solution obtiens-tu?

[Alexis.M]

Une approche fréquente pour les problèmes mal conditionnés consiste à ajouter un terme de régularisation sur la solution et à résoudre le problème de minimisation:

min_x ||Ax - b||^2 + c ||x||^2
avec c > 0.

Le gradient est :

2 A^t (Ax - b) + 2 c x

Pour annuler le gradient il faut donc:

x = (A^t A + c I)^{-1} A^t b

On remarque que si c=0 (pas de régularisation) on a :

x = (A^t A)^{-1} A^t b

Ce qui est la solution des moindres carrés standard puisque (A^t A)^{-1} A^t est la pseudo inverse de A

[Alexis.M]

As-tu des contraintes de positivité sur les composantes de x ?

Auquel cas ton problème est un problème de type LASSO avec
contrainte de non-négativité est il peut se résoudre au sens des
moindres carrés avec des algorithmes spécialisés.

Le problème LASSO s'écrit:

argmin_{x} || Ax - b ||^2 + lambda * || x ||_1

Certain algorithmes résolves le chemin complet des solutions pour toutes les
valeurs de lambda>0 (le chemin est linéaire par morceau) il te suffit donc de trouver pour quelle valeur de lambda tu obtiens || x ||_1 = 1

[FR119492]

Salut!

Oui j'utilise la formule de Cramer.

C'est exactement ce qu'il ne faut pas faire. Utilise plutôt la méthode de Gauss ou celle de Crout.
Jean-Matc Blanc

[Aleph69]

Salut Alexis,

le système linéaire en question n'est finalement pas mal conditionné.
Si problème il y a, c'est au niveau de la stabilité (rétrograde) de l'algorithme de résolution employé.

[PiRick]

Salut!

C'est exactement ce qu'il ne faut pas faire. Utilise plutôt la méthode de Gauss ou celle de Crout.
Jean-Matc Blanc

Bonjour à tous
Effectivement, je ne pensais pas qu'il était nécessaire d'utiliser ces méthodes pour des systèmes à 3 inconnues, mais finalement ça marche mieux (par contre ça prend un peu plus de temps de calcul, je ne sais pas si j'ai mal codé pour le coup).
Merci pour votre aide

[Aleph69]

Les temps de factorisation et de résolution ne devraient même pas être de l'ordre de la seconde.

[PiRick]

Les temps de factorisation et de résolution ne devraient même pas être de l'ordre de la seconde.

Le problème c'est que j'effectue cette opération des milliards de fois dans un programme qui l'utilise.

[Aleph69]

Bonjour,

as-tu un milliard de matrices différentes ou résous-tu Ax=b pour différents b?