[C++] Résolution d'un systême d'équation

Recherche :

Dernière réponse
Sujet : [C++] Résolution d'un systême d'équation
BENB	Le systeme est quand meme particulier puisque le vecteur solution est nul. Le coditionnenement est un probleme c'est vrai. Dans beaucoup de Pb de ce genre la matrice est creuse, a diagonale dominante, et n grand (>1000). Le conditionement est bon mais le Pivot de Gauss est inaplicable les erreurs d'arondis s'ajoutants les unes aux autres. Le principe c'est alors de rearranger la matrice (deplacer les lignes pour s'assurer qu'elle est a diagonale dominante, si elle est creuse ce n'est en general pas un pb) puis resoudre par un systeme iteratif supposer un X de depard puis calculer x(i) a l'aide de l'equation i, et des valeurs de X jusqu'a ce que les valeurs de X ne varient plus. Si l'estimation initiale de X est bonne c'est tres rapide.

Dernière réponse

Sujet : [C++] Résolution d'un systême d'équation

BENB

Le systeme est quand meme particulier puisque le vecteur solution est nul.

Le coditionnenement est un probleme c'est vrai.
Dans beaucoup de Pb de ce genre la matrice est creuse, a diagonale dominante, et n grand (>1000). Le conditionement est bon mais le Pivot de Gauss est inaplicable les erreurs d'arondis s'ajoutants les unes aux autres.

Le principe c'est alors de rearranger la matrice (deplacer les lignes pour s'assurer qu'elle est a diagonale dominante, si elle est creuse ce n'est en general pas un pb) puis resoudre par un systeme iteratif supposer un X de depard puis calculer x(i) a l'aide de l'equation i, et des valeurs de X jusqu'a ce que les valeurs de X ne varient plus.

Si l'estimation initiale de X est bonne c'est tres rapide.

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

BENB

janoscoder

remarque à la con:
une matrice prise au pif à de fortes chances d'être inversible

sinon je sais qu'il existe des méthodes de conditionnement de matrices où l'on mesure la capacité de faire un pivot de gauss sans pourrir la matrice. on transforme M en M'*M" bien condirionnées et on les inverse toutes les deux.
Je pense qu'une recherche sur conditionnement peut aider

gilou

Krueger a écrit a écrit :

Salut,

J'ai un sytême de type:
a11 * x1 + ... + a1n * xn = 0
.
.
.
an1 * x1 + ... + ann * xn = 0

Les inconnues sont x1, ... , xn

Comment le résoudre efficacement?

Merci d'avance

--Message édité par Krueger--

Lis qques bouquins d'analyse numerique.
A+,

BENB

zeltron a écrit a écrit :

Il aurait plutot fallu dire une solution triviale est x1 = ... = xi= ...=xn=0.
Sauf hypothese tres forte sur les coefficients (a)ij (la matrice (a)ij doit etre inversible )cette solution est loin d'etre unique.

Je reconnais, mais tout ce que je propose repose sur l'impothese que la matrice est inversible, et que donc il y a une et une seule solution.
Si la matrice n'est pas inversible il y a aucune ou une infinite de solutions. Dans notre cas il y en a au moins une (0,0,...0).

Resoudre dans ce cas (matrice non inversible) reviens a dire que on va rechercher une relation entre les xn...

Le pivot de Gauss est alors une solution...

Krueger

C'est justement pour en trouver une solution non nulle. En fait je voulais trouver le noyau de l'application de matrice M = (aij) =
/a11 ... an1\
| . . |
\a1n ... ann/

Sinon j'ai retrouvé le topic dont vous me parliez. Merci du conseil.

--Message édité par Krueger--

zeltron

BENB a écrit a écrit :

La solution est triviale : x1 = ... = xi= ...=xn=0

Il aurait plutot fallu dire une solution triviale est x1 = ... = xi= ...=xn=0.
Sauf hypothese tres forte sur les coefficients (a)ij (la matrice (a)ij doit etre inversible )cette solution est loin d'etre unique.

Krueger

Ok merci. Pour le pivot de Gauss je le savais déjà (théorique), mais je pensais que ça serait trop brutal de l'implémenter comme ça.

BENB

A propos du Pivot de Gauss : c'est effectivement une methode, mais autant chasser le tigre a la petite culliere...

Pour un syteme AX=B (matriciel)

1) Systemes de de petite taille n connu :
resoudre a la main combinaison / substitution ou Cramer

2) Systemes de petite taille n inconnu
eventuellement Gauss ou derive, mais il y a les factorisation LR etc

3) Systemes de grande taille
Gauss ne marche plus (trop long et resultat faux) car les arrondis deviennent trop importants. Il faut utiliser des algo iteratifs. Tu suppose un vecteur X solution puis tu evalues AX(1) et tu as X(2)=f(AX(1)-B)...

Attention ces problemes ont generalement des particularites (matrice creuse, diagonale dominante, etc) qui permettent d'eviter le Pivot de Gauss qui est la pire (la plus lente) des methodes.

Attention Le Pivot de Gauss a la reputation de marcher quelque soit la matrice : c'est faux quand la matrice est trop grande le resultat est faux !

BENB

BENB	La solution est triviale : x1 = ... = xi= ...=xn=0

Gertom

Pivot de Gauss. Fait une recherche dans le forum, il y a quelques mois, y'avait un très bon topic là-dessus.

Krueger

Salut,

J'ai un sytême de type:
a11 * x1 + ... + a1n * xn = 0
.
.
.
an1 * x1 + ... + ann * xn = 0

Les inconnues sont x1, ... , xn

Comment le résoudre efficacement?

Merci d'avance

--Message édité par Krueger--