[PDF] MT09-Analyse numérique élémentaire

View - Download MT09-Analyse numérique élémentaire

Previous PDF

Next PDF

MT09-Analyse numérique élémentaire

Chapitre 4 : Méthodes itératives pour la résolution des systèmes linéaires et non-linéaires

Équipe de Mathématiques Appliquées

UTC

Septembre 2021

5

Sommaire

Concepts

Exemples

Exercices

2

Chapitre 4

Méthodes itératives

4.1 Méthodes itératives de résolution des systèmes linéaires

3

4.2 Résolution d"une équation non-linéaire à une inconnue

14

4.3 Résolution d"un système d"équations non-linéaires

33

Sommaire

Concepts

Exemples

Exercices

3

4.1 Méthodes itératives de résolution des systèmes linéaires

4.1.1 Principes généraux

4

4.1.2 La méthode de Jacobi

6

4.1.3 La méthode de Gauss-Seidel

9

4.1.4 Étude de la convergence des méthodes itératives

11

Sommaire

Concepts

Exemples

Exercices

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 vecteursx(0),x(1),¢¢¢,x(k),...

qui, on l"espère, ou mieux on le démontre, convergera vers la solution du système li- néaire à résoudre. SoitA2Mnn(IR)une matrice régulière etb2IRndonnés. On se propose de résoudre le problème f(x)AEAx¡bAE0 par une méthode itérative de la forme suivante :

½x(0)donné

Mx (kÅ1)AENx(k)Åb où les matricesM,N2Mnn(IR),Minversible, sont convenablement choisies. Si cette méthode itérative converge, c"est-à-dire si la suitex(k)converge vers¯xalors on a, à la limite, (M¡N)¯xAEb, ce qui correspondra à la résolution deAxAEbsi

AAEM¡N.

Sommaire

Concepts

Exemples

Exercices

générauxIl y a une infinité de choix possibles pourMetNvérifiantAAEM¡N, nous allons en

donner deux à titre d"exemples. L"idée est bien sûr de choisir une matriceMparticu- lièrement facile à inverser, par exemple diagonale, ou bien triangulaire inférieure. Ces deux choix correspondent respectivement à laméthode de Jacobiet à laméthode de

Gauss-Seidel.

Sommaire

Concepts

Exemples

Exercices

Exercice B.1.1

Exercice B.1.2

Le système linéaireAxAEbs"écrit

8>>>>>>>>>>>>><

>>>>>>>>>>>>:n X jAE1a

1jxjAEb1,

nX jAE1a i jxjAEbi,pour2·i·n¡1, nX jAE1a njxjAEbn. La méthode de Jacobi consiste, à chaque itérationk, à résoudre chaque équation par

rapport à l"une des variables, les autres étant fixées à leurs valeurs obtenues à l"itéra-

tion précédente. Soit donc le vecteurx(k)donné, alors on détermine successivement les

Sommaire

Concepts

Exemples

Exercices

de Jacobicomposantes dex(kÅ1)par les formules :

8>>>>>>>>>>>>><

>>>>>>>>>>>>:a

11x(kÅ1)

1AEb1¡nX

jAE2a

1jx(k)

j, a iix(kÅ1) iAEbi¡nX jAE1,j6AEia i jx(k) j,pour2·i·n¡1, a nnx(kÅ1)nAEbn¡n¡1X jAE1a njx(k) j. Les formules précédentes ne définissent effectivementx(kÅ1)que si les coefficients dia- gonaux deAsont tous non nuls. Ceci n"est pas une restriction, car on peut démontrer que si une matrice est inversible, il existe une permutation de ses lignes telle que tous les éléments de la diagonale de la matrice ainsi obtenue soient non nuls (voir exercice). On peut écrire les relations précédentes sous forme matricielle. Pour cela introdui- sons la décomposition suivante de A :

AAED¡E¡F,

avec -Dmatrice diagonale contenant la diagonale deA, -Ematrice triangulaire inférieure (triangle inférieur de¡A), -Fmatrice triangulaire supérieure (triangle supérieur de¡A),

Sommaire

Concepts

Exemples

Exercices

de JacobiAvec ces notations on peut écrire le systèmeAxAEbsous la forme

DxAE(EÅF)xÅb,

La méthode de Jacobi s"écrit

½x(0)donné,

Dx (kÅ1)AE(EÅF)x(k)Åb.

Sommaire

Concepts

Exemples

Exercices

Exercice B.1.3Cours:

Jacobi

Il s"agit d"une modification de la méthode de Jacobi qui consiste à utiliser pour chaque équation les composantes dex(kÅ1)déjà calculées, ceci conduit aux formules

8>>>>>>>>>>>>>>><

>>>>>>>>>>>>>>:a

11x(kÅ1)

1AEb1¡nX

jAE2a

1jx(k)

j, a iix(kÅ1) iAEbi¡i¡1X jAE1a i jx(kÅ1) j¡nX jAEiÅ1a i jx(k) j,pour2·i·n¡1, a nnx(kÅ1)nAEbn¡n¡1X jAE1a njx(kÅ1) j. Sous forme matricielle cela revient à écrire le systèmeAxAEbsous la forme (D¡E)xAEFxÅb,

où les matricesD,EetFont été données dans le paragraphe référencé sur la méthode

de Jacobi.

Sommaire

Concepts

Exemples

Exercices

de Gauss-SeidelLa méthode de Gauss-Seidel s"écrit donc

½x(0)donné,

(D¡E)x(kÅ1)AE(Fx(k)Åb), A chaque itération la matrice du système à résoudre est triangulaire inférieure. On observe que les méthodes de Jacobi et Gauss-Seidel que nous venons de voir peuvent se mettre sous la formeMx(kÅ1)AENx(k)Åb: -MAED,NAEEÅF, pour la méthode de Jacobi, -MAED¡E,NAEF, pour la méthode de Gauss-Seidel.

Sommaire

Concepts

Exemples

Exercices

Exercices:

Exercice B.1.4

Commençons par étudier la convergence de la méthode itérative

½x(0)donné,

x (kÅ1)AECx(k)Åd.(4.1.1) Proposition 4.1.1.S"il existe une norme matricielle subordonnée telle que kjCkjÇ1 la méthode(4.1.1)est convergente quel que soit le choix dex(0)et elle converge vers la solution de (I¡C)¯xAEd. Démonstration -Tout d"abord la solution¯xdu système d"équations(I¡C)¯xAEdexiste et elle est unique, car la matriceI¡Cest inversible. En effet

Sommaire

Concepts

Exemples

Exercices

convergence des méthodes

itérativessikxk 6AE0, on aurait, après simplification1· kjCkj, ce qui est contraire à l"hypothèse,

donckxk AE0, doncxAE0. On vient de montrer queker(I¡C)AE{0}, ce qui est équivalent à I¡Cinversible, car la matriceI¡Cest carrée. Montrons maintenant quex(k)converge vers¯xsolution de(I¡C)¯xAEd. On a x d"où Passons à la limite quandktend vers l"infini. PuisquekjCkjÇ1,kjCkjktend vers0et donc x (k)tend vers¯x. Définition 4.1.1.On dit que la matriceAest à diagonale strictement dominante si jaiijÈX j6AEijai jj,8i, 1·i·n.(4.1.2) Proposition 4.1.2.Si la matriceAest à diagonale strictement dominante alors les méthodes de Jacobi et Gauss-Seidel sont convergentes. Démonstration -Démontrons cette proposition pour la méthode de Jacobi. La dé- monstration sera faite en travaux dirigés pour la méthode de Gauss-Seidel.

La méthode de Jacobi s"écrit

x (kÅ1)AED¡1[bÅ(EÅF)x(k)],

Sommaire

Concepts

Exemples

Exercices

DocumentsÎprécédentsection NÎÎ13Étude de la convergence des méthodes itérativeset donc la matrice d"itération est

CAED¡1(EÅF).

PuisqueAest à diagonale dominante, on a

kjD¡1(EÅF)kj1AEmax1·i·nÃ

1jaiijX

j6AEijai jj! Ç1 et donc la méthode est convergente. Un autre résultat intéressant pour les applications est le suivant (nous l"admettrons sans démonstration) : Proposition 4.1.3.Si la matriceAest symétrique définie positive, alors la méthode de

Gauss-Seidel est convergente.

Un résultat intéressant et admis sur la convergence des méthodes itératives donne une caractérisation à partir du rayon spectral de la matriceC. Théorème 4.1.2.Une condition nécessaire et suffisante pour que la méthode itéra- tive(4.1.1)soit convergente est que

½(C)Ç1.

Sommaire

Concepts

Exemples

Exercices

14

4.2 Résolution d"une équation non-linéaire à une inconnue

4.2.1 Méthode de la dichotomie

15

4.2.2 Le principe des méthodes de point fixe

17

4.2.3 Convergence des méthodes de point fixe

19

4.2.4 Méthode de Newton pour résoudre une équation

25

4.2.5 Convergence de la méthode de Newton pour résoudre une équa-

tion 28

4.2.6 La méthode de la sécante

30

Sommaire

Concepts

Exemples

Exercices

Exercice B.1.5

On veut résoudref(x)AE0, oùfest une fonction deIRdansIRnon linéaire (sinon c"est méthode itérative, on va donc construire une suite de nombres réelsx(0),x(1),...,x(k),... notera plus simplementx0,x1,...,xk,.... Le principe de la dichotomie est très simple. On suppose quef: [a,b]!IRest conti- nue et quef(a)f(b)Ç0, c"est-à-dire qu"il y a au moins une racine réelle defdans[a,b]. On prend alors le milieu de l"intervallecAEaÅb2 .Sif(c)AE0(ou numériquement très proche de0) on considère que l"on a résolu le problème. Autrement deux cas peuvent se présenter. Sif(a)f(c)Ç0, alorsfa une racine réelle dans[a,c](au moins une, en tous cas, un nombre impair de racines), autrementf(a)f(c)È0et doncf(a)f(b)f(a)f(c)Ç0, ce qui donnef(b)f(c)Ç0etfa une racine réelle dans[c,b]. On itère alors le processus avec l"intervalle qui contient au moins une racine.

La méthode de dichotomie s"écrit :

a

0AEa,b0AEb,x0AEa0Åb02

Sommaire

Concepts

Exemples

Exercices

x kÅ1AEakÅ1ÅbkÅ12 Il est clair qu"à chaque itération la longueurlkde l"intervalle de localisation de la racine x Proposition 4.2.1.La suite de segments([ak,bk])k¸0est telle que l kAEbk¡akAEb¡a2 k,k¸1. Cette proposition est utile sur le plan numérique; en effet elle renseigne sur le

nombre minimal d"itérations nécessaires pour calculer la racine à²près,²È0étant

une précision fixée à l"avance par l"utilisateur (test d"arrêt). En effet, on peut montrer

(en exercice) que ce nombrendoit vérifier n¸log2µ b¡a²

Sommaire

Concepts

Exemples

Exercices

Exercices:

Exercice B.1.6

Pour résoudref(x)AE0, on peut se ramener à un problème équivalent de la forme g(x)AEx(par exemple en posantg(x)AEf(x)Åx). Mais il y a beaucoup de choix possibles pour définirg! La résolution deg(x)AExs"appelle recherche des points fixes deg. Par exemple, pour calculer la racine carrée d"un nombre réelaÈ0, on résoutx2AEa. Il existe alors différentes manières de se ramener à un problème de point fixe : xAEax ,etg1(x)AEax

2xAExÅax

soitxAE2x¡axquotesdbs_dbs20.pdfusesText_26

[PDF] exercices corrigés microéconomie 1ère année

[PDF] exercices corrigés microéconomie équilibre général

[PDF] exercices corrigés mitose

[PDF] exercices corrigés mouvement des satellites

[PDF] exercices corrigés mouvement seconde

[PDF] exercices corrigés ondes seconde

[PDF] exercices corrigés ondes terminale s

[PDF] exercices corrigés optimisation non linéaire

[PDF] exercices corrigés optique géométrique pdf

[PDF] exercices corrigés optique ondulatoire mp

[PDF] exercices corrigés orthogonalité dans l'espace

[PDF] exercices corrigés outlook 2010

[PDF] exercices corrigés pendule elastique

[PDF] exercices corrigés pert pdf

[PDF] exercices corrigés ph des solutions aqueuses