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

3 Décrire l’algorithme de Gauss pour la résolution des systèmes linéaires 4 Justifier et décrire l’algorithme de Cholesky pour la résolution des systèmes SDP 5 Donner l’ordre de grandeur du nombre d’opérations nécessaire à la résolution d’un système de grande taille, à l’inversion d’une matrice de grande taille 6

AL2 - RÉSOLUTION DE SYSTÈMES

On modifie la valeur de a dans la matrice A (écran 7) Le calcul du déterminant de [A] donne – Il est différent de zéro, donc le système admet une solution unique que l’on calcule (écran 8) La solution est fort différente, Victor s’est avancé un peu vite 3) a = 2 On modifie la valeur de a dans la matrice A

RESOLUTION DE SYSTEMES activité de découverte

Objectif : apprentissage de la résolution de systèmes par substitution puis par combinaison Prérequis: résolution d’équations du 1er degré, notions de calcul algébrique Notions abordées et travaillées dans le problème: résolution de systèmes par combinaison et substitution Choix de la méthode la plus adaptée selon le problème

Résolution numérique de systèmes linéaires

Résolution numérique de systèmes linéaires Le but de ce chapitre est l’étude de méthodes algorithmiques de résolutions de systèmes AX = B, où A ∈Mn,p(R) et B ∈Mn,1(R), l’inconnue X étant un élément de Mp,1(R) On peut bien sûr aussi

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

Résolution de systèmes linéaires : Méthodes directes Polytech’Paris-UPMC Propriétés mathématiques Rappels mathématiques Exemples Propriétés Principe

Analysenumérique: Résolutiondesystèmeslinéaires

Analysenumérique: Résolutiondesystèmeslinéaires Pagora1A Chapitre 5 18mars2013 Analyse numérique (Pagora 1A) Résolution de systèmes linéaires 18 mars 2013 1 / 31

Résolution de systèmes linéaires par la méthode du Pivot de Gauss

Résolution de systèmes linéaires par la méthode du Pivot de Gauss Le butde cettefeuille d’exercicesest d’apprendre la technique de résolution des systèmes d’équations linéaires par la méthode du pivot de Gauss Mais d’abord, qu’est-ce un système linéaire? Exercice 1 Décider, pour chacun des systèmes d’équations aux

Chapitre 4 : Méthodes itératives pour la résolution des

Les méthodes itératives sont utilisées soit pour la résolution de systèmes linéaires de très grande taille, soit lorsque l’on dispose d’une estimation de la solution que l’on veut améliorer Une méthode itérative consiste à construire une suite de vecteurs x(0),(1) ¢¢¢ (k),

Résolution des systèmes polynômiaux en utilisant les bases de

Résolution des systèmes polynômiaux en utilisant les bases de Gröbner (algorithmes classiques) Jean-Charles Faugère INRIA (POLSYS) / UPMC / CNRS/ LIP6 1 Introduction Le problème abordé dans ce cours est le problème fondamental de la résolution d’équations polynomiales par des méthodes de Calcul Formel

Systèmes de deux équations du premier degré à deux inconnues

Systèmes de deux équations du premier degré à deux inconnues 1 Présentation de la problématique 2 Résolution par la méthode de combinaison linéaire (Elimination ) 3 Résolution par la méthode de substitution 4 Résolution graphique 5 Diverses présentations de systèmes de deux équations du premier degré à deux

[PDF] Resolution de systemes lineaires a deux inconnues

[PDF] Résolution de systèmes paramétriques URGENT! SVP

[PDF] résolution de triangle en topographie

[PDF] resolution definition

[PDF] résolution définition juridique

[PDF] Résolution des équations

[PDF] Résolution des équations ci dessous

[PDF] résolution des équations de la physique mathématique

[PDF] Résolution des Equations Différentielles

[PDF] résolution des inéquations

[PDF] resolution des nations unies sur israel

[PDF] résolution des systèmes d équations linéaires

[PDF] résolution du conseil de sécurité force obligatoire

[PDF] Résolution d’équation

[PDF] résolution écran

- 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

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):quotesdbs_dbs49.pdfusesText_49

[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