Résolution système linéaire

par **Benjamin** » 22 Oct 2012, 15:51

Salut,

Une problématique m'occupe pour laquelle je n'arrive pas à trouver la solution.

Tout part du problème de trouver les caractéristiques d'un cercle (centre et rayon) à partir des coordonnées de 3 points.

De (xi-x0)²+(yi-y0)²=r² avec i de 1 à 3, on voit que le système d'équation est équivalent à

xi * (-2x0) + yi * (-2y0) + 1 * (x0²+y0²-r²) = -(xi²+yi²)

ce qui revient à résoudre le système d'inconnu -2x0, -2y0 et x0²+y0²-r².

Jusque là, pas de problèmes.

Maintenant, au lieu d'avoir un cercle, j'ai en fait un super-cercle avec des puissances au cube. Et là, c'est le drame car je n'arrive pas à construire un système linéaire avec une matrice carré.

J'aboutie à

xi² * (-3x0) + yi² * (-3y0) + xi * (3x0²) + yi * (3y0²) + -1 * (x0^3+y0^3+r²) = -(xi^3+yi^3)

Au lieu d'avoir une matrice (3x3), j'ai donc une matrice (3x5) avec comme inconnues -3x0, -3y0, 3x0², 3y0² et x0^3+y0^3+r² (qui ne sont plus indépendantes les unes des autres d'ailleurs).

Or, j'ai pu voir que le rang de cette matrice (3x5) est 3 (si les 3 points ne sont pas alignés bien sûr), et qu'il y a donc bien a priori existence et unicité de la solution (est-ce que j'ai bon jusque là ?).

Ma question est donc comment passer de cette matrice 5x3 à une matrice 3x3 et quelles sont alors les nouvelles inconnues ?

Merci.

par **cuati** » 22 Oct 2012, 16:09

Bonjour,
ton second système n'est pas linéaire, donc l'histoire du rang 3 (pour avoir un cramer ?) ne tient pas la route..

par **wserdx** » 22 Oct 2012, 16:18

La difficulté est en effet que le système est quadratique. Il existe des méthodes calculatoires dans le cas des corps finis mais qui ne vont pas s'appliquer ici. Dans ton cas, j'utiliserais deux variables auxiliaires

et

Tu devrais ensuite trouver des expressions linéaires

mais ensuite il faut éliminer les variables auxiliaires.

par **DamX** » 22 Oct 2012, 16:20

Juste pour savoir, c'est quoi le contexte ?
Parce que cet objet n'est pas un "super-cercle", il faudrait des valeurs absolues en plus du cube pour avoir une norme et obtenir un objet comparable à un cercle. Avec juste les cubes la figures produites est une courbe non bornée avec y = y0 - (x-x0) comme asymptote en + et - infini.

Et si tu rajoutes les valeurs absolues c'est bien un cercle (pour la norme 3) mais ça complique encore la donne dans ton problème d'identification.

par **Benjamin** » 22 Oct 2012, 16:20

Bonjour,

Merci de ta réponse, cependant je n'arrive pas à voir où le système n'est pas linéaire.

Typiquement, pour le premier cas, si on est pas très "intelligent", on abouti aussi à une matrice (5x3) de rang 3 en considérant

xi * (-2x0) + yi * (-2y0) + 1 * (x0²) + 1 * (y0²) - 1* (r²) = -(xi²+yi²) avec les 5 inconnues -2x0, -2y0, x0², y0² et r². Là, il était facile de regrouper les 3 dernières inconnues en une seule.

Je ne sais pas comment faire (si c'est possible), pour le deuxième cas. Et si ce n'est pas possible, j'aimerais comprendre pourquoi :) (via une CNS par exemple)

par **Benjamin** » 22 Oct 2012, 17:04

DamX a écrit:Juste pour savoir, c'est quoi le contexte ?
Parce que cet objet n'est pas un "super-cercle", il faudrait des valeurs absolues en plus du cube pour avoir une norme et obtenir un objet comparable à un cercle. Avec juste les cubes la figures produites est une courbe non bornée avec y = y0 - (x-x0) comme asymptote en + et - infini.

Et si tu rajoutes les valeurs absolues c'est bien un cercle (pour la norme 3) mais ça complique encore la donne dans ton problème d'identification.

Salut,

Oui, tu as raison en effet. Sans les |.|, ce n'est pas un "super-cercle". Le contexte importe peu dans le cas présent en fait, la question que je soulève étant je pense suffisamment générale (et la réponse plus ou moins adaptable).

Pas d'autres solutions que ce que propose wserdx ?

par **wserdx** » 22 Oct 2012, 17:25

Éventuellement, pourrais-tu avoir 5 points de contacts au lieu de 3 ?
Dans ce cas tu aurais un système sur-déterminé mais plus facile à résoudre car linéarisable.

par **Doraki** » 22 Oct 2012, 18:36

En soustrayant les équations, tu obtiens deux équations de la forme
(xi-xj)[(xi²+xixj+xj²) - 3(xi+xj)x0 + 3x0²] + (yi-yj)[(yi²+yiyj+yj²) - 3(yi+yj)y0 + 3y0²] = 0
C'est l'équation d'une ellipse.
Donc tu traces les deux ellipses que tu obtiens, elles auront 0, 2 ou 4 points d'intersections, et n'importe lequel d'entre eux est le centre d'un super-cercle passant par tes 3 points.

Dans le cas du cercle, tu obtiens deux équations de droite, donc un seul point d'intersection.
Là bah tu peux en avoir jusqu'à 4.

par **Benjamin** » 22 Oct 2012, 23:14

Doraki a écrit:En soustrayant les équations, tu obtiens deux équations de la forme
(xi-xj)[(xi²+xixj+xj²) - 3(xi+xj)x0 + 3x0²] + (yi-yj)[(yi²+yiyj+yj²) - 3(yi+yj)y0 + 3y0²] = 0
C'est l'équation d'une ellipse.
Donc tu traces les deux ellipses que tu obtiens, elles auront 0, 2 ou 4 points d'intersections, et n'importe lequel d'entre eux est le centre d'un super-cercle passant par tes 3 points.

Dans le cas du cercle, tu obtiens deux équations de droite, donc un seul point d'intersection.
Là bah tu peux en avoir jusqu'à 4.

Salut Doraki,

Merci pour ta réponse, je comprends le principe. Donc en fait, 3 points ce n'est pas suffisant pour tout déterminer, contrairement à ce que je pensais.

@wsrdex
Je peux éventuellement avoir 5 points. Comment procéderais-tu alors ?

par **wserdx** » 22 Oct 2012, 23:18

En considérant 5 variables:

et

(ou

?)

par **Benjamin** » 22 Oct 2012, 23:41

Est-ce que c'est possible que je trouve un x0² (deuxième inconnue) différent de x0 au carré, ou x0 est la première inconnu ?

par **Doraki** » 23 Oct 2012, 00:02

C'est possible si tu prends 5 points qui ne sont pas tous sur un même super-cercle.

par **Benjamin** » 23 Oct 2012, 00:07

Ok, ok. Merci à tous.

Résolution système linéaire

Résolution système linéaire

Qui est en ligne