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

livre-algorithmes EXo7.pdf

Une fonction en informatique est similaire à une fonction mathématique c'est un objet qui prend en entrée des variables (dites variables formelles ou

RÉSOLUTION DE SYSTÈMES À DEUX INCONNUES

Pour la même raison les valeurs 3

LES ÉTAPES DE LALGORITHME DU SIMPLEXE

Avant que l'algorithme du simplexe puisse être utilisé pour résoudre un programme linéaire ce programme linéaire doit b) On résout le système pour les.

Chapitre V La méthode du pivot de Gauss et ses applications

Notez que le premier indice de est celui de la ligne et le second celui On décrit l'algorithme qui permet d'échelonner un système linéaire quelconque.

Analyse Numérique

Ceci explique pourquoi le second calcul est plus précis que le premier. ?1 signifie qu'on prend l'inverse de la matrice et donc qu'on résout un système.

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

2 mai 2022 Rappels mathématiques. Exemples. Propriétés. Principe général des algorithmes. Triangularisation. Forme matricielle de la triangularisation.

Untitled

est une structure d'algorithme qui répète le bloc d'instructions tant de la racine carrée sur Python qu'il faut importer à l'aide de from math import *.

Étape A : processus délimination de Gauss

La matrice U = A2 est une matrice triangulaire supérieure. Ainsi le systeme (4) (qui peut être réécrit Ux = b2) est un système triangulaire supérieur qui va

Analyse Numérique 0 0

On suppose que la matrice triangulaire inférieure L est inversible. Soit b un vecteur colonne ayant n composantes. Donner un algorithme qui permet de

Cours de mathématiques - Exo7

La seconde partie est entièrement consacrée à l'algèbre linéaire. C'est un domaine totalement nouveau pour vous et très riche qui recouvre la notion de matrice

- p. 1/51 Résolution de systèmes linéaires : Méthodes directes

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 PolytechParis

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