Résolution de systèmes linéaires.

Dattier a écrit:@Fun : OK, vas-y expliques moi le concept de matrice mal ou bien conditionné.

preuve que tu ne lis pas les messages !
j'ai donné un système pas compliqué ici : https://dlz9.forumactif.com/t1034-resolution-de-systemes-lineaires#14635
et indiquer qu'une petite variation numérique sur le 1 en bas à droite entraîne des variations jusqu'à 13122 fois plus importantes sur les x_i solutions.

A toi de faire le calcul en machine (le système est déjà résolu pour ainsi dire)
pour comprendre l'effet d'un mauvais conditionnement (dont la définition n'est pas du niveau collège en 3 lignes).

Dattier a écrit:

Dattier a écrit:@Fun : OK, vas-y expliques moi le concept de matrice mal ou bien conditionné.

Fais comme, si j'avais le niveau 3ème (niveau que vous estimez pour Dlzlogic).

Je t'écoute.

Dattier, ou comment taper du pied comme un enfant impatient !

Tu permets que je réponde à Dlzlogic ? ...ou pas ??

Allez, tu ferais mieux d'aller jouer avec ta voiture.

funfumfunfun a écrit:Imagine un peu qu'on peut avoir des systèmes linéaires ayant des bonnes propriétés (comme la symétrie par exemple, ou autres).

D'ailleurs pour A.X = B, la méthode des moindres carrés appliquée à une matrice A rectangulaire avec davantage de lignes que de colonnes, aboutit finalement à un système linéaire symétrique qui est :  C.X = transposée(A).B où  C est la matrice carrée transposée(A).A

c'est ce que j'ai indiqué sur mon exemple :

funfumfunfun a écrit:une petite variation numérique sur le 1 en bas à droite entraîne des variations jusqu'à 13122 fois plus importantes sur les x_i solutions.

mais aussi

funfumfunfun a écrit: conditionnement (dont la définition n'est pas du niveau collège en 3 lignes).

On peut parler de modification des coefficients du second membre, mais aussi des coefficients de la matrice.

@ Fun
Voila la copie de la question posée.

Bonjour,
J'ai programmé deux codes matlab pour résoudre un système linéaire par la méthode de Gauss. L'une est sans pivotage l'autre avec pivotage partiel. J'ai remarqué que les solutions calculées par la méthode à pivotage partiel sont plus stables numériquement que celle calculées sans pivotage, ceci est naturel. J'ai essayé avec avec une matrice de Pascal de taille 20 mais cette fois ce n'est pas le même phénomène. Bref, j'ai voulu savoir s'il y a des cas où la méthode de Gauss à pivots partiel ou total donne des solutions pires que celles données par la méthode de Gauss sans pivots. Merci d'avance pour votre aide.
Bien cordialement,
Walid

Il n'est en aucun cas de problème de conditionnement dans le question, mais justement, la discussion a très vite dévié, c'est en quelle que sort le but de ce fil.
La résolution d'un système linéaire est un sujet simple, mais il s'avère que très vite on s'embarque dans des situations tout à fait particulières. Sauf le plaisir de contredire systématiquement et de compliquer les choses par plaisir, je ne comprends l'intérêt de cette démarche.

Dlzlogic a écrit:La résolution d'un système linéaire est un sujet simple, mais il s'avère que très vite on s'embarque dans des situations tout à fait particulières.

Se poser la question de résoudre un système linéaire est simple, oui,
mais sa résolution peut être bien plus compliquée qu'il n'y a parait au premier abord.
Surtout si on y ajoute des considérations de vitesse de calcul, de stabilité de la méthode, etc.

Dlzlogic a écrit: je ne comprends l'intérêt de cette démarche.

c'est que tu n'as pas été confronté à des types de systèmes linéaires particuliers (avec des propriétés particulières, bonnes ou mauvaises).

Dlzlogic a écrit:@ Fun
Voila la copie de la question posée.

Bonjour,
J'ai programmé deux codes matlab pour résoudre un système linéaire par la méthode de Gauss. L'une est sans pivotage l'autre avec pivotage partiel. J'ai remarqué que les solutions calculées par la méthode à pivotage partiel sont plus stables numériquement que celle calculées sans pivotage, ceci est naturel. J'ai essayé avec avec une matrice de Pascal de taille 20 mais cette fois ce n'est pas le même phénomène. Bref, j'ai voulu savoir s'il y a des cas où la méthode de Gauss à pivots partiel ou total donne des solutions pires que celles données par la méthode de Gauss sans pivots. Merci d'avance pour votre aide.
Bien cordialement,
Walid

Il n'est en aucun cas de problème de conditionnement dans le question,

Les matrices de Pascal (de déterminant 1) sont mal conditionnées... Donc le demandeur est bien dans ce cas particulier !

Je ce comprends pas cette phrase :

Fun a écrit:D'ailleurs pour A.X = B, la méthode des moindres carrés appliquée à une matrice A rectangulaire avec davantage de lignes que de colonnes, aboutit finalement à un système linéaire symétrique qui est : C.X = transposée(A).B où C est la matrice carrée transposée(A).A

La notation A.X = B est la notation matricielle d'un système linéaire.
L'application de la méthode des moindres carrés aboutit à un système linéaire (en général) mais cela ne veut rien dire "la méthode des moindres carrés appliquée à une matrice ...". Une matrice est un tableau n * p qui sont les coefficients d'une application linéaire. Les données nécessaires lorsqu'on utilise la méthode des moindres carrés sont souvent représentées sous forme de tableau(x) rien à voir avec la notion de matrice.
J'ai souvent répété que le terme "matrice" était utilisé à tort lorsqu'il s'agissait d'un tableau et il me semble que c'est là un cas qui le justifie.
Mais il est vrai que l'on peut utiliser des outils de calcul matriciel pour faire d'autres choses.

En réponse à Dattier :

@ Fun,
Oui, il a essayé avec une matrice de Pascal, il aurait pu aussi essayer avec des fléchettes.

Dlzlogic a écrit:Je ce comprends pas cette phrase :

Fun a écrit:D'ailleurs pour A.X = B, la méthode des moindres carrés appliquée à une matrice A rectangulaire avec davantage de lignes que de colonnes, aboutit finalement à un système linéaire symétrique qui est :  C.X = transposée(A).B où  C est la matrice carrée transposée(A).A

ok, je vais expliquer sur un petit exemple :
x+y = 1
2x+y = 1
2x+2y = 1

système que l'on code par M.X = B


Système sans solution exacte.
On se pose la question d'avoir la meilleure solution au sens des moindres carrée, à savoir trouver x,y tels que

soit de norme euclidienne  (y+x-1)² + (y+2x-1)² + (2y+2x-1)²   minimale.

Cela peut se résoudre en multipliant chaque membre par la transposée de M


ce qui donne :


Là, on obtient un système carré symétrique, qui ne possède qu'une seule solution :

@ Fun,
Moi, je pose la question autrement : comment a-t-on pu faire pour obtenir ce système de 3 équations à deux inconnues ?
Je ne suis pas sûr que ce soient les meilleures valeurs pour x et y. C'est possible, mais il faudrait le prouver, au moins le vérifier.

@ Dattier,
Non, ce n'est pas du mauvais esprit.
Si on doit résoudre un système, c'est qu'on l'a posé. Donc, ça commence par là.
Je veux bien croire que le calcul matriciel permette des opérations que la machine résout facilement, mais ce n'est pas le sujet.
Si on cherche les valeurs les plus proches pour x et y, je veux bien admettre que la technique est bonne, mais je n'en suis pas sûr.
Je suis entrain de vérifier. De toute façon on est hors sujet, il n'est pas question de méthode des moindres carrés mais de résolution de systèmes linéaires.

Dlzlogic,
je reprend mon petit exemple M.X = B  :
x+y = 1
2x+y = 1
2x+2y = 1
à résoudre suivant les moindres carrés.

Si tu veux vérifier que la solution obtenue plus haut est la bonne, tu prends (le carré de) la norme euclidienne de M.X-B, à savoir :
(x+y-1)² + (2x+y-1)² + (2x+2y-1)²
que tu connais sous le nom écart-quadratique,
et tu en cherches le minimum, par annulation des dérivées suivant x et y. On obtient alors le système suivant :
                          18 x + 14 y =10
                          14 x + 12 y = 8
qui est le même, à un facteur 2 près, que celui obtenu par multiplication matricielle avec la transposée de M :

(matrice symétrique donc !)

Le solutions sont effectivement x = 2/5 et y = 1/5.

Tu n'avais jamais constaté que le système linéaire à résoudre dans le cadre des moindres carrés était codé par une matrice symétrique ? ben tu vois.

@ Fun,
Tu sais très bien que je ne fais pas de calcul matriciel, mais ça ne m'a pas empêché d'apprendre à mon ordinateur à le faire. Il suffit de savoir lire une doc et l'appliquer.
Ceci dit, je ne comprends pas très bien ton calcul, celui que tu appelles norme matricielle de M.X=B
Si j'ai à résoudre
9x+9y = 9
2x+y = 1
2x+2y = 1
Tu es bien d'accord que c'est le même système que le tiens. Je ne suis pas sûr que le résultat soit le même.
Par ailleurs, comme solution, j'ai trouvé x=1/4 ; y=1/2.

Dlzlogic a écrit:Par ailleurs, comme solution, j'ai trouvé x=1/4 ; y=1/2.

Tu t'es trompé quelque part.

avec x := 1/4 ; y := 1/2 ;  on a (x+y-1)² + (2x+y-1)² + (2x+2y-1)² =  5/16

avec x := 2/5 ; y := 1/5 ;  on a (x+y-1)² + (2x+y-1)² + (2x+2y-1)² =  1/5   < 5/16

Dlzlogic a écrit:
Tu sais très bien que je ne fais pas de calcul matriciel, mais ça ne m'a pas empêché d'apprendre à mon ordinateur à le faire. Il suffit de savoir lire une doc et l'appliquer.

et je pense que tu as utilisé un tableau pour y placer les coefficients du système, donc la matrice est là.
Ton traitement en machine de l'algorithme pour résoudre le système linéaire fait du calcul sur les coefficients que l'on pourrait, si on le voulait, interpréter avec des matrices.
Ce n'est là qu'une remarque. Quand je résous à la main un système linéaire, je n'utilise pas les matrices : j'écris simplement les équations, les combine, etc.

Dlzlogic a écrit:
Ceci dit, je ne comprends pas très bien ton calcul, celui que tu appelles norme matricielle de M.X=B
Si j'ai à résoudre  
9x+9y = 9
2x+y = 1
2x+2y = 1
Tu es bien d'accord que c'est le même système que le tiens. Je ne suis pas sûr que le résultat soit le même.

oui, c'est une remarque très importante ! En effet, on ne trouvera pas la même solution au sens des moindres carrés, car on voudra alors minimiser
(9x+9y-9)² + (2x+y-1)² + (2x+2y-1)²
ce qui n''est pas la même fonction en x,y qu'au premier système.

Comme tu dis, les deux systèmes sont équivalents, car on passe de l'un à l'autre avec ce facteur 9.
Deux systèmes sont dit équivalents lorsqu'ils ont les mêmes solutions "exactes".
Or là, tous les deux systèmes n'ont aucune solution "exactes", il n'y a donc pas de souci logique.

En revanche, quand on cherche une solution "suivant les moindres carrés", il y a un souci de "poids" : le 9 par exemple.
Ta remarque peut se faire pour tous les systèmes linéaires que l'on cherche à résoudre au sens des moindres carrés.
C'est un problème important que l'on rencontre fréquemment avec les moindres carrés :
pour que la solution au sens des moindres carrées est un sens, il faut que les données aient le même "poids" :
il faut "normaliser" les équations, et cela dépend du contexte par lequel on obtient le système linéaire.

Par exemple, quand on cherche à "fitter" suivant une fonction y = f(x) , on normalise classiquement les équations
en prenant un coefficient 1 pour les y_i , on obtient alors y_i - f(x_i) = 0 pour tout i=1..n, et on résout le système.

En mesures physiques, quand on utilise plusieurs instruments de mesure,
on normalise en divisant chaque équation par l'écart-type de l'outils de mesure par lequel  elle a été obtenue (afin de ne pas privilégier l'outils le moins précis qui donne des résultats les plus fluctuants)

Oui, Fun, tu as parfaitement raison.
Dattier m'a recommandé, avec raison, de ne pas faire de mauvais esprit. cela n'a jamais été le cas.
Pour ton infirmation, j'ai dessiné les trois droites correspondant aux trois équations, à mon avis, sans doute possible, c'est la solution la meilleure que j'ai trouvée.
Pour plus de détaisl, c'est une méthode de calcul très utilisée en topométrie, lorsqu'il s'agit de trouver le meilleur point. Je n'ai rien inventé, j'ai juste appliqué mon cours.

Pour ton infirmation, j'ai dessiné les trois droites correspondant aux trois équations, à mon avis, sans doute possible, c'est la solution la meilleure que j'ai trouvée.

Donc c'est "la meilleure" parce que tu l'as décrété, et que dans ton monde c'est comme tu veux.

Mais en maths on donne une définition, un critère, précis. Ici on parlait de la somme des carrés des écarts entre le membre de gauche et le membre de droite.
Et avec cette définition de moindre carré (qui est généralement ce que tu présentes comme la seule approche possible) la solution (2/5,1/5), sans le moindre doute possible.

Peut être que (1/4,1/2) fait mieux selon un autre critère, encore faut-il le définir, et ne pas se contenter d'affirmer "c'est mieux", ou "c'est un meilleur point".

Bonjour Fun,
Je n'ai toujours pas compris ce que viennent faire les moindres carrés dans cette histoire de système linéaire, ni de norme matricielle, mais c'est pas grave.