Résolution de systèmes linéaires : Méthodes directes Polytech

Algorithme 1: Algorithme d’élimination de Gauss (L,b) qui résout un système trian-gulaire inférieur Lx = b Tester sur le système 2 4 1 0 0 2 3 0 1 4 1 3

Résolution de systèmes linéaires : Méthodes directes Polytech

À partir d’un système d’équations linéaires quelconques, on triangularise le système, on résout le système triangulaire, pour cela on utilise des permutations de lignes et de colonnes et des combinaisons linéaires de lignes

Systèmes et Algorithmiques Répartis

Une couche service qui résout des problèmes génériques et récurrents dans le domaine de la répartition Modèle de répartition 10 Un système distribué [Tanenbaum 1994] Système Exploitation Réseau Machine A Machine B Machine C Machine (Hardware) Machine (Hardware) Machine (Hardware)

Calcul scienti que en Fortran 90 TP Résolution de systèmes

cet algorithme, les termes non nuls de Lsont dans la partie triangulaire inférieure de M (sauf les 1 sur la diagonale) et ceux de U dans la partie triangulaire supérieure 2 Écrire un programme SysLin , qui construit une matrice Aau pro l dyna-mique (remplie en se basant sur un exemple du cours ou du TD d'analyse 1

Cours CN5 - Résolution dun système déquations algébriques

Résolution d’un système linéaire : pivot de Gauss Existence d’une unique solution : système de Cramer Système de Cramer Dans la suite, on se restreint à un système de Cramer ce qui garantit : I n équations pour n inconnues I Qu’il existe une solution I Que la solution est unique I Qu’on peut toujours trouver un pivot pour

Algorithmes gloutons

Pour cette raison, un tel système de monnaie est qualiﬁé de canonique D’autres systèmes ne sont pas canoniques L’algorithme glouton ne répond alors pas de manière optimale Par exemple, avec le système {1,3,6,12,24,30}, l’algorithme glouton répond en proposant le rendu 49 = 30+12+6+1, soit 4 pièces alors que la

Algorithmes - Programmes - Organigramme

Un algorithme est une suite d'instructions précise et structurée qui décrit la manière dont on résout un problème Cette description est souvent textuelle en utilisant le langage naturel et des mots clés (si, alors, sinon, tant que, jusqu’à ) Exemple : Un robot évitant un obstacle Si le robot détecte un obstacle avec sont capteur

Algorithmes - Programmes - Organigramme Connaissance

1 Convention d’écriture d’un organigramme : L'organigramme obéit à des règles d'écriture normalisées très simples, chaque case de l’organigramme possède une fonction précise : Un algorithme est une suite d'instructions précises et structurées qui décrit la manière dont on résout un problème

UN ALGORITHME DE CALCUL DE STRUCTURE POUR LIDENTIFICATION DE

la structure à un système plastique discret qui peut ensuite être traité par un algorithme approprié qui sera, lui, appliqué de manière répétitive l'approche proposée résout un

Polytech'Paris-UPMC

Propriétés mathématiquesRappels mathématiquesExemplesPropriétésPrincipe général desalgorithmesTriangularisationForme matricielle de latriangularisationConditionsRecherche de pivots maximauxConditionnement

Propriétés mathématiques- p. 2/51

Propriétés mathématiques

Propriétés mathématiques- p. 3/51

Rappels mathématiques

Soit à résoudre le système linéaire

Ax=b.

A?Mn(IR) :matrice carrée de dimensionn×n

x,b?IRn:vecteurs de dimensionn.

Propriétés mathématiques- p. 3/51

Rappels mathématiques

Soit à résoudre le système linéaire

Ax=b.

A?Mn(IR) :matrice carrée de dimensionn×n

x,b?IRn:vecteurs de dimensionn.CNS d'existence de la solution :Le systèmeAx=ba une solution unique si et seulement si son

déterminant est non nul.

Propriétés mathématiques- p. 3/51

Rappels mathématiques

Soit à résoudre le système linéaire

Ax=b.

A?Mn(IR) :matrice carrée de dimensionn×n

x,b?IRn:vecteurs de dimensionn.CNS d'existence de la solution :Le systèmeAx=ba une solution unique si et seulement si son

déterminant est non nul.

Si le déterminant est nul :

?Sib?Im(A)le système a une infinité de solutions ?Sib?IRn-Im(A)le système n'a pas de solution

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

Le déterminant vautD=-18, le système a une solution unique x

1= 1,x2= 1

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

Le déterminant vautD=-18, le système a une solution unique x

1= 1,x2= 1

Exemple 2 :

2x1+ 3x2= 5

4x1+ 6x2= 10

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

Le déterminant vautD=-18, le système a une solution unique x

1= 1,x2= 1

Exemple 2 :

2x1+ 3x2= 5

4x1+ 6x2= 10

Le déterminant vautD= 0, le système a une infinité de solutions : (1,1) +λ×(3,-2),(λ?IR).

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

Le déterminant vautD=-18, le système a une solution unique x

1= 1,x2= 1

Exemple 2 :

2x1+ 3x2= 5

4x1+ 6x2= 10

Le déterminant vautD= 0, le système a une infinité de solutions : (1,1) +λ×(3,-2),(λ?IR).

Exemple 3 :

2x1+ 3x2= 5

4x1+ 6x2= 9

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

Le déterminant vautD=-18, le système a une solution unique x

1= 1,x2= 1

Exemple 2 :

2x1+ 3x2= 5

4x1+ 6x2= 10

Le déterminant vautD= 0, le système a une infinité de solutions : (1,1) +λ×(3,-2),(λ?IR).

Exemple 3 :

2x1+ 3x2= 5

4x1+ 6x2= 9

Le déterminant vautD= 0, le système n'a pas de solution.

Propriétés mathématiques- p. 5/51

Propriétés

On ne change pas la solution d'un système linéaire lorsque :

Propriétés mathématiques- p. 5/51

Propriétés

On ne change pas la solution d'un système linéaire lorsque : on permute deux lignes,

Propriétés mathématiques- p. 5/51

Propriétés

On ne change pas la solution d'un système linéaire lorsque : on permute deux lignes,on permute deux colonnes,

Propriétés mathématiques- p. 5/51

Propriétés

On ne change pas la solution d'un système linéaire lorsque : on permute deux lignes,on permute deux colonnes,on multiplie une ligne par un réel non nul,

Propriétés mathématiques- p. 5/51

Propriétés

On ne change pas la solution d'un système linéaire lorsque : on permute deux lignes,on permute deux colonnes,on multiplie une ligne par un réel non nul, on ajoute une ligne à une autre.

Propriétés mathématiques- p. 5/51

Propriétés

On ne change pas la solution d'un système linéaire lorsque : on permute deux lignes,on permute deux colonnes,on multiplie une ligne par un réel non nul, on ajoute une ligne à une autre. Nous allons donc utiliser ces transformations pour se ramener à un cas simple.

Propriétés mathématiques- p. 5/51

Propriétés

Propriétés mathématiquesPrincipe général desalgorithmesLes matrices triangulairesAlgorithme de remontéeMéthodesMéthodes (suite)Ce qu'il reste à faireTriangularisationForme matricielle de latriangularisationConditionsRecherche de pivots maximauxConditionnement

Principe général des algorithmes- p. 6/51

Principe général des algorithmes

Principe général des algorithmes- p. 7/51

Les matrices triangulaires

Pour certaines matrices, il est simple de calculer une solution.Définition supérieure (respectivement inférieure) si ?i,jt.q.j > i(resp.j > i) a ij= 0 Si A est une matrice triangulaire supérieure, et si aucun élément diagonal n'est nul, la solution du systèmeAx=best : ?x n=bn ann x i=bi-?nj=i+1aijxj aii Si A est une matrice triangulaire inférieure, et si aucun élément diagonal n'est nul, la solution du systèmeAx=best : ?x 1=b1 a11 x i=bi-?i-1 j=1aijxj aii

Principe général des algorithmes- p. 8/51

Algorithme de remontée

Dans le cas des matrices triangulaires supérieures, l'algorithme est donc le suivant. Donn d

´ebut

x[n]←b[n]

A[n,n]

pouri=n-1...1faire sum←0 pourk=i+ 1...nfaire sum←sum+A[i,k]·x[k] x[i]←b[i]-sum

A[i,i]

fin

Principe général des algorithmes- p. 8/51

Algorithme de remontée

Dans le cas des matrices triangulaires supérieures, l'algorithme est donc le suivant. Donn d

´ebut

x[n]←b[n]

A[n,n]

pouri=n-1...1faire sum←0 pourk=i+ 1...nfaire sum←sum+A[i,k]·x[k] x[i]←b[i]-sum

A[i,i]

finÀ partir d'un système d'équations linéaires quelconques,

Principe général des algorithmes- p. 8/51

Algorithme de remontée

Dans le cas des matrices triangulaires supérieures, l'algorithme est donc le suivant. Donn d

´ebut

x[n]←b[n]

A[n,n]

pouri=n-1...1faire sum←0 pourk=i+ 1...nfaire sum←sum+A[i,k]·x[k] x[i]←b[i]-sum

A[i,i]

finÀ partir d'un système d'équations linéaires quelconques,on triangularise le système,

Principe général des algorithmes- p. 8/51

Algorithme de remontée

Dans le cas des matrices triangulaires supérieures, l'algorithme est donc le suivant. Donn d

´ebut

x[n]←b[n]

A[n,n]

pouri=n-1...1faire sum←0 pourk=i+ 1...nfaire sum←sum+A[i,k]·x[k] x[i]←b[i]-sum

A[i,i]

finÀ partir d'un système d'équations linéaires quelconques,on triangularise le système,on résout le système triangulaire,

Principe général des algorithmes- p. 8/51

Algorithme de remontée

Dans le cas des matrices triangulaires supérieures, l'algorithme est donc le suivant. Donn d

´ebut

x[n]←b[n]

A[n,n]

pouri=n-1...1faire sum←0 pourk=i+ 1...nfaire sum←sum+A[i,k]·x[k] x[i]←b[i]-sum

A[i,i]

finÀ partir d'un système d'équations linéaires quelconques,on triangularise le système,on résout le système triangulaire,pour cela on utilise des permutations de lignes et de colonnes et

des combinaisons linéaires de lignes.

Principe général des algorithmes- p. 9/51

Méthodes

Pour résoudre le systèmeAx=b, il faut appliquer les modifications

à la fois à la matriceAet au vecteurb.

Il y a deux cas possibles :

Principe général des algorithmes- p. 9/51

Méthodes

Pour résoudre le systèmeAx=b, il faut appliquer les modifications

à la fois à la matriceAet au vecteurb.

Il y a deux cas possibles :

On souhaite résoudre une seule équationAx=b.

Principe général des algorithmes- p. 9/51

Méthodes

Pour résoudre le systèmeAx=b, il faut appliquer les modifications

à la fois à la matriceAet au vecteurb.

Il y a deux cas possibles :

On souhaite résoudre une seule équationAx=b. On travaille sur la matrice[A b]qui anlignes etn+1colonnes ?C'est l'élimination deGAUSS

Principe général des algorithmes- p. 9/51

Méthodes

Pour résoudre le systèmeAx=b, il faut appliquer les modifications

à la fois à la matriceAet au vecteurb.

Il y a deux cas possibles :

On souhaite résoudre une seule équationAx=b. On travaille sur la matrice[A b]qui anlignes etn+1colonnes ?C'est l'élimination deGAUSS

Pour résoudre le système, il fautUne triangularisation,Une remontée (solution d'un système triangulaire).

Principe général des algorithmes- p. 10/51

Méthodes (suite)

On doit résoudre plusieurs systèmes avec la même matrice

Ax=b1...Ax=bk.

Principe général des algorithmes- p. 10/51

Méthodes (suite)

On doit résoudre plusieurs systèmes avec la même matrice

Ax=b1...Ax=bk.

On décomposeAen produit de deux matrices triangulaires (U est supérieure etLinférieure) :

A=L·U

Principe général des algorithmes- p. 10/51

Méthodes (suite)

On doit résoudre plusieurs systèmes avec la même matrice

Ax=b1...Ax=bk.

Principe général des algorithmes- p. 10/51

Méthodes (suite)

On doit résoudre plusieurs systèmes avec la même matrice

Ax=b1...Ax=bk.

On décomposeAen produit de deux matrices triangulaires (U est supérieure etLinférieure) : A=L·UUne résolution se fait grâce à deux systèmes triangulaires Ax k=bk?? Ly k=bk Ux k=yk ?C'est la décomposition LU Il faut une triangularisation pour " préparer » la matrice et deux remontées par vecteurbk.

Principe général des algorithmes- p. 11/51

Ce qu'il reste à faire

Comment triangulariser?

Principe général des algorithmes- p. 11/51

Ce qu'il reste à faire

Comment triangulariser?Quelles conditions?

Principe général des algorithmes- p. 11/51

Ce qu'il reste à faire

Comment triangulariser?Quelles conditions?Que faire pour les matrices singulières?

Principe général des algorithmes- p. 11/51

Ce qu'il reste à faire

Comment triangulariser?Quelles conditions?Que faire pour les matrices singulières?Que faire pour les matrices rectangulaires?

Principe général des algorithmes- p. 11/51

Ce qu'il reste à faire

Comment triangulariser?Quelles conditions?Que faire pour les matrices singulières?Que faire pour les matrices rectangulaires?Conditionnement du problème?

Propriétés mathématiquesPrincipe général desalgorithmesTriangularisationTriangularisation simpleTriangularisationAlgorithme de triangularisationÉlimination de GAUSS

ExempleForme matricielle de latriangularisationConditionsRecherche de pivots maximauxConditionnement

Triangularisation- p. 12/51

Triangularisation

Propriétés mathématiquesPrincipe général desalgorithmesTriangularisationTriangularisation simpleTriangularisationAlgorithme de triangularisationÉlimination de GAUSS

ExempleForme matricielle de latriangularisationConditionsRecherche de pivots maximauxConditionnement

Triangularisation- p. 13/51

Triangularisation simple

Contrairement à ce qu'on dit parfois, cette méthode a été rapportée pour la première fois par CHANGTS'ANGau 2esiècle avant JC. On l'appelle aussi méthode fang-cheng

La méthode utilise :

la multiplication par un scalairela somme de deux lignes. Le but de la méthode est d'annuler progressivement les coefficients qui se trouvent sous la diagonale.

Propriétés mathématiquesPrincipe général desalgorithmesTriangularisationTriangularisation simpleTriangularisationAlgorithme de triangularisationÉlimination de GAUSS

ExempleForme matricielle de latriangularisationConditionsRecherche de pivots maximauxConditionnement

Triangularisation- p. 14/51

Triangularisation

On commence avecAune matricenlignes etmcolonnes

Propriétés mathématiquesPrincipe général desalgorithmesTriangularisationTriangularisation simpleTriangularisationAlgorithme de triangularisationÉlimination de GAUSS

ExempleForme matricielle de latriangularisationConditionsRecherche de pivots maximauxConditionnement

Triangularisation- p. 14/51

Triangularisation

On commence avecAune matricenlignes etmcolonnesIl y anétapes :

Propriétés mathématiquesPrincipe général desalgorithmesTriangularisationTriangularisation simpleTriangularisationAlgorithme de triangularisationÉlimination de GAUSS

ExempleForme matricielle de latriangularisationConditionsRecherche de pivots maximauxConditionnement

Triangularisation- p. 14/51

Triangularisation

On commence avecAune matricenlignes etmcolonnesIl y anétapes :À l'étapek, on annule sous la diagonale les coefficients de la

colonnek:

Propriétés mathématiquesPrincipe général desalgorithmesTriangularisationTriangularisation simpleTriangularisationAlgorithme de triangularisationÉlimination de GAUSS

ExempleForme matricielle de latriangularisationConditionsRecherche de pivots maximauxConditionnement

Triangularisation- p. 14/51

Triangularisation

On commence avecAune matricenlignes etmcolonnesIl y anétapes :À l'étapek, on annule sous la diagonale les coefficients de la

colonnek: On appelle kepivot (p(k)) le coefficient de la diagonale p (k)=ak,kÀ chaque lignei > kon soustrait la lignekmultipliée parai,k p(k): q=ai,k a i,j=ai,j-ak,j.q p(k)

Propriétés mathématiquesPrincipe général desalgorithmesTriangularisationTriangularisation simpleTriangularisationAlgorithme de triangularisationÉlimination de GAUSS

quotesdbs_dbs46.pdfusesText_46

[PDF] Résolution de systèmes linéaires : Méthodes directes Polytech

Polytech'Paris-UPMC

Propriétés mathématiques- p. 2/51

Propriétés mathématiques

Propriétés mathématiques- p. 3/51

Rappels mathématiques

Soit à résoudre le système linéaire

A?Mn(IR) :matrice carrée de dimensionn×n

Propriétés mathématiques- p. 3/51

Rappels mathématiques

Soit à résoudre le système linéaire

A?Mn(IR) :matrice carrée de dimensionn×n

Propriétés mathématiques- p. 3/51

Rappels mathématiques

Soit à résoudre le système linéaire

A?Mn(IR) :matrice carrée de dimensionn×n

Si le déterminant est nul :

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

1= 1,x2= 1

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

1= 1,x2= 1

Exemple 2 :

2x1+ 3x2= 5

4x1+ 6x2= 10

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

1= 1,x2= 1

Exemple 2 :

2x1+ 3x2= 5

4x1+ 6x2= 10

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

1= 1,x2= 1

Exemple 2 :

2x1+ 3x2= 5

4x1+ 6x2= 10

Exemple 3 :

2x1+ 3x2= 5

4x1+ 6x2= 9

Propriétés mathématiques- p. 4/51

Exemples

Exemple 1 :

2x1+ 3x2= 5

4x1-3x2= 1

1= 1,x2= 1

Exemple 2 :

2x1+ 3x2= 5

4x1+ 6x2= 10

Exemple 3 :

2x1+ 3x2= 5

4x1+ 6x2= 9

Propriétés mathématiques- p. 5/51

Propriétés

Propriétés mathématiques- p. 5/51

Propriétés

Propriétés mathématiques- p. 5/51

Propriétés

Propriétés mathématiques- p. 5/51

Propriétés

Propriétés mathématiques- p. 5/51

Propriétés