Mathématiques - algorithme de résolution des systèmes linéaires ..

algorithme de résolution des systèmes linéaires ..
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: sandrine_guillerme

Bonjour tout le monde,

(j'ai pas sommeil)
j'ai décidé d'ouvrir un livre d'algèbre linéaire, et me voilà devant un sujet très intéréssant comme le titre le montre, il s'agit d'une méthode (directe?) qui s'appele procédé d'élimination de Gauss !(tiens Gauss partout on le voit!)

bref tout ce que j'ai compris sur cette méthode c'est qu'elle est d'abord général et consiste pour une matrice inversible à déterminer une matrice M telle que MA soit triangulaire supérieur, on doit donc résoudre le problème linéaire suivant

MAX=MF de façon très rapide par la méthode de remontée.

donc, j'ai besoin de quelques lecteurs afin de m'eéclaircir des choses à propos parceque malheuresueement le bouquin que j'ai l'a zappe sur beaucoup trop de chose, et tout .. donc voici mes première question,
y a t il des gens qui aime découvrir de nouvelles méthode ? elle est briallante et élégante je vous assure, tenez d'abord au courant,

Cordialement.

http://img185.imageshack.us/img185/3690/smile56ab8.gif

Posted by: Joker62

C'est le pivot de Gauss non ???
On effectue des opérations sur les lignes/colonnes pour faire apparaître des 0 dans le triangle inférieur.

Et donc on peut résoudre en remontant comme tu dis rien de bien compliqué si c'est de ça dont tu parles évidemment.

Posted by: sandrine_guillerme

Salut !

je ne sais pas si c'est bien le pivot de Gauss, en tout cas je connais pas bien cette méthode, mais bon on verra si c'est bien ça! elle me permettra de mieux comprendre de quoi il s'agit !

pourquoi doit on avoir une matrice A inversible ?

en fait il dit que si B = MA a la forme suivante

$\Large \rm B= \begin{pmatrix} B{1,1} & B_{1,2} & B_{1,3} & ... & ... & ... & B_{1,n} \\ 0 & B_{2,2} & B_{2,3} & ... & ... & .... & B_{2,n} \\ 0 & ... & B_{3,3} & ... & ... & ... & B_{3,n} \\ ... & ... & ... & ... & ...& ...\\ 0 & ... & ... & ... & .... & .... & B_{n,n}\end{pmatrix}$

en fait y a $\Large \rm B_{i,i}$ sur la diagonale et c'est une matrice triangulaire supérieur .

Il dit que la la solution $\Large \rm BX =G$ s'obtient très facilement

$\rm \Large X_n = \frac{G_n}{B_{n,n}$
$\rm \Large X_{n-1} = \frac{G_{n-1} - B_{n-1,n}X_n}{B_{n-1,n-1}}$
.
.
.
$\rm \Large X_1 = \frac{G_1 - B_{1,2}X_2 - ... - B_{1,n}X_n}{B_{1,1}}$

Vous en pensez quoi ? pourquoi A doit être inversible et si vous aurrez un exemple moi je ne suis pas très familiarisée avec ce genre de choses...

Merci bien d'avance !

Posted by: serge75

C'est le pivot de gauss, sandrine, mais écrit sous forme matricielle.

Posted by: sandrine_guillerme

Bonjour serge
oki .. tu n'aurais pas un lien ou je pourrais trouver mon bonheure ?
sinon si ça ne te dérange pas peut on en discuter ici , parceque tout ça n'est que le début !

Posted by: allomomo

Salut,

C'est le pivot de Gauss, en effet, c'est assez simple de résoudre des système avec cette méthode ... en écrivant la matrice associée à ce système + la matrice augmentée. Et par suite, on fabrique une matrice triangulaire supérieur ... et voila .

Exemple extrait d'ici : mot clès : algèbre.

http://img221.imageshack.us/img221/8149/pivotpm5.gif

Posted by: sandrine_guillerme

Salut

Oui, je vois, il me semble que ce sont les notations qu'ils l'ont rendu lègèrement compliqué a comprendre, mais je vais essayer de voir ceci de plus prêt ..

Merci bien ..

Posted by: fahr451

bonsoir

à noter que le pivot permet également de résoudre un système qui n'est pas de cramer
> matrice échelonnée
> relations de compatibilité
> inconnues principales et secondaires

Posted by: sandrine_guillerme

Merci allomomo pour l'exoemple !! je l'avais pas vu !

et fahr merci toi !

et au fait tu n'aurrais pas des exemples stp ?
pour

> matrice échelonnée
> relations de compatibilité
> inconnues principales et secondaires

j'ai lu aussi que le pivot sert à la factorisation d'une matrice ??

vous connaissez ?

Merci encore !

Posted by: sandrine_guillerme

en attendant une réponse de fahr je poursuis donc ce qui est dis avant ..
l'auteur dit :

Revenons à la procèdure d'élimination. Nous allons calculer directement la matrice MA et le vecteur MF, par réccurence. pour celà on multiplie surccessivement la matrice A par certaines matrices pour obtenir une matrice triangulaire supérieure, au bout de n-1 étape. Nous notons A^1 = A. Puisque A est inversible, la première colonne de A contient au moins un élèment non nul à savoir $\rm A^1_{i,1}$ .(je comprends maintenant pourquoi exige t'on l'inversibilité de A,

L'élèment non nul choisi est appelé le premier oivot de l'élimination et on échange la ligne i avec la première ligne, en multipliant par la matrice de transposition $\rm T_{1,i}$ .
Notons $\rm P^1=T_{1,i}$ si le pivot choisi esti. cette opération permet de se ramener à une nouvelle matrice $\rm P^1A^1$ dont le terme à l'intersection de la première ligne et de la première colonne est non nul.

Jusque là très bien !

Nous sommes aisi amenés à résoudre $\rm P^1A^1X = P^1F$ là je ne suis pas sure de ce que j'ai compris, mais set ce tout simplement parceque l'on veut faire des permutations ?.

Notons $\rm (\alpha^1_{i,j)1 \le i,j \le n}$ les termes de la matrice $\rm P^1A^1$
Nous allons maintenant multiplier la matrice $\rm P^1A^1$ par la matrice $\rm E^1$ (c'est une matrice élémentaire ?) mais pourquoi veut on le faire ?)

Voici xomment définit il la matrice $\rm \E^1$

$\rm E^1= \begin{pmatrix} 1 & 0 & ... & ... & ... & ... & 0 \\ - \rm \frac{\alpha^1_{2,1}}{ \alpha^1_{1,1}} & 1 & ... & ... & ... & .... & ... \\ ... & ... & ... & ... & ... & ... & ... \\ ... & ... & ... & ... & ...& ... & 0 \\ -\rm \frac{ \alpha^1_{n,1}}{ \alpha^1_{1,1}} & ... & ... & ... & .... & .... & 1\end{pmatrix}$

Qui est choisie de sorte que la matrice $\rm A^2 = E^1P^1A^1$ soit de la forme suivante

ATTENTION: A^2 c'est ne pas le carré de A, mais le seco,d élèment d'une suite $\rm A^k$

$\rm A^1= \begin{pmatrix} A^1_{1,1} & A^1_{12} & ... & ... & ... & ... & A^1_{1n} \\ 0 & A^2_{22} & ... & ... & ... & .... & A^2_{2n} \\ ... & ... & ... & ... & ... & ... & ... \\ ... & ... & ... & ... & ...& ... & 0 \\ ... & ... & ... & ... & .... & .... & A^2_{nn}\end{pmatrix}$

Voici ma question synthèse, pourquoi tout se mécanisme, pourquoi se casse t on les pied alors que c'est censé être une méthode directe ? je vous prie ausi de ne pas oublier les question en rouge ...

et merci bien

Posted by: sandrine_guillerme

je tente de remonter ce fil, voire s'il y a quelqu'un qui est intéréssé ?

Posted by: fahr451

bonjour
je ne suis pas certain de comprendre ta question

ce que tu cites c'est la justification de la méthode :
l e fait que toute opération revient à multiplier par une matrice inversible il précise laquelle à chaque fois

Posted by: sandrine_guillerme

Je vois,

ce choix n'est pas arbitraire bien sûr parcequ'il dis " de façon à avoir .."
ces matrices portent t il un nom spécial ... ? matrice élémentaire non ?

et puis y avait une question avant stp .. cf . post hier à 23h25 .

Posted by: fahr451

matrice d'opération élémentaire st souvent le nom utilisé

"factorisation" oui le pivot permet d'avoir la factorisation LU par exemple

lower x upper

Posted by: sandrine_guillerme

Oki très bien .. !

Merci fahr ,

je revienderais si besoin :)

Posted by: sandrine_guillerme

Et c'est quoi donc ce lower x upper stp ? pourquoi faire?

Posted by: fahr451

A inversible

A = LU , L matrice triangulaire inférieure U triangulaire sup

tape sur google (pas trop fort ça fait mal) les applications sont multiples

une seule :

à résoudre A X = y avec de nombreux Y différents

au lieu de faire à chaque fois le pivot sur la matrice complète (avec le second membre) on résoud LU X =Y ainsi

d'abord LZ = Y puis UX = Z qui sont deux systèmes en cascade très rapides àrésoudre

Posted by: sandrine_guillerme

ok fahr,

Je vais regarder ce soir, comme d'hab ..

Merci bien .

Posted by: Rain'

Citation:

Posté par sandrine_guillerme

procédé d'élimination de Gauss !(tiens Gauss partout on le voit!)

Comme disait mon prof de maths en sup.

Là où Gauss à laissé son nom, c'est que c'est important.

Posted by: Flodelarab

Oui oui. On reconnait bien le pivot de Gauss.
A noter que parler du gosse de Pivot aurait suscité moins de réponses, aussi fort en dictée soit-il.

Citation:

Voici ma question synthèse, pourquoi tout se mécanisme, pourquoi se casse t on les pied alors que c'est censé être une méthode directe ?

Tu vois une méthode plus directe pour résoudre n équations à n inconnues ? (savoir s'il y a des solutions et les trouver)

Posted by: sandrine_guillerme

Citation:

Posté par Flodelarab

Tu vois une méthode plus directe pour résoudre n équations à n inconnues ? (savoir s'il y a des solutions et les trouver)

En fait je ne pensais pas du tout au méthodes directes mais aux méthodes itératives, mais là je suis d'accord que ça va vraiment rapide,

seulement que j'ai tout de même quelques question ..

l'auteur dit :

(...)
Notons que la liberté de pivoter des lignes et des colonnes peut s'avèrer préciseuse même si, en appliquant la méthode de Gauss sans élimination, aucun élèment $\rm \alpha_{k,k}^k$ n'est nul. il peut en effet arriver que l'un de ces élèments soit très petit et des erreurs d'arrondis risquent alors de dégrader la solution . deux stratègies sont courament utilisées.
pivot partiel
pivot total

ce que j'ai cru comprendre c'est que dans le pivot partiel on prend le max des élèments en colonne,
et le pivot total on prend le max de ce qu'il y a en ligne et en colonnes

et bien entendu les élèments pris on les considère comme des pivots qui annuleront les élèments ..

Alors si j'ai bon, aurriez vous des exemples concrèts d'élèments qui peuvent perturber la solution ?
je pensais qu'avec la méthode directe et A inversible on a une solution unique contrairement aux méthodes itératives qui donnes des valeurs approchés convergeant vers la solution ...

Merci pour votre aide ...

Posted by: buzard

Citation:

Posté par sandrine_guillerme

Alors si j'ai bon, aurriez vous des exemples concrèts d'élèments qui peuvent perturber la solution ?

l'exemple type c'est le calcul d'inverse d'une matrice très mal conditionné, alors dans ce cas on est presque sûre d'avoir des erreurs d'arrondis qui vont influer sur l'exactitude du résultat (il y aura des grands nombres qui seront vraiment très grand par rapport à des nombres très petits)

ceci est à mettre en relation avec l'utilisation pratique du pivot de gauss, qui est une méthode algorithmique utilisé avec une machine. C'est pourquoi la sensibilité aux erreurs d'arrondis est un facteur important.

Posted by: sandrine_guillerme

Citation:

Posté par buzard

l'exemple type c'est le calcul d'inverse d'une matrice très mal conditionné

J'aimerais un exemple concret stp .. une matrice par exemple..

Je présume que cet exemple résume ce que tu a dis ..

(0.001,0.0002,0.2)
(0.002,0.005,0.3)
(0.2,0.5,0.6)

matrice 3*3 , je suppose que là il serait prèférable pour éviter les erreurs d'arrondi de prendre l'élèment le plus grand, dans la première colonne, à savoir 0.2 ou bien le plus grand de tout 0.6 .. et le considèrer comme un pivot ..

Correct?

Posted by: buzard

Citation:

Posté par sandrine_guillerme

matrice 3*3 , je suppose que là il serait prèférable pour éviter les erreurs d'arrondi de prendre l'élèment le plus grand, dans la première colonne, à savoir 0.2 ou bien le plus grand de tout 0.6 .. et le considèrer comme un pivot ..

Correct?

Oui et non, en faite la condition d'une matrice est indépendante de la base choisi pour la représenté. C'est-à-dire que cela à plutôt avoir avec les valeurs et espaces propre de la matrice (ou de son endomorphisme associée)

la condition d'une matrice c'est le rapport de la valeur absolue de sa plus grande valeur propre sur la plus petite :

$\displaystyle r=\frac{\left|\lambda_n^*\right|}{\left|\lambda_1^ *\right|}$

lorsque la condition et très grande cela signifie que l'endomorphisme associé est plus proche d'une projection. en gros il favorise certaine direction (lambda grand)

exemple : une matrice qui ressemble beaucoup à une projection

$\lambda={10}^{18} \\ \mu={10}^{-18} \\ M = \begin{pmatrix} \lambda & 0 \\ 0 & \mu \end{pmatrix}$

représenté dans une base propre on peut toujours faire les calculs, mais essaye d'appliquer le pivot de gauss sur la même matrice dans une autre base.

$M' = R_{-\theta} M R_{\theta}$

tu vera vite que le 10^-18 est assez vite oublié rendant du même coup la matrice non inversible.

Posted by: sandrine_guillerme

Je comprends largement mieux là ..

Merci beaucoup buzard,

pour l'info, c'est un très bon bouquin de Masson

là en fait , l'auteur donne une proposition que je ne comprends pas vraiment,

il dit qu'elle est vraiment importante,

Notons que le procèdé d'élimination de Gauss "remplit" la matrice : certains termes qui étaient égaux à zéro dans la matrice initiale ne restent pas nécéssairement nuls au cours de l'élimination. (là c'est Ok)

Nous notons cependant une propriété très importante du procèdé délimination de GAuss: étant donné une matrice A, nous définissons la largeur du profil de A comme l'entier m tel que :

$\Large \rm A_{i,j} = 0 si |i - j| \ge m$

je comprends pas vraiment au fait,
sur un exemple
je vois bien pour une matrice diagoanel la largeur de profil égal à 1 ..

Je crois comprendre, d'après la définition d'une matrice diagonale le terme est non nul si i différent de j donc i-j différent de 0 c'est même positif.. (j'ai pas dis des bêtises ? je crois bien que si ..

Merci bien ...

Posted by: sandrine_guillerme

Bonjour je tente de remonter ce fil ..

Aurriez vous une idée je vous prie ?

Merci

Posted by: Rain'

D'après ce que j'ai compris de la définition que tu as donné de m.

m = max {|i-j| | $a_{ij}\not= 0$ }

Ainsi pour donner des exemples en 3*3

(A,B,C)
(D,E,F)
(G,H,I)

On a différents styles de diagonales.

La diagonale rouge composée de G et C

La diagonale verte composé de D, H , B et F

et la diagonale orange composée de A,E,I.

Dans le cas d'une matrice 3*3,
m=3 <=> l'un des termes rouge est non nul.
m=2 <=> les termes rouges sont nuls, l'un des vert ne l'est pas
m=1 <=> les termes rouges et verts sont nuls, l'un des termes orange ne l'est pas. (Autrement dit la matrice est diagonale).
m=0 <=> Tous les termes sont nuls.

Dans le cas d'une matrice A (n*n) , même principe et on a clairement les équivalences suivantes :
m=0 <=> A=0
m=1 <=> A diagonale.

Voilà d'après ta définition, il me semble que c'est ça. En espérant t'avoir aidé.

Posted by: sandrine_guillerme

Eh bien , faut crois que les garçons sont plus intélligent que les filles

Merci Rain'

Posted by: Rain'

lol mais non, pas toujours

.

De rien. J'espère que c'est ça et que je ne t'ai pas envoyé sur une fausse piste.

Posted by: sandrine_guillerme

Bonjour,

En poursuivant la lecture l'auteur donne la conclusion suivante :

On dit que le procèdé d'élimination de Gauss remplit le profil de la matrice A .
Ainsi pour une matrice creuse A, la matrice triangulaire finalement obtenue contiendera beaucoup de zéros pourvu que le profil de la matrice initiale soit assez petit. Or le profil dépend directement de la numérotation des degrés de liberté (ou des différents composants de X ) . On aura donc intérêt à choisir une numérotation de ces degrés de liberté de sorte à savoir le profil le plus petit possible et ainsi économiser de la place en mémoire. Les logiciels d'élèments finis comprennent tous une procèdure déstinée à limiter le plus possible le profil de la matrice de rigidité : Une fois la première numérotation effectuée, un algorithme de renumérotation effectuée permet de réduire le profil . Les résultats peuvent être spectaculaire.

J'y pas compris grand choses non plus là ..

Posted by: Rain'

Juste une idée qui me passe par la tête.

Par exemple si ta matrice est :

(0,0,3)
(0,2,0)
(0,0,0) le profil vaudrait 3

Tandis que si tu bouges juste les colonnes comme ceci :

(3,0,0)
(0,2,0)
(0,0,0) le profil passe à 1 ce qui ne modifie pas le système car

(0,0,3) (x)
(0,2,0) (y)
(0,0,0) (z) =

(3,0,0) (z)
(0,2,0) (y)
(0,0,0) (x)

donc tu as le même système à résoudre mais tu as réduis le profil ce qui simplifies la matrice triangulaire obtenue finalement.

Je suis clair ?

Posted by: sandrine_guillerme

Et gentil aussi .. !

Merci

Posted by: Rain'

En fait en optimisant la permutation des colonnes , tu simplifies la résolution.

Je serais pas contre une confirmation quand même.

Posted by: sandrine_guillerme

Bonsoir,

allez chers compatriotes

un peu de maths,

Citation:

Posté par buzard

ici j'ai essayé d'appliquer le pivot de Gauss sur la même matrice dans une autre base, mais j'arrive pas à la conclusion souhaitée ..

Un volontaire pour m'aider je vous pris ?

Merci ..